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

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

par Pierre Schaus

Sciences formelles & physiques IA — Actualité & Applications UYInformatiqueUYQIntelligence artificielle (IA)
🎙 Pierre Schaus 👥 889 📅 11 mars 2026 ⏱ 46 min 👁 85 📄 exposé de recherche 🧭 2026-08-16
Disponible en : Français (actuel) English

Mots-clés

sequence variablesconstraint programmingvehicle routinglarge neighborhood searchinsertion heuristics

Résumé

L’exposé de Pierre Schaus, professeur à l’UCLouvain, présente une nouvelle abstraction de modélisation pour la programmation par contraintes (CP) : les variables de séquence. Ces variables sont conçues pour représenter des structures ordonnées comme des tournées, en supportant naturellement les visites optionnelles et les heuristiques basées sur l’insertion. L’orateur commence par rappeler les bases de la CP et la modélisation classique du problème du voyageur de commerce (TSP) avec des variables successeur et la contrainte circuit. Il identifie trois faiblesses de cette approche : la qualité médiocre des premières solutions trouvées par des heuristiques gloutonnes, la difficulté de modéliser des visites optionnelles, et la limitation de la recherche locale à grand voisinage (LNS) due à un espace de voisinage restreint. Il propose alors les variables de séquence, dont le domaine est défini par quatre composantes : nœuds requis, nœuds exclus, sous-séquences partielles et triplets interdits. La représentation implicite par un graphe d’insertion permet une gestion efficace de la mémoire. Il détaille les opérations de mise à jour du domaine, les stratégies de branchement inspirées du principe ‘first fail’, et l’intégration dans des solveurs CP existants. Il présente également des contraintes globales dédiées, comme la contrainte de distance, avec des mécanismes de filtrage par relaxation. L’exposé se conclut sur des perspectives d’intégration dans des solveurs comme MiniCP et MaxiCP, et sur des travaux en collaboration avec Augustin Delecluse et Pascal Van Hentenryck.

231 mots

Évaluation critique

Valeur des informations & solidité de l’argumentation

La valeur des informations est élevée : l’exposé présente une contribution originale et novatrice dans le domaine de la programmation par contraintes, avec des définitions formelles claires et des exemples illustratifs. L’argumentation est solide : l’orateur justifie la nécessité des variables de séquence en montrant les limitations des modèles à base de variables successeur, puis démontre leur efficacité sur des exemples concrets, notamment pour améliorer la qualité des solutions en recherche locale. La démonstration est progressive et bien structurée, passant de la motivation à la formalisation, puis aux aspects pratiques de mise en œuvre.

Rigueur scientifique, qualité des sources, adéquation du titre

La rigueur scientifique est exemplaire : l’exposé s’appuie sur des définitions formelles, des références à des travaux antérieurs (comme la contrainte circuit de J.-C. Régin, la contrainte element de P. Van Hentenryck) et des collaborations avec des chercheurs reconnus. Les sources citées dans la description sont institutionnelles (liste de diffusion et archives de séminaires AI4OPT), mais ne fournissent pas directement les références académiques des travaux présentés ; celles-ci sont évoquées oralement sans URL. L’adéquation entre le titre et le contenu est parfaite, le titre annonçant précisément le sujet traité. Aucun commentaire n’étant fourni, aucune analyse des tendances du public n’est possible.

210 mots

Adéquation titre / contenu

Le titre correspond parfaitement au contenu : il annonce l'introduction de variables de séquence pour résoudre des problèmes de tournées de véhicules avec la programmation par contraintes, ce qui est exactement le sujet traité.

Qualité & fiabilité

8/10

Exposé scientifique rigoureux par un chercheur reconnu, présentant des travaux originaux avec définitions formelles et démonstrations. Les concepts sont bien expliqués et s'appuient sur des références académiques solides.

Moments clés

Repères établis par PSI à partir de la transcription : le créateur n'a pas défini de chapitres.

Sources citées

  • Liste de diffusion AI4OPT — Annonce des séminaires AI4OPT, mentionnée en fin de description.
  • Séminaires passés AI4OPT — Archives des séminaires AI4OPT, mentionnée en fin de description.

Sources concordantes

  • Liste de diffusion AI4OPT — Annonce des séminaires AI4OPT, mentionnée en fin de description.
  • Séminaires passés AI4OPT — Archives des séminaires AI4OPT, mentionnée en fin de description.

Apport & nouveautés

L’apport original de cette présentation est l’introduction des variables de séquence en programmation par contraintes, une abstraction qui permet de modéliser naturellement les tournées avec visites optionnelles et de faciliter l’implémentation d’heuristiques d’insertion et de recherche locale à grand voisinage. Cette contribution comble une lacune des modèles classiques à base de variables successeur, qui sont moins adaptés à ces stratégies. L’exposé détaille la formalisation du domaine, les opérations de mise à jour, et l’intégration dans les solveurs CP existants, ouvrant la voie à de nouvelles applications.

Pour aller plus loin :

  • Programmation par contraintes — Notion de base essentielle pour comprendre le contexte.
  • Problème de tournées de véhicules — Problème central abordé dans l’exposé.
  • Recherche locale à grand voisinage — Technique d’optimisation mentionnée et améliorée par les variables de séquence.
  • Contrainte circuit — Contrainte classique de CP pour les tournées, comparée aux variables de séquence.
  • Contrainte element — Contrainte fondamentale utilisée dans les modèles CP, inventée par Pascal Van Hentenryck.

160 mots

Profil radar

Le profil radar montre des scores élevés et équilibrés dans toutes les dimensions, avec une légère prédominance de la qualité de l'information et du niveau technique, reflétant un exposé scientifique dense et bien structuré, adapté à un public averti.

Fiabilité 8/10