基于两阶段行程时间的交通流分配理论

何胜学

(上海理工大学 管理学院，上海200093)

0 引言

现有静态交通流分配理论假设路段行程时间具有对于路段流量的单调递增特征，因此无法对拥挤的路段交通状态进行合理刻画.根据交通流量、密度和速度的基本关系图，当路段处于拥挤状态时，路段流量与行程时间应具有反向变化关系，即当流量增加时，行程时间应当减少.根源于上述缺陷，现有理论难以对网络交通流的演变进行描述分析.本文以反λ基本图为基础，提出考虑自由流和拥挤2种状态的新交通流分配模型.利用新模型给出了分析网络交通流演化的新方法.

静态交通流分配理论始于1952年Wardrop提出的出行路径选择两原则，即Wardrop第一原则(用户均衡)和Wardrop第二原则(系统最优)[1].1956年Beckman给出了对应Wardrop第一原则的用户均衡交通流分配数学模型，即有名的Beckman变换[2].1975年，Leblanc首次给出了求解上述模型的实用有效Frank-Wolfe算法[2].Dafermos和Sparrow探讨了如何利用变分不等式构建交通流分配模型[3]；Daganzo和Sheffi最早提出了随机交通流分配的理念[4].2002年Bar-Gera提出的基于起点的交通流分配算法大大提高了求解静态模型的效率[5].近年来研究者更多关注动态交通流分配和一些拟动态交通流分配，例如应用投影动态理论对交通流分配问题进行建模分析[6-7].为了克服经典理论中路段流量可超出路段通行能力的缺陷，研究者提出了一系列基于变分不等式理论的有边约束的交通流分配模型[8-9].静态交通流分配理论中，一般假设路段行程时间函数具有对于路段流量的单调递增特征，而该假设与路段处于拥挤状态时的情景相矛盾.最近的基于静态交通流分配理论的研究也没有改变上述假设，例如文献[10]假设路段行程时间函数为一般的连续可微单调增凸函数；文献[11]则利用了经典BPR单调增函数；而文献[12]则简单利用了线性单调增函数.流量、密度和速度的基本关系图是交通流理论的基础理论之一，广泛应用于交通研究的各个领域，例如基于该理论建立的经典元胞传播模型[13-14].

本文主要创新为，基于反λ交通流基本图建立了新的静态交通流分配模型；以新模型为基础，给出了利用静态交通流分配模型分析网络交通流演化的新方法.

1 问题引入

目前常用的路段行程时间函数一般具有如图1所示的对于路段流量的单调递增特征.基于该类行程时间函数所建立的交通流分配模型，例如用户均衡(User Equilibrium，UE)和系统最优(System Optimization，SO)模型，一般具有良好的数学性质，因此可以被有效求解.从图1可知，随着路段流量的增加，车辆通过路段的行程时间不断增加.研究者希望通过增函数的这一性质体现道路的拥挤特征.但是该函数对现实的描述存在3个明确缺陷.首先，可通过路段的流量有一个上限，不可能无限增加.尽管该问题可以通过增加路段通行能力的边约束得到处理，但是模型的求解将变得更加复杂.由于“全有全无”算法需要将起讫点对间所有流量一次加载于当前连接该起讫点对的最短路上，因此加载到最短路上的路段流量一般会超过路段的通行能力.因此嵌套“全有全无”算法的均衡算法很难被直接用于求解具有路段通行能力约束的模型.其次，现实中路段的行程时间在自由流状态下一般会随着流量的增大而增加，但是增加的幅度一般较小.而目前常用的路段行程时间函数虽然假设随着流量的增大行程时间增加，但是随着流量的增加，行程时间增长幅度变得越来越大.最后，现实中当路段交通处于拥挤状态时，实际路段的通行能力下降，即随着流量的减少，路段的行程时间变得越来越大.而这一点在图1所给出的常用路段行程时间函数中完全没有体现.综上，我们认为利用图1给出行程时间函数得到的交通流分配结果将与现实存在较大差异.

