Real-time Approximate Routing for Smart Transit Systems
Real-time Approximate Routing for Smart Transit Systems
复制标题
智能交通系统的实时近似路线
DOI：
10.1145/3460091
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Banerjee, Siddhartha
中科院分区：
文献类型：
--
作者：
Périvier, Noémie;Hssaine, Chamsi;Samaranayake, Samitha;Banerjee, Siddhartha
我们研究智能交通系统中的实时路由策略，其中平台具有汽车和高容量车辆的组合（例如，公共汽车或班车），并试图服务一组传入的行程请求。该平台可以利用其汽车车队作为支线，将乘客连接到其在固定路线上运营的高容量车队。我们的目标是在给定的时间窗口内找到最优的（公交）路线和相应的频率，以最大限度地提高系统的社会福利。这概括了线路规划问题，这是交通文献中广泛研究的主题，现有的解决方案要么是启发式的（没有性能保证），要么需要大量的计算时间（因此对于实时使用是不切实际的）。为此，我们开发了一个1-1/e-ε近似算法的实时线路规划问题，从随机舍入和广义分配问题的想法。我们的保证在两个假设下成立：（i）没有公交车间的换乘，以及（ii）可以使用预先指定的一组可行的公交线路。此外，我们证明，这两个假设是至关重要的，如果任何一个假设是放松的，campineplanningproblem不承认任何常数因子近似。最后，我们通过在真实世界和合成数据集上的数值实验证明了我们算法的实用性，在实验中，我们表明，在给定的固定时间预算下，我们的算法优于基于线性规划的精确方法。
We study real-time routing policies in smart transit systems, where the platform has a combination of cars and high-capacity vehicles (e.g., buses or shuttles) and seeks to serve a set of incoming trip requests. The platform can use its fleet of cars as a feeder to connect passengers to its high-capacity fleet, which operates on fixed routes. Our goal is to find the optimal set of (bus) routes and corresponding frequencies to maximize the social welfare of the system in a given time window. This generalizes the Line Planning Problem, a widely studied topic in the transportation literature, for which existing solutions are either heuristic (with no performance guarantees), or require extensive computation time (and hence are impractical for real-time use). To this end, we develop a 1-1/e-ε approximation algorithm for the Real-Time Line Planning Problem, using ideas from randomized rounding and the Generalized Assignment Problem. Our guarantee holds under two assumptions: (i) no inter-bus transfers and (ii) access to a pre-specified set of feasible bus lines. We moreover show that these two assumptions are crucial by proving that, if either assumption is relaxed, the łineplanningproblem does not admit any constant-factor approximation. Finally, we demonstrate the practicality of our algorithm via numerical experiments on real-world and synthetic datasets, in which we show that, given a fixed time budget, our algorithm outperforms Integer Linear Programming-based exact methods.
登录
查看更多内容
DOI：
10.1145/3055399.3055412
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pasin Manurangsi
通讯作者：
Pasin Manurangsi
DOI：
10.1145/3219617.3219619
发表时间：
2018-03
期刊：
Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems
影响因子：
--
作者：
Siddhartha Banerjee;Yashodhan Kanoria;Pengyu Qian
通讯作者：
Siddhartha Banerjee;Yashodhan Kanoria;Pengyu Qian
DOI：
--
发表时间：
2019
期刊：
影响因子：
--
作者：
L. Fleischer;M. Goemans;V. Mirrokni;M. Sviridenko
通讯作者：
M. Sviridenko
关于在不相关机器上进行调度的配置-LP
影响因子：
2
作者：
José Verschae;Andreas Wiese
通讯作者：
Andreas Wiese
城市快速交通网络设计：加速本德斯分解
影响因子：
4.8
作者：
Á. Marín;Patricia Jaramillo
通讯作者：
Patricia Jaramillo