License: 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.2015.82
URN: urn:nbn:de:0030-drops-54561
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5456/
Go to the corresponding OASIcs Volume Portal

Mihalák, Matúš ; Montanari, Sandro

Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks

pdf-format:
7.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{mihalk_et_al:OASIcs:2015:5456,
  author =	{Mat{\'u}{\v{s}} Mihal{\'a}k and Sandro Montanari},
  title =	{{Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{82--94},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Giuseppe F. Italiano and Marie Schmidt},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5456},
  URN =		{urn:nbn:de:0030-drops-54561},
  doi =		{10.4230/OASIcs.ATMOS.2015.82},
  annote =	{Keywords: shortest path, time-dependent, bi-criteria, bi-directional search, min-max relative regret}
}

Keywords: shortest path, time-dependent, bi-criteria, bi-directional search, min-max relative regret
Collection: 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)
Issue Date: 2015
Date of publication: 14.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI