基于成对可替代子路径的交通分配改进算法*

苏焕银，史峰，徐光明

(中南大学交通运输工程学院，湖南长沙410075)

用户均衡(UE)交通分配模型在现实中被广泛运用。当前求解该模型的算法主要有3类:(1)基于路段的交通分配算法，如Frank－Wolfe算法［1］;(2)基于起点的交通分配算法，如Bar－Gera设计了起点算法［2］，Dial等提出了 B 算法［3］，Yu Nie 研究了 Bush算法［4］;(3)基于路径的交通分配算法［5］，如梯度投影算法［6］。该模型主要有 2 个计算难题，一是获取足够精确的路段流量;二是确定符合现实情况的路径流量。根据已有的研究可知，该模型可以确定唯一的路段流量，但无法确定唯一的路径流量。目前的研究工作主要集中在第1个难题上。Bar－Gera设计的基于成对可替代子路径(a pair of alternative segments，PAS)的交通分配算法(TAPAS)［7］能够同时解决上述2个难题，首先建立UE模型和最大熵用户均衡模型(MEUE)，提出成对可替代子路径的概念，并将其作为算法的核心，通过实验分析对比当前的主流交通分配算法，证明了TAPAS算法在运行效率和解的精度方面都具有较强的优势。

TAPAS算法的核心操作是基于PAS，包括构建PAS，管理PAS集合，基于有效的PAS在子路径之间转移流量以均衡子路径费用，在相关起点之间均衡路径流量比例。Bar－Gera［7］提到一个覆盖的PAS集合对于实现PAS的相关起点之间的路径流量的等比例非常重要，然而对于算法的收敛作用甚微。本文旨在提高算法的收敛速度，因此，从该角度出发，可以将算法的核心操作集中于新构建的PAS，保证PAS的有效性，基于新构建的PAS在子路径之间转移流量以均衡子路径费用，在相关起点之间均衡路径流量比例，减少PAS集合的相关操作。根据Bar－Gera［7］对算法收敛性的证明可知，基于有效的PAS进行流量转移可以保证算法的收敛性，因此调整之后的算法仍然是收敛的。详细设计各子模块算法，最后可通过算例验证改进策略对提高算法收敛速度的有效性。

1 符号及概念定义

将研究的区域划分为若干小区，以小区的中心点为点，交通网络可以表示为强连通的有向网络 G={N，A}，其中 N 为点集，A={［u，v］:u，v∈N}为有向弧集(也称为路段集)，假设两点之间最多只有一条路段，任何点到它自身不存在路段，网络的强连通性表示网络中任意2点之间都存在一条有向路径。一条路径是一些不同点构成的序列［v1，…，vk］，并且［vl，vl+1］∈ A，1 ≤ l≤ k － 1，下面提到的路径都是不包含有向圈的路径。路径r的起点记为rt，终点记为rh，特别地，a=［at，ah］∈ A。一条路段 a=［at，ah］和一个单点［v］也都是一条路。

记点i至点j的路径集为Rij。对于子路径s=［i=v1，…，vn=j］与子路径 r=［j=u1，…，um=k］，子路径的包含关系s⊆r表示s是r的子路径，即s为r的一部分。路－弧关联关系由δra表示，若a∈r，其值为1，否则为0。

记起点集为No，起点p∈No对应的终点集为Nd(p)，起点p∈No至终点q∈Nd(p)的交通流(或需求)为dpq，O－D流数组为d，起点p至终点q的路径r∈Rpq上的流量为hr，路径流向量为h。从起点p出发、通过路段a、到达所有终点的路径流量之和称为基于起点的路段流量，|A|乘以|No|维路段流量记为f。所有起点的总路段流量为，总路段流向量为f·。本文对TAPAS算法的核心概念PAS作如下进一步的阐述。

子路径:在一条路径的某些节点处分割路径，分割成的部分即为子路径，一条子路径可由若干相连的路段组成。

