基于有效路径集逐步生成的网络交通流分配方法

何胜学

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

0 引 言

有效的交通流分配有助于设计有效的交通信号控制方案、完善交通基础设施建设、提升交通诱导信息质量.实现网络交通流分配的方法大致可分为基于路段的配流方法和基于路径的配流方法.由于现实中一般很难预知所有的有效路径，因此基于路径的交通流分配方法一般用于小规模的路网和理论分析.而等价的基于路段的交通流分配方法则在各类实践中被广泛应用.与基于路段的配流方法相比，基于路径的配流方法具有更强的解释性，其配流结果更加直观，因此更方便被用于其他领域.本文将尝试解决基于路径配流方法面临的有效路径集合一般无法提前预知的难题，并针对投影集合特征，改进投影梯度类算法的投影操作效率.

在解决无法预知有效路径集方面，最常见的处理方法是将有效路径行程时间或出行费用限定在一定范围，例如，限定在当前最短路径对应值的一个倍数范围之内[1-2].文献[3-4]提出了一些方法来确定上述的有效路径.何胜学等[5]提出利用起讫点对的相对位置，模拟重力场，利用水流的流动确定给定起讫点对间的有效路径集.另一个常用方法是直接利用图论中的K最短路方法搜索有效路径集合.在基于路段的交通流分配结束后，文献[6-7]提出了利用线路流量持续分解得到任意起讫点对间实际被选路径的一种有效方法.另一种常用方法是记录在执行“全有全无”步骤时产生的最短路，将其作为最终的有效路径集合元素[8].与上述研究不同，本文将结合基于路径的交通流分配方法，在算法的执行过程中逐步生成有效路径集合，并在算法收敛时得到实际被选用的路径集合、对应的路径流量和路径出行费用.

基于路径的交通流分配方法中，最常用是投影梯度类算法.而该类算法的核心步骤是进行投影操作.为了提升投影操作的效率，本文将摒弃求解投影的二次规划类经典方法，针对投影集合的特征设计一个无需迭代可一次性确定投影精确解的有效算法，并通过数值试验验证新方法的有效性.

1 基于路径的交通流分配模型

1.1 基本参变量

W为交通网络中的起讫点对集合；w为交通网络一个典型起讫点对(OD对)，w∈W；dw为OD对w间的交通出行需求量；Rw为OD对w间所有有效路径集合；Pw为OD对w间已知的有效路径集合；p为交通路网中的一条路径；xw,p为连接OD对w的路径p上的路径流量；cw,p为连接OD对w的路径p的出行费用，一般指路径的行程时间；x为由所有有效路径流量组成的网络路径流向量，称为网络路径流量模式；ΠQ(·)为向集合Q进行投影操作；*为上标，指示对应的量为网络流量处于平衡状态时的对应量值.

1.2 网络交通流平衡分配模型

根据经典交通流分配理论，网络交通流处于平衡状态时应满足Wardrop第一原则，即用户均衡原则[9].Wardrop第一原则表明当网络流处于平衡状态时，任一OD对间实际被选用的出行路径具有相同且最小的出行阻抗，而未被选取的路径阻抗均大于或等于上述阻抗.路径行程时间是一种常用的路径出行阻抗.

(1)

将对应OD对w间的所有有效路径上的上述不等式加和，可得：

(2)

可对(2)作如下的代数计算：

(3)

考虑到任意可行流量模式x与平衡条件下的流量模式x*均须满足∑p∈Rwxw,p=dw，因此

(4)

将对应所有OD对的不等式(4)加和，得到最终的网络流平衡模型为

(5)

(6)

xw,p≥0，∀w∈W,p∈Rw

(7)

式(5)为平衡路径流需要满足的变分不等式；式(6)为路径流量在OD对上的流量守恒约束；式(7)为路径流量的非负约束.

2 求解算法

2.1 基于有效路径集逐步生成的修正投影梯度算法

在有效路径集合逐步生成条件下，对经典的修正投影算法加以改进，得到求解问题(5)的算法步骤如下.

(8)

xw,p≥0，∀w∈W,p∈Pw

(9)

在约束集合Qw上，进行如下的投影.

(10)

(11)

步骤3如果|xk+1-xk|≤θ，算法终止；否则，令k:=k+1，转步骤2.

如果将投影操作(7)和(8)用下面的单一投影操作代替，

(12)

上面的修正投影梯度算法就变成了经典投影梯度算法.一般而言，修正投影梯度算法比投影梯度算法要求的算法收敛条件低，但是计算量相对较大.

2.2 算法的有效性证明

定理1当2.1给出的修正投影梯度算法(或投影梯度算法)收敛时，得到的路径流量在整个交通路网上满足Wardrop第一原则.

证明设OD对w间的所有有效路径集合为Rw，当前已知的OD对w间的所有有效路径集合为Pw.Rw与Pw之间的关联机制如下：在xk流量模式下，得到OD对w间的一条最短路径pw；如果pw∉Pw，则令Pw:=Pw∪{pw}，xw,pw=0；否则，Pw保持不变.

