Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing

Augustin Delecluse; Pierre Schaus; Pascal Van Hentenryck

cs.AIOct 10, 2025

Sequence Variables: A Constraint Programming Computational Domain for Routing and Sequencing

Authors: Augustin Delecluse, Pierre Schaus, Pascal Van Hentenryck

Organizations: KU Leuven · UCLouvain · GATECH

Abstract

Constraint Programming (CP) offers an intuitive, declarative framework for modeling Vehicle Routing Problems (VRP). While classical successor-based CP models can be adapted to handle optional visits or insertion-based heuristics, sequence variables provide a significantly more natural and elegant formulation for these requirements. Building upon our prior work that introduced the initial concept, the main contribution of this article is the complete semantic and operational formalization of sequence variables as a computational domain. Specifically, we formally define the sequence domain and its update operations, and detail the implementation and data structures required to integrate sequence variables into trail-based CP solvers. Furthermore, we introduce consistency levels for associated constraints on this domain alongside specialized global constraints tailored for routing problems. Finally, we demonstrate that sequence variables simplify problem modeling while achieving competitive computational performance on Pickup and Delivery Problems with and without Time Windows, the Dial-a-Ride Problem, and a Prize-Collecting Scheduling Problem.

Figures & tables

	Type of variable
Feature	Successor	Head-tail sequence	Insertion-based sequence
Nearest neighbor heuristics	✓	✓	✓
Insertion-based heuristics			✓
Optional visits		✓	✓
Memory complexity on VRP with $n$ nodes and $k$ vehicles	$\mathcal{O}(n^{2})$	$\mathcal{O}(k\cdot n)$	$\mathcal{O}(k\cdot n^{2})$

Table 1. Characteristics of CP variables.

$\mathcal{P}(V)$	$\mathcal{D}^{\text{\raisebox{0.27126pt}{\scalebox{1.0}{\textcircled{\scriptsize r}}}}}(R)$	$\mathcal{D}^{\text{\raisebox{0.27126pt}{\scalebox{1.0}{\textcircled{\scriptsize x}}}}}(X)$	$\mathcal{D}^{\text{\raisebox{0.27126pt}{\scalebox{1.0}{\textcircled{\scriptsize s}}}}}(\lx@scalerel@obj{$ \overrightarrow{s} $})$	$\mathcal{D}^{\text{\raisebox{0.27126pt}{\scalebox{1.0}{\textcircled{\scriptsize\raisebox{-0.0ex}{{n}}}}}}}(N)$
$\alpha\cdot\omega$		✓		✓
$\alpha\cdot v_{1}\cdot\omega$		✓	✓	✓
$\alpha\cdot v_{2}\cdot\omega$	✓	✓		✓
$\alpha\cdot v_{3}\cdot\omega$				✓
$\bm{\alpha\cdot v_{1}\cdot v_{2}\cdot\omega}$	$\bm{\checkmark}$	$\bm{\checkmark}$	$\bm{\checkmark}$	$\bm{\checkmark}$
$\alpha\cdot v_{1}\cdot v_{3}\cdot\omega$			✓	✓

Table 2. The compositions of subdomains in Example 4.3 . A check mark in one of the last 4 columns indicates that the corresponding sequence in the first column is included within the subdomain.

Panel of Figure 1 — Figure 1. Compact domain implementation. On the left, the partial sequence $\overrightarrow{s}$ and the graph $G(V,E)$ are shown. Below them is a table showing the edges ${E}^{-},{E}^{+}$ , the insertion counters $nI$ , and the successors ${\mathbf{s}}^{+}$ and predecessors ${\mathbf{s}}^{-}$ of the nodes (only relevant for nodes $v\in\lx@scalerel@obj{$ \overrightarrow{s} $}$ ). The right-hand part shows the domain after performing an insertion with $(\alpha,v_{3})$ , extending the partial sequence.

Operation	Description	Complexity
$\mathrm{isFixed}()$	Returns true if there are no remaining insertions	$\mathcal{O}(1)$
$\mathrm{isMember}(v_{i})$	Returns true if $v_{i}\in\lx@scalerel@obj{$ \overrightarrow{s} $}{}$	$\mathcal{O}(1)$
$\mathrm{isRequired}(v_{i})$	Returns true if the node $v_{i}$ is required	$\mathcal{O}(1)$
$\mathrm{isExcluded}(v_{i})$	Returns true if the node $v_{i}$ is excluded	$\mathcal{O}(1)$
$\mathrm{isPossible}(v_{i})$	Returns true if the node $v_{i}$ is possible	$\mathcal{O}(1)$
$\mathrm{isInsertable}(v_{i})$	Returns true if the node $v_{i}$ is insertable	$\mathcal{O}(1)$

Table 3. Queries on a compact sequence domain.

