Insertion Sequence Variables for Hybrid Routing and Scheduling Problems

Schaus, Pierre;Thomas, Charles;Kameugne, Roger;et.al.
(2020) 17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research — Location: Online (21.September.2020)

Files

Sequences_cpaior2020.pdf
  • Open Access
  • Adobe PDF
  • 531.38 KB
Download

Details

Authors
Abstract
The Dial a Ride family of Problems (DARP) consists in routing a fleet of vehicles to satisfy transportation requests with time-windows. This problem is at the frontier between routing and scheduling. The most successful approaches in dealing with DARP are often tailored to specific variants. A generic state-of-the-art constraint programming model consists in using a sequence variable to represent the ordering of visits in a route. We introduce a possible representation for the domain called Insertion Sequence Variable that naturally extends the standard subset bound for set variables with an additional insertion operator after any element already sequenced. We describe the important constraints on the sequence variable and their filtering algorithms required to model the classical DARP and one of its variants called the Patient Transportation Problem (PTP). Our experimental results on a large variety of instances show that the proposed approach is competitive with existing sequence based approaches.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Schaus, P., Thomas, C., Kameugne, R., & et al. (2020). Insertion Sequence Variables for Hybrid Routing and Scheduling Problems. 17th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research, Online. https://hdl.handle.net/2078.5/271169