A General VNS heuristic for the traveling salesman problem with time windows

作者：da Silva Rodrigo Ferreira^*; Urrutia Sebastian

来源：Discrete Optimization, 2010, 7(4): 203-211.

DOI：10.1016/j.disopt.2010.04.002

• Traveling salesman
• Time windows
• Heuristics
• Variable neighborhood search
• Variable neighborhood descent

This paper presents a General Variable Neighborhood Search (GVNS) heuristic for the Traveling Salesman Problem with Time Windows (TSPTW). The heuristic is composed by both constructive and optimization stages. In the first stage, the heuristic constructs a feasible solution using VNS, and in the optimization stage the heuristic improves the feasible solution with a General VNS heuristic. Both constructive and optimization stages take advantage of elimination tests, partial neighbor evaluation and neighborhood partitioning techniques. Experimental results show that this approach is efficient, reducing significantly the computation time and improving some best known results from the literature.

• 出版日期2010-11