AI4OPT Seminar: Sequence Variables for solving Vehicle Routing Problems with Constraint Programming

AI4OPT Seminar: Sequence Variables for solving Vehicle Routing Problems with Constraint Programming

by Pierre Schaus

Formal & Physical Sciences AI — News & Applications UYComputer scienceUYQArtificial intelligence (AI)
🎙 Pierre Schaus 👥 889 📅 March 11, 2026 ⏱ 46 min 👁 85 📄 expert opinion 🧭 2026-08-16
Available in: English (current) Français

Keywords

sequence variablesconstraint programmingvehicle routinginsertion-based searchlarge neighborhood search

Summary

The seminar presents sequence variables, a new modeling abstraction for constraint programming (CP) to better handle ordered structures like routes in vehicle routing problems (VRPs). The speaker, Pierre Schaus, begins by reviewing CP fundamentals and the traditional successor-variable model for the Traveling Salesman Problem (TSP), highlighting its weaknesses: poor first solutions from greedy heuristics, difficulty modeling optional visits, and limited flexibility for large neighborhood search (LNS). He then introduces sequence variables, which represent a partial path with optional insertions, and describes their domain representation using four components: required nodes, excluded nodes, required subsequences, and forbidden between-triplets. The domain is efficiently represented using a graph of possible insertions, with reversible sparse sets for backtracking. Branching schemes for sequence variables are discussed, including binary and n-ary variants, and the first-fail principle is applied to select nodes with fewest insertion possibilities. The talk also covers a distance constraint that filters based on lower bounds and insertion costs. The approach is illustrated with TSP and VRP examples, showing improved LNS performance compared to successor variables. The work is collaborative with Augustin Delecluse and Pascal Van Hentenryck.

182 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides a clear motivation for sequence variables by demonstrating the limitations of successor variables in CP for routing problems. The argumentation is solid: it identifies three specific weaknesses (poor greedy solutions, difficulty with optional visits, and limited LNS flexibility) and then shows how sequence variables address them. The formal definition of the domain and the filtering algorithms are presented with enough detail to understand the approach, though some implementation specifics are omitted. The speaker uses intuitive examples and animations to illustrate the benefits, making the case compelling. The presentation is well-structured, building from CP basics to the new contribution, and the potential impact on solving VRPs is convincingly argued.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, with formal definitions and references to established CP concepts (e.g., circuit constraint, element constraint, LNS). The speaker cites his collaborators and mentions prior work by Pascal Van Hentenryck and others. The title accurately reflects the content. The description provides links to the AI4OPT seminar mailing list and past seminars, but no direct references to the paper or related publications are given. The talk is a seminar presentation, so it is not peer-reviewed, but the technical depth and the speaker’s expertise lend credibility. The adéquation between title and content is excellent.

221 words

Title / Content Match

The title accurately reflects the content: the talk introduces sequence variables for solving vehicle routing problems with constraint programming.

Quality & Reliability

8/10

Presentation by a recognized expert in constraint programming, with formal definitions and algorithmic details. The talk is a research seminar, not peer-reviewed, but the content is technically sound and based on published work.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

  • AI4OPT seminar mailing list — Sign up for seminar announcements
  • AI4OPT past seminars — Access to previous seminar recordings

Concurring Sources

Contribution & Novelties

The talk introduces sequence variables, a novel modeling abstraction for constraint programming that directly supports insertion-based search strategies, which are crucial for solving vehicle routing problems. This is a significant contribution as it addresses the limitations of traditional successor variables in handling optional visits and large neighborhood search. The formal definition of the domain and the efficient graph-based representation are original contributions. The talk also presents dedicated global constraints for routing, such as the distance constraint, and demonstrates improved performance in LNS.

Pour aller plus loin :

126 words

Radar Profile

The radar profile shows high scores in technical level and information quality, indicating a specialized and detailed presentation. The quantity of information is also high, but the overall reliability is slightly lower due to the lack of peer-reviewed sources in the talk itself. The profile suggests a content that is highly technical and informative, suitable for an expert audience.

Reliability 8/10

💬 No comments were provided for analysis.