License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.17
URN: urn:nbn:de:0030-drops-120910
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12091/
Kleff, Alexander ;
Schulz, Frank ;
Wagenblatt, Jakob ;
Zeitz, Tim
Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas
Abstract
We study the problem of planning routes in road networks when certain streets or areas are closed at certain times. For heavy vehicles, such areas may be very large since many European countries impose temporary driving bans during the night or on weekends. In this setting, feasible routes may require waiting at parking areas, and several feasible routes with different trade-offs between waiting and driving detours around closed areas may exist. We propose a novel model in which driving and waiting are assigned abstract costs, and waiting costs are location-dependent to reflect the different quality of the parking areas. Our goal is to find Pareto-optimal routes with regards to arrival time at the destination and total cost. We investigate the complexity of the model and determine a necessary constraint on the cost parameters such that the problem is solvable in polynomial time. We present a thoroughly engineered implementation and perform experiments on a production-grade real world data set. The experiments show that our implementation can answer realistic queries in around a second or less which makes it feasible for practical application.
BibTeX - Entry
@InProceedings{kleff_et_al:LIPIcs:2020:12091,
author = {Alexander Kleff and Frank Schulz and Jakob Wagenblatt and Tim Zeitz},
title = {{Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas}},
booktitle = {18th International Symposium on Experimental Algorithms (SEA 2020)},
pages = {17:1--17:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-148-1},
ISSN = {1868-8969},
year = {2020},
volume = {160},
editor = {Simone Faro and Domenico Cantone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12091},
URN = {urn:nbn:de:0030-drops-120910},
doi = {10.4230/LIPIcs.SEA.2020.17},
annote = {Keywords: driving bans, realistic road networks, route planning, shortest paths}
}
|
Keywords: |
|
driving bans, realistic road networks, route planning, shortest paths |
|
Collection: |
|
18th International Symposium on Experimental Algorithms (SEA 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
12.06.2020 |
