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.2017.16
URN: urn:nbn:de:0030-drops-79035
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7903/
Go to the corresponding OASIcs Volume Portal

Dokka, Trivikram ; Goerigk, Marc

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

pdf-format:
OASIcs-ATMOS-2017-16.pdf (0.5 MB)

Abstract

Through the development of efficient algorithms, data structures and preprocessing techniques, real-world shortest path problems in street networks are now very fast to solve. But in reality, the exact travel times along each arc in the network may not be known. This led to the development of robust shortest path problems, where all possible arc travel times are contained in a so-called uncertainty set of possible outcomes.

Research in robust shortest path problems typically assumes this set to be given, and provides complexity results as well as algorithms depending on its shape. However, what can actually be observed in real-world problems are only discrete raw data points. The shape of the uncertainty is already a modelling assumption. In this paper we test several of the most widely used assumptions on the uncertainty set using real-world traffic measurements provided by the City of Chicago. We calculate the resulting different robust solutions, and evaluate which uncertainty approach is actually reasonable for our data. This anchors theoretical research in a real-world application and gives an indicator which robust models should be the future focus of algorithmic development.

BibTeX - Entry

@InProceedings{dokka_et_al:OASIcs:2017:7903,
  author =	{Trivikram Dokka and Marc Goerigk},
  title =	{{An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems}},
  booktitle =	{17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)},
  pages =	{16:1--16:13},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{Gianlorenzo D'Angelo and Twan Dollevoet},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7903},
  URN =		{urn:nbn:de:0030-drops-79035},
  doi =		{10.4230/OASIcs.ATMOS.2017.16},
  annote =	{Keywords: robust shortest paths, uncertainty sets, real-world data, experimental study}
}

Keywords: robust shortest paths, uncertainty sets, real-world data, experimental study
Collection: 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)
Issue Date: 2017
Date of publication: 04.09.2017

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