城市交通网络中社会成本的优化上界

毛太田，黄 格，李 勇,2

(1. 湘潭大学 公共管理学院，湖南 湘潭 411105；2. 长沙学院 工商管理系，湖南 长沙 410022)



城市交通网络中社会成本的优化上界

毛太田1，黄 格1，李 勇1,2

(1. 湘潭大学 公共管理学院，湖南 湘潭 411105；2. 长沙学院 工商管理系，湖南 长沙 410022)

在固定需求的交通网络中，均衡状态下的网络流量可能不是社会最优的，为了进一步明确用户均衡与系统最优之间的关系，通过引入一个与均衡流量社会成本相关的量值，得到城市交通网络社会成本优化上界的计算公式。结果表明：均衡交通网络流量模式的社会成本最高为社会最优流量模式的两倍，也就是说通过有效的控制策略最多可以节约网络社会成本的一半。

交通工程；城市交通网络；博弈；流量均衡；社会最优

20世纪80年代以来，我国城市普遍进入了快速发展期。在城市化与机动化的快速推进期，伴随着车辆饱有量的不断增加，交通问题逐渐成为众多城市尤其是大城市的“心腹之患”，交通拥塞等城市病日益严重，成为城市可持续发展的重要瓶颈之一。很多学者从交通经济学[1]、社会学[2]、建筑学[3]等不同的角度对交通拥塞问题进行了分析。从复杂网络的角度来看，在给定的交通网络中，网络的结构和网络节点的容量是相对固定的，可变化的值为网络的交通流量，决定交通流量最重要的因素是出行者的数量与分布[4]，当一个交通网络系统正常运行的时候，根据初行者的需求形成一个网络流量模式，若每个出行者都拥有理性决策行为，那么网络流量将出现一种均衡，这种均衡是基于出行者个人行为做出的最优选择，往往这种均衡并不是系统的最优成本值[5]。笔者将运用网络博弈论模型来分析网络流量均衡与网络社会成本最优值之间的关系，为城市解决交通拥堵提供可借鉴和参考的依据。

1 交通网络流量的博弈论模型描述

在实际的交通网络中，有向图是一种常用的描述方式，图1为一个典型的交通网络。其中边表示道路，节点表示路口。

图1 一个典型的交通网络Fig.1 A typical traffic network

1.1 均衡状态流量模式

利用博弈论的思想来构建网络流量模型：假设每个司机都要从v1开到vn，每一辆车都有多种可行的路线。这个过程相当于一场博弈，参与者是司机，每个参与者可能的策略是由v1到vn的可能路线，每个参与者得到的回报就是司机行程时间的负数。很容易发现，在这个流量博弈中，一般是没有占优策略的[6]。每条路线都可能是参与者的最佳选择，前提是其他参与者选择另一条路线。

博弈论中的最佳应对即参与人的最佳选择，而最佳应对过程就是参与人不断动态调整其选择策略以求能实现最佳应对的过程，交通流量网络中参与者的最佳应对过程就是司机为了减少行驶时间而不断动态调整路线以求能最佳应对当前的情况的过程[7]。定义一个流量模式为每个司机所作出的路线选择，如果每个司机都对现状作出了最佳选择，这个过程终止，就形成了一种均衡状态的网络流量模式。

1.2 社会最优流量模式

现实情况下，交通网络的社会成本不仅包括所有司机的行驶时间，还包括汽油的成本、车辆和路面的损耗等。而在交通拥塞，尤其是上下班高峰期时，相对于其他因素，行驶时间是影响司机选择的主要因素，加快疏通网络，缩短拥堵时间是降低整个交通网络社会成本的关键。基于Roughgarden和Tardos等人的研究工作，所有司机的行驶时间和整个网络的社会成本之间呈正比例线性关系。因此，为方便模型描述，定义一个流量模式的社会成本(Social Cost，以SC表示)是所有司机使用该流量模式产生的行程时间的和xTe(x)[8]，如果该流量模式实现了最小社会成本，就称该模式为社会最优流量模式。

2 交通网络社会成本的优化上界

均衡状态下的网络流量可能不是社会最优的，需要定量地比较均衡状态下的流量与最理想的流量。相对而言，社会最优流量模式下的社会成本比较容易描述，即总行程时间xTe(x)，均衡状态下的社会成本则不能简单通过当前流量模式产生的社会成本来描述，因为一些最佳应对更新可以使社会成本变低(如出行者离开拥挤的道路更换到一条相对空闲的路段)，但另一些更新也可以使成本变高(如布雷斯悖论情况[9])，这就导致流量模式中的社会成本随着最佳应对过程的进展而在上升或下降之间浮动，并且它与向均衡状态发展的过程的之间的关系不明显。因此，为了跟踪最佳应对过程，引入潜能(Potential Energy，以PE表示)的概念[10]，假设某一边e上有x量车在行驶，那么这条边的潜能为：

PE(e)=Te(1)+Te(2)+…+Te(x)

(1)

一条边的潜能并不是所有车辆穿过此边的总行驶时间，而是一种累积的量值。定义一种流量模式的潜能为基于当前在其中行驶的车辆数，所有边的潜能总和。

跟踪潜能的变化很简单，因为流量模式的变化过程也就是一个司机放弃当前的路线，更换到一条新路线的过程[11]。如果把这个过程分成两步：首先，司机放弃当前路线，暂时离开该系统；然后司机回到系统中选择一条新的路线，通过观察这个转换过程就可以知道潜能的变化。

具体地，有x个司机的边e的潜能是：

PE(e)=Te(1)+Te(2)+…+Te(x-1)+Te(x)

(2)

当一个司机离开时，部分潜能被释放，潜能变化为：

PE′(e)=Te(1)+Te(2)+…+Te(x-1)

(3)

因此，边e的潜能变化为Te(x)，即司机在该边上的行驶时间。综合该司机在所有边上的行驶时间，可以看到一个司机放弃当前路线所释放的潜能恰巧是该司机当前的行驶时间。同样，当一个司机选择一条新的路线，所加入的每一边e的潜能从PE(e)增加到：

PE″(e)=Te(1)+Te(2)+…+Te(x+1)

(4)

当一个司机改变路线，潜能的净变化是该司机新的行驶时间减去原来的行驶时间。但是在最佳应对过程中，只有当司机的行驶时间会减少的情况下，他才会改变路线。所以每一次最佳应对更新都产生一个负值的潜能变化。因此，系统中的潜能随着最佳应对过程的进行而减少，最终停止，形成一个均衡状态的流量模式。

2.1 一条边上潜能与行驶时间的关系

基于前面的论述，当一条边上有x辆车行驶时，潜能为：

PE(e)=Te(1)+Te(2)+…+Te(x)

(5)

另外，x辆车中每辆车的行驶时间为Te(x)，则每条边上所有车辆的总行驶时间(以T(e)表示)为：

(6)

由于潜能和总行驶时间都是x项，但行驶时间中的每一项至少应该和潜能中的每一项一样大。因此：

PE(e)≤T(e)

(7)

图2展示了当Te是一个线性函数时，潜能和总行驶时间之间的对比关系：总行驶时间为水平线以下的阴影部分的面积，Y值为Te(x)，而潜能则是高度分别为Te(1)，Te(2)，…，Te(x)，宽度为一个标准单位的所有长方形的面积。

图2 潜能和总行驶时间关系的几何图示Fig.2 Geometric illustration of relationship between potential energy and total traveling time

图2供了一个几何图示，由于Te(x)=αex+βe(αe,βe≥0)，可以得到：

(8)

以潜能和总行驶时间的形式来表述，得到：

(9)

2.2 均衡状态行驶时间与社会最优行驶时间关系

当所有司机都遵循社会最优流量模式A时，所有边的总潜能为PE(A)，该流量模式中的社会成本记为SC(A)，也就是所有司机行驶时间的总和∑T(e)。

根据前面的论述，潜能随着最佳应对过程而减少，因此，均衡状态流量模式的总潜能：

PE(A′)≤PE(A)

(10)

其次，根据潜能和社会成本之间的数量关系：

SC(A′)≤2PE(A′)

(11)

并且，PE(A)≤SC(A)

(12)

因此：

(13)

这就证明了最佳应对过程中潜能逐步减少，这种减少致使社会成本的增加限定在两倍之内。因此，交通网络社会成本的优化上界是社会最优流量模式社会成本的两倍。

3 案例分析

