大规模道路交通量分配的节点分配算法

高明瑶，石红国

大规模道路交通量分配的节点分配算法

高明瑶，石红国

（西南交通大学，交通运输与物流学院，成都 611756）

针对传统的多路径-容量限制分配算法速度慢, 效率低下, 且在大规模交通路网中难以应用的缺陷, 本文提出其简化算法—— 节点分配算法, 通过将讫点相同的OD对进行列的合并, 每次批量分配讫点相同的所有OD对, 来加速分配过程, 同时考虑道路阻抗在道路流量变化时的修正, 将OD矩阵分成个子矩阵分次进行分配, 每次分配一个OD矩阵, 分配一次, 路阻修正一次。最后给出算例并分析了此方法的效果与优势。

交通分配; 多路径-容量限制法; 节点分配法; 大规模路网; 路阻

0 引 言

目前四阶段模型是国内外应用最多的交通规划模型，主要分为四个阶段：出行生成、出行分布、方式划分与交通分配。作为四阶段法的最后一个步骤，交通分配是将前三个阶段得到的出行OD 矩阵分配到路网上，交通分配的结果可以为相关的决策者制定相应的道路交通控制与管理措施提供量化依据。而交通分配的方法也一直吸引着众多国内外学者对其进行研究。参考文献[1-4]采用动态交通规划的方法来描述动态交通流分配的问题，将其转化为静态的系统最优分配模型。参考文献[5-12]通过变分不等式建立了均衡交通分配公式，采用了逐次平均法（MSA），通过求解一个动态程序，在每次迭代过程中生成策略。在上述研究中，不难看出，目前针对交通量分配的方法集中于均衡分配法和迭代计算，该类方法在交通网络规模较小的时候很有效，但是当面对大规模的交通网络时，计算量巨大，因此迫切需要对上述方法进行深入探究，优化传统的流量分配方法。参考文献[13]中对多路径交通分配模型的改进得到节点分配算法，提高了运算效率。参考文献[14-18]通过城市轨道交通的AFC数据对乘客的出行路径进行研究，得到城市轨道交通客流量分配的结果。

1 交通分配中的相关概念

1.1 道路阻抗

在交通规划四阶段法中的交通分配阶段，在对交通量进行分配时，需要依据各个路段的阻抗。随着分配过程的进行，各个路段的交通量发生着变化，因此需要对路阻进行修正，常用的修正方法是根据行驶时间和路段交通量之间的关系，即根据路阻函数确定。最为常见的路阻函数就是美国联邦公路局函数（BPR函数）[13]，其具体公式为：

1.2 有效路段

1.3 有效出行路线

2 交通分配模型与方法

交通分配是交通规划中四阶段法的一个重要步骤，它是将出行分布（OD）矩阵按照现有的或者规划中的路网分配到各条道路上，从而推测各道路上的流量。

目前，国内外交通流分配模型大体上可以分为平衡分配与非平衡分配模型两大类，其中平衡分配法是指分配模型满足Wardrop第一、二原理的方法。Wardrop第一原理也被称为用户最优平衡原理（User Optimized Equilibrium），其内容为：在考虑拥挤对行驶时间影响的交通流网络中，当网络达到平衡状态时，每个OD对的各条被使用的径路具有相同且最小的行驶时间；没有被使用的径路的行驶时间大于或等于最小行驶时间。Wardrop第二原理也被称为系统最优平衡原理（System Optimized Equilibrium），其内容为：车辆在交通流网络中的分配使得网络上所有车辆的总出行时间最小，从而达到系统最优。

目前，由于非平衡分配模型计算量大，难以应用，因此现实中使用的交通分配模型主要为非平衡分配模型，主要包括：最短路交通流分配法、容量限制交通流分配法、多路径概率交通流分配法。

最短路分配法是将每个OD点对的交通量全部分配到连接该OD点对之间的最短路径上，该OD对间其余的路径不分配交通量，即交通流为0。该法使用过程中的主要特点是不考虑路段通行能力的限制，也不考虑交通量对道路路阻的影响，因此也被称为容量非限制分配法或全有全无分配法[7]。

容量限制交通流分配法是将交通量全部分配到交通区之间的最短路上，不过，容量限制分配法的路阻考虑了路段交通量对车辆行驶速度的影响，在实际操作过程中，将OD矩阵分成个子矩阵，即将其分成次进行分配，同时考虑道路阻抗在道路流量变化时的修正，每分配一次，路阻修正一次，直到个子矩阵全部分配完毕。

多路径分配法是将OD量分配到各条出行路线上，与单路径分配不同的地方在于，OD量会被分配到每一条道路上，各条出行路线被选择的概率取决于各条出行路线的效用（一般为出行时间或者出行距离的倒数）。

相较于单路径交通流分配方法，多路径交通流分配法的优点是修正了单路径分配中OD对间流量全部集中于该OD对间最短路这一不合理现象，所有可能的出行路线均分配到交通量，与实际情况相符合，因为出行者在出行过程中会根据道路实时的交通状况不断更改自己的出行路线选择。Dial于1971年提出了初始的概率分配模型，模型反映了出行路线被选用的概率随着线路长度的增加而减少的规律。Florian和Fox于1976年对Dial模型进行了修正，认为出行者在某一OD对间选择路线的概率为：

对于简单的道路网，可以枚举其可能路线，但是对于复杂的大规模路网，Dial模型没有办法解决。本文通过对多路径模型进行改进可以给出该问题的解。理性的出行者出行会选择出行效用最大的出行路线（通常表现为出行时间最短），出行者从某出行起点到对应的出行终点，需经过一连串的交通节点（一般交叉口），每经过任一交叉口，都会在该交叉口所邻接的有效路段中选择其中一条路段作为他的下一条出行路线，继续前进。在每一交叉口处，可供出行者选择的有效出行路线条数等于该交叉口所有有效出行路段个数之和[19]。

在实际出行过程中，每一路段的路阻并不是固定的，而是时时刻刻随着道路流量的变化而变化，随着道路流量越来越大，道路的路阻也越来越大，因此对交通量在实际路网中进行分配的时候，理应考虑路阻与交通负荷之间的关系，故采用多路径—容量限制分配法更为合理。

3 多路径-容量限制分配法的改进

3.1 多路径-容量限制分配法的节点分配法

在实际出行时，考虑每个出行者对于出行路线的选择只与出行终点有关系，即出行者在节点（交叉口）进行决策时不会考虑自己来自哪个节点，而是考虑选择哪个后续节点使得从当前位置到目的地的路权最小[20]。因此，对于一个OD矩阵，无需同时对所有的OD量进行分配，而是只需要将终点相同的所有OD量进行合并，对合并之后的OD量进行统一的分配，这一过程可以大大地减少交通量分配的工作量，加速分配过程，提高分配效率，因此更适用于大规模路网的交通量分配。同时，考虑到道路阻抗随道路流量的变化，因此，在进行实际的交通量分配时，将OD矩阵分成个子矩阵，分次进行分配，每次分配按照多路径分配的原则进行，每分配一次，路阻修正一次，直到个OD矩阵分配完毕。

3.2 路网中节点的分配次序

对于改进的多路径-节点分配法，在进行道路交通量的分配时，由于将到达各个节点的总流量进行统一的分配，因此需要确定各个节点的分配次序，由前文可知，任一节点的后续节点必然更接近于终点（否则构不成有效路段），因此在对某一节点进行分配时，需要确保除了该节点之外的所有节点与该节点均构成有效路段，也就是说，在该节点之前被分配的节点与该节点均构不成有效路段。按照上述步骤，即可确定所有节点的分配次序，如果开始时路网中存在多个可以同时进行分配的节点，可以任选其一。

4 算法实例

道路网络如图1所示，节点代表交叉口，路段上的数字代表路阻（行驶时间），各个交通节点至交通节点（终点）3的OD量如表1所示（该OD是将原始各个节点间的OD按照列叠加求得），现用上述基于多路径-容量限制的节点分配法分配该OD表。

图1 待分配道路网

表1 各个节点至节点5的OD量

将OD表分成三个子OD矩阵进行分配，每次按照多路径模型进行分配，每分配一次，路阻修正一次，直到把三个子OD矩阵分配完毕。

（1）第一次分配

第一次分配的OD矩阵见表2所示，分配结果如表3所示。

表2 第一次分配的子OD矩阵

表3 第一次分配的结果

第一次分配后进行路阻修正，如图2所示。

图2 第一次修正路阻后的道路网

（2）第二次分配

第二次分配的OD矩阵及分配结果如表4、表5所示。

表4 第二次分配的OD矩阵

表5 第二次分配的结果

第二次分配后进行路阻修正，如图3所示。

图3 第二次分配后的路阻修正

（3）第三次分配

第三次分配的OD矩阵和分配结果如表6和表7所示。

表6 第三次分配的OD矩阵

表7 第三次分配的结果

通过对上述表格进行简要分析，运用多路径-容量限制分配法的改进算法—— 节点分配法，对路网的交通量进行分配可以将终点相同的OD量进行合并，批量分配，经过三次的分配计算就得到最终的结果，即各条道路上最终的交通量，与此前已经广泛使用的算法相比较，将九次分配过程简化为三次，计算量减少了三分之一，本文的算例道路网规模并不是很大，优越性体现并不十分明显。综上，这种算法大大加速了交通量的分配过程，使得复杂的交通分配过程大大简化，交通分配的计算量同时大大减少，因此该算法可以应用于中型规模的道路交通量分配。

5 结论与展望

本文基于多路径-容量限制分配法的改进算法—— 节点分配法，对路网的交通量进行分配，并给出算例，结果表明，该分配方法将终点相同的OD量进行合并，批量分配，可以加速分配过程，将分配的计算量减少为原来的1/，为OD矩阵第一维的值。本文中算例仅仅考虑了道路流量对路阻的影响，而没有考虑到实际道路上的突发事件等对其交通量分配的影响，这些还有待后续的研究。

