Robust and resilient equilibrium routing mechanism for traffic congestion mitigation built upon correlated equilibrium and distributed optimization
Robust and resilient equilibrium routing mechanism for traffic congestion mitigation built upon correlated equilibrium and distributed optimization
复制标题
DOI：
10.1016/j.trb.2022.12.006
复制
发表时间：
2023-02
期刊：
影响因子：
--
通讯作者：
Yuqi Ning;Lili Du
中科院分区：
文献类型：
--
作者：
Yuqi Ning;Lili Du
随着无线通信、移动计算和GPS技术的快速发展，如今驾驶员的路线决策更多地依赖于导航服务，例如Google或Waze。然而，这些导航服务并不总是伴随着交通状况的改善。个别司机经常做出独立且自私的路线决策，这些决策在系统上并不有利，因此常常导致严重的拥堵。本研究旨在通过利用个人与中央计划者（CP）之间的信息差距来缓解此类问题。具体来说，我们为CP开发了一种相关均衡路由机制（CeRM），它驱动一组车辆的路线选择达到系统最优交通条件的平衡，同时仍然满足个体的自私本性。参与的驾驶员遵循建议的路线指南只会比根据实时交通信息的最佳响应进行导航更好。 CeRM 被建模为涉及大量用户的非凸非线性程序。开发了分布式增强拉格朗日算法（D-AL）来有效地解决CeRM问题，以提供在线实时导航服务，利用单个车辆的车载计算资源。考虑到 D-AL 依赖于车辆和 CP 之间的无线通信，我们证明了 D-AL 针对随机通信故障的收敛鲁棒性，并导出了收敛速度上限作为通信故障概率的函数。值得注意的是，随着通信失败概率的增加，D-AL 的收敛速度急剧下降，这阻碍了 CeRM 在实践中实施的适用性。为了提高求解算法在计算性能上的弹性，我们进一步设计并证明了一种辅助D-AL的加速方案（aD-AL），以在高可能性通信失败的情况下加快收敛速度。在苏福尔斯城市网络上进行的数值实验证实了 D-AL 的收敛特性、针对随机通信故障的鲁棒性以及 aD-AL 解决 CeRM 问题的弹性。实验还表明，与现有的独立路由（IR）机制和面向用户的均衡路由（uoER）机制相比，CeRM具有更好的系统性能（具有更低的系统成本）。
With the rapid development of wireless communication, mobile computing, and GPS technologies, drivers’ route decisions nowadays rely more on navigation services, such as Google or Waze. However, these navigation services don't always come with improved traffic conditions. Individual drivers often make independent and selfish route decisions that are not systematically favorable and thus often result in severe congestions. This study aims to alleviate such problems by exploiting the information gaps between individuals and the central planner (CP). Specifically, we develop a correlated equilibrium routing mechanism (CeRM) for the CP, which drives a group of vehicles’ route choices to an equilibrium with a systematically optimal traffic condition while still satisfying individuals’ selfish nature. Participating drivers would only be better off by following the suggested routing guidance than navigating on their best responses to real-time traffic information. The CeRM is modeled as a nonconvex and nonlinear program involving a large-scale of users. A distributed Augmented Lagrangian algorithm (D-AL) is developed to efficiently solve the CeRM to provide online real-time navigation service, taking advantage of the on-board computation resources of individual vehicles. Considering the D-AL relies on the wireless communications between vehicles and the CP, we proved the convergence robustness of the D-AL against random communication failures and derived the convergence rate upper bound as a function of the communication failure probability. It is noticed that the convergence rate of the D-AL degrades dramatically as the communication failure probability increases, which hampers the applicability of implementing the CeRM in practice. To improve the solution algorithm's resilience in the computation performance, we further designed and proved an acceleration scheme aided D-AL (aD-AL) to expedite the convergence rate under the high likelihood of communication failures. Numerical experiments conducted on the Sioux Falls city network confirmed the D-AL's convergence properties, robustness against random communication failures, and the resilience of the aD-AL to solve the CeRM. The experiments also show that the CeRM results in better system performance (have less system cost) compared with the existing Independent Routing (IR) mechanism and user-oriented Equilibrium Routing (uoER) mechanism.