Complexity of scheduling for DARP with soft ride times

Janka Chlebikova; Clément Dallard; Niklas Paulsen

doi:10.1007/978-3-030-17402-6_13

Complexity of scheduling for DARP with soft ride times

Janka Chlebikova, Clément Dallard, Niklas Paulsen

School of Computing

University of Kiel

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

179 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Algorithms and Complexity
Subtitle of host publication	11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019, Proceedings
Editors	Pinar Heggernes
Publisher	Springer
Pages	149-160
Number of pages	12
ISBN (Electronic)	978-3-030-17402-6
ISBN (Print)	978-3-030-17401-9
DOIs	https://doi.org/10.1007/978-3-030-17402-6_13
Publication status	Published - 1 May 2019
Event	11th International Conference on Algorithms and Complexity - Rome, Italy Duration: 27 May 2019 → 29 May 2019 http://easyconferences.eu/ciac2019/

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	11485
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	11th International Conference on Algorithms and Complexity
Abbreviated title	CIAC
Country/Territory	Italy
City	Rome
Period	27/05/19 → 29/05/19
Internet address	http://easyconferences.eu/ciac2019/

Keywords

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

Access to Document

10.1007/978-3-030-17402-6_13

Complexity of scheduling postprint
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

Cite this

@inproceedings{11e1c8f3cfc44cf58881c648b7d77fec,

title = "Complexity of scheduling for DARP with soft ride times",

abstract = "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.",

keywords = "dial-a-ride, time windows, ride times, NPhardness, Vehicle Routing Problem, scheduling",

author = "Janka Chlebikova and Cl{\'e}ment Dallard and Niklas Paulsen",

year = "2019",

month = may,

day = "1",

doi = "10.1007/978-3-030-17402-6_13",

language = "English",

isbn = "978-3-030-17401-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "149--160",

editor = "Pinar Heggernes",

booktitle = "Algorithms and Complexity",

note = "11th International Conference on Algorithms and Complexity, CIAC ; Conference date: 27-05-2019 Through 29-05-2019",

url = "http://easyconferences.eu/ciac2019/",

}

Chlebikova, J, Dallard, C & Paulsen, N 2019, Complexity of scheduling for DARP with soft ride times. in P Heggernes (ed.), Algorithms and Complexity: 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019, Proceedings. Lecture Notes in Computer Science, vol. 11485, Springer, pp. 149-160, 11th International Conference on Algorithms and Complexity, Rome, Italy, 27/05/19. https://doi.org/10.1007/978-3-030-17402-6_13

Complexity of scheduling for DARP with soft ride times. / Chlebikova, Janka; Dallard, Clément; Paulsen, Niklas.
Algorithms and Complexity: 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019, Proceedings. ed. / Pinar Heggernes. Springer, 2019. p. 149-160 (Lecture Notes in Computer Science; Vol. 11485).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Complexity of scheduling for DARP with soft ride times

AU - Chlebikova, Janka

AU - Dallard, Clément

AU - Paulsen, Niklas

PY - 2019/5/1

Y1 - 2019/5/1

N2 - 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.

AB - 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.

KW - dial-a-ride

KW - time windows

KW - ride times

KW - NPhardness

KW - Vehicle Routing Problem

KW - scheduling

U2 - 10.1007/978-3-030-17402-6_13

DO - 10.1007/978-3-030-17402-6_13

M3 - Conference contribution

SN - 978-3-030-17401-9

T3 - Lecture Notes in Computer Science

SP - 149

EP - 160

BT - Algorithms and Complexity

A2 - Heggernes, Pinar

PB - Springer

T2 - 11th International Conference on Algorithms and Complexity

Y2 - 27 May 2019 through 29 May 2019

ER -

Complexity of scheduling for DARP with soft ride times

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this