Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints

Daiane Maria Genaro Chiroli (), Sérgio Fernando Mayerle () and João Neiva Figueiredo ()
Additional contact information
Daiane Maria Genaro Chiroli: Federal Technology University of Paraná
Sérgio Fernando Mayerle: Federal University of Santa Catarina
João Neiva Figueiredo: Saint Joseph’s University

Journal of Heuristics, 2022, vol. 28, issue 1, No 2, 23-59

Abstract: Abstract This paper addresses the vehicle routing and driver scheduling problem of finding a low cost route and stoppage schedule for long-haul point-to-point full-load trips with intermediate stops due to refueling needs and driver hours-of-service regulatory restrictions. This is an important problem for long-haul truck drivers because in practice regulatory driving limits often do not coincide with availability of stoppage alternatives for quick rest, for meal, for overnight, or for weekly downtime required stops. The paper presents a methodology and algorithm to pick routes that optimize stoppages within the HOS constraints, an important factor of both highway safety and driver productivity. A solution for this variant of the vehicle routing and truck driver scheduling problem (VRTDS-HOS) that is fast enough to potentially be used in real time is proposed by modeling possible stoppage configurations as nodes in an iteratively built multi-dimensional state-space graph and by using heuristics to decrease processing time when searching for the lowest-cost path in that graph. Individual nodes in the graph are characterized by spatial, temporal, and stoppage attributes, and are expanded sequentially to search for low-cost paths between the origin and the destination. Within this multi-dimensional state-space graph, the paper proposes two heuristics applied to a shortest-path algorithmic solution based on the $$A^*$$ A ∗ algorithm to increase processing speed enough to potentially permit real-time usage. An illustrative application to Brazilian regulations is provided. Results were successful and are reported together with sensitivity analyses comparing alternative routes and different heuristics processing speeds.

Keywords: Vehicle routing and driver scheduling; Point-to-point long-haul full-load trip optimization; Driver hours of service regulatory constraints; Heuristic state-space graph search; $$A^*$$ A ∗ algorithm (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-021-09489-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:28:y:2022:i:1:d:10.1007_s10732-021-09489-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-021-09489-7

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().