Joint Vehicle and Crew Routing and Scheduling

Edward Lam; Pascal Van Hentenryck; Philip Kilby

doi:10.1007/978-3-319-23219-5_45

Joint Vehicle and Crew Routing and Scheduling

Edward Lam, Pascal Van Hentenryck, Philip Kilby

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

6 Citations (Scopus)

Abstract

Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehicle-then-crew sequential approach.

Original language	English
Title of host publication	Principles and Practice of Constraint Programming
Subtitle of host publication	21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings
Editors	Gilles Pesant
Place of Publication	Cham Switzerland
Publisher	Springer
Pages	654-670
Number of pages	17
ISBN (Electronic)	9783319232195
ISBN (Print)	9783319232188
DOIs	https://doi.org/10.1007/978-3-319-23219-5_45
Publication status	Published - 2015
Externally published	Yes
Event	International Conference on Principles and Practice of Constraint Programming 2015 - Cork, Ireland Duration: 31 Aug 2015 → 4 Sep 2015 Conference number: 21st https://web.archive.org/web/20150810094235/http://booleconferences.ucc.ie/cp2015

Publication series

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

Conference

Conference	International Conference on Principles and Practice of Constraint Programming 2015
Abbreviated title	CP 2015
Country	Ireland
City	Cork
Period	31/08/15 → 4/09/15
Internet address	https://web.archive.org/web/20150810094235/http://booleconferences.ucc.ie/cp2015

Access to Document

10.1007/978-3-319-23219-5_45

Link to publication in Scopus

Cite this

Lam, E., Van Hentenryck, P., & Kilby, P. (2015). Joint Vehicle and Crew Routing and Scheduling. In G. Pesant (Ed.), Principles and Practice of Constraint Programming : 21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings (pp. 654-670). (Lecture Notes in Computer Science ; Vol. 9255). Springer. https://doi.org/10.1007/978-3-319-23219-5_45

@inproceedings{da9ab4c5b3544495badfcddbf275f8a4,

title = "Joint Vehicle and Crew Routing and Scheduling",

abstract = "Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehicle-then-crew sequential approach.",

author = "Edward Lam and {Van Hentenryck}, Pascal and Philip Kilby",

year = "2015",

doi = "10.1007/978-3-319-23219-5_45",

language = "English",

isbn = "9783319232188",

series = "Lecture Notes in Computer Science ",

publisher = "Springer",

pages = "654--670",

editor = "Gilles Pesant",

booktitle = "Principles and Practice of Constraint Programming",

note = "International Conference on Principles and Practice of Constraint Programming 2015, CP 2015 ; Conference date: 31-08-2015 Through 04-09-2015",

url = "https://web.archive.org/web/20150810094235/http://booleconferences.ucc.ie/cp2015",

}

Lam, E, Van Hentenryck, P & Kilby, P 2015, Joint Vehicle and Crew Routing and Scheduling. in G Pesant (ed.), Principles and Practice of Constraint Programming : 21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings. Lecture Notes in Computer Science , vol. 9255, Springer, Cham Switzerland, pp. 654-670, International Conference on Principles and Practice of Constraint Programming 2015, Cork, Ireland, 31/08/15. https://doi.org/10.1007/978-3-319-23219-5_45

Joint Vehicle and Crew Routing and Scheduling. / Lam, Edward; Van Hentenryck, Pascal; Kilby, Philip.

Principles and Practice of Constraint Programming : 21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings. ed. / Gilles Pesant. Cham Switzerland : Springer, 2015. p. 654-670 (Lecture Notes in Computer Science ; Vol. 9255).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Joint Vehicle and Crew Routing and Scheduling

AU - Lam, Edward

AU - Van Hentenryck, Pascal

AU - Kilby, Philip

N1 - Conference code: 21st

PY - 2015

Y1 - 2015

N2 - Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehicle-then-crew sequential approach.

AB - Traditional vehicle routing problems implicitly assume only one crew operates a vehicle for the entirety of its journey. However, this assumption is violated in many applications arising in humanitarian and military logistics. This paper considers a Joint Vehicle and Crew Routing and Scheduling Problem, in which crews are able to interchange vehicles, resulting in space and time interdependencies between vehicle routes and crew routes. It proposes a constraint programming model that overlays crew routing constraints over a standard vehicle routing problem. The constraint programming model uses a novel optimization constraint that detects infeasibility and bounds crew objectives. Experimental results demonstrate significant benefits of using constraint programming over mixed integer programming and a vehicle-then-crew sequential approach.

UR - http://www.scopus.com/inward/record.url?scp=84944604893&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-23219-5_45

DO - 10.1007/978-3-319-23219-5_45

M3 - Conference Paper

AN - SCOPUS:84944604893

SN - 9783319232188

T3 - Lecture Notes in Computer Science

SP - 654

EP - 670

BT - Principles and Practice of Constraint Programming

A2 - Pesant, Gilles

PB - Springer

CY - Cham Switzerland

T2 - International Conference on Principles and Practice of Constraint Programming 2015

Y2 - 31 August 2015 through 4 September 2015

ER -

Lam E, Van Hentenryck P, Kilby P. Joint Vehicle and Crew Routing and Scheduling. In Pesant G, editor, Principles and Practice of Constraint Programming : 21st International Conference, CP 2015 Cork, Ireland, August 31 – September 4, 2015 Proceedings. Cham Switzerland: Springer. 2015. p. 654-670. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-23219-5_45