Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies

Authors

  • Marieke van der Tuin Delft University of Technology
  • Mathijs de Weerdt Delft University of Technology
  • G. Batz ORTEC B.V.

DOI:

https://doi.org/10.1609/icaps.v28i1.13912

Keywords:

time-dependent shortest path, break planning, driving bans, multi-criteria search, contraction hierarchies, drivers legislation

Abstract

Mandatory breaks for truck drivers are nowadays scheduled after the route has been decided. However, in some cases it is beneficial to plan these breaks during waiting time caused by truck driving bans. Optimally planning a single break considering driving bans can be done using Dijkstra’s algorithm with multiple labels. This has large effects on predicted travel times: 17% of the analysed routes having a night rest obtain an earlier arrival time by 5 hours on average. However, the computation times of this algorithm are long. A novel heuristic version of time-dependent contraction hierarchies leads to significant reductions in computation times from several seconds to several milliseconds per route. Experiments show that the solutions are still optimal for a representative test set consisting of 10,000 route queries.

Downloads

Published

2018-06-15

How to Cite

van der Tuin, M., de Weerdt, M., & Batz, G. (2018). Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies. Proceedings of the International Conference on Automated Planning and Scheduling, 28(1), 356-364. https://doi.org/10.1609/icaps.v28i1.13912

Issue

Vol. 28 (2018): Twenty-Eighth International Conference on Automated Planning and Scheduling

Section

Novel Applications Track