DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2020.17

Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas

Authors: Alexander Kleff, Frank Schulz, Jakob Wagenblatt, and Tim Zeitz

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

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.

Cite as

Alexander Kleff, Frank Schulz, Jakob Wagenblatt, and Tim Zeitz. Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kleff_et_al:LIPIcs.SEA.2020.17,
  author =	{Kleff, Alexander and Schulz, Frank and Wagenblatt, Jakob and Zeitz, Tim},
  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 =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.17},
  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}
}

Search Results

Documents authored by Wagenblatt, Jakob

Efficient Route Planning with Temporary Driving Bans, Road Closures, and Rated Parking Areas

Abstract

Cite as

Thanks for your feedback!

Could not send message