An efficient GVNS for solving Traveling Salesman Problem with Time Windows

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.