An Optimal Algorithm for the Traveling Salesman Problem with Time Windows

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.