基于蚁群算法的多维Stackelberg博弈配流研究

（西南交通大学交通运输与物流学院，610031，成都∥第一作者，硕士研究生）

基于蚁群算法的多维Stackelberg博弈配流研究

艾 毅 李宗平

（西南交通大学交通运输与物流学院，610031，成都∥第一作者，硕士研究生）

根据Stackelberg博弈对道路公交系统与城市轨道交通进行交通流分配，并建立Nash均衡。假设路网上有多个OD（起止点）对，通过Wardrop均衡准则证明每个OD间出行的用户是同质的。据此假设建立道路公交路径与城市轨道交通路径的j维混合策略Stackelberg-Nash均衡博弈模型。采用改进的蚁群算法对出行用户的均衡过程进行模拟。结果表明，改进的蚁群算法合理地仿真了Stackelberg博弈的均衡过程。

道路公交；城市轨道交通；交通流分配；Stackelberg博弈；改进蚁群算法

First-author's address Transportation and Logistics Institute，Southwest Jiaotong University，610031，Chengdu，China

随着城市轨道交通的出现，人们的出行方式由当初单一的道路公交系统逐渐转变为道路公交系统与城市轨道交通并存的方式。因此，交通流在这两种出行策略中的协调分配问题是合理规划路网的重要工作。在以往的研究结果中，交通流分配基本集中在单一层面上，对其在不同交通方式之间和在路网不同路径中的辩证和博弈关系并没有进行探讨。本文将探讨不同出行用户在选择路径和选择出行方式上的博弈思路，即j维OD（起止点）对之间的博弈均衡。

1 博弈论方法

1.1 路网博弈分析

博弈论模型的主要思想是建立在一个假想的博弈游戏上，包括局中人、策略空间和得益等方面［1］。可以将道路公交与城市轨道交通之间的博弈看作是路网中j个OD间出行的用户之间的非合作博弈，他们通过对交通资源的效益判断得出自己的最优线路，这样就形成了j维出行用户之间的博弈。他们的支付函数就是综合支付函数。因此，可将出行用户相互之间的关系转化为j维混合策略Nash均衡博弈。利用Stackelberg-Nash均衡来建立出行用户关于道路公交系统路径和城市轨道交通路径的j维博弈模型［2］。

1.2 Wardrop均衡与混合策略Nash均衡

通过博弈分析，构建Wardrop均衡和混合策略Nash均衡的关系。根据文献［3］提出的方法，在第j个OD间，由于相同OD间出行用户是同质的，因此，当路网达到用户均衡时，某OD间出行的用户选择总走行时间最短的策略集合。即Wardrop第一均衡准则。其数学表达为：

式中：

Djk---第j个OD间出行的用户采取第k种乘车策略所包含城市轨道交通路径的集合；

Gjk---第j个OD间出行的用户采取第k种乘车策略所包含道路公交路径的集合；

Zjk（Djk，Gjk，tjk）---在混合策略下的综合支付函数。

当Zjk（Djk，Gjk，tjk）＞min Zjk（Djk，Gjk，tjk）时，说明该混合策略不是最优，出行用户不会选择该策略下的路径集合，即Djk+Gjk=0。同理，当出行用户选择该混合策略时，说明该混合策略等价于最优策略。

使用博弈论的方法考虑交通策略问题，第j个OD间出行的用户面临着不同路径选择的混合策略Nash均衡博弈。第j个OD间出行的用户的混合策略Sjk为道路公交与城市轨道交通混合乘车策略与策略概率的线性组合。即：

式中：

pjk---第j个OD间出行的用户选择策略k的概率。

当OD对j的综合支付函数的变量包含状态集合时，可以将混合策略的综合支付函数表达为：

式中：

S-j---第j个OD以外各OD间的策略集合；

h---第h个OD间出行的用户（h≠j）；

ah---第h个OD间的策略组合个数。

由于相同OD间出行用户都是同质的，根据Wardrop第一均衡准则，对任意OD对来说，出行用户都会选择期望最大的混合策略［4］：

对于有j个OD间出行的用户状况，不同出行用户独立无合作追求最大利益（时间和拥挤负载的综合收益最大）情形下的博弈平衡，这样就形成在Wardrop第一均衡准则下的混合策略Nash均衡［5］。

2 Stackelberg-Nash博弈配流模型

根据Wardrop第一均衡准则下的混合策略Nash均衡准则，可以将模型改写为一维极值问题。对每个OD对j来说，都有如下极值问题：

式中：

Q---目标函数；

min Q---配流最优；

w---OD个数；

Fjk---第j个OD间采取第k种城市策略的路径拥挤函数；

Zjk（Fjk，tjk）---第j个OD间采取第k种策略的综合支付函数；

djk，rs---第j个OD间的第k种轨道交通策略是否经过路段rs的0-1变量，o和i表示城市轨道交通路段的任意节点组合；

gjk，rs---第j个OD间的第k种道路公交策略是否经过路段rs的0-1变量，u和v表示道路公交路段的任意节点组合；

aj---第j个OD间的策略组合个数；

求得的pjkDjk，rs和pjkGjk，rs即交通流分配方案。

3 改进蚁群求解算法

3.1 改进蚁群算法依据

根据出行用户路线走向设计的配流博弈模型是多个OD之间的混合策略博弈。其体现了OD对之间的相互抑制，是逆向反馈的过程；相同OD之间的影响体现了人与人之间的相互吸引，是正向反馈的过程。这是人工智能的一般应用，而对蚁群算法的改进恰好可以实现上述两个方面的智能。所以本文选择了蚁群算法。这是一种模拟蚂蚁外出觅食时根据前面蚂蚁所留下的信息素的存在及其强度来指导自己的运动的方法［6］。

由于本文研究的情况复杂，对算法进行了两个方面的改进：

第一，对转移规则中对能见度ηrs进行修正，解决搜索的方向性问题。同一个OD的出行用户之间通过信息素进行正向反馈，而不同OD所属的出行用户之间则通过信息素相互抑制。

第二，考虑到路段拥挤和排队消散等问题，需对局部更新规则进行改进。

3.1.1 转移规则改进

由于乘客倾向于乘坐路径综合支付函数较小的交通工具，所以对能见度ηrs进行如下更新：

式中：ZD，rs（Frs，trs），ZG，rs（Frs，trs）分别表示路径rs中乘坐城市轨道交通与乘坐道路公交的综合支付函数。

将w个OD对假设为蚁群A1，A2，…Aw，t时刻城市轨道交通路径rs上信息素浓度为τD，rs（t，1），τD，rs（t，2），…τD，rs（t，w），道路公交路径rs上信息素浓度为τG，rs（t，1），τG，rs（t，2），…τG，rs（t，w）。则属于蚁群Aj的蚂蚁a由区域r行驶到区域s的转移概率可表示为：

当s∈Sallowedk时，

当s∉Sallowedk时，

当s∈Sallowedk时，

当s∉Sallowedk时，

3.1.2 局部规则改进

对局部规则的更新可有效避免蚂蚁收敛到同一路径。蚂蚁在每一步搜索后，更新它所经过路径的信息素强度，更新规则为：

式中：

Δτrs---信息素增量；

Δτrs，a---蚂蚁a遗留的信息素数量。

如果第a只蚂蚁经过路段（r，s），

否则

式中：

Q---信息素强度，它在一定程度上影响算法的收敛速度；

La---第a只蚂蚁在本次循环中所走路径的总长度。

基于以上改进方法的算法如下：

步骤1：初始化τrs和Δτrs，禁忌表tua置空，将A1，A2，…Aw只蚂蚁置于1～w个顶点上；

步骤2：蚂蚁以概率prs，a尝试选择下一节点s，将s添入至tua中，直至禁忌表满；

步骤3：根据tua的记录，更新τrs与Δτrs；

步骤4：对各路径（r，s）置Δτrs=0；

步骤5：记录到目前为止最短的路径，若不满足终止条件，清空禁忌表，转步骤2；

步骤6：输出配流方案。

4 算法仿真

利用图1的网络布局图进行算法仿真。其中，实线表示道路公交连通线路；空心箭头表示城市轨道交通连通线路。布局图节点之间无拥挤走行时间数据见表1。表中G开头表示道路公交线路时间，D开头表示城市轨道交通线路时间，单位为min。

道路公交线路与城市轨道交通线路设计见表2。设计不同节点之间的OD，如表3所示。

图1 网络布局图

表1 节点走行时间表

表2 道路公交线路与城市轨道交通线路设计表

针对上述参数设计，对换乘进行相关时间叠加，规定换乘一次的时间为2 min，并按算法步骤进行迭代。迭代出的部分配流结果如表4、表5所示。从表中可以看出，出行用户在蚁群算法中的配流结果基本符合蚁群算法的相关智能要求。通过对求解过程和结果的分析，改进蚁群算法基本实现了博弈的均衡过程，是合理的。

表3 不同OD间走行时间 min

表4 地铁1号线各路段配流仿真表

表5 1路公交车各路段配流仿真表

5 结语

本文根据Stackelberg博弈构造了含有使用混合策略Nash的均衡准则，用来表述出行选择，能够体现出行行为的多重性和多元性。而蚁群算法的引入，合理地解决了这个复杂的博弈模型的求解方法问题，也为问题的完善开辟了一条新思路。

［1］ 施锡铨.博弈论［M］.上海：上海财经大学出版社，2000.

［2］ 陈涛，陈森发，陶耘.公交与轨道交通的多维Stackelberg博弈与均衡［J］.系统工程学报，2010，25（5）：638.

［3］ Bell M G H.A game theory approach to measuring the performance reliability of transport networks［J］. Transportation Research Part B，2000，34（6）：533.

［4］ Bell M G H，Cassir C.Risk averse user equilibrium traffic assignment：an application of game theory［J］.Transportation Research Part B，2002，36（8）：671.

［5］ Perez T，Goodwin G C.Constrained predictive control of ship fin stabilizers to prevent dynamic stall［J］.Control Engineering Practice，2008，16（4）：482.

［6］ 李士勇.蚁群算法的改进及应用研究进展［J］.计算机测量与控制，2003，11（12）：911.

Multidimensional Stackelberg Game Assignment Based on Ant Colony Algorithm

Ai Yi，Li Zongping

To discuss the network traffic flow in urban bus system and the distribution of urban rail transit，Stackelberg Game is used for traffic distribution study and the Nash equilibriumis established.According to an assumption，there aremultipleOD（origin of departure）on road network，based on the Wardrop equilibrium standards，the trip users of each OD is proved to be homogeneous.Thus，a mixed strategy Stackelberg-Nash equilibrium game model for bus route and rail transit route is established.Then，with an improved ant colony algorithm for travelers，the process of equilibrium is simulated.The numerical results show that the improved ant colony simulates the matchup Stackelberg Game equilibrium process very reasonably.

urban traffic；urban rail transit；traffic flow distribution；Stackelberg game；improved ant colony algorithm

U 491.1+12

2012-04-13）