License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2013.108
URN: urn:nbn:de:0030-drops-42485
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4248/
Go to the corresponding OASIcs Volume Portal

Paraskevopoulos, Andreas ; Zaroliagis, Christos

Improved Alternative Route Planning

pdf-format:
10.pdf (2 MB)

Abstract

We present improved methods for computing a set of alternative source-to-destination routes in road networks in the form of an alternative graph. The resulting alternative graphs are characterized by minimum path overlap, small stretch factor, as well as low size and complexity. Our approach improves upon a previous one by introducing a new pruning stage preceding any other heuristic method and by introducing a new filtering and fine-tuning of two existing methods. Our accompanying experimental study shows that the entire alternative graph can be computed pretty fast even in continental size networks.

BibTeX - Entry

@InProceedings{paraskevopoulos_et_al:OASIcs:2013:4248,
  author =	{Andreas Paraskevopoulos and Christos Zaroliagis},
  title =	{{Improved Alternative Route Planning}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{108--122},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Daniele Frigioni and Sebastian Stiller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4248},
  URN =		{urn:nbn:de:0030-drops-42485},
  doi =		{10.4230/OASIcs.ATMOS.2013.108},
  annote =	{Keywords: Alternative route, stretch factor, shortest path, non-overlapping path, penalty, plateau}
}

Keywords: Alternative route, stretch factor, shortest path, non-overlapping path, penalty, plateau
Collection: 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2013
Date of publication: 05.09.2013

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