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

COAgents: Multi-Agent Framework to Learn and Navigate Routing Problems Search Space
May 20, 2026Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed +4Vehicle Routing Problem Multi-Agent Path Finding
Huawei Technologies Canada, 4321 Still Creek Dr, Burnaby, BC, Canada V5C 6S7 · Huawei Technologies, China
Robust Feasible Route Construction through Collaborative Partition Optimization
Jul 4, 2026Oguzhan Karaahmetoglu, Hyong KimVehicle Routing Problem Prompt Optimization
Department of Electrical and Computer Engineering, Carnegie Mellon University
PyCSP3-Scheduling: A Scheduling Extension for PyCSP3
May 14, 2026Sohaib AfifiJob Shop Scheduling Schedule
Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France

May 20, 2026, cs.AIJ/K move · Enter open · S save

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

Oleksandr Yakovenko, Mahdi Mostajabdaveh, Cheikh Ahmed, Abdullah Ali Sivas+3

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

Vehicle Routing Problem Multi-Agent Path Finding Neural Solvers

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Robust Feasible Route Construction through Collaborative Partition Optimization

PyCSP3-Scheduling: A Scheduling Extension for PyCSP3