建立一个交通运输网络如图3。图3中，边表示道路，节点表示路口，每个司机都要从V1开到V4[7]。假设V1-V3和V2-V4边并不受交通状况影响，无论有多少辆车行驶都需要4个单位的时间穿越。相比之下，V1-V2和V3-V4边受拥堵的影响较大，其行驶时间Te(x)=αex+βe，是为了使模型更简单化，设置该两条路线的行驶时间为x，V2-V3的行驶时间为0，尽管由此产生的效果有别于实际情况(但影响应该很小)。

图3 案例网络Fig.3 Network of the case

假设有4个司机，每个司机的起节点为V1，讫节点为V4，图4展示了基于图3两种不同的流量模式。第一个流量模式如图4(a)，该模式达到了最小社会成本，即每个司机需要8个单位时间到达目的地，因此社会成本为SC(A)=4×(2+4)=24，是社会最优流量模式。第二个流量模式图4(b)是唯一的纳什均衡，它的社会成本较高，SC(A′)=4×(4+4)=32。

图4 两种网络流量模式Fig.4 Network traffic of two different modes

根据前面的假设，建立博弈矩阵如表1，通过3×3表格的行代表一部分出行者3种路线选择，V1-V2-V4，V1-V3-V4以及V1-V2-V3-V4，也同样通过3×3表格的列代表另外一部分出行者的3种路线选择，出行者的回报是所消耗的行驶时间的负值。

表1 该流量模式中出行者之间的博弈

由该博弈矩阵发现，其中并没有占优策略，V1-V2-V3-V4是该博弈中唯一的纳什均衡，选择这条路线是每个司机最佳应对。利用潜能跟踪从图4(a)模式转变到图4(b)模式的最佳应对过程，由PE(e)=Te(1)+Te(2)+…+Te(x)计算得出了网络从社会最优向均衡交通进展时的潜能变化，图5展示了最佳应多过程经历的5个流量模式，并列出了每条边的潜能。

图5 最佳应对过程的追踪Fig.5 Track of best-response dynamics progress

图5中，(a)流量模式社会成本最小，是社会最优流量模式，其社会成本SC(a)=24，潜能PE(a)=22，从(b)开始，每一步变更一个司机的路线到V1-V2-V3-V4；(b)模式的社会成本SC(b)=25，潜能PE(b)=21；(c)模式的社会成本SC(c)=28，潜能PE(c)=21；(d)模式的社会成本SC(d)=29，潜能PE(d)=20；(e)模式的潜能最小，是均衡状态流量模式，其社会成本SC(e)=32，潜能PE(e)=20。

容易发现，尽管在5个流量模式中社会成本在增加(从24增加到32)，潜能却在不断减少(从22到20)。图6进一步细分了司机更换路线的过程，分为两个步骤：第一步，司机放弃当前路线，暂时离开系统，表现为从图6(a)向图6(b)转变，放弃之前的路线释放了2+4=6个单位的潜能；第二步，司机重新回到系统选择一条新路线，也就是图6(b)向图6(c)的变化，司机选择之字形路线后，只有2+0+3=5个潜能回到系统中，因此潜能减少了1个单位。

图6 潜能的释放与增加Fig.6 Release and increase of potential energy

当一个司机为了其他路线而放弃当前路线时，潜能的改变就是司机行驶时间的改善。因此，系统增加的潜能等同于该司机当前的行驶时间。

再分析一条边的潜能与行驶时间的关系。因为该模型中只有V1-V2和V3-V4边受拥堵的影响，其行驶时间Te(x)=αex+βe=x，所以以V1-V2边为例。该边的潜能为：

PE(e)=1+2=3

(14)

行驶时间为：

T(e)=2×2=4

(15)

因此：

(16)

一个流量模式中的社会成本就是所有司机行驶时间的总和，因此，均衡状态下的社会成本和社会最优流量模式下的社会成本之间的关系也就是总潜能和总行驶时间的关系。在本案例中表现为图4(a)社会最优流量模式和图4(b)均衡状态中总行驶时间和总潜能的对比。以SC(a)表示(a)流量模式下的社会成本，以PE(a)表示(a)流量模式下的潜能，根据式17易算得：

(17)

以SC(b)表示(b)流量模式下的社会成本，以PE(b)表示(b)流量模式下的潜能，由于潜能随着如图6所示的最佳应对过程逐步减少，(a)流量模式的总潜能PE(a)=22，(b)模式的总潜能PE(b)=20，因此：

