2026-07-26T20:56:38Z https://drops.dagstuhl.de/oai

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

Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks Mihalák, Matúš Montanari, Sandro shortest path time-dependent bi-criteria bi-directional search min-max relative regret Based on time-dependent travel times for N past days, we consider the computation of robust routes according to the min-max relative regret criterion. For this method we seek a path minimizing its maximum weight in any one of the N days, normalized by the weight of an optimum for the respective day. In order to speed-up this computationally demanding approach, we observe that its output belongs to the Pareto front of the network with time-dependent multi-criteria edge weights. We adapt a well-known algorithm for computing Pareto fronts in time-dependent graphs and apply the bi-directional search technique to it. We also show how to parametrize this algorithm by a value K to compute a K-approximate Pareto front. An experimental evaluation for the cases N = 2 and N = 3 indicates a considerable speed-up of the bi-directional search over the uni-directional. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Matúš Mihalák and Sandro Montanari 2015 Is Part Of OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2015.82 urn:nbn:de:0030-drops-54561 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.82 eng https://creativecommons.org/licenses/by/3.0/legalcode