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

高明瑤，石紅國

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

高明瑤，石紅國

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

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

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

0 引 言

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

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

1.1 道路阻抗

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

1.2 有效路段

1.3 有效出行路線

2 交通分配模型與方法

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

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

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

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

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

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

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

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

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

3 多路徑-容量限制分配法的改進

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

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

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

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

4 算法實例

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

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

表1 各個節(jié)點至節(jié)點5的OD量

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

（1）第一次分配

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

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

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

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

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

（2）第二次分配

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

表4 第二次分配的OD矩陣

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

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

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

（3）第三次分配

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

表6 第三次分配的OD矩陣

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

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

5 結(jié)論與展望

本文基于多路徑-容量限制分配法的改進算法—— 節(jié)點分配法，對路網(wǎng)的交通量進行分配，并給出算例，結(jié)果表明，該分配方法將終點相同的OD量進行合并，批量分配，可以加速分配過程，將分配的計算量減少為原來的1/，為OD矩陣第一維的值。本文中算例僅僅考慮了道路流量對路阻的影響，而沒有考慮到實際道路上的突發(fā)事件等對其交通量分配的影響，這些還有待后續(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] 任華玲, 高自友. 動態(tài)交通分配中一種離散VI模型的算法研究[J]. 土木工程學(xué)報, 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é)東, 四兵峰. 基于隨機均衡配流的O-D量估計雙層規(guī)劃模型及算法[J]. 山東科技大學(xué)學(xué)報, 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] 黃志遠, 周峰, 徐瑞華. 基于多路徑可達的城市軌道交通網(wǎng)絡(luò)考慮負載均衡方法[J]. 武漢理工大學(xué)學(xué)報, 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] 王煒. 多路徑交通分配模型的改進及節(jié)點分配算法[J]. 東南大學(xué)學(xué)報, 1994(6): 21-26.

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

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

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

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

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

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

[20] 高自友, 任華玲. 城市動態(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

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

高明瑤（1996—），女，漢族，江蘇揚州人，碩士研究生，研究方向為交通運輸規(guī)劃與管理，E-mail：17851101369@163.com

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

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