[1] MERCHANT D K. A model nemhauser G L. and an algorithm for dynamic traffic assignment problems[J]. Transportation Science, 1978, 12(3): 183-199.

[2] UKKUSURI S V, WALLERS T. Linear programming models for the user and system optimal dynamic network design problem: formulations, comparisons and extensions[J]. Networks and Spatial Economics, 2008, 8(4): 383-406.

[3] FRIESZT T L, LUQUE J, TOBIN R L, et al. Dynamic network traffic assignment considered as a continuous time optimal control problem[J]. Operations Research, 1989, 37(6): 893-901.

[4] 任华玲, 高自友. 动态交通分配中一种离散VI模型的算法研究[J]. 土木工程学报, 2004, 3(3): 105-108.

[5] NGUYEN S, PALLOTTINO S. Equilibrium traffic assignment for large scale transit networks[J]. EuropeanJournal of Operational Research, 1988, 37(2): 176-186.

[6] 杜学东, 四兵峰. 基于随机均衡配流的O-D量估计双层规划模型及算法[J]. 山东科技大学学报, 2005, 24(3): 86-89.

[7] ZHOU Xuesong, HANI S, Mahmassani, ZHANG Kuilin. Dynamic micro-assignment modeling approach for integrated multimodel urban corridor management[J]. Transportation Research Part C, 2008, 16: 167-186.

[8] 黄志远, 周峰, 徐瑞华. 基于多路径可达的城市轨道交通网络考虑负载均衡方法[J]. 武汉理工大学学报, 2018, 4(3): 430-434.

[9] YOUNES H W, HAMDOUCH H. Schedule-based transit assignment model with vehicle capacity and seat availability [J]. Transportation Research Part B, 2008. 45(10), 1805- 1830.

[10] VERBAS Ö, MAHMASSANI H S, HYLAND M F. Gap-based transit assignment algorithm with vehicle capacity constraints: simulation-based implementation and large-scale application[J]. Transportation Research Part B, 2016, 93, 1-16.

[11] COMINETTI R, Correa J. Common-lines and passenger assignment in congested transit networnsportation Science, 2001, 35(3), 250-267.

[12] CEPEDA M, COMINETTI R, FLORIAN M. A frequency- based assignment model for congested transit networks with strict capacity constraints: characterization and computation of equilibria[J]. Transportation Research Part B, 2006, 40, 437-459.

[13] 王炜. 多路径交通分配模型的改进及节点分配算法[J]. 东南大学学报, 1994(6): 21-26.

[14] 吴丽娟. 基于AFC数据的城市轨道交通网络乘客出行路径匹配及突发事件影响研究[D]. 北京: 北京交通大学, 2016.

[15] 许胜博. 基于票务信息的城市轨道交通客流实时测算问题研究[D]. 成都: 西南交通大学, 2017.

[16] 褚耀程. 前景理论下路径选择行为参考点选取问题研究[D]. 成都: 西南交通大学, 2017.

[17] 李原. 城市轨道交通网络换乘客流分配研究[D]. 成都: 西南交通大学, 2017.

[18] 吴正阳. 城市轨道交通网络客流分配理论与控制技术研究[D]. 成都: 西南交通大学, 2018.

[19] 邵春福. 交通规划原理[M]. 北京: 中国铁道出版社, 2008.

[20] 高自友, 任华玲. 城市动态交通流分配模型与算法[M]. 北京: 人民交通出版社, 2005.

Node Assignment Approach for Large-scale Road Traffic Allocation

GAO Ming-yao, SHI Hong-guo

( School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 611756, China )

The traditional multi-path capacity limited allocation algorithm is slow, inefficient, and difficult to apply to large-scale traffic networks. To address this issue, this paper proposes a simplified algorithm for accelerating the allocation process by merging the origin-destination (OD) pairs with the same destination and allocating all OD pairs with the same destination in each batch. Simultaneously, considering the modification of road impedance caused by the changes in road flow, the OD matrix is divided intosubmatrices. One OD matrix is allocated at a time and the road resistance is corrected once per assignment. Finally, an example is provided, and the assignment results are analyzed; thus, the advantages of the method are highlighted.

traffic assignment; multi-path capacity restriction method; node allocation method; large-scale road network; road resistance

1672-4747（2020）02-0119-06

U49.1+4

A

10.3969/j.issn.1672-4747.2020.02.014

2019-04-07

国家自然科学基金（61803314）

高明瑶（1996—），女，汉族，江苏扬州人，硕士研究生，研究方向为交通运输规划与管理，E-mail：17851101369@163.com

高明瑶，石红国. 大规模道路交通量分配的节点分配算法[J]. 交通运输工程与信息学报, 2020, 18（2）：119-124.

（责任编辑：刘娉婷）