Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements
Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements
复制标题
并行网络上的在线路由：确定性限制和数据驱动的增强
DOI：
10.1287/ijoc.2023.1275
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
M. Pavone
中科院分区：
文献类型：
--
作者：
Devansh Jalota;Dario Paccagnan;Maximilian Schiffer;M. Pavone
在过去的十年中，支持GPS的交通应用程序，如谷歌地图和Waze已经变得无处不在，并对数十亿日常通勤者的出行模式产生了重大影响。这种应用的在线路线建议（例如，经由贪婪路由）的结果通常是交通拥堵的增加，因为所引起的行进模式可能远离系统最优。受交通应用对出行模式的广泛影响，本文研究了容量受限的并行道路网络中的在线交通路由，并从两个角度分析了这个问题。首先，我们进行了最坏情况下的分析，以确定性的在线路由的限制。虽然我们发现，确定性在线算法实现有限的，问题/实例依赖的竞争比在特殊情况下，我们表明，对于一般设置的竞争比是无界的。这一结果促使我们超越最坏情况分析。在这里，我们考虑利用过去的问题实例的知识的算法，并展示如何设计数据驱动的算法，其性能可以量化，并正式推广到看不见的未来实例。然后，我们提出了数值实验的基础上的应用程序的情况下，旧金山弗朗西斯科海湾地区的贪婪算法和两个前瞻性算法相比，访问额外的信息的时间和到达时间参数的用户的数据驱动算法的性能进行评估。我们的研究结果表明，开发的数据驱动算法优于常用的贪婪在线路由算法。此外，我们的工作揭示了数据可用性和可实现的解决方案质量之间的相互作用。历史：由Andrea Lodi接受，区域编辑设计和离散分析。资金来源：这项工作得到了国家科学基金会（NSF）奖1830554和德国研究基金会（DFG）的支持[Grant 449261765]。补充材料：电子伴侣可在https://doi.org/10.1287/ijoc.2023.1275上获得。
Over the past decade, GPS-enabled traffic applications such as Google Maps and Waze have become ubiquitous and have had a significant influence on billions of daily commuters’ travel patterns. A consequence of the online route suggestions of such applications, for example, via greedy routing, has often been an increase in traffic congestion since the induced travel patterns may be far from the system optimum. Spurred by the widespread impact of traffic applications on travel patterns, this work studies online traffic routing in the context of capacity-constrained parallel road networks and analyzes this problem from two perspectives. First, we perform a worst-case analysis to identify the limits of deterministic online routing. Although we find that deterministic online algorithms achieve finite, problem/instance-dependent competitive ratios in special cases, we show that for a general setting the competitive ratio is unbounded. This result motivates us to move beyond worst-case analysis. Here, we consider algorithms that exploit knowledge of past problem instances and show how to design data-driven algorithms whose performance can be quantified and formally generalized to unseen future instances. We then present numerical experiments based on an application case for the San Francisco Bay Area to evaluate the performance of the proposed data-driven algorithms compared with the greedy algorithm and two look-ahead heuristics with access to additional information on the values of time and arrival time parameters of users. Our results show that the developed data-driven algorithms outperform commonly used greedy online-routing algorithms. Furthermore, our work sheds light on the interplay between data availability and achievable solution quality. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Funding: This work was supported by National Science Foundation (NSF) Award 1830554 and by the German Research Foundation (DFG) under [Grant 449261765]. Supplemental Material: The e-companion is available at https://doi.org/10.1287/ijoc.2023.1275 .
超越最坏情况分析
影响因子：
22.7
作者：
Roughgarden, Tim
通讯作者：
Roughgarden, Tim