A generalized insertion heuristic for the traveling salesman problem with time windows
成果类型：
Article
署名作者：
Gendreau, M; Hertz, A; Laporte, G; Stan, M
署名单位：
Universite de Montreal; Swiss Federal Institutes of Technology Domain; Ecole Polytechnique Federale de Lausanne; Universite de Montreal; HEC Montreal
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.46.3.330
发表日期：
1998
页码：
330-335
关键词：
摘要：
This article describes a generalized insertion heuristic for the Traveling Salesman Problem with Time Windows in which the objective is the minimization of travel times. The algorithm gradually builds a route by inserting at each step a vertex in its neighbourhood on the current route, and performing a local reoptimization. This is done while checking the feasibility of the remaining part of the route. Backtracking is sometimes necessary. Once a feasible route has been determined, an attempt is made to improve it by applying a post-optimization phase based on the successive removal and reinsertion of all vertices. Tests performed on 375 instances indicate that the proposed heuristic compares very well with alternative methods and very often produces optimal or near-optimal solutions.