Extended Abstract: Sequence Variables for Routing Problems

Augustin Delecluse;Schaus, Pierre;Van Hentenryck, Pascal
(2022) , 3 pages

Files

Sequence_Variables_for_Routing_Problems___Extended_Abstract.pdf
  • Open Access
  • Adobe PDF
  • 424.46 KB
  • https://creativecommons.org/licenses/by/4.0/
Download

Details

Authors
  • Augustin DelecluseUCLouvain
    Author
  • Schaus, Pierreorcid-logoUCLouvain
    Author
  • Van Hentenryck, PascalGeorgia Tech
    Author
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 [2] 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
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Augustin Delecluse, Schaus, P., & Van Hentenryck, P. (2022). Extended Abstract: Sequence Variables for Routing Problems. https://hdl.handle.net/2078.5/235805