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

Published

Standard

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. / Dokka Venkata Satyanaraya, Trivikram; Goerigk, Marc.

Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017). ed. / Gianlorenzo D'Angelo; Twan Dollevoet. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. p. 16:1-16:13 16 (Open Access Series in Informatics ; Vol. 59).

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

Harvard

Dokka Venkata Satyanaraya, T & Goerigk, M 2017, An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. in G D'Angelo & T Dollevoet (eds), Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017)., 16, Open Access Series in Informatics , vol. 59, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, pp. 16:1-16:13.

APA

Dokka Venkata Satyanaraya, T., & Goerigk, M. (2017). An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. In G. D'Angelo, & T. Dollevoet (Eds.), Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017) (pp. 16:1-16:13). [16] (Open Access Series in Informatics ; Vol. 59). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.

Vancouver

Dokka Venkata Satyanaraya T, Goerigk M. An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. In D'Angelo G, Dollevoet T, editors, Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. 2017. p. 16:1-16:13. 16. (Open Access Series in Informatics ).

Author

Dokka Venkata Satyanaraya, Trivikram ; Goerigk, Marc. / An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017). editor / Gianlorenzo D'Angelo ; Twan Dollevoet. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. pp. 16:1-16:13 (Open Access Series in Informatics ).

Bibtex

@inproceedings{da3bdab697b744a9a343079b8d46a0bc,
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, theexact travel times along each arc in the network may not be known. This led to the developmentof robust shortest path problems, where all possible arc travel times are contained in a so-calleduncertainty set of possible outcomes.Research in robust shortest path problems typically assumes this set to be given, and providescomplexity results as well as algorithms depending on its shape. However, what can actually beobserved in real-world problems are only discrete raw data points. The shape of the uncertainty isalready a modelling assumption. In this paper we test several of the most widely used assumptionson 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 isactually reasonable for our data. This anchors theoretical research in a real-world application andgives an indicator which robust models should be the future focus of algorithmic development.",
keywords = "robust shortest paths, uncertainty sets, real-world data, experimental study",
author = "{Dokka Venkata Satyanaraya}, Trivikram and Marc Goerigk",
year = "2017",
month = sep,
day = "1",
language = "English",
isbn = "9781510849679",
series = "Open Access Series in Informatics ",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
pages = "16:1--16:13",
editor = "Gianlorenzo D'Angelo and Twan Dollevoet",
booktitle = "Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017)",

}

RIS

TY - GEN

T1 - An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

AU - Dokka Venkata Satyanaraya, Trivikram

AU - Goerigk, Marc

PY - 2017/9/1

Y1 - 2017/9/1

N2 - 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, theexact travel times along each arc in the network may not be known. This led to the developmentof robust shortest path problems, where all possible arc travel times are contained in a so-calleduncertainty set of possible outcomes.Research in robust shortest path problems typically assumes this set to be given, and providescomplexity results as well as algorithms depending on its shape. However, what can actually beobserved in real-world problems are only discrete raw data points. The shape of the uncertainty isalready a modelling assumption. In this paper we test several of the most widely used assumptionson 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 isactually reasonable for our data. This anchors theoretical research in a real-world application andgives an indicator which robust models should be the future focus of algorithmic development.

AB - 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, theexact travel times along each arc in the network may not be known. This led to the developmentof robust shortest path problems, where all possible arc travel times are contained in a so-calleduncertainty set of possible outcomes.Research in robust shortest path problems typically assumes this set to be given, and providescomplexity results as well as algorithms depending on its shape. However, what can actually beobserved in real-world problems are only discrete raw data points. The shape of the uncertainty isalready a modelling assumption. In this paper we test several of the most widely used assumptionson 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 isactually reasonable for our data. This anchors theoretical research in a real-world application andgives an indicator which robust models should be the future focus of algorithmic development.

KW - robust shortest paths

KW - uncertainty sets

KW - real-world data

KW - experimental study

M3 - Conference contribution/Paper

SN - 9781510849679

SN - 9783959770422

T3 - Open Access Series in Informatics

SP - 16:1-16:13

BT - Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS2017)

A2 - D'Angelo, Gianlorenzo

A2 - Dollevoet, Twan

PB - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

ER -