Title: An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems,
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 lead 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 allows us to point
out which robust models should be the future focus of algorithmic development.