大規(guī)模道路交通量分配的節(jié)點(diǎn)分配算法

高明瑤，石紅國(guó)

大規(guī)模道路交通量分配的節(jié)點(diǎn)分配算法

高明瑤，石紅國(guó)

（西南交通大學(xué)，交通運(yùn)輸與物流學(xué)院，成都 611756）

針對(duì)傳統(tǒng)的多路徑-容量限制分配算法速度慢, 效率低下, 且在大規(guī)模交通路網(wǎng)中難以應(yīng)用的缺陷, 本文提出其簡(jiǎn)化算法—— 節(jié)點(diǎn)分配算法, 通過(guò)將訖點(diǎn)相同的OD對(duì)進(jìn)行列的合并, 每次批量分配訖點(diǎn)相同的所有OD對(duì), 來(lái)加速分配過(guò)程, 同時(shí)考慮道路阻抗在道路流量變化時(shí)的修正, 將OD矩陣分成個(gè)子矩陣分次進(jìn)行分配, 每次分配一個(gè)OD矩陣, 分配一次, 路阻修正一次。最后給出算例并分析了此方法的效果與優(yōu)勢(shì)。

交通分配; 多路徑-容量限制法; 節(jié)點(diǎn)分配法; 大規(guī)模路網(wǎng); 路阻

0 引 言

目前四階段模型是國(guó)內(nèi)外應(yīng)用最多的交通規(guī)劃模型，主要分為四個(gè)階段：出行生成、出行分布、方式劃分與交通分配。作為四階段法的最后一個(gè)步驟，交通分配是將前三個(gè)階段得到的出行OD 矩陣分配到路網(wǎng)上，交通分配的結(jié)果可以為相關(guān)的決策者制定相應(yīng)的道路交通控制與管理措施提供量化依據(jù)。而交通分配的方法也一直吸引著眾多國(guó)內(nèi)外學(xué)者對(duì)其進(jìn)行研究。參考文獻(xiàn)[1-4]采用動(dòng)態(tài)交通規(guī)劃的方法來(lái)描述動(dòng)態(tài)交通流分配的問(wèn)題，將其轉(zhuǎn)化為靜態(tài)的系統(tǒng)最優(yōu)分配模型。參考文獻(xiàn)[5-12]通過(guò)變分不等式建立了均衡交通分配公式，采用了逐次平均法（MSA），通過(guò)求解一個(gè)動(dòng)態(tài)程序，在每次迭代過(guò)程中生成策略。在上述研究中，不難看出，目前針對(duì)交通量分配的方法集中于均衡分配法和迭代計(jì)算，該類方法在交通網(wǎng)絡(luò)規(guī)模較小的時(shí)候很有效，但是當(dāng)面對(duì)大規(guī)模的交通網(wǎng)絡(luò)時(shí)，計(jì)算量巨大，因此迫切需要對(duì)上述方法進(jìn)行深入探究，優(yōu)化傳統(tǒng)的流量分配方法。參考文獻(xiàn)[13]中對(duì)多路徑交通分配模型的改進(jìn)得到節(jié)點(diǎn)分配算法，提高了運(yùn)算效率。參考文獻(xiàn)[14-18]通過(guò)城市軌道交通的AFC數(shù)據(jù)對(duì)乘客的出行路徑進(jìn)行研究，得到城市軌道交通客流量分配的結(jié)果。

1 交通分配中的相關(guān)概念

1.1 道路阻抗

在交通規(guī)劃四階段法中的交通分配階段，在對(duì)交通量進(jìn)行分配時(shí)，需要依據(jù)各個(gè)路段的阻抗。隨著分配過(guò)程的進(jìn)行，各個(gè)路段的交通量發(fā)生著變化，因此需要對(duì)路阻進(jìn)行修正，常用的修正方法是根據(jù)行駛時(shí)間和路段交通量之間的關(guān)系，即根據(jù)路阻函數(shù)確定。最為常見(jiàn)的路阻函數(shù)就是美國(guó)聯(lián)邦公路局函數(shù)（BPR函數(shù)）[13]，其具體公式為：

1.2 有效路段

1.3 有效出行路線

2 交通分配模型與方法

交通分配是交通規(guī)劃中四階段法的一個(gè)重要步驟，它是將出行分布（OD）矩陣按照現(xiàn)有的或者規(guī)劃中的路網(wǎng)分配到各條道路上，從而推測(cè)各道路上的流量。

