Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kleff, Alexander; Schulz, Frank; Wagenblatt, Jakob; Zeitz, Tim https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-120910
URL:

; ; ;

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

pdf-format:


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
Seminar: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue date: 2020
Date of publication: 12.06.2020


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI