Joint vehicle and crew routing and scheduling

Edward Lam, Pascal Van Hentenryck, Phil Kilby

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Traditional vehicle routing problems implicitly assume that 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. The problem is formulated as a mixed integer programming (MIP) model and a constraint programming (CP) model that overlay crew routing constraints over a standard vehicle routing problem. The constraint program uses a novel optimization constraint to detect infeasibility and to bound crew objectives. This paper also explores methods using large neighborhood search over the MIP and CP models. Experimental results indicate that modeling the vehicle and crew routing problems jointly and supporting vehicle interchanges for crews may bring significant benefits in cost reduction compared with a method that sequentializes these decisions.

Original languageEnglish
Pages (from-to)488-511
Number of pages24
JournalTransportation Science
Volume54
Issue number2
DOIs
Publication statusPublished - Mar 2020

Keywords

  • Constraint programming
  • Crew routing
  • Crew scheduling
  • Hybrid optimization
  • Large neighborhood search
  • Mixed integer programming
  • Synchronization
  • Vehicle routing
  • Vehicle scheduling

Cite this