图1 常见的路段行程时间与流量关系图Fig.1 The common relation between link travel time and link flow

针对上述问题，我们认为在交通流分配时应当使用如图2所示的两阶段行程时间函数.两阶段行程时间函数包括2个不连续部分，分别对应自由流状态和拥挤状态.图2的两阶段行程时间函数对应图3给出的反λ型流—密—速基本关系图.显然，对应不同的流—密—速基本关系，例如常见的三角形和梯形关系图，两阶段行程时间函数的具体形式会存在一定差异.

图2 两阶段路段行程时间函数Fig.2 Link travel time function with two stages

图3 反λ型流—密—速基本关系图Fig.3 The inverseλfundamental diagram

图3给出的反λ型流—密—速基本关系体现了路段交通状态从自由流状态转为拥挤状态时的通行能力失效特征，即图中交通状态从C到B的突变.现代交通流理论，如三相交通流理论，对上述突变有更深入的分析.鉴于本文研究面向交通规划的宏观特征，我们认为应用类似图3给出的线条形非区块化基本关系图比较合理.假设路段的长度为l，则图2和图3中的量存在如下关系：tfree=l/vfree和tcr=l/vcr.

假设自由流状态下，路段行程时间函数为t=tfree+αq；而拥挤状态下路段行程时间函数为t=γ+βq-1.其 中α、β和γ是待定常数.由tcr=tfree+αqcr=l/vcr和基本关系q=kv，可以基于图3的特征参数确定具体的α=(tcr-tfree)qcr=lkcr/qcr2-tfree/qcr；反之，也可以由给定的α值，确定图3中自由流阶段流量和密度的曲线函数.简单的推算可知，拥挤状态下路段行程时间函数t=γ+βq-1与直线型的路段拥挤阶段流量和密度的关系相对应，且有β=lkjam和γ=l(kmax-kjam)qmax成立.

2 路段交通状态已知的交通流分配模型

交通分配模型相关的参变量如下：

a∈A——指代有向路段a，A为所有的有向路段集合；

n∈N——指代节点n，N为所有节点集合；

b∈B——指代起讫点(Origin and Destination，OD)对b，B为所有OD对的集合；

qb——OD对b的交通需求流量；

xa——路段a上的流量；

δa∈{0,1}—— 路段a的交通状态指示量，当δa=1时，路段a的交通状态为自由流状态，否则，路段a的交通状态为拥挤状态；——拥挤状态下路段a的最大通行流量；

Δ＞0——为给定的拥挤状态下的路段最小通行流量.

相关的约束包括：

式(1)～式(3)分别为一般节点、OD对起点和OD对终点的交通流守恒方程；式(4)是路段流量和约束；式(5)和式(6)是路段流量和的上下限约束；式(7)限定路段交通状态指示参数为0-1变量.

与出行者的择路行为对应，可以给出2个不同的目标函数.式(8)对应SO，式(9)则对应UE.

为了方便表述，将以式(8)为目标函数的配流模型称为新系统最优模型，而将以式(9)为目标函数的配流模型称为新用户均衡模型.

定理1如果对于任意路段a在自由流阶段的行程时间函数为而在拥挤状态的行程时间函数形式为ta=γa+βa xa-1，且已知路段交通状态δa，∀a∈A，那么系统最优的交通流分配模型为凸二次规划.

证明当路段交通状态δa，∀a∈A已知时，约束集为线性单纯形.显然对应自由流状态的目标函数部分为变量的二次函数，而对应拥挤状态的目标函数部分为变量的线性函数.综上结论可证.

定理2如果对于任意路段a在自由流阶段的行程时间函数为在拥挤状态的行程时间函数形式为ta=γa+βa xa-1，所有δa，∀a∈A已知，且至少有交通状态δc=0，∃c∈A，那么用户均衡的交通流分配模型为非凸规划.

证明对应δc=0的目标函数加和项为而该项为变量x的凹函c数.易知结论成立.

由定理1可知新系统最优模型为凸二次规划.该类问题可以被非常有效的求解.而由定理2可知新用户均衡模型实质上均为带有线性约束的非凸规划问题.对于该类问题目前也已有一些比较有效的算法，例如可以通过KKT松弛或半定规划松弛得到相应的线性模型，利用分支定界法求解.在已知各种函数的具体形式后，也可以采取更有针对性地求解算法.例如当约束为线性紧约束时，可以结合KKT条件松弛与正交变换变量替代设计更加有效的分支定界法对问题求解.

3 基于新模型的网络交通状态演化分析法

如果已知路段的交通状态，可以利用上节的优化模型求解具体的网络流量分布.但是如果δa，∀a∈A未知，就不能直接利用已有模型求解流量分布.

静态配流模型假设OD对需求流量在一定时间段内维持稳定，因此模型求解的结果反映了稳定OD需求下交通流的网络分布状态.从实际网络交通演化的角度看，如果发生拥堵，必然存在一个路段交通状态由自由流转变为拥挤状态的过程，且根据OD需求持续时间的长度，拥挤区域会存在一个扩大与消减的过程.可以利用上节给出的已知路段交通状态的交通流分配模型对上述演化过程进行模拟.下面定义中的新分配模型可根据实际指代新系统最优模型或新用户均衡模型.

定义 1令δa=1，∀a∈A，求解新分配模型.如果得到的路段流量满足则称该网络为自由流网络；如果则称该网络为一级拥挤网络；如果模型无解，则称该网络为一级失效网络.对于一级拥挤网络，称路段集合为网络一级瓶颈.

定义 2在得到n级拥挤网络后，令δa=0，求解对应上述δa值的新分配模型.如果得到的路段流量满足则称该网络为完全n级拥挤网络；如果则称该网络为n+1级拥挤网络；如果模型无解，则称该网络为n+1级失效网络.对于n+1级拥挤网络，称集合为网络n+1级瓶颈.

上述的2个定义暗含了如何利用新配流模型对网络交通流的演化进行分析的方法.网络实际的交通拥堵区域的形成应与上述定义的递增式的拥堵区求解一致，实际拥堵区域的范围与OD间交通需求量持续的时间长短有关.而网络拥堵消散的过程应与递增式的拥堵区求解相逆.当两阶段优化模型无解时，表示网络最大瓶颈通行能力小于OD对间的交通需求，流量不能完全加载上网，部分流量必须在起点排队等待.

4 算例分析

本节以新用户均衡模型为例对第3节的网络交通状态演化分析方法进行验证.设时间单位为h，距离单位为km，流量单位为pcu/h，速度的单位为km/h，这里pcu表示标准小汽车单位.求解算法利用Lingo语言实现，其中的二次规划模型的求解直接利用Lingo软件的自带程序实现.因此计算的效率与软件自带的算法密切相关，对于随后给出的简单算例，得到最终结果需要的时间少于6 s.

图4给出了一个简单交通网络.其中路段的交通流方向用箭头表示.假设节点1和3为起点，节点5、6和7为终点.网络存在4对OD对，分别为(1,6)、(1,7)、(3,5)和(3,7).对应上述OD对的交通需求量分别为1 200、1 800、500和600 pcu/h.表1给出了对应10条路段的各种参变量值.表1中第1列用路段的前后2个端点构成有序对表示对应路段.

图4 有7个节点的交通网络Fig.4 Traffic network with 7 nodes

表1 路段相关参数Table 1 Coefficients of links

表2 路段不同状态下的计算平衡流量Table 2 The equilibrium link flow under different link states