一对可替代子路径(PAS):2条子路径若有相同的起始节点和相同的终止节点，且中间节点不同，则称为一对可替代子路径，也称可替代子路径对。起始节点可称为一对可替代子路径的分叉点，终止节点可称为一对可替代子路径的结合点。

等比例就是对于不同起点(或不同终点)的流量在一对可替代子路径上的分配比例是相等的。

2 交通分配模型

交通分配问题(traffic assignment problem，TAP)是根据一定的行为假设，将给定的O－D流分配到指定的路径上。最常见的假设是Wardrop用户均衡准则，该准则下出行者总选择最小费用路径出行。

上述问题的前提假设:O－D流相对于时间是静态的、相对于出行费用是固定不变的。所有出行者的时间价值、货币费用和其它路径贡献度都是等同的，出行者都完全掌握出行决策的相关信息。路径费用为路径上路段费用之和，即 cs=，其中 t=(ta)a∈A表示路段费用向量，依赖于总路段流量反映的拥挤程度。TAP问题能够描述为如下路径流量模型［TAP］(Patriksson［9］):

通过上述模型可以确定用户均衡交通分配的唯一路段流量解f*·，但不能确定唯一的路径流量解 hr，r∈ Rpq。Rossi等［10］证明了最大熵路径流量解却是唯一的。Bar－Gera等［11］提出等比例假设(对于不同起点(或不同终点)的流量在一对可替代子路径上的分配比例是相等的)，解释了按照最大熵原理求出路径流量解的最优条件。Bar－Gera［12］在理论上证明了等比例条件下的路径流量解并不唯一，最大熵原理是等比例的充分不必要条件，即最大熵原理和等比例并不等价。但同时。Bar－Gera［12］在一个现实网络中证明了这2个条件之间的不同点是非常小的。所以可以通过等比例条件求出一组路径流量解，近似的代表最大熵原理下唯一的路径流量解。

建立最大熵用户均衡模型［MEUE］(Bar－Gera［7］):

3 算法设计

3.1 TAPAS 算法

TAPAS算法可以同时求解上述2个模型，该算法的主体思想源于网络流模型(固定路段费用、线性目标函数)的负费用圈优化算法，在用户均衡交通分配问题中，PAS与负费用圈相对应，算法TAPAS关键通过PAS上的操作实施，包括新建、删除PAS及修正PAS的相关起点列表;在当前PAS的子路径之间转移流量，均衡子路径费用;在PAS的相关起点之间均衡路径流量比例。算法过程中存储了PAS，构建了PAS集合。

TAPAS算法的核心操作是在存储的大量PAS中选择PAS集，进而在此PAS集上进行流量转移。虽然在PAS集上的流量转移对相关起点之间的路径流量的等比例分配非常重要，但对于算法的收敛作用却是有限的。

3.2 TAPAS 改进算法

由于很多交通分配问题更加专注于算法的收敛速度，可以考虑仅限于在当前有效的PAS上进行流量转移，减少PAS集合的相关操作。将调整后的算法称为MTAPAS算法。

Bar－Gera构建的算法强调基于PAS集合，认为构建适量的PAS即可，通过不断地在集合内的PAS上进行流量转移以达到费用均衡，然而随着迭代次数的增加，集合中PAS的有效性会降低。注意到当前有效的单一PAS是基于实时的路网流量分布信息获取的，可以实现将非最短路上的流量转移到最短路上，是单次流量转移效率较高的PAS。如果将算法的核心操作仅限于当前有效的单一PAS，可以提高单次流量转移的效率，当然也减小了转移范围。同时，算法结构更简单，编程工作量更小，也有其有利的一面。

基于上述分析，给出MTAPAS算法的具体设计，如算法1。

算法1 MTAPAS算法

开始

赋初值fpa=0，a∈A，PASs={};

进行全有全无分配;

当不满足终止条件时，循环执行。

开始1

对于每个起点p，p∈No，分别执行。

开始2

构建基于起点的非零流路段子网络;

检测子网络中是否有圈流，若有则删除;