如果在执行第k+1次迭代时，Pw保持不变，那么根据投影理论[10]，在集合Pw上，Wardrop第一原则成立；而此时，集合Rw-Pw中所有路径流量为0，而且其中的最短路径出行费用与Pw中最短路径的出行费用相等，因此可以看出在Rw上Wardrop第一原则依然成立.

2.3 内嵌的投影精确解确定方法

在2.1的相关投影梯度算法中，需要反复进行投影操作.如果采用常见的二次规划算法求解该投影子问题，一般需要较多的迭代计算才能得到满意的投影结果.为了提高投影操作效率，针对投影的具体集合特征，下面给出一个无需迭代的投影精确解确定方法.

观察可知2.1的相关投影梯度算法可分别针对不同的OD对进行，而对于任一给定OD对w，需要在其上进行投影的集合具有如下形式.

(13)

xw,p≥0，∀p∈Pw

(14)

(15)

式中：集合X={x=(x1,x2,…,xn)|∑ixi=D且xi≥0,∀i=1,2,…,n}.

首先分析如何求解问题(11).由下面的简单代数计算.

(16)

(17)

(18)

定理2问题(11)与问题(14)等价.

证明问题(13)的目标函数：

问题(14)的目标函数.

由上面的计算可知，具有相同约束集合的问题(13)与问题(14)的目标函数仅相差一个常数项，因此两者等价.而已知问题(11)与问题(13)等价，因此问题(11)与问题(14)等价.

图1为对应问题(14)的交通流分配网络.其中起点r到终点s的总流量为D；连接起点r和终点s有n条路径，其中路径i的流量和行程时间函数分别表示为xi和xi+bi.根据经典交通流分配理论，问题(14)是对应图(1)中路网的用户均衡配流模型.而用户均衡配流模型的最优路径流量需满足Wardrop第一原则.依据Wardrop第一原则，可以设计求解问题(14)的无迭代精确解算法.

图1 问题(14)对应的交通流分配网络

算法的基本思路简述如下.假设b1≤b2≤…≤bn成立；否则，对b中元素加以重新排序与编号，使其满足上述条件.接下来确定路径流量，具体思路如下：出行者首先选择路径1(对应路径阻抗x1+b1)；而当在该路径上的当前流量x10满足：x10+b1=b2时，出行者将同时选择路径1和路径2(对应路径阻抗x2+b2)出行，并保持两条路径的出行阻抗相等；而当两条路径上的当前流量满足x10+x20+b1=x20+b2=b3时，出行者将选择路径1，2，3同时出行，并保持三条路线的出行阻抗相等.上述操作可以持续进行，直到所有流量被加载上网.

具体的路径流量确定步骤总结如下．

步骤1依次考虑路径1，2，…,n；设当前的路径为i.

步骤2如果i+1≤n，令：xi0=bi+1-bi.

xj:=xj+xi0，∀j=1,2,…,i；

很多学生在参与中长跑活动后会出现一些副作用，包括胸闷、气短、脸色发白等，这些副作用让学生对中长跑活动存有一定的抵触心理。所以教师要云用合适的方法引导学生去“善后”，帮助学生去可致不良反应，这样能够让学生环节对中长跑活动的为难心理。如教师可以带领学生做一些保健按摩、放松操，适当的做一些简单的轻松的小游戏等，让学生对中长跑活动不再抵触。

xj:=0，∀j∈{k|k>i}.

步骤3如果i=n，进行如下路径流量更新.

3 算例分析

图2 具有13个节点的交通网络

表1的流量列情景1列出了基于路段的Frank-Wolfe算法的路段流量解，情景2列出了基于有效路径逐步生成的梯度投影算法的路段流量解.通过对比可知，两种算法得到的路段流量基本一致，证实了新方法的有效性.

表1 路段行程时间函数的参数和均衡流量

表2 已知有效路径均衡流量和行程时间

从结果可以看出除了OD对(1,4)之间有两条有效路径被实际选用，其他OD对间均只有一条有效路径被选用.表中的路径流量和行程时间符合Wardrop第一原则.

新算法的迭代终止阀值θ设为0.000 5，算法执行254次终止.同样阀值下，Frank-Wolfe算法执行136次终止.在不同阀值和OD需求量条件下，两种算法的执行次数表现差异较大，两者间不存在必然的优劣关系.在基于路段的Frank-Wolfe法流量分配结束后，计算各OD对间最短路的行程时间，结果为：对应OD对(1,3)、(1,4)、(2,3)和(2,4)的最短行程时间分别为30.288、54.050、48.024和40.873.上述结果与表2中各OD对间最短行程时间比较，可知两者基本一致.

4 结 束 语

通过在投影梯度类算法执行过程中，不断搜索各OD对间的最短路径，逐步扩展各OD对之间可选的有效路径集合，从而实现在算法收敛条件下有效路径集合的构建和网络交通流量分配.通过问题形式的转化，可以将算法中的投影操作转化为一个简单路网上的流量分配问题，进而设计了求解投影的无迭代精确算法.通过解决上述两个问题，可以使传统的基于路径的网络交通流分配方法更有效地应用于实际.