2026-07-20T05:59:58Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4248 2024-03-06T10:29:21Z ddc:004 open_access

Improved Alternative Route Planning Paraskevopoulos, Andreas Zaroliagis, Christos Alternative route stretch factor shortest path non-overlapping path penalty plateau 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andreas Paraskevopoulos and Christos Zaroliagis 2013 Is Part Of OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2013.108 urn:nbn:de:0030-drops-42485 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.108 eng https://creativecommons.org/licenses/by/3.0/legalcode