Algorithms and Heuristics for Time-Window-Constrained Traveling Salesman Problems.
NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Pagination or Media Count:
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 Stewarts 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. Keywords Heuristic, Algorithm, Time Window, Hard Time Window, Soft Time Window, Slack, Branch and Bound, Nearest Neighbor, Penalty Cost, Traveling Salesman Problem, and State-Space Relaxation.
- Theoretical Mathematics