目前，國(guó)內(nèi)外交通流分配模型大體上可以分為平衡分配與非平衡分配模型兩大類，其中平衡分配法是指分配模型滿足Wardrop第一、二原理的方法。Wardrop第一原理也被稱為用戶最優(yōu)平衡原理（User Optimized Equilibrium），其內(nèi)容為：在考慮擁擠對(duì)行駛時(shí)間影響的交通流網(wǎng)絡(luò)中，當(dāng)網(wǎng)絡(luò)達(dá)到平衡狀態(tài)時(shí)，每個(gè)OD對(duì)的各條被使用的徑路具有相同且最小的行駛時(shí)間；沒(méi)有被使用的徑路的行駛時(shí)間大于或等于最小行駛時(shí)間。Wardrop第二原理也被稱為系統(tǒng)最優(yōu)平衡原理（System Optimized Equilibrium），其內(nèi)容為：車輛在交通流網(wǎng)絡(luò)中的分配使得網(wǎng)絡(luò)上所有車輛的總出行時(shí)間最小，從而達(dá)到系統(tǒng)最優(yōu)。

目前，由于非平衡分配模型計(jì)算量大，難以應(yīng)用，因此現(xiàn)實(shí)中使用的交通分配模型主要為非平衡分配模型，主要包括：最短路交通流分配法、容量限制交通流分配法、多路徑概率交通流分配法。

最短路分配法是將每個(gè)OD點(diǎn)對(duì)的交通量全部分配到連接該OD點(diǎn)對(duì)之間的最短路徑上，該OD對(duì)間其余的路徑不分配交通量，即交通流為0。該法使用過(guò)程中的主要特點(diǎn)是不考慮路段通行能力的限制，也不考慮交通量對(duì)道路路阻的影響，因此也被稱為容量非限制分配法或全有全無(wú)分配法[7]。

容量限制交通流分配法是將交通量全部分配到交通區(qū)之間的最短路上，不過(guò)，容量限制分配法的路阻考慮了路段交通量對(duì)車輛行駛速度的影響，在實(shí)際操作過(guò)程中，將OD矩陣分成個(gè)子矩陣，即將其分成次進(jìn)行分配，同時(shí)考慮道路阻抗在道路流量變化時(shí)的修正，每分配一次，路阻修正一次，直到個(gè)子矩陣全部分配完畢。

多路徑分配法是將OD量分配到各條出行路線上，與單路徑分配不同的地方在于，OD量會(huì)被分配到每一條道路上，各條出行路線被選擇的概率取決于各條出行路線的效用（一般為出行時(shí)間或者出行距離的倒數(shù)）。

相較于單路徑交通流分配方法，多路徑交通流分配法的優(yōu)點(diǎn)是修正了單路徑分配中OD對(duì)間流量全部集中于該OD對(duì)間最短路這一不合理現(xiàn)象，所有可能的出行路線均分配到交通量，與實(shí)際情況相符合，因?yàn)槌鲂姓咴诔鲂羞^(guò)程中會(huì)根據(jù)道路實(shí)時(shí)的交通狀況不斷更改自己的出行路線選擇。Dial于1971年提出了初始的概率分配模型，模型反映了出行路線被選用的概率隨著線路長(zhǎng)度的增加而減少的規(guī)律。Florian和Fox于1976年對(duì)Dial模型進(jìn)行了修正，認(rèn)為出行者在某一OD對(duì)間選擇路線的概率為：

對(duì)于簡(jiǎn)單的道路網(wǎng)，可以枚舉其可能路線，但是對(duì)于復(fù)雜的大規(guī)模路網(wǎng)，Dial模型沒(méi)有辦法解決。本文通過(guò)對(duì)多路徑模型進(jìn)行改進(jìn)可以給出該問(wèn)題的解。理性的出行者出行會(huì)選擇出行效用最大的出行路線（通常表現(xiàn)為出行時(shí)間最短），出行者從某出行起點(diǎn)到對(duì)應(yīng)的出行終點(diǎn)，需經(jīng)過(guò)一連串的交通節(jié)點(diǎn)（一般交叉口），每經(jīng)過(guò)任一交叉口，都會(huì)在該交叉口所鄰接的有效路段中選擇其中一條路段作為他的下一條出行路線，繼續(xù)前進(jìn)。在每一交叉口處，可供出行者選擇的有效出行路線條數(shù)等于該交叉口所有有效出行路段個(gè)數(shù)之和[19]。

