Authors: Mladenović, Nenad 
Todosijević, Raca 
Urošević, Dragan 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: An efficient GVNS for solving Traveling Salesman Problem with Time Windows
Journal: Electronic Notes in Discrete Mathematics
Volume: 39
First page: 83
Last page: 90
Issue Date: 1-Dec-2012
ISSN: 1571-0653
DOI: 10.1016/j.endm.2012.10.012
Although GVNS is shown to be powerful and robust method for solving traveling salesman and vehicle routing problems, its efficient implementation may play significant role in solving large size instances. In this paper we suggest new GVNS heuristic for solving TSPTW. It uses more efficient data structure, different neighborhoods, new efficient feasibility checking procedure, for example, than a recent GVNS method [Da Silva, R. F., and S. Urrutia, A General VNS heuristic for the traveling salesman problem with time windows, Discrete Optimization 7 (2010), 203-211.], that may be considered as a state-of-the-art heuristic. As a result, our GVNS is significantly faster than previous GVNS and therefore is able to improve 14 out of 25 best known solutions for large test instances from the literature.
Keywords: GVNS | Time window | Traveling Salesman Problem
Publisher: Elsevier

Show full item record


checked on May 18, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.