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

Marieke van der Tuin; Mathijs de Weerdt; G. Veit Batz

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

Marieke van der Tuin, Mathijs de Weerdt, G. Veit Batz

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

6 Citations (Scopus)

45 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 language	English
Title of host publication	Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling
Editors	Mathijs de Weerdt, Sven Koenig, Gabriele Röger, Matthijs Spaan
Publisher	American Association for Artificial Intelligence (AAAI)
Pages	356-364
Number of pages	9
ISBN (Print)	978-1-57735-797-1
Publication status	Published - 2018
Event	28th International Conference on Automated Planning and Scheduling: KEPS 2018 - Delft, Delft, Netherlands Duration: 24 Jun 2018 → 29 Jun 2018 Conference number: 28 http://www.icaps-conference.org

Conference

Conference	28th International Conference on Automated Planning and Scheduling
Abbreviated title	ICAPS 2018
Country/Territory	Netherlands
City	Delft
Period	24/06/18 → 29/06/18
Internet address	http://www.icaps-conference.org

Bibliographical note

Green Open Access added to TU Delft Institutional Repository ‘You share, we take care!’ – Taverne project https://www.openaccess.nl/en/you-share-we-take-care

Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.

Access to Document

17745-77862-1-PBFinal published version, 861 KB

https://www.aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17745

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

van der Tuin, Marieke ; de Weerdt, Mathijs ; Batz, G. Veit. / Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies. Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling. editor / Mathijs de Weerdt ; Sven Koenig ; Gabriele Röger ; Matthijs Spaan. American Association for Artificial Intelligence (AAAI), 2018. pp. 356-364

@inproceedings{1526632b600745d99458b4bb81afcad0,

title = "Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies",

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{\textquoteright}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.",

author = "{van der Tuin}, Marieke and {de Weerdt}, Mathijs and Batz, {G. Veit}",

note = "Green Open Access added to TU Delft Institutional Repository {\textquoteleft}You share, we take care!{\textquoteright} – Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.; 28th International Conference on Automated Planning and Scheduling : KEPS 2018, ICAPS 2018 ; Conference date: 24-06-2018 Through 29-06-2018",

year = "2018",

language = "English",

isbn = "978-1-57735-797-1",

pages = "356--364",

editor = "{de Weerdt}, Mathijs and Sven Koenig and Gabriele R{\"o}ger and Matthijs Spaan",

booktitle = "Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling",

publisher = "American Association for Artificial Intelligence (AAAI)",

address = "United States",

url = "http://www.icaps-conference.org",

}

van der Tuin, M, de Weerdt, M & Batz, GV 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. American Association for Artificial Intelligence (AAAI), pp. 356-364, 28th International Conference on Automated Planning and Scheduling, Delft, Netherlands, 24/06/18. <https://www.aaai.org/ocs/index.php/ICAPS/ICAPS18/paper/view/17745>

Route Planning with Breaks and Truck Driving Bans Using Time-Dependent Contraction Hierarchies. / van der Tuin, Marieke; de Weerdt, Mathijs; Batz, G. Veit.
Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling. ed. / Mathijs de Weerdt; Sven Koenig; Gabriele Röger; Matthijs Spaan. American Association for Artificial Intelligence (AAAI), 2018. p. 356-364.

Research output: Chapter in Book/Conference proceedings/Edited volume › Conference contribution › Scientific › peer-review

TY - GEN

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

AU - van der Tuin, Marieke

AU - de Weerdt, Mathijs

AU - Batz, G. Veit

N1 - Conference code: 28

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 978-1-57735-797-1

SP - 356

EP - 364

BT - Proceedings of The Twenty-Eighth International Conference on Automated Planning and Scheduling

A2 - de Weerdt, Mathijs

A2 - Koenig, Sven

A2 - Röger, Gabriele

A2 - Spaan, Matthijs

PB - American Association for Artificial Intelligence (AAAI)

T2 - 28th International Conference on Automated Planning and Scheduling

Y2 - 24 June 2018 through 29 June 2018

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this