An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems
An Experimental Comparison of Uncertainty Sets for Robust Shortest Path Problems
复制标题
鲁棒最短路径问题的不确定性集的实验比较
DOI：
10.4230/oasics.atmos.2017.16
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
M. Goerigk
中科院分区：
文献类型：
--
作者：
Trivikram Dokka;M. Goerigk
通过开发有效的算法，数据结构和预处理技术，街道网络中最短的路径问题现在非常快速地解决。但实际上，网络中每个弧线的确切旅行时间可能尚不清楚。这导致了最短路径问题的发展，其中所有可能的弧旅行时间都包含在所谓的不确定性结果集中。
在鲁棒的最短路径问题中进行的研究通常假定要给出此设置，并根据其形状提供复杂性结果以及算法。但是，在现实世界中实际上可以观察到的只是离散的原始数据点。不确定性的形状已经是一个建模假设。在本文中，我们使用芝加哥市提供的现实世界交通测量值测试了一些最广泛使用的假设。我们计算产生的不同鲁棒解决方案，并评估哪种不确定性方法实际上对于我们的数据是合理的。这将理论研究锚定在现实世界的应用中，并使我们可以指出哪种健壮模型应该是算法开发的未来重点。
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.
DOI：
10.1007/978-3-319-49487-6_2
发表时间：
2016-01-01
期刊：
ALGORITHM ENGINEERING: SELECTED RESULTS AND SURVEYS
影响因子：
--
作者：
Bast, Hannah;Delling, Daniel;Werneck, Renato F.
通讯作者：
Werneck, Renato F.