PE(b)

(18)

其次，(b)模式的社会成本SC(b)=32，潜能PE(b)=20，得：SC(b)<2PE(b)=40

(19)

将这些不等式联系起来，得到：

(20)

最佳应对过程中潜能逐步减少，这种减少致使社会成本的增加限定在两倍之内。

4 结 语

笔者运用博弈论的方法对交通网络中出行者的行为和网络流量进行分析，通过计算发现均衡交通网络流量模式的社会成本最高为社会最优流量模式的两倍，该值为交通网络社会成本的可优化上界，也就是说通过有效的控制策略最多可以节约网络社会成本的一半。

[1] 韩小亮,邓祖新.城市交通拥堵的经济学分析——基于计算经济学的模拟检验[J].财经研究,2006,32(5):19-31. Han Xiaoliang,Deng Zuxin.The economic analysis of traffic congestions——an agent-based computational economics approach[J].Journal of Finance and Economics,2006,32(5):19-31.

[2] 王煜.交通拥堵现象背后的社会问题[J].城市问题,2004(2):76-78. Wang Yu.Social problems behind the traffic jam phenomenon[J].Urban Problems,2004(2):76-78.

[3] 李迅,张国华,黄坤鹏.中国城市交通发展的绿色之路[J].城市规划学刊,2008(6):51-56. Li Xun,Zhang Guohua,Huang Kunpeng,The green way to the development of Chinese urban transportation[J].Urban Planning Forum,2008(6):51-56.

[4] Roughgarden T,Tardos é.How bad is selfish routing? [J].Journal of the ACM,2002,49(2):236-259.

[5] Anshelevich E,Dasgupta A,Kleinberg J,et al.The price of stability for network design with fair cost allocation[J].SIAM Journal on Computing,2008,38(4):1602-1623.

[6] Easley D,Kleinberg J.Networks,Crowds and Markets[M].Cambridge:Cambridge University Press,2010:229-230.

[7] 余孝军.一类混合路由博弈的调和率研究[J].应用数学和力学,2013,34(4):420-426. Yu Xiaojun.On coordination ratio of a mixed routing game[J].Applied Mathematics and Mechanics,2013,34(4):420-426.

[8] Roughgarden T.Selfish Routing and the Price of Anarchy[M].MIT press,2005:16-17.

[9] Braess D.Uber ein Paradoxon aus der Verkehrsplanung[J].Unternehmensforschung,1968,12(1):258-268.

[10] Monderer D,Shapley L S.Potential games[J].Games and economic behavior,1996,14(1):124-143.

[11] 徐寅峰,余海燕,苏兵,等.基于时间和路径偏好的交通流分配模型与诱导策略[J].系统工程理论与实践,2012,32(10):2306-2314. Xu Yinfeng,Yu Haiyan,Su Bing,et al.Traffic flow distribution models based on time and path preference and inducement strategy[J].Systems Engineering Theory & Practice,2012,32(10):2306-2314.

Upper Bound of Social Cost Optimization in Urban Traffic Networks

Mao Taitian1, Huang Ge1, Li Yong1,2

(1. School of Public Management, Xiangtan University, Xiangtan 411105, Hunan, China; 2. Department of Business Management, Changsha University, Changsha 410022, Hunan, China)

Existing research shows that network traffic at equilibrium may not be socially optimal in traffic networks with fixed demands. In order to further clarify the relationship between user equilibrium and system optimum flow patterns, new formula for computing the upper bound of social cost optimization in urban traffic networks was derived through introducing an alternate quantity associated with the user social cost of equilibrium flow pattern. The results show that the social cost of the equilibrium is twice the cost of the social optimum at most; hence the social cost of the network can be halved through an effective control strategy at most.

traffic engineering; urban traffic networks; game; traffic at equilibrium; social optimum

10.3969/j.issn.1674-0696.2015.02.26

2014-04-10；

2014-06-29

国家自然科学基金项目(71101013)；湖南省教育厅优秀青年项目(11B013)

毛太田(1971—)，男，湖南永州人，副教授，博士，主要从事信息资源管理方面的研究。E-mail: maotaitian@xtu.edu.cn。

U491

A

1674-0696(2015)02-124-04