Evolution and Evaluation of the Penalty Method for Alternative Graphs

Abstract : Computing meaningful alternative routes in a road network is a complex problem ― already giving a clear definition of a best alternative seems to be impossible. Still, multiple methods describe how to compute reasonable alternative routes, each according to their own quality criteria. Among these methods, the penalty method has received much less attention than the via-node or plateaux based approaches. A mayor cause for the lack of interest might be the unavailability of an efficient implementation. In this paper, we take a closer look at the penalty method and extend upon its ideas. We provide the first viable implementation ―suitable for interactive use― using dynamic runtime adjustments to perform up to multiple orders of magnitude faster queries than previous implementations. Using our new implementation, we thoroughly evaluate the penalty method for its flaws and benefits.
Type de document :
Communication dans un congrès
Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.94--107, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.94〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00871738
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 10 octobre 2013 - 11:59:30
Dernière modification le : vendredi 11 octobre 2013 - 13:34:55
Document(s) archivé(s) le : vendredi 7 avril 2017 - 08:55:50

Fichier

9.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Moritz Kobitzsch, Marcel Radermacher, Dennis Schieferdecker. Evolution and Evaluation of the Penalty Method for Alternative Graphs. Daniele Frigioni and Sebastian Stiller. ATMOS - 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems - 2013, Sep 2013, Sophia Antipolis, France. Schloss Dagstuhl―Leibniz-Zentrum fuer Informatik, 33, pp.94--107, 2013, OpenAccess Series in Informatics (OASIcs). 〈10.4230/OASIcs.ATMOS.2013.94〉. 〈hal-00871738〉

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

324