License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2011.64
URN: urn:nbn:de:0030-drops-32670
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3267/
Go to the corresponding OASIcs Volume Portal

Kirchler, Dominik ; Liberti, Leo ; Pajor, Thomas ; Wolfler Calvo, Roberto

UniALT for regular language contrained shortest paths on a multi-modal transportation network

pdf-format:
7.pdf (0.7 MB)

Abstract

Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constrained shortest path problem deals with this kind of problem. It uses a regular language to model the constraints. The problem can be solved efficiently by using a generalization of Dijkstra's algorithm (D_RegLC). In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate D_RegLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent cost functions on arcs. The experiments show that our algorithm performs well, with speed-ups of a factor 2 to 20.

BibTeX - Entry

@InProceedings{kirchler_et_al:OASIcs:2011:3267,
  author =	{Dominik Kirchler and Leo Liberti and Thomas Pajor and Roberto Wolfler Calvo},
  title =	{{UniALT for regular language contrained shortest paths on a multi-modal transportation network}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{64--75},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Alberto Caprara and Spyros Kontogiannis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3267},
  URN =		{urn:nbn:de:0030-drops-32670},
  doi =		{10.4230/OASIcs.ATMOS.2011.64},
  annote =	{Keywords: time-dependency, ALT, regular language, shortest path, multi-modal}
}

Keywords: time-dependency, ALT, regular language, shortest path, multi-modal
Collection: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2011
Date of publication: 19.09.2011

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