OASIcs.ATMOS.2013.108.pdf
- Filesize: 2.15 MB
- 15 pages
Document
Improved Alternative Route Planning
Authors
-
Part of:
Volume:
13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2013)
Series: Open Access Series in Informatics (OASIcs)
Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2013-09-05
Cite As Get BibTex
Andreas Paraskevopoulos and Christos Zaroliagis. Improved Alternative Route Planning. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 108-122, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
https://doi.org/10.4230/OASIcs.ATMOS.2013.108
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.
Subject Classification
Keywords
- Alternative route
- stretch factor
- shortest path
- non-overlapping path
- penalty
- plateau
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads