基于Stackelberg博弈的时变双层交通分配模型

胡文君 周溪召

摘 要 提出一个时变双层交通分配模型，其中上层网络管理者设立了一个路段的最大排队长度，其目标是使由网络流和排队长度定义的总出行时间最小.目标函数在离散时段内以路段流量和排队长度作为决策变量，同时考虑不同类型的信号交叉口延误的影响.下层网络用户的反应依赖于上层管理者的决策，其选择是使自身感知阻抗最小的路径，服从一个基于成对组合Logit的路径选择模型，构成一个成对组合Logit的均衡分配问题.结合了交通分配和流传播方法，将其表示为一个均衡约束下的双层数学规划问题，形成了一个Stackelberg非合作博弈.使用遗传算法求解该双层规划问题，并采用实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素对网络均衡流分布均有显著影响.

关键词 交通运输经济学;双层交通模型;Stackelberg博弈;时变;排队长度

中图分类号 U491            文献标识码 A

Timevaring Bilevel Transportation Assignment

Model Based on Stackelberg Game

HU Wenjun ， ZHOU Xizhao

（1. Economics and Management College， Shanghai Zhongqiao College，Shanghai 201309， China;

2. School of Management， Shanghai University of Technology，Shanghai 200093， China）

Abstract A time varying bilevel transportation assignment model is proposed in which the upper level network administrator establishes the maximum queue of a link to minimum total travel time defined by network flow and length of queue. The objective function uses the link flow and queue length as decision variables in discrete time， taking into account the influence of different types of signalized intersection delays. The response of users from the lower level network depends on the decision of the upper level manager. They choose a route that minimizes their own perceived impedance and follow a paired combinatorial legitbased route choice model and constitutes a paired combinatorial legit equilibrium assignment problem. The formula combines the methods of traffic assignment and flow propagation and presents a bilevel mathematical programming problem under equilibrium constraints， forming a Stackelberg noncooperative game. A genetic algorithm is used to solve the bilevel problem and an positive analysis is performed to express the characteristics of the model and the computational performance of the algorithm. The results show that the overlap of routes， the traffic volume of the link and the queue length of the link all have significant effects on the distribution of network equilibrium flows.

Key words traffic economics;bilevel transportation model;Stakelberg game;time varying;length of queue

1 引 言

Stackelberg非合作博弈是由德國经济学家H. Von Stackelberg提出来的，该模型提出了一个基于“领导者”与“追随者”的主从结构的分析范式.Stackelberg非合作博弈模型广泛应用于环境监测、航天航空、抢险救灾、实时视频传、话务通信、有线网络、交通运输、供应链管理等领域.

在交通规划中，高自友等（2004）[1]指出，网络设计问题（NDP）是一种常见形式，它关注交通网络的结构以达到特定的目标.一般地是在现有投资规模条件下，通过在现有交通网络中增加新的路段或更新、改善已有路段的供给能力，从而达到使整个交通网络某种系统性能最优的目的.

网络设计过程实质上是交通网络管理者和网络用户之间的一个Stackelberg非合作博弈，两者追求不同的目标.作为博弈中的领导者，网络管理者一般关心整个交通网络状态的改善，如最小化总投资、最小化社会总阻抗、最大化路网绩效或最大化社会总收益.而作为跟随者，网络用户一般不关心整个社会的利益，而是从自身出发，选择使自身阻抗或感知阻抗最小的路径来应对领导者的行为，导致一个用户均衡（UE）或随机用户均衡（SUE）的流模式.

交通网络设计问题可以用来解决一系列的交通问题，如道路扩容问题、道路拥挤收费问题、信号设置问题、OD矩阵调整问题和道路基础设施位置问题等.

史峰和李志纯（2003）[2]提出了网络扩容和拥挤道路使用收费的组合模型，并给出了求解算法.赵泽斌等（2007）[3]在道路扩容后分析道路拥挤定价收入对交通出行者效用影响的基础上，构建了基于道路扩容的道路拥挤定价收入再分配双层规划模型，并给出了求解算法和实证分析.李志瑶等（2005）[4]应用基于活动的出行需求预测方法，分别建立了出发和到达时间选择模型，并分析了拥挤收费政策.张华歆和周溪召（2005）[5]研究了多模式交通网络的拥挤道路收费问题，建立了双层規划模型.徐建闽等（2011）[6]提出一个基于双层规划模型的交通信号区域协调控制并用虚拟退火算法进行仿真.安梅和高自友（2001）[7]利用多模式均衡配流的变分不等式模型，建立了拥挤条件下多模式 O-D需求估计问题的双层规划模型，并在对多模式均衡配流变分不等式模型进行灵敏度分析的基础上，给出了关于此类双层规划模型的基于灵敏度分析的求解算法.许项东和程琳（2009）[8]提出了一个城市道路单行系统布局优化的双层规划模型，用混合算法验证了模型的有效性.田晟等（2017）[9]针对交通出行者的出行行为存在不同属性的实际情况，在网络设计双层规划理论的基础上，研究基于随机均衡配流的连续性交通网络设计问题.

通常将一个Stackelberg非合作博弈归结为一个双层数学规划，因为双层规划能很好地刻画两阶段的动态博弈.

针对一个改善现有网络运作的NDP，建立了一个时变双层交通分配模型.在双层模型中，上层领导者网络管理者的目标是最小化由网络路段流和路段排队长度决定的总出行时间，下层跟随者网络用户的反应依赖于领导者的决策并选择使自身感知阻抗最小的路径.同时考虑路段重叠效应，建立一个基于成对组合Logit（PCL）的分配模型.建立了保证NDP解存在的条件，使用了遗传算法来求解上述问题，并进行实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素均对网络均衡流分布有显著影响.

2 一般双层规划模型

首先给出后续所要用到的符号.

Stackelberg模型提出了一个包括“领导者”与“追随者”的主从结构的分析范式.模型的基本假设是：在博弈过程中，首先由领导者做决策，随后追随者再做出决策.领导者可以预测到追随者未来的最优行为选择，从而做出自己的最优决策.追随者则在观测到领导者的最优决策后做出自身的最优决策.

交通网络设计模型是一个典型的Stackelberg博弈模型，其中博弈的一方交通网络管理者充当了领导者的角色，而博弈的另一方交通网络系统中的用户则是追随者.首先由网络管理者决定一个系统目标，然后网络用户可以观察到这个系统目标并根据此目标来决定他自己的目标.网络管理者在决定系统目标的时候，充分了解网络用户会如何行动，知道网络用户的相机决策，从而预期到自己决定的目标对网络中用户的影响.一个常见的交通分配模型和网络设计问题在领导者问题中引入设计变量y，在跟随者问题中引入流变量x，形成一个一般双层规划模型.

其中，F（x（y），y）是上层网络管理者的目标函数，表明网络管理者通过求解min y F（x（y），y）来寻求最佳控制情景y，同时必须考虑由用户应对给定控制变量y而导致的相应流模式x（y）.G（x（y），y）是上层问题的约束集合.f（x，y）是下层网络用户的目标函数，g（x，y）是下层问题的约束集合，x是下层控制向量（流模式）.对一个给定控制状况y，min xf（x，y）在静态情况下可能导致一个用户均衡（UE）或随机用户均衡（SUE）流模式.在动态情况下可能导致一个动态用户最优（UO）流模式.y是上层控制向量（道路扩容、拥挤收费、信号控制或OD调整向量等）.

3 动态路径选择和交通分配下

考虑路径重叠的双层规划模型

3.1 静态路径选择和交通分配下考虑路径重叠的双层规划公式

3.1.1 上层公式

上层问题一般用来解释网络管理者优化系统绩效的决策行为.上层问题中的决策变量可能是信号时间、拥挤收费、道路扩容、OD调整变量等.则上层优化模型可表示为：

min y∑a∈Axaw（xa，y） （5）

s.t.yl≤y≤yu， （6）

其中，w（xa，y）是给定y时由网络管理者定义的路段阻抗函数，可能体现在出行总阻抗、出行时间、排队延误、能源消耗或污染排放等指标上.

对于拥挤网络，需求过量会导致排队长度过长，阻碍上游交叉口，引起系统瘫痪.因此在上层目标函数中应该加入一项反映排队长度的项.此时网络管理者关注路段上的流量和排队长度两个方面，上层目标函数是寻找由路段上的流量和排队长度构成的总阻抗最小化：

min q∑a∈A[Ca（x，q）x+λQa（x，q）] （7）

s.t.qla≤qa≤qua， （8）

其中，q为设计变量，Ca（x，q）是路段a上总出行时间，是流向量x和排队长度q的函数，Qa（x，q）是与路段a上排队长度相关的时间函数，λ为权重因子.

3.1.2 下层公式

3.1.2.1 UE路径选择行为下层公式

下层问题设计网络中用户的路径选择行为，因此决策变量是由用户选择自身最优化路径选择而导致的决策变量.假设用户均衡UE是假定用户具有路径阻抗的完全信息，能够选择使自身出行阻抗最小的路径.静态固定需求下的下层UE均衡模型为：

min x∫xa0Ca（w，y）dw （9）

s.t.∑rs∈RS∑k∈Krsfrskδrsak=xa，a∈A，（10）

∑k∈Krsfrsk=Drs，rs∈RS.（11）

frsk≥0，k∈Krs，rs∈RS， （12）

其中，Ca（w，y）为给定控制向量y时路段a的阻抗函数.δrsak为路段-路径关联变量，若路段a在路径k上，则等于1，否则为0.frsk为OD对rs间路径k上的路径流.Drs为OD对rs间需求.式（10）和（11）为流守恒约束，式（12）为非负路径流约束.

3.1.2.2 SUE路径选择行为下层公式

UE假定用户对路网状况有完全信息，显然不太符合实际情况，随机用户均衡SUE假定用户对路网状况不完全了解，存在一个感知误差.在SUE假定下采用多项式Logit（MNL）来反映用户的出行选择行为.其路径感知负效用函数假定为

Crsk=crsk+εrsk.（13）

其中Crsk是用户使用路径k的感知阻抗（随机变量），crsk是用户使用路径k的实际阻抗，εrsk是使用路径k的感知误差.

则连接OD对rs的路径k被选择的概率Pm，rsk为：

SymbolcB@Crsl，l≠k且l，k∈Krs）. （14）

假定εrsk是独立同Gumbel分布的，则出行者的路径选择就服从多项式Logit（Multinomial Logit，MNL）模型，选择OD对rs间路径k的概率可以表示为如下公式：

其中，θ为分配参数，其他参数同UE模型.

3.1.2.3 PNLSUE路径选择行为下层公式

为了克服MNL无法处理重叠路径的缺陷，一系列复杂的改进Logit模型可用于路径选择，比如成对组合Logit（PCL）、交叉巢式Logit（CNL）、路径因子Logit（PSL）等.在这些模型中，实证研究表明PCL较适合于交通分配问题的应用，比其他类型logit模型表现更好.

PCL模型以不同规模参数来考虑成对方案间的相关性，将其看作两个方案对.其选择路径k的概率为：

假定效用Vk为路径阻抗ck的线性组合，可将选择一条路径的概率表达式为：

P（k）=∑k≠jP（kj）·P（k|kj），（21）

其中在选择路径对（k，j）的条件下选择路径k的条件概率为：

P（k|kj）=exp （Vk1-ηkj）exp （Vk1-ηkj）+exp （Vj1-ηkj） （22）

选择路徑对（k，j）的边际概率为：

其中，ηkj为方案k和方案j的相似性指标，0≥ηkj≥1，若ηkj等于1，则表明是最大重叠;若ηkj等于0，说明两条路径之间没有共同路段.可以定义：

其中，Zkj是路径k和路径j的共同部分的长度，Zk和Zj分别是路径k和路径j的长度.

则使用PCL路径选择标准的下层问题可以表示为：

3.2 动态路径选择和交通分配下考虑路径重叠的双层规划公式

引入时间变量t∈T，其中T为研究时间段.则时变需求下使用PCL路径选择模型的动态双层公式为：

其中，右上角带符号τ的变量表明时段τ内的相关变量，是时变模型的表示.

上层模型（29）-（30）使用一个时变出行流函数和一个排队，可以加入一些延误函数来计算，如Webster延误函数和Akcelik延误函数：

ta（xa（τ），qa（τ））=t0a+Φd1a，Webster+d2a，Akcelik.（34）

公式（34）中，t0a表示自有流出行时间，d1a，Webster表示Webster型延误函数，d2a，Akcelik表示Akcelik型延误函数.Φ为一个0-1变量，当路段交叉口是信号灯控制交叉口类型时，Φ=1;当路段交叉口是限制入口交叉口类型时，Φ=0.

下层模型（31）-（33）包含一个确定性物理排队函数，公式（31）的目标函数中Ψka（t）是一个确定性排队模型，满足以下关系式：

其中，公式（25）中，Ψka（θ（τ））为时刻θ（τ）用户在路径k上路段a的排队长度.ta[Ψka（τ）]表示时刻τ路径k上路段ai的用户花费的出行时间/出行阻抗，它是路段a上流量和排队的函数.vka[θ（τ）]表示时刻θ（τ）用户在路径k的路段a上的交通流入量，即入流.Dka（τ）表示时刻τ在路径k的路段a的起点产生的出行需求量，通常为已知.okai（τ）为时刻τ离开路径k上路段ai的流出量，即出流.Δvkai（τ）表示时刻τ路径k的路段ai上入流的变化.θka1（τ）为时刻τ路径k上路段a1的路段阻抗，同理θkai（τ）为时刻τ路径k上路段ai的路段阻抗.公式（37）界定了第一个路段的流传播.公式（38）界定了接下来的i-1个路段的流传播情况.公式（39）是路段的先进先出FIFO条件.

4 模型的求解算法

双层规划问题是一个非凸优化问题，其最优解的求解是一个NP-hard问题.近年来随着对双层规划问题研究的深入以及计算机技术的发展，大量有效的求解算法被提出，其中由美国密西根大学的Holland提出和改进的遗传算法（Generic Algorithm， GA）对非线性问题具有较强的空间搜索能力，适应性较好，可以用来求解问题.GA借鉴生物进化论中的基本概念，以染色体为研究对象，仿照生物进化的过程，对染色体进行选择、交叉和变异等处理，自动生成算法的搜索空间及搜索方向，对双层规划问题进行求解.陆化普等（2011）[10]开发了基于MonteCarlo模拟、遗传算法和交通分配算法的方法，此算法可用来求解双层规划问题.

遗传算法求解模型的流程可归纳为如下步骤.

步骤1：初始化：

定义GA参数：染色体编码方案、种群进化最大代数、种群规模、代沟、交叉概率、变异概率.设置进化代数计数器t=0，最大代数T，设个体的适应度函数值即为目标函数（29）.随机生成M个个体作为初始群体P（0），随机生成初始染色体.

步骤2：个体评价：

计算群体P（t）中各个个体的适应度;根据染色体编码方案，更新交通网络中的结构参数;进行下层模型基于PCL的交通分配模型求解.首先考虑路径重叠效应，算出下层基于PCL的路径选择公式（31）-（33）的值.

步骤3：计算上层时变出行流函数和排队函数下的目标函数值（29）-（30）.其中，上层的决策变量是设计变量即排队长度q，下层的决策变量是路段流变量x.

步骤4：选择、交叉、变异运算：

将选择算子作用于群体，经过选择、交叉、变异运算之后得到下一代群体P（t+1）.

步骤5：步骤六：

终止条件判断：若t=T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算.

5 实证分析

截取2019年常州某一住宅区规划及单体设计方案文本中的某一区段的道路作为主要研究对象，该住宅小区用地面积17023m2，地块呈不等边梯形状，南北长约160米，东西长约150米，分布较对称，

如图1所示.将之抽象为一个包含四个节点、五个路段和两个OD对的简单实际网络以便进行分析.以一个研究时段作为观测对象，研究排队长度和道路拓扑结构对网络均衡流的影响.

OD对1-4共有3条路径：路径1由路段1，4构成;路径2由路段2，5构成;路径3由路段1，3，5构成.OD对2-4有两条路径：路径1即为路段4，

路径2由路段3，5构成.OD对14间和24间需求均为50.

采用BPR型路段阻抗函数：

ta（xa）=t0a[α+0.15（xaca）β]. （40）

其中，t0a是自由流出行时间，ca是路段a上的设计容量.α，β为BPR函数的参数.各路段的自由流出行时间和设计容量参数，如表1所示.

OD对1-4中，路径1和2的相似度指标为0，因为两条路径没有重叠部分.为方便假定路段长度均相同且为1，则路径1和2的相似度指标η13=12+3=15≈0.72.同理，路径2和3的相似度指标η23=η13=15.

總研究时段T=10划分为10个子时段Δτ=1，为方便计算和比较，只取第一个研究时段τ=1作为观察对象.

排队长度阻抗函数Qa（xa，qa）假定为：Qa（xa，qa）=0.1ta（xa）+1/xala.其中la为路段a的长度.其他参数为：用户感知误差参数θ1=θ2=0.1，排队长度权重因子λ=0.5，排队长度上下界qua=100，qla=0.路段交叉口是信号灯控制类型Φ=1.

经过多次调试，将GA参数假定为：最大种群数gmax =500，种群规模数量为50，后代数量50，变异概率为0.001，交叉概率为0.8.最大种群数超过500会导致群体数量过大，计算效率偏低;交叉概率若小于0.8，会导致产生新个体速度太慢;变异概率大于0.001，虽然会产生较多新个体，但会破坏很多较好的模式，使遗传算法性能接近随机搜索算法.

由表2的计算结果可知，由双层模型求得的均衡结果为下层路段1至5的均衡流分别为29.14、15.27、29.32、47.93和40.14.上层均衡排队长度分别为11.93、3.60、10.57、20.53和13.03.相比不考虑重叠路段即相似度指标η=0的情形，重叠路径3分配到的流量要小得多，其他路段流量变化不大.说明加入重叠的影响更符合实际情况，网络中一些用户出行时会避开该路段，而非都是涌向该路段.相比不考虑排队长度的影响Qa=0时，各路段的均衡流量均会减少，但趋于均匀，说明排队长度的限制会抑制用户使用阻抗较小的路径，转而使用其他阻抗较大的路径.结果表明，考虑重叠因素及排队长度均会对网络的均衡状态和均衡流产生影响.

通过对截取的常州某住宅区一区段道路网络的实证研究分析，可以发现，加入重叠影响的PCL模型更符合现实路网情况，信号交叉口的不同类型延误导致的排队长度的限制会影响用户的出行路径的选择，同时造成不同的道路均衡状态和流量.

6 结 论

提出一个时变双层交通分配模型，其中上层领导者网络管理者的目标是最小化由网络路段流和路段排队长度决定的总出行时间，采用一个考虑自由流出行时间、Webster型信号交叉口延误函数和Akcelik型延误函数的总出行时间函数，同时根据信号交叉口的不同类型来确定延误.下层跟随者网络用户的反应依赖于领导者的决策，其选择使自身感知阻抗最小的路径，同时考虑了路径的重叠效应，建立了一个基于PCL的交通分配模型，下层中包含了一个确定性的物理排队.上下层的交互作用构成了一个Stackelberg非合作博弈.使用遗传算法求解双层问题，并进行实证分析来表现模型的特征和算法的计算表现.结果表明路径重叠、路段流量、路段排队长度等因素对网络均衡流分布都有显著影响.提出的模型可计算路段流、路径流、出行时间和排队长度，可用于预测ATIS信息和优化交通控制系统.

参考文献

[1] 高自友， 张好智， 孙会君. 城市交通网络设计问题中双层规划模型、方法及应用[J]. 交通运输系统工程与信息， 2004， 4（1）：35-44.

[2] 史峰， 李志纯. 网络扩容和拥挤道路使用收费的组合模型及求解算法[J]. 中国公路学报， 2003， 16（2）：90-94.

[3] 赵泽斌， 安实， 王健. 基于道路扩容的道路拥挤定价收入再分配研究[J]. 中国管理科学， 2007， 15（1）：81-85.

[4] 李志瑶， 隽志才， 宗芳. 居民出行时间选择及拥挤收费政策[J]. 交通运输工程学报， 2005， 5（3）：105-110.

[5] 张华歆， 周溪召. 多模式交通网络的拥挤道路收费双层规划模型[J]. 系统工程理论方法应用， 2005， 14（6）：546-551.

[6] 徐建闽， 首艳芳， 卢凯. 基于双层规划模型的交通信号区域协调控制[J]. 华南理工大学学报（自然科学版）， 2011， 39（3）：95-100.

[7] 安梅， 高自友. 模式间相互影响时估计O-D需求的双层规划模型及求解算法[J]. 系统工程理论与实践， 2001， 21（4）：36-42.

[8] 许项东， 程琳. 城市道路单行系统布局优化的双层规划模型和混合算法[J]. 系统工程理论与实践， 2009， 29（10）：180-187.

[9] 田晟， 马美娜， 许凯. 随机均衡配流下的连续性交通网络设计[J]. 华南理工大学学报：自然科学版， 2017， 45（11）：23-29.

[10]陆化普， 蔚欣欣， 卞长志. 发生吸引量不确定的离散交通网络设计模型[J]. 统计与决策， 2011（6）：8-12.