Balancing fairness and efficiency in traffic routing via interpolated traffic assignment
Balancing fairness and efficiency in traffic routing via interpolated traffic assignment
复制标题
DOI：
10.1007/s10458-023-09616-7
复制
发表时间：
2021-03
影响因子：
1.9
通讯作者：
Devansh Jalota;Kiril Solovey;Stephen Zoepf;M. Pavone
中科院分区：
文献类型：
--
作者：
Devansh Jalota;Kiril Solovey;Stephen Zoepf;M. Pavone
系统最优（SO）路由，其中所有用户的总旅行时间是最小的，是交通当局的圣杯。然而，SO路由可能会歧视那些为实现高系统效率（即低总旅行时间）而花费更大旅行时间的用户。为了解决SO路由固有的不公平问题，我们研究了公平SO问题，其目标是在保证不公平程度的同时最小化总行程时间，即指定具有共享起点和目的地的不同用户的行程时间之间的最大可能比。为了获得公平SO问题的可行解，同时获得较高的系统效率，我们开发了一个新的凸规划，即插值交通分配问题（I-TAP），它在促进公平和促进效率的交通分配目标之间插值。我们通过对系统总行程时间和不公平程度的插值参数的理论界限来评估I-TAP的有效性，并在一系列交通网络上对I-TAP和最先进的算法进行了数值比较。数值结果表明，与基准算法相比，我们的方法速度快了几个数量级，同时在所有理想的不公平水平上实现了更高的系统效率。我们进一步利用I-TAP的结构，开发了两种定价机制，分别在自私的同质用户和异质用户面前共同执行I-TAP解决方案，这些用户独立选择路线以最小化自己的旅行成本。我们提到，这是第一次在一般道路网络公平路由的背景下进行定价研究（与平行道路网络相反）。
System optimum (SO) routing, wherein the total travel time of all users is minimized, is a holy grail for transportation authorities. However, SO routing may discriminate against users who incur much larger travel times than others to achieve high system efficiency, i.e., low total travel times. To address the inherent unfairness of SO routing, we study the-fair SO problem whose goal is to minimize the total travel time while guaranteeing alevel of unfairness, which specifies the maximum possible ratio between the travel times of different users with shared origins and destinations. To obtain feasible solutions to the-fair SO problem while achieving high system efficiency, we develop a new convex program, the interpolated traffic assignment problem (I-TAP), which interpolates between a fairness-promoting and an efficiency-promoting traffic-assignment objective. We evaluate the efficacy of I-TAP through theoretical bounds on the total system travel time and level of unfairness in terms of its interpolation parameter, as well as present a numerical comparison between I-TAP and a state-of-the-art algorithm on a range of transportation networks. The numerical results indicate that our approach is faster by several orders of magnitude as compared to the benchmark algorithm, while achieving higher system efficiency for all desirable levels of unfairness. We further leverage the structure of I-TAP to develop two pricing mechanisms to collectively enforce the I-TAP solution in the presence of selfish homogeneous and heterogeneous users, respectively, that independently choose routes to minimize their own travel costs. We mention that this is the first study of pricing in the context of fair routing for general road networks (as opposed to, e.g., parallel road networks).