A decomposition-based approach to the traveling salesman problem with time windows

The Traveling Salesman Problem with Time Windows is a variation of the Traveling Sales- man Problem wherein the salesman is required to arrive at each customer node during a specified time interval. This dissertation presents a new solution methodology for the Traveling Salesman Problem with Time Windows. This solution methodology is based on Bender's Decomposition. The master problem can be represented as a Traveling Salesman Problem with additional constraints, while the subproblem is a pure linear program. The master problem provides a route while the subproblem checks for feasibility of the route with respect to time windows. Several different representations of the problem are considered. The nature of cuts generated in each of these representations is studied. A heuristic based on the solution methodology is proposed. The optimal solution methodology is tested on a set of small problems. The heuristic is tested on these small problems as well as on an expanded set of moderately large problems. A variation of the Traveling Salesman Problem with Time Windows that minimizes the total time spent on the tour rather than the cost of the tour is also studied. This problem is referred to as the Traveling Salesman Makespan Problem with Time Windows. An extension of the solution process to solve the Traveling Salesman Makespan Problem with Time Windows is also discussed.