|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||Abstract:||
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 Oct 6, 2022
checked on Oct 5, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.