Operation	Update	Precondition	Complexity
$\mathrm{notBetween}(v_{i},v_{j},v_{k})$	$N\leftarrow N\cup{(v_{i}\cdot v_{j}\cdot v_{k})}$	$v_{i},v_{k}\in\lx@scalerel@obj{$ \overrightarrow{s} $}{}$	$\begin{cases}\mathcal{O}(\|I\|)&\text{if }v_{i}\xrightarrow{}v_{k}\\ \mathcal{O}(n)&\text{otherwise}\end{cases}$
$\mathrm{insert}(v_{i},v_{j})$	$\mathrel{\underset{\scriptstyle(v_{i},v_{j})}{\longmapsto}}$	$v_{i}\in\lx@scalerel@obj{$ \overrightarrow{s} $}{}$	$\Theta(\|{E}_{j}^{-}\|)$
$\mathrm{insertAtEnd}(v_{i})$	$\mathrel{\underset{\scriptstyle(\mathrm{getPrev}(\omega),v_{i})}{\longmapsto}}$		$\Theta(\|{E}_{i}^{-}\|)$
$\mathrm{require}(v_{i})$	$R\leftarrow R\cup\{\,v_{i}\,\}$		$\mathcal{O}(\|{E}_{i}^{-}\|)$
$\mathrm{exclude}(v_{i})$	$X\leftarrow X\cup\{\,v_{i}\,\}$		$\mathcal{O}(\|{E}_{i}^{-}\|)$

Table 4. Updates on a compact sequence domain.

Boolean variable		Sequence variable
$\|\mathcal{D}(\mathcal{R}_{i}{(\lx@scalerel@obj{$ \overrightarrow{S} $})})\|=1$	$\Longleftrightarrow$	$\neg\lx@scalerel@obj{$ \overrightarrow{S} $}.\mathrm{isPossible}(v_{i})$
$\textit{false}\in\mathcal{D}(\mathcal{R}_{i}{(\lx@scalerel@obj{$ \overrightarrow{S} $})})$	$\Longleftrightarrow$	$\neg\lx@scalerel@obj{$ \overrightarrow{S} $}.\mathrm{isRequired}(v_{i})$
$\textit{true}\in\mathcal{D}(\mathcal{R}_{i}{(\lx@scalerel@obj{$ \overrightarrow{S} $})})$	$\Longleftrightarrow$	$\neg\lx@scalerel@obj{$ \overrightarrow{S} $}.\mathrm{isExcluded}(v_{i})$

Table 5. Correspondence between operations on a boolean variable

\mathcal{R}_{i}{(Sq)}

defined over a node

v_{i}

in a sequence variable

\overrightarrow{S}

. The left part shows queries over the domains, while the right part shows updates of the domains.

Panel of Figure 2 — Figure 2. $\mathrm{Cumulative}(\lx@scalerel@obj{$ \overrightarrow{S} $},(s_{0},s_{1},s_{2},s_{3}),(e_{0},e_{1},e_{2},e_{3}),(2,1,1,2),3)$ over a fixed sequence variable $\lx@scalerel@obj{$ \overrightarrow{S} $}=\alpha\cdot s_{0}\cdot s_{1}\cdot e_{1}\cdot e_{0}\cdot s_{3}\cdot e_{3}\cdot\omega$ . The sequence is shown at the top, and the graph below shows the accumulated load for each node $v\in\lx@scalerel@obj{$ \overrightarrow{S} $}$ . Note how nodes $s_{2},e_{2}$ related to activity 2 are not part of the sequence.

Panel of Figure 3 — Figure 3. Sequences created from a fully connected graph $G(V,E)$ with $V=\{\alpha,v_{1},v_{2},v_{3},\omega\}$ , where all nodes are required ( $V=R$ ). Nodes $\alpha$ and $\omega$ are implicit and not shown. Left: each sequence is extended by inserting any node at each step. Right: a node is first selected for insertion, then all its feasible positions are considered for insertion before moving to the next node (first $v_{1}$ , then $v_{2}$ , then $v_{3}$ ).

Panel of Figure 4 — Figure 4. Paths generated by Algorithm 6 from an initial path (left). Numbers indicate the order in which the paths are considered.

Figure 5. Primal-gap performance on the PDP, PDPTW, and DARP. The top row shows the mean primal gap over time; lower-left curves indicate faster convergence. The bottom row shows the percentage of instances with final gap at most the x-axis value after 15 minutes; upper-left curves are better.

Panel of Figure 6 — Figure 6. PCSP solution

