Sequence Variables and Search Heuristics for Vehicle Routing Problems in Constraint Programming
(2025)
Files
thesis_elec.pdf
Open Access - Adobe PDF
- 1.81 MB
Details
- Authors
Delecluse, Augustin 
- Supervisors
- Schaus, Pierre
- Abstract
- Constraint Programming (CP) is an optimization paradigm well suited for solving Vehicle Routing Problems (VRPs), thanks to its declarative framework. Yet, despite this relative ease of modeling, CP solvers tend to make poor branching decisions while searching for optimal solutions on a VRP. This, combined with the difficulty in dealing with optional visits in some VRPs variants, hinders the performance of CP solvers on such problems. This thesis proposes two ways to strengthen the CP solving of VRPs. First, several heuristics are introduced that automate more informed decisions (e.g. nearest neighbor selection) within the CP search, which discover better VRPs solutions more quickly. Second, insertion sequence variables introduced in previous work are modified, formalized, and enhanced. Sequence variables allow easy handling of optional visits and support efficient heuristic strategies based on insertions into existing paths, both of which are valuable for efficient solving of VRPs. The proposed modifications further improve their performance, simplify the modeling and implementation of custom heuristics, and clarify their domain and consistency properties. On benchmarks such as the Dial-A-Ride Problem we approach the best-known objective values, and on the Traveling Salesman Problem with Time Windows we match them; demonstrating that CP performance can be greatly improved by incorporating our contributions.
- Affiliations
Citations
Delecluse, A. (2025). Sequence Variables and Search Heuristics for Vehicle Routing Problems in Constraint Programming. https://hdl.handle.net/2078.5/273380