SEQUOIA: SEQuence-variable-based Optimization In Action for the Traveling Salesman Problem with Time Windows
(2023) Doctoral Program of CP23 — Location: Toronto (27.August.2023)
Files
CP23_DP_TSPTW-3.pdf
Open Access - Adobe PDF
- 766.91 KB
Details
- Authors
Delecluse, Augustin 
Pascal Van Hentenryck
- Abstract
- The Traveling Salesman Problem with Time Windows (TSPTW) is a Vehicle Routing Problem (VRP) variant imposing time-window constraints on customer visits. The objective is to serve all customers within specified time windows while minimizing the total travel distance. Finding even a feasible solution for this problem is NP-hard. State-of-the-art local search methods typically begin with a circuit that visits all customers, possibly violating time windows, before iteratively reducing these violations through local search moves, such as shifting visits. In contrast, this paper proposes to satisfy time-window constraints while relaxing the requirement to visit all customers. It relies on constraint programming, and a model based on sequence variables for neighborhood exploration. Flexible removal and insertion-based heuristics are exploited in a large neighborhood search setting. This approach consistently yields feasible solutions in under one second for popular TSPTW benchmarks, and can be readily adapted to other routing problems.
- Affiliations
Citations
Delecluse, A., Schaus, P., & Pascal Van Hentenryck. (2023). SEQUOIA: SEQuence-variable-based Optimization In Action for the Traveling Salesman Problem with Time Windows. Doctoral Program of CP23, Toronto. https://hdl.handle.net/2078.5/273387