License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CP.2022.19
URN: urn:nbn:de:0030-drops-166485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16648/
Go to the corresponding LIPIcs Volume Portal

Delecluse, Augustin ; Schaus, Pierre ; Van Hentenryck, Pascal

Sequence Variables for Routing Problems

pdf-format:
LIPIcs-CP-2022-19.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{delecluse_et_al:LIPIcs.CP.2022.19,
  author =	{Delecluse, Augustin and Schaus, Pierre and Van Hentenryck, Pascal},
  title =	{{Sequence Variables for Routing Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16648},
  URN =		{urn:nbn:de:0030-drops-166485},
  doi =		{10.4230/LIPIcs.CP.2022.19},
  annote =	{Keywords: Constraint Programming, Dial-A-Ride, Patient Transportation, TSPTW, Vehicle Routing, Sequence Variables, Insertion Variables}
}

Keywords: Constraint Programming, Dial-A-Ride, Patient Transportation, TSPTW, Vehicle Routing, Sequence Variables, Insertion Variables
Collection: 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Issue Date: 2022
Date of publication: 23.07.2022
Supplementary Material: Software (Source Code): https://github.com/augustindelecluse/minicp-sequences archived at: https://archive.softwareheritage.org/swh:1:dir:144eae8f012ef66bb6f2289b1419f48b6779e294

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI