Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements
From MaRDI portal
Publication:6203502
DOI10.1287/IJOC.2023.1275arXiv2109.08706OpenAlexW4321494565MaRDI QIDQ6203502FDOQ6203502
Authors: Devansh Jalota, Dario Paccagnan, Maximilian Schiffer, Marco Pavone 
Publication date: 28 February 2024
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Abstract: 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, e.g., 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 and show that the ratio between the total travel cost of the online solution of any deterministic algorithm and that of the optimal offline solution is unbounded, even in simple settings. 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 present numerical experiments based on an application case for the San Francisco Bay Area to evaluate the performance of our approach. Our results show that the data-driven algorithms we develop outperform commonly used greedy online-routing algorithms.
Full work available at URL: https://arxiv.org/abs/2109.08706
This page was built for publication: Online Routing Over Parallel Networks: Deterministic Limits and Data-driven Enhancements
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203502)
