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

^*Corresponding author for this work

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

11 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 - 21st International Conference, CP 2015, Proceedings
Editors	Gilles Pesant
Publisher	Springer Verlag
Pages	654-670
Number of pages	17
ISBN (Print)	9783319232188
DOIs	https://doi.org/10.1007/978-3-319-23219-5_45
Publication status	Published - 2015
Event	21st International Conference on the Principles and Practice of Constraint Programming, CP 2015 - Cork, Ireland Duration: 31 Aug 2015 → 4 Sept 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9255
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
Country/Territory	Ireland
City	Cork
Period	31/08/15 → 4/09/15

Access to Document

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

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, Proceedings (pp. 654-670). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9255). Springer Verlag. https://doi.org/10.1007/978-3-319-23219-5_45

Lam, Edward ; Van Hentenryck, Pascal ; Kilby, Philip. / Joint vehicle and crew routing and scheduling. Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings. editor / Gilles Pesant. Springer Verlag, 2015. pp. 654-670 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{72caff2ee6bb4c098ab6ad7d82f64120,

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",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015 ; Conference date: 31-08-2015 Through 04-09-2015",

year = "2015",

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

language = "English",

isbn = "9783319232188",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "654--670",

editor = "Gilles Pesant",

booktitle = "Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings",

address = "Germany",

}

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, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9255, Springer Verlag, pp. 654-670, 21st International Conference on the Principles and Practice of Constraint Programming, CP 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, Proceedings. ed. / Gilles Pesant. Springer Verlag, 2015. p. 654-670 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9255).

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

TY - GEN

T1 - Joint vehicle and crew routing and scheduling

AU - Lam, Edward

AU - Van Hentenryck, Pascal

AU - Kilby, Philip

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 contribution

SN - 9783319232188

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 654

EP - 670

BT - Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings

A2 - Pesant, Gilles

PB - Springer Verlag

T2 - 21st International Conference on the Principles and Practice of Constraint Programming, CP 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, Proceedings. Springer Verlag. 2015. p. 654-670. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-23219-5_45

Joint vehicle and crew routing and scheduling

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this