2026-08-17T08:35:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16648 2024-03-06T10:57:57Z ddc:004 open_access

Sequence Variables for Routing Problems Delecluse, Augustin Schaus, Pierre Van Hentenryck, Pascal Constraint Programming Dial-A-Ride Patient Transportation TSPTW Vehicle Routing Sequence Variables Insertion Variables Constraint Programming (CP) is one of the most flexible approaches for modeling and solving vehicle routing problems (VRP). This paper proposes the sequence variable domain, that is inspired by the insertion graph introduced in [Bent and Van Hentenryck, 2004] and the subset bound domain for set variables. This domain representation, which targets VRP applications, allows for an efficient insertion-based search on a partial tour and the implementation of simple, yet efficient filtering algorithms for constraints that enforce time-windows on the visits and capacities on the vehicles. Experiment results demonstrate the efficiency and flexibility of this CP domain for solving some hard VRP problems, including the Dial-A-Ride, the Patient Transportation, and the asymmetric TSP with time windows. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Augustin Delecluse and Pierre Schaus and Pascal Van Hentenryck 2022 Is Part Of LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CP.2022.19 urn:nbn:de:0030-drops-166485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.19 eng https://creativecommons.org/licenses/by/4.0/legalcode