Skip to content

Complexity of scheduling for DARP with soft ride times

Research output: Chapter in Book/Report/Conference proceedingConference contribution

The Dial-a-Ride problem may contain various constraints for pickup-delivery requests, such as time windows and ride time constraints. For a tour, given as a sequence of pickup and delivery stops, there exist polynomial time algorithms to nd a schedule respecting these constraints, provided that there exists one. However, if no feasible schedule exists, the natural question is to nd a schedule minimising constraint violations. We model a generic xed-sequence scheduling problem, allowing lateness and ride time violations with linear penalty functions and prove its APX-hardness. We also present an approach leading to a polynomial time algorithm if only the time window constraints can be violated (by late visits). Then, we show that the problem can be solved in polynomial time if all the ride time constraints are bounded by a constant. Lastly, we give a polynomial time algorithm for the instances where all the pickups precede all the deliveries in the sequence of stops.
Original languageEnglish
Title of host publicationAlgorithms and Complexity
Subtitle of host publication11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019, Proceedings
EditorsPinar Heggernes
PublisherSpringer
Pages149-160
Number of pages12
ISBN (Electronic)978-3-030-17402-6
ISBN (Print)978-3-030-17401-9
DOIs
Publication statusPublished - 1 May 2019
Event11th International Conference on Algorithms and Complexity - Rome, Italy
Duration: 27 May 201929 May 2019
http://easyconferences.eu/ciac2019/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11485
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference11th International Conference on Algorithms and Complexity
Abbreviated titleCIAC
CountryItaly
CityRome
Period27/05/1929/05/19
Internet address

Documents

  • Complexity of scheduling postprint

    Rights statement: The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-17402-6_13.

    Accepted author manuscript (Post-print), 420 KB, PDF document

Related information

Relations Get citation (various referencing formats)

ID: 15620980