在實(shí)際出行過(guò)程中，每一路段的路阻并不是固定的，而是時(shí)時(shí)刻刻隨著道路流量的變化而變化，隨著道路流量越來(lái)越大，道路的路阻也越來(lái)越大，因此對(duì)交通量在實(shí)際路網(wǎng)中進(jìn)行分配的時(shí)候，理應(yīng)考慮路阻與交通負(fù)荷之間的關(guān)系，故采用多路徑—容量限制分配法更為合理。

3 多路徑-容量限制分配法的改進(jìn)

3.1 多路徑-容量限制分配法的節(jié)點(diǎn)分配法

在實(shí)際出行時(shí)，考慮每個(gè)出行者對(duì)于出行路線的選擇只與出行終點(diǎn)有關(guān)系，即出行者在節(jié)點(diǎn)（交叉口）進(jìn)行決策時(shí)不會(huì)考慮自己來(lái)自哪個(gè)節(jié)點(diǎn)，而是考慮選擇哪個(gè)后續(xù)節(jié)點(diǎn)使得從當(dāng)前位置到目的地的路權(quán)最小[20]。因此，對(duì)于一個(gè)OD矩陣，無(wú)需同時(shí)對(duì)所有的OD量進(jìn)行分配，而是只需要將終點(diǎn)相同的所有OD量進(jìn)行合并，對(duì)合并之后的OD量進(jìn)行統(tǒng)一的分配，這一過(guò)程可以大大地減少交通量分配的工作量，加速分配過(guò)程，提高分配效率，因此更適用于大規(guī)模路網(wǎng)的交通量分配。同時(shí)，考慮到道路阻抗隨道路流量的變化，因此，在進(jìn)行實(shí)際的交通量分配時(shí)，將OD矩陣分成個(gè)子矩陣，分次進(jìn)行分配，每次分配按照多路徑分配的原則進(jìn)行，每分配一次，路阻修正一次，直到個(gè)OD矩陣分配完畢。

3.2 路網(wǎng)中節(jié)點(diǎn)的分配次序

對(duì)于改進(jìn)的多路徑-節(jié)點(diǎn)分配法，在進(jìn)行道路交通量的分配時(shí)，由于將到達(dá)各個(gè)節(jié)點(diǎn)的總流量進(jìn)行統(tǒng)一的分配，因此需要確定各個(gè)節(jié)點(diǎn)的分配次序，由前文可知，任一節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)必然更接近于終點(diǎn)（否則構(gòu)不成有效路段），因此在對(duì)某一節(jié)點(diǎn)進(jìn)行分配時(shí)，需要確保除了該節(jié)點(diǎn)之外的所有節(jié)點(diǎn)與該節(jié)點(diǎn)均構(gòu)成有效路段，也就是說(shuō)，在該節(jié)點(diǎn)之前被分配的節(jié)點(diǎn)與該節(jié)點(diǎn)均構(gòu)不成有效路段。按照上述步驟，即可確定所有節(jié)點(diǎn)的分配次序，如果開始時(shí)路網(wǎng)中存在多個(gè)可以同時(shí)進(jìn)行分配的節(jié)點(diǎn)，可以任選其一。

4 算法實(shí)例

道路網(wǎng)絡(luò)如圖1所示，節(jié)點(diǎn)代表交叉口，路段上的數(shù)字代表路阻（行駛時(shí)間），各個(gè)交通節(jié)點(diǎn)至交通節(jié)點(diǎn)（終點(diǎn)）3的OD量如表1所示（該OD是將原始各個(gè)節(jié)點(diǎn)間的OD按照列疊加求得），現(xiàn)用上述基于多路徑-容量限制的節(jié)點(diǎn)分配法分配該OD表。

圖1 待分配道路網(wǎng)

表1 各個(gè)節(jié)點(diǎn)至節(jié)點(diǎn)5的OD量

將OD表分成三個(gè)子OD矩陣進(jìn)行分配，每次按照多路徑模型進(jìn)行分配，每分配一次，路阻修正一次，直到把三個(gè)子OD矩陣分配完畢。

（1）第一次分配

第一次分配的OD矩陣見(jiàn)表2所示，分配結(jié)果如表3所示。

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

表3 第一次分配的結(jié)果

第一次分配后進(jìn)行路阻修正，如圖2所示。

圖2 第一次修正路阻后的道路網(wǎng)

（2）第二次分配

第二次分配的OD矩陣及分配結(jié)果如表4、表5所示。

