1 Search Results for "Montanari, Sandro"

Document
DOI: 10.4230/OASIcs.ATMOS.2015.82
Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks

Authors: Matúš Mihalák and Sandro Montanari

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

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.
Cite as

Matúš Mihalák and Sandro Montanari. Bi-directional Search for Robust Routes in Time-dependent Bi-criteria Road Networks. In 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. 82-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{mihalak_et_al:OASIcs.ATMOS.2015.82,
  author =	{Mihal\'{a}k, Mat\'{u}\v{s} and Montanari, Sandro},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.82},
  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}
}
  • Refine by Author
  • 1 Mihalák, Matúš
  • 1 Montanari, Sandro

  • Refine by Classification

  • Refine by Keyword
  • 1 bi-criteria
  • 1 bi-directional search
  • 1 min-max relative regret
  • 1 shortest path
  • 1 time-dependent

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact