AN OPTIMAL ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS
成果类型：
Note
署名作者：
DUMAS, Y; DESROSIERS, J; GELINAS, E; SOLOMON, MM
署名单位：
Universite de Montreal; HEC Montreal; Northeastern University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.43.2.367
发表日期：
1995
页码：
367-371
关键词：
摘要：
This paper presents the development of new elimination tests which greatly enhance the performance of a relatively well established dynamic programming approach and its application to the minimization of the total traveling cost for the traveling salesman problem with time windows. The tests take advantage of the time window constraints to significantly reduce the state space and the number of state transitions. These reductions are performed both a priori and during the execution of the algorithm. The approach does not experience problems stemming from increasing problem size, wider or overlapping time windows, or an increasing number of states nearly as rapidly as other methods. Our computational results indicate that the algorithm was successful in solving problems with up to 200 nodes and fairly wide time windows. When the density of the nodes in the geographical region was kept constant as the problem size was increased, the algorithm was capable of solving problems with up to 800 nodes. For these problems, the CPU time increased linearly with problem size. These problem sizes are much larger than those of problems previously reported in the literature.