构建基于该起点的最短路树Ap;

对于路段a∈A，如果fpa＞0且a∉Ap，执行。

开始3

构造一个有效的PAS;

构建相关起点列表;

执行流量转移操作，以均衡路径费用;

调整相关起点之间路径流量，以满足比例条件。

返回3

返回2

返回1

结束

3.3 关键子算法设计

下面对MTAPAS算法的子算法操作给出详细设计过程。

算法2 有效PAS的构建子算法

输入 路段b=(bt，bh)，起点P，最短路树AP，基于起点的路段流量

输出 PAS=［s1，s2］;

开始

获取路段a，满足ah=bh，a∈AP;

确定从起点P到点bh的最短路径rpbh=［p=u1，u2，…，ul=bh］;

从节点bt沿有流量的路段逆向采用广度优先搜索法搜寻rpbh中的节点;

确定第一个搜索到的节点uk;

从uk沿搜索路径逆向追溯获取uk到bt路径

PAS 的第1 条子路径 s1=［uk，uk+1…，ul］;

PAS的第2 条子路径 s2=［rukbt，bh］;

结束

新构建的PAS都可以保证费用的有效性。流量有效性需要在搜索路径时附加限制条件，即只对流量满足一定条件的路段搜索。假设搜索的路段为c，则要求 fpc≥ k*fpb，k为0到1之间的数值，取值越大可转移的流量越多，因此为了提高流量转移的效率可以取值大一些，但是取值过大时会出现搜索不成功的现象，所以要根据具体实例适当的调整取值。

算法3 基于PAS的流量转移子算法

输入 PAS=［s1，s2］，PAS的相关起点列表LPAS;f=［fpa］，p∈ No，a ∈ A;

开始

从s2上可转移到s1上的最大流量为δmax=

对于p∈LPAS，循环执行，

开始1

δp=k·mina⊆s2fpa;

fpa=fpa+ δp，a ⊆ s1;

fpa=fpa－ δp，a ⊆ s2;

结束1

结束

因为在构建PAS时就确定了s1在最短路树上，所以流量确定从s2上转移到s1上，然而TAPAS算法中转移流量之前需要确定流量转移的方向。所以该算法中的流量转移要简单许多，且本算法采用二分法计算转移流量的最佳取值，分化的次数可以根据算法当前收敛的精度动态确定。

算法4 基于PAS的相关起点之间均衡路径流量等比例分配子算法

输入 PAS=［s1，s2］，PAS的相关起点列表LPAS，基于起点的路段流量矩阵f=［fpa］，p∈No，a∈A

输出 基于起点的路段流量矩阵f=［fpa］，p∈ No，a ∈ A

开始

k1=0，k2=0;

对于p∈LPAS，循环执行

开始1

结束1

计算方程k1ρ2－k2ρ+k2=0的根ρ;

对于p∈LPAS，循环执行，

开始2

结束2

结束

up为基于起点 p需要调整的流量，Bar－Gera［7］建议采取 up的二次逼近函数，推导出 U(ρ)的二次函数形式，因为，所以本文设计，满足上述2个条件。所有的流量调整之和为0，所以只需求解U(ρ)=0的根即可。

4 数值试验分析

以常用的Sioux Falls测试网络为示例进行数值试验，该网络划分了24个小区，共包含24个节点，76个路段，528个OD对，具体结构如图1所示，详细的数据可以从 Bar－ Gera(2001)［13］获取。采用Matlab编程，并与 TAPAS算法进行比较分析，结果见图2。

图1 Sioux Falls测试网络Fig.1 Sioux Falls test network

图2 相应收敛水平下CPU时间Fig.2 CPU time required to achieve desired levels of convergence

由图2可知，对于Sioux Falls测试网络，相比TAPAS算法，MTAPAS算法的收敛速度有一定的提高，当收敛精度在10－12以内时优势明显，特别是当精度在10－8以内时的收敛速度比TAPAS算法快2倍左右。

