DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2017.16

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

Authors: Trivikram Dokka and Marc Goerigk

Published in: OASIcs, Volume 59, 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)

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.

Cite as

Trivikram Dokka and Marc Goerigk. An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Open Access Series in Informatics (OASIcs), Volume 59, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dokka_et_al:OASIcs.ATMOS.2017.16,
  author =	{Dokka, Trivikram and Goerigk, Marc},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-042-2},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{59},
  editor =	{D'Angelo, Gianlorenzo and Dollevoet, Twan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2017.16},
  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}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2016.4

Pricing Toll Roads under Uncertainty

Authors: Trivikram Dokka, Alain Zemkoho, Sonali Sen Gupta, and Fabrice Talla Nobibon

Published in: OASIcs, Volume 54, 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)

Abstract

We study the toll pricing problem when the non-toll costs on the network are not fixed and can vary over time. We assume that users who take their decisions, after the tolls are fixed, have full information of all costs before making their decision. Toll-setter, on the other hand, do not have any information of the future costs on the network. The only information toll-setter have is historical information (sample) of the network costs. In this work we study this problem on parallel networks and networks with few number of paths in single origin-destination setting. We formulate toll-setting problem in this setting as a distributionally robust optimization problem and propose a method to solve to it. We illustrate the usefulness of our approach by doing numerical experiments using a parallel network.

Cite as

Trivikram Dokka, Alain Zemkoho, Sonali Sen Gupta, and Fabrice Talla Nobibon. Pricing Toll Roads under Uncertainty. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dokka_et_al:OASIcs.ATMOS.2016.4,
  author =	{Dokka, Trivikram and Zemkoho, Alain and Gupta, Sonali Sen and Nobibon, Fabrice Talla},
  title =	{{Pricing Toll Roads under Uncertainty}},
  booktitle =	{16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)},
  pages =	{4:1--4:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-021-7},
  ISSN =	{2190-6807},
  year =	{2016},
  volume =	{54},
  editor =	{Goerigk, Marc and Werneck, Renato F.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2016.4},
  URN =		{urn:nbn:de:0030-drops-65289},
  doi =		{10.4230/OASIcs.ATMOS.2016.4},
  annote =	{Keywords: Conditional value at risk, robust optimization, toll pricing}
}

Search Results

Documents authored by Dokka, Trivikram

An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems

Abstract

Cite as

Pricing Toll Roads under Uncertainty

Abstract

Cite as

Thanks for your feedback!

Could not send message