Home > Research > Publications & Outputs > An Experimental Comparison of Uncertainty Sets ...

Electronic data

  • paper

    Accepted author manuscript, 539 KB, PDF document

    Available under license: CC BY

View graph of relations

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSNConference contribution/Paperpeer-review

Publication date1/09/2017
Host publicationProceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017)
EditorsGianlorenzo D'Angelo, Twan Dollevoet
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Number of pages13
ISBN (Print)9781510849679, 9783959770422
<mark>Original language</mark>English

Publication series

NameOpen Access Series in Informatics
PublisherSchloss Dagstuhl
ISSN (Print)2190-6807


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.