Complexity of scheduling for DARP with soft ride times

Janka Chlebikova, Clément Dallard, Niklas Paulsen

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

160 Downloads (Pure)


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
Number of pages12
ISBN (Electronic)978-3-030-17402-6
ISBN (Print)978-3-030-17401-9
Publication statusPublished - 1 May 2019
Event11th International Conference on Algorithms and Complexity - Rome, Italy
Duration: 27 May 201929 May 2019

Publication series

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


Conference11th International Conference on Algorithms and Complexity
Abbreviated titleCIAC
Internet address


  • dial-a-ride
  • time windows
  • ride times
  • NPhardness
  • Vehicle Routing Problem
  • scheduling


Dive into the research topics of 'Complexity of scheduling for DARP with soft ride times'. Together they form a unique fingerprint.

Cite this