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: https://drops.dagstuhl.de/opus/volltexte/2013/4248/
Paraskevopoulos, Andreas ; Zaroliagis, Christos
Improved Alternative Route Planning
| pdf-format: |
|
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 | |
| Seminar: | 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems | |
| Issue date: | 2013 | |
| Date of publication: | 05.09.2013 |