Figure 7. Primal-gap performance on the PCSP. The left plot shows the mean primal gap over time; lower-left curves indicate faster convergence. The right plot shows the percentage of instances with final gap at most the x-axis value after 15 minutes; upper-left curves are better.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 8 — Figure 8. A sequence variable $\overrightarrow{S}$ with partial sequence $\lx@scalerel@obj{$ \overrightarrow{s} $}=\alpha\cdot s_{0}\cdot s_{1}\cdot e_{2}\cdot s_{3}\cdot e_{3}\cdot\omega$ (top) and its corresponding load profile (bottom) when using a $\mathrm{Cumulative}(\lx@scalerel@obj{$ \overrightarrow{S} $},(s_{0},s_{1},s_{2},s_{3}),(e_{0},e_{1},e_{2},e_{3}),(2,1,1,3),4)$ constraint. Edges between insertable nodes are not shown. For the partially inserted activity $1$ , the closest node after which $e_{1}$ can be inserted is $e_{2}$ ; hence, rectangle 1 ends at $\bm{l}_{e_{2}}^{+}$ instead of $\bm{l}_{s_{1}}^{+}$ on the load profile.

Panel of Figure 9 — Figure 9. Two load profiles for different sequences, with a capacity of 2. With $\bm{l}_{s_{0}}^{s_{0}+1}$ , we detect that an activity of load 2 can be put between $s_{0}$ and $e_{1}$ on the left but cannot be put between $s_{0}$ and $e_{0}$ on the right.

Name	$k$	$\|R\|$	bks	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best
				Succ				Succ-LNS				CPO				RF (2021)				OR-Tools Routing				Hexaly				Seqvar
R1a	3	24	190.02	$18.26$	$\pm$	0.00	18.26	$6.03$	$\pm$	2.00	3.19	$3.62$	$\pm$	1.54	0.71	0.00	$\pm$	0.00	0.00		-		-	$2.98$	$\pm$	1.42	0.54	0.00	$\pm$	0.00	0.00
R1b	3	24	164.46	$33.22$	$\pm$	0.00	33.22	$7.81$	$\pm$	3.66	4.34	$12.81$	$\pm$	4.15	4.32	0.00	$\pm$	0.00	0.00	0.00	$\pm$	0.00	0.00	$3.69$	$\pm$	1.33	1.38	$0.82$	$\pm$	1.35	0.00
R7a	4	36	291.71		-		-	$11.22$	$\pm$	4.71	4.71	$23.55$	$\pm$	14.85	6.09	0.00	$\pm$	0.00	0.00		-		-	$4.39$	$\pm$	2.03	1.08	$2.06$	$\pm$	1.34	0.00
R7b	4	36	248.21		-		-	$10.87$	$\pm$	1.96	7.33	$12.95$	$\pm$	3.48	8.11		-		-		-		-	$8.58$	$\pm$	2.32	5.75	2.41	$\pm$	1.46	1.07
R2a	5	48	301.34		-		-	$8.03$	$\pm$	2.79	2.87	$29.61$	$\pm$	24.07 $\dagger$	12.59		-		-		-		-	$6.70$	$\pm$	4.01	2.39	1.55	$\pm$	1.05	0.29

Appendix

Table 6. Primal gaps (%) to the best known solution (bks) on DARP instances after 15 minutes of runtime. Entries report the mean primal gap

\pm

the sample standard deviation and the best primal gap over ten runs. A dash indicates that no run found a feasible solution. Except for entries marked with † , numerical entries are based on ten feasible runs. For marked entries, statistics use the feasible runs specified in the table note. Best mean and best gap values are in bold.

Dataset	$n$	$m$	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best	Mean $\pm$ SD			Best
			MZN-Succ				MZN-Disj				CPO				OR-Tools Routing				Hexaly				SeqVar
A_E	50	3	$17.11$	$\pm$	2.19	16.40	$19.34$	$\pm$	0.84	19.25	0.00	$\pm$	0.00	0.00	$4.25$	$\pm$	1.59	4.25	$32.30$	$\pm$	3.54	25.26	0.00	$\pm$	0.00	0.00
	50	4	$18.35$	$\pm$	1.94	17.81	$20.02$	$\pm$	3.03	19.86	$0.11$	$\pm$	0.18	0.00	$3.81$	$\pm$	1.35	3.81	$31.41$	$\pm$	2.59	28.11	0.00	$\pm$	0.00	0.00
	100	3	$61.79$	$\pm$	8.10	61.75	$36.24$	$\pm$	3.76	36.24	$0.75$	$\pm$	0.90	0.00	$4.62$	$\pm$	0.29	4.62	$39.28$	$\pm$	1.40	35.04	0.41	$\pm$	0.29	0.28
	100	4	$77.99$	$\pm$	11.88	77.99	$56.11$	$\pm$	38.28	56.11	$0.70$	$\pm$	0.74	0.00	$3.93$	$\pm$	1.09	3.93	$40.80$	$\pm$	3.84	37.13	0.32	$\pm$	0.43	0.00
	150	3	$96.44$	$\pm$	6.17	96.44	$44.42$	$\pm$	2.57	44.29	0.36	$\pm$	0.53	0.28	$3.83$	$\pm$	2.80	3.83	$45.59$	$\pm$	1.73	38.84	$0.59$	$\pm$	0.42	0.14