Sioux Falls测试网络是比较典型的交通测试网络，在该网络上验证了算法仅仅在当前PAS上转移流量具有更高的效率，只说明存在这种可能，在部分例子中仅仅在当前PAS上转移流量不会降低其效率。

5 结论

(1)对TAPAS算法的主体算法结构做出调整，将算法的核心操作仅限于当前有效的单一PAS上，减少PAS集合的相关操作。

(2)详细设计了包括有效PAS构建子算法、基于PAS的流量转移子算法和基于PAS在相关起点之间均衡路径流量等比例分配子算法。

(3)通过对Sioux Falls测试网络计算分析，我们认为，在部分例子中仅仅在当前PAS上转移流量不会降低算法的效率。

(4)由于避免了大量PAS的存储、管理以及PAS集上的流量转移，算法结构更简单，编程工作量更小。

［1］张欢，卢毅，朱东铁.基于用户均衡分析的公路超限车辆补偿费率优化模型［J］.铁道科学与工程学报，2012，9(6):84 －89.

ZHANG Huan，LU Yi，ZHU Dongtie.Optimization model on highway reimbursement rate of oversize vehicles with user equilibrium analysis［J］.Journal of Railway Science and Engineering，2012，9(6):84 －89.

［2］史峰，王英姿，徐光明，等.考虑支路路段双向车流相互影响的单向交通组织优化［J］.铁道科学与工程学报，2012，9(2):66 －71.

SHI Feng，WANG Yingzi，XU Guangming，et al.Optimization approach for one－way traffic organization with bi－directional flow’s effect of local road［J］.Journal of Railway Science and Engineering，2012，9(2):66 －71.

［3］LeBlanc L J，Morlok E K，Pierskalla W P.An efficient approach to solving the road network equilibrium traffic assignment problem［J］.Transportation Research，1975，9(5):309－318.

［4］周和平，胡列格，晏克非.基于模糊路段流量的OD反推的不确定规划模型与算法研究［J］.铁道科学与工程学报，2005，43(1):68 －74.

ZHOU Heping，HU Liege，YAN Kefei.Uncertain programming model and algorithm for estimating origindestination matrices based on fuzzy link flow［J］.Journal of Railway Science and Engineering，2005，43(1):68 －74.

［5］Bar－Gera H.Origin－based algorithm for the traffic assignment problem［J］.Transportation Science ，2002，36(4):398－417.

［6］Dial R B.A path－based user－equilibrium traffic assignment algorithm that obviates path storage and enumeration［J］.Transportation Research Part B，2006，40(10):917－936.

［7］许项东，程琳，邱松林.交通分配自适应梯度投影算法的敏感性分析［J］.东南大学学报(自然科学版)，2013，43(1):226 －230.

XU Xiangdong，CHENG Lin，QIU Songlin.Sensitivity analysis of self－adaptive gradient projection traffic assignment algorithm［J］.Journal of Southeast University(Natural Science Edition)，2013，43(1):226－230.

［8］Bar－Gera H.Traffic assignment by paired alternative segments［J］.Transportation Research Part B，2010，44:1022－1046.

［9］Patriksson M.The traffic assignment problem models and methods［R］.VSP，Utrecht，Netherlands，1994.

［10］Rossi T F，McNeil S，Hendrickson C.Entropy model for consistent impact fee assessment［J］.Journal of Urban Planning and Development/ASCE ，1989，115(2):51－63.

［11］Bar－Gera H，Boyce D.Route flow entropy maximization in origin － based traffic assignment［C］//Ceder，A.(Ed.).Proceedings of the 14th International Symposium on Transportation and Traffic Theory，Jerusalem，Israel，Elsevier Science，Oxford，UK，1999:397 －415.

［12］Bar－Gera，H.Primal method for determining the most likely route flows in large road networks［J］.Transportation Science，2006，40(3):269 －286.

［13］Bar－Gera H.Transportation network test problems［EB/OL］.2001.ww.bgu.ac.il/～ bargera/tntp ＞.