AN OPTIMAL ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM WITH TIME WINDOWS

This paper presents the development of new elimination tests which gre atly enhance the performance of a relatively well established dynamic programming approach and its application to the minimization of the to tal traveling cost for the traveling salesman problem with time window s. The tests take advantage of the time window constraints to signific antly reduce the state space and the number of state transitions. Thes e reductions are performed both a priori and during the execution of t he algorithm. The approach does not experience problems stemming from increasing problem size, wider or overlapping time windows, or an incr easing number of states nearly as rapidly as other methods. Our comput ational results indicate that the algorithm was successful in solving problems with up to 200 nodes and fairly wide time windows. When the d ensity of the nodes in the geographical region was kept constant as th e problem size was increased, the algorithm was capable of solving pro blems 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.