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

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

3 Citations (Scopus)
23 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationProceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling
EditorsMathijs de Weerdt, Sven Koenig, Gabriele Röger, Matthijs Spaan
PublisherAmerican Association for Artificial Intelligence (AAAI)
Pages356-364
Number of pages9
ISBN (Print)978-1-57735-797-1
Publication statusPublished - 2018
Event28th International Conference on Automated Planning and Scheduling: KEPS 2018 - Delft, Delft, Netherlands
Duration: 24 Jun 201829 Jun 2018
Conference number: 28
http://www.icaps-conference.org

Conference

Conference28th International Conference on Automated Planning and Scheduling
Abbreviated titleICAPS 2018
CountryNetherlands
CityDelft
Period24/06/1829/06/18
Internet address

Fingerprint Dive into the research topics of 'Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies'. Together they form a unique fingerprint.

  • Cite this

    van der Tuin, M., de Weerdt, M., & Batz, G. V. (2018). Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies. In M. de Weerdt, S. Koenig, G. Röger, & M. Spaan (Eds.), Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling (pp. 356-364). American Association for Artificial Intelligence (AAAI). https://www.aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17745