Appendix

Table 7. Primal gaps (%) to the best known solution (bks) on PCSP instances. Entries report the mean primal gap

\pm

the sample standard deviation across constituent instance-level mean gaps; best gaps retain the existing mean of per-instance best gaps. A dash indicates that no feasible solution was found for the corresponding group. Except for entries marked with † , numerical entries use all ten runs of each constituent instance. For marked entries, the affected instance contribution uses its feasible runs only, as specified in the table note. Best mean and best gap values are in bold.

Explore similar work

May 20, 2026cs.AI

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space

Although Vehicle Routing Problems (VRP) are essential to many real-world systems, they remain computationally intractable at scale due to their combinatorial complexity. Traditional heuristics rely on handcrafted rules for local improvements and occasional \textit{jumps} to escape local minima, but often struggle to generalize across diverse instances. We introduce \textbf{COAgents}, a cooperative multi-agent framework that models the search process as a graph: nodes represent solutions, and edges correspond to either local refinements or large perturbations for diversification (i.e., jumps). A \textit{Partial Search Graph} (PSG) is dynamically constructed during search, enabling COAgents to train a Node Selection Agent and a Move Selection Agent to guide intensification, and a Jump Agent to trigger well-timed explorations of new regions. Unlike end-to-end learning approaches, COAgents cleanly separates problem-agnostic search control from compact domain-specific encoding, facilitating adaptability across tasks. Extensive experiments on the CVRP and VRPTW benchmarks show that COAgents remains competitive with several learn-to-search baselines on CVRP and sets a new state of the art among learning-based methods on the more challenging VRPTW instances, reducing the gap to the best-known solutions by 14% at

N\!=\!100

and 44% at

N\!=\!50

relative to the strongest neural solver (POMO), and by 21% and 40% respectively relative to ALNS. Code is available at https://github.com/mahdims/COAgents.

Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed +4

Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S7 · Huawei Technologies, China

Vehicle Routing Problem Multi-Agent Path Finding Neural Solvers

Ask PDF

Jul 4, 2026cs.AI

Robust Feasible Route Construction through Collaborative Partition Optimization

Large-scale Capacitated Vehicle Routing Problems (CVRPs) are commonly solved by partitioning customers into smaller routing problems that can be optimized independently. While this substantially reduces computational complexity, independently constructed routing solutions may leave some customer demand unserved even when sufficient resources exist elsewhere in the fleet. We present Collaborative Routing Constructors (CoRC), a routing framework that enables independently solved subproblems to exchange customers and vehicles during optimization rather than relying solely on a fixed partition or a subsequent global re-optimization stage. Computational experiments on AGS benchmark instances and synthetic instances containing up to 200,000 customers compare CoRC against independent routing, post-routing global re-optimization, and state-of-the-art, end-to-end routing frameworks. Across all evaluated partitioning strategies, CoRC consistently constructs feasible routing solutions where competing partition-based methods do not. Furthermore, it remains effective on problem instances for which the evaluated end-to-end routing frameworks did not produce solutions under the same computational budget. These results demonstrate that collaboration between routing subproblems provides a robust and scalable approach for feasible large-scale route construction.

Oguzhan Karaahmetoglu, Hyong Kim

Department of Electrical and Computer Engineering, Carnegie Mellon University

Vehicle Routing Problem Prompt Optimization Construction Benchmark Saturation

Ask PDF

May 14, 2026cs.AI

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3

PyCSP

^3

provides a productive way to build constraint models for solving combinatorial constrained problems and export them to XCSP

^3

, preserving a complete separation between modeling and solving. However, it lacks native support for scheduling abstractions such as interval variables, sequence variables, and resource functions. As a result, scheduling models must be encoded with low-level integer variables and manual channeling constraints, even though PyCSP

^3

already provides global constraints like NoOverlap and Cumulative on integer arrays. We present PyCSP

^3

Scheduling, a library that adds scheduling abstractions to PyCSP

^3

through 53 dedicated constraints and 27 expressions, and compiles them down to standard PyCSP

^3

/XCSP

^3

constraints, maintaining the modeling/solving separation that underpins the PyCSP

^3

ecosystem. On 261 paired instances across 17 model families (5 runs each), both formulations produce identical objectives on all 72 doubly-proved optimal pairs and nearly half of the families (8/17) remain structurally unchanged after compilation; however, runtime performance diverges across families, with clear gains on some (up to 5.8x) and regressions on others due to the overhead of compilation decompositions. Code and benchmarks are available at: https://github.com/sohaibafifi/pycsp3-scheduling

Sohaib Afifi

Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France

Job Shop Scheduling Schedule Structural Constraints Decomposition Quantum Chemistry

Ask PDF