按照第3节给出的分析思路，首先假设所有路段处于自由流状态，计算得到路段的平衡流量，如表2中情景1下的xa列，此时路段(1,2)和(3,6)达到了自由流流量的上限.因此假设上述2条路段处于拥挤状态，计算得到路段的平衡流量，如表2中情景2下的xa列.情景2下，路段(3,4)达到自由流流量上限，因此进一步假设该路段也进入拥挤交通流状态，即设定新的情景3.情景3的计算表明，路段(1,3)达到自由流流量上限，因此进一步假设该路段也进入拥挤交通流状态，得到情景4.对情景4进行计算，得到结果如表2中情景4下的xa列.此时没有新的路段平衡流量达到自由流流量上限.因此，可以得出网络在完全4级拥挤网络，对应的4级拥挤瓶颈包括路段(1,2)、(3,6)、(3,4)和(1,3).上述 4种情景对应的UE目标函数值分别为544.22、5 418.69、7 131.43和10 362.75.

5 结论

以反λ型流—密—速基本关系图为基础，得到新的两阶段路段行程时间函数，进而建立对应静态交通流分配模型.依据新模型给出了不断更新网络路段交通状态，动态分析网络交通演变的方法.算例分析验证了新模型与分析方法的可行性.理论提供了网络交通流分析的新思路，但理论的完善还有待进一步的实证数据验证.

[1]WARDROP J.Some theoretical aspects of road traffic research[J].Proceedings of the Institution of Civil Engineers,1952,1(36):325-378.

[2]SHEFFI Y.Urban transportation networks:equilibrium analysis with mathematical programming methods[M].New Jersey：Prentice-Hall,1985.

[3]DAFERMOSS C,SPARROW F T.The traffic assignment problem for a general network[J].J.Res.Natl.Bureau Stand.,Ser.B,1969,73(2):91-118.

[4]DAGANZO C F,SHEFFI Y.On stochastic models of traffic assignment[J].Transportation Science,1977,11(3):253-274.

[5]BAR-GERA H.Origin-based algorithm for the traffic assignment problem[J].Transportation Science,2002,36(4):398-417.

[6]何胜学,范炳全.多用户动态交通流分配模型及算法研究[J].上海理工大学学报,2006,28(5):460-464.[HE S X,FAN B Q.Multi user dynamic traffic assignment model and relevant algorithm[J].Journal University of Shanghai for Science and Technology,2006，28(5):460-464.]

[7]何胜学,董琼,徐福缘.基于网络对偶均衡的交通流分配模型[J].公路交通科技，2010,27(9):105-110.[HE S X,DONG J,XU F Y.Traffic assignment model based on network dual equilibrium[J].Journal of Highway and Transportation Research and Development,2010,27(9):105-110.]

[8]何胜学,何建佳,徐福缘.基于网络对偶均衡的有边约束的交通流分配模型[J].交通运输系统工程与信息,2011,11(2):100-105.[HE S X,HE J J,XU F Y.Side constrained traffic assignment model based on network dual equilibrium[J].Journal of Transportation Systems Engineering and Information Technology,2011,11(2):100-105.]

[9]何胜学,李秋曼.考虑边约束的网络交通流分配及应用[J].计算机应用研究,2011,28(7):2595-2598.[HE S X,LIQ M.Side constrained network traffic assignment and application[J].Application Research of Computers,2011,28(7):2595-2598.]

[10]XIE J,XIE C.New insights and improvements of using paired alternative segments for traffic assignment[J].Transportation Research Part B,2016,93(4):406-424.

[11]MA W,QIAN S.On the variance of recurrent traffic flow for statistical traffic assignment[J].Transportation Research Part C,2017,81(1):57-82.

[12]GUO R Y,HUANG H J.A discrete dynamical system of formulating traffic assignment:Revisiting Smith’s model[J].Transportation Research Part C,2016,71(1):122-142.

[13]DAGANZO C F.The cell transmission model:a dynamic representation of highway traffic consistent with the hydrodynamic theory[J].Transportation Research Part B,1994,28(4):269-287.

[14]HE S X.Will a higher free-flow speed lead us to a less congested freeway?[J].Transportation Research Part A，2016,85(1):17-38.