表4 第二次分配的OD矩陣

表5 第二次分配的結(jié)果

第二次分配后進(jìn)行路阻修正，如圖3所示。

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

（3）第三次分配

第三次分配的OD矩陣和分配結(jié)果如表6和表7所示。

表6 第三次分配的OD矩陣

表7 第三次分配的結(jié)果

通過(guò)對(duì)上述表格進(jìn)行簡(jiǎn)要分析，運(yùn)用多路徑-容量限制分配法的改進(jìn)算法—— 節(jié)點(diǎn)分配法，對(duì)路網(wǎng)的交通量進(jìn)行分配可以將終點(diǎn)相同的OD量進(jìn)行合并，批量分配，經(jīng)過(guò)三次的分配計(jì)算就得到最終的結(jié)果，即各條道路上最終的交通量，與此前已經(jīng)廣泛使用的算法相比較，將九次分配過(guò)程簡(jiǎn)化為三次，計(jì)算量減少了三分之一，本文的算例道路網(wǎng)規(guī)模并不是很大，優(yōu)越性體現(xiàn)并不十分明顯。綜上，這種算法大大加速了交通量的分配過(guò)程，使得復(fù)雜的交通分配過(guò)程大大簡(jiǎn)化，交通分配的計(jì)算量同時(shí)大大減少，因此該算法可以應(yīng)用于中型規(guī)模的道路交通量分配。

5 結(jié)論與展望

本文基于多路徑-容量限制分配法的改進(jìn)算法—— 節(jié)點(diǎn)分配法，對(duì)路網(wǎng)的交通量進(jìn)行分配，并給出算例，結(jié)果表明，該分配方法將終點(diǎn)相同的OD量進(jìn)行合并，批量分配，可以加速分配過(guò)程，將分配的計(jì)算量減少為原來(lái)的1/，為OD矩陣第一維的值。本文中算例僅僅考慮了道路流量對(duì)路阻的影響，而沒(méi)有考慮到實(shí)際道路上的突發(fā)事件等對(duì)其交通量分配的影響，這些還有待后續(xù)的研究。

[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] 任華玲, 高自友. 動(dòng)態(tài)交通分配中一種離散VI模型的算法研究[J]. 土木工程學(xué)報(bào), 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] 杜學(xué)東, 四兵峰. 基于隨機(jī)均衡配流的O-D量估計(jì)雙層規(guī)劃模型及算法[J]. 山東科技大學(xué)學(xué)報(bào), 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] 黃志遠(yuǎn), 周峰, 徐瑞華. 基于多路徑可達(dá)的城市軌道交通網(wǎng)絡(luò)考慮負(fù)載均衡方法[J]. 武漢理工大學(xué)學(xué)報(bào), 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ìn)及節(jié)點(diǎn)分配算法[J]. 東南大學(xué)學(xué)報(bào), 1994(6): 21-26.

[14] 吳麗娟. 基于AFC數(shù)據(jù)的城市軌道交通網(wǎng)絡(luò)乘客出行路徑匹配及突發(fā)事件影響研究[D]. 北京: 北京交通大學(xué), 2016.

[15] 許勝博. 基于票務(wù)信息的城市軌道交通客流實(shí)時(shí)測(cè)算問(wèn)題研究[D]. 成都: 西南交通大學(xué), 2017.

[16] 褚耀程. 前景理論下路徑選擇行為參考點(diǎn)選取問(wèn)題研究[D]. 成都: 西南交通大學(xué), 2017.

[17] 李原. 城市軌道交通網(wǎng)絡(luò)換乘客流分配研究[D]. 成都: 西南交通大學(xué), 2017.

[18] 吳正陽(yáng). 城市軌道交通網(wǎng)絡(luò)客流分配理論與控制技術(shù)研究[D]. 成都: 西南交通大學(xué), 2018.

[19] 邵春福. 交通規(guī)劃原理[M]. 北京: 中國(guó)鐵道出版社, 2008.

[20] 高自友, 任華玲. 城市動(dòng)態(tài)交通流分配模型與算法[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

國(guó)家自然科學(xué)基金（61803314）

高明瑤（1996—），女，漢族，江蘇揚(yáng)州人，碩士研究生，研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理，E-mail：17851101369@163.com

高明瑤，石紅國(guó). 大規(guī)模道路交通量分配的節(jié)點(diǎn)分配算法[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2020, 18（2）：119-124.

（責(zé)任編輯：劉娉婷）