Algorithms and Heuristics for Time-Window-Constrained Traveling Salesman Problems

摘要

This thesis reports on methods for solving traveling salesman problems with time-window constraints. Two types of windows are considered: hard time windows, which are inviolable, and soft time windows, which are violable at a cost. For both cases, we develop several heuristic procedures, including some that are based on Stewart's effective heuristics for the traveling salesman problem without time-window constraints. In addition, we develop exact algorithms for each case, which are based on the state-space relaxation dynamic programming method of Christofides, Mingozzi, and Toth. Computational experience is reported for all the heuristics and algorithms we develop.