Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing
This work addresses modeling challenges in vehicle routing for constraint programming practitioners, though it is incremental as it builds on existing CP frameworks.
The paper tackles the limitations of classical Constraint Programming models for Vehicle Routing Problems by formalizing sequence variables, which handle optional visits and support insertion heuristics, and demonstrates their effectiveness by simplifying modeling and achieving competitive computational performance on the Dial-a-Ride Problem.
Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP), yet classical CP models based on successor variables cannot always deal with optional visits or insertion based heuristics. To address these limitations, this paper formalizes sequence variables within CP. Unlike the classical successor models, this computational domain handle optional visits and support insertion heuristics, including insertion-based Large Neighborhood Search. We provide a clear definition of their domain, update operations, and introduce consistency levels for constraints on this domain. An implementation is described with the underlying data structures required for integrating sequence variables into existing trail-based CP solvers. Furthermore, global constraints specifically designed for sequence variables and vehicle routing are introduced. Finally, the effectiveness of sequence variables is demonstrated by simplifying problem modeling and achieving competitive computational performance on the Dial-a-Ride Problem.