The Price of Anarchy for Transportation Networks with Mixed Autonomy*
The Price of Anarchy for Transportation Networks with Mixed Autonomy*
复制标题
DOI：
10.23919/acc.2018.8431087
复制
发表时间：
2017-10
期刊：
影响因子：
--
通讯作者：
Daniel A. Lazar;S. Coogan;Ramtin Pedarsani
中科院分区：
文献类型：
--
作者：
Daniel A. Lazar;S. Coogan;Ramtin Pedarsani
我们研究了具有混合自主性的交通网络中的路由行为，即每条道路上的一部分车辆都配备了自适应巡航控制等自主功能的网络，这些功能可以减少车头时距并增加道路容量。出于这种道路与混合自主开发的能力模型，我们认为交通网络中的每一条道路或链接的延迟是一个仿射函数的两个数量：车辆的数量与自主能力的链接和定期车辆的链接。我们特别研究了这种网络的无政府状态的价格，即自私路由所经历的社会最优路由策略的总延迟的比率。与所有车辆都是相同类型的情况下，无政府状态的价格是已知的有界的，我们首先表明，无政府状态的价格可以是任意大的混合自治网络。接下来，我们定义了一个不对称的概念，对应于由于自动驾驶汽车的存在而导致的最大可能的旅行时间改善。我们表明，当网络中的所有环节的不对称程度是有界的一个因素小于4，无政府状态的价格是有界的。我们还绑定的双准则，这是一个约束的自私路由流量的成本相比，最佳路由额外的流量的成本。这些界限取决于不对称的程度，并恢复经典的无政府状态和bicriteria的情况下，不存在不对称的价格界限。此外，我们的例子表明，这些界是紧在特定情况下。
We study routing behavior in transportation networks with mixed autonomy, that is, networks in which a fraction of the vehicles on each road are equipped with autonomous capabilities such as adaptive cruise control that enable reduced headways and increased road capacity. Motivated by capacity models developed for such roads with mixed autonomy, we consider transportation networks in which the delay on each road or link is an affine function of two quantities: the number of vehicles with autonomous capabilities on the link and the number of regular vehicles on the link. We particularly study the price of anarchy for such networks, that is, the ratio of the total delay experienced by selfish routing to the socially optimal routing policy. Unlike the case when all vehicles are of the same type, for which the price of anarchy is known to be bounded, we first show that the price of anarchy can be arbitrarily large for such mixed autonomous networks. Next, we define a notion of asymmetry corresponding to the maximum possible travel time improvement due to the presence of autonomous vehicles. We show that when the degree of asymmetry of all links in the network is bounded by a factor less than 4, the price of anarchy is bounded. We also bound the bicriteria, which is a bound on the cost of selfishly routing traffic compared to the cost of optimally routing additional traffic. These bounds depend on the degree of asymmetry and recover classical bounds on the price of anarchy and bicriteria in the case when no asymmetry exists. Further, we show with examples that these bound are tight in particular cases.