Solving the Traveling Salesman Problem with Time Windows Through Dynamically Generated Time-Expanded Networks

摘要

The Traveling Salesman Problem with Time Windows is the problem of finding a minimum-cost path visiting each of a set of cities exactly once, where each city must be visited within a specified time window. It has received significant attention because it occurs as a sub-problem in many real-life routing and scheduling problems. We explore an approach in which the strength of a time-expanded integer linear programming (IP) formulation is exploited without ever explicitly creating the complete formulation. The approach works with carefully designed partially time-expanded networks, which are used to produce upper as well as lower bounds, and which are iteratively refined until optimality is reached. Preliminary computational results illustrate the potential of the approach as, for almost all instances tested, optimal solutions can be identified in only a few iterations.