基于路徑選擇偏好的路網(wǎng)容量啟發(fā)式算法*

白　樺　葉曉飛　凌　鐳　張　旭

(江蘇省交通規(guī)劃設(shè)計院股份有限公司1)　南京　210014)　(寧波大學(xué)海運學(xué)院2)　寧波　315211)

基于路徑選擇偏好的路網(wǎng)容量啟發(fā)式算法*

白樺1)葉曉飛2)凌鐳1)張旭1)

(江蘇省交通規(guī)劃設(shè)計院股份有限公司1)南京210014)(寧波大學(xué)海運學(xué)院2)寧波315211)

摘要：為了準確地測算路網(wǎng)容量，考慮道路通行效用和出行時間兩個主要因素，構(gòu)建了路徑選擇偏好模型，設(shè)計了基于最大忍耐時間的路徑生成方法和基于增量加載的交通分配啟發(fā)式算法.以淮北市路網(wǎng)為例進行應(yīng)用.結(jié)果表明，路網(wǎng)容量隨著道路偏好權(quán)重的增加而減??；路網(wǎng)平均速度約束下的路網(wǎng)容量低于路段通行能力約束下的路網(wǎng)容量大小.

關(guān)鍵詞：啟發(fā)式算法；路徑選擇偏好；路網(wǎng)容量；K最短路徑算法；出行效用

0引言

城市路網(wǎng)容量描述了路網(wǎng)對交通需求的承載能力，是城市交通規(guī)劃與管理的基礎(chǔ)，為交通流控制與需求管理提供依據(jù)[1-2].已有文獻表明，單層規(guī)劃方法因難以建立交通供需平衡關(guān)系而應(yīng)用比較少[3]；確定路網(wǎng)容量常用的方法是雙層規(guī)劃模型[4-8]，上層以系統(tǒng)總體費用最小化為目標，下層為靜態(tài)或者動態(tài)用戶平衡分配問題；亦有學(xué)者基于增量分配方式提出了啟發(fā)式算法計算路網(wǎng)容量，通過設(shè)置出行時間為無窮大，來計算路網(wǎng)容量[9-10].每種方法均存在缺陷，雙層和單層規(guī)劃模型中不能動態(tài)的反映道路效用對路網(wǎng)容量的影響，并且僅能得到近似解；啟發(fā)式算法中不合理的繞行增大了路網(wǎng)容量；兩種模型均未能考慮出行者個體選擇偏好對路網(wǎng)容量的影響.因此，本文針對規(guī)劃模型和啟發(fā)式算法的缺陷，基于出行個體對路徑選擇的偏好，提出改進的路網(wǎng)容量啟發(fā)式算法，從而為設(shè)計合理的、科學(xué)的道路網(wǎng)絡(luò)提供決策依據(jù).

2路徑選擇偏好模型

(1)

(2)

由此，基于通行效用和出行時間的路徑選擇模型為

(3)

3基于道路出行效用和出行時間的啟發(fā)式算法

啟發(fā)式算法的核心思想是通過增量分配方式，將一定比例的原始OD矩陣逐步的分配到道路網(wǎng)絡(luò)，直到路網(wǎng)容量飽和.假設(shè)道路使用者可根據(jù)道路的實時路況選擇一條合適的路徑.

3.1考慮道路出行效用和出行時間的路徑生成方法

(4)

(5)

3.2基于增量加載的交通分配方法

(6)

已有文獻采用飽和流率作為達到網(wǎng)絡(luò)容量的判定條件，采用路段飽和流率達到90%作為網(wǎng)絡(luò)容量的判定條件.啟發(fā)式算法求解序列見圖1.

圖1　基于通行效用和出行時間的啟發(fā)式算法求解程序

4道路網(wǎng)絡(luò)容量計算與評價

通過上述啟發(fā)式算法，將增量矩陣逐步分配到網(wǎng)絡(luò)中，當某一路段的飽和流量達到約束條件時，道路網(wǎng)絡(luò)交通流量的之和視為道路網(wǎng)絡(luò)容量.網(wǎng)絡(luò)容量的表達式為

(7)

路網(wǎng)平均行駛速度是網(wǎng)絡(luò)整體通行效率的表征，在計算網(wǎng)絡(luò)平均行駛速度時，只需將增量矩陣加載到調(diào)查得到的原始矩陣即可,計算方法為：

(8)

5案例分析

以淮北市的路網(wǎng)及交通流量為例，采用上述啟發(fā)式算法，對路徑選擇偏好和路網(wǎng)容量進行敏感性分析.路網(wǎng)包括26個節(jié)點，82條路段，676個OD對，見圖2.路段的長度和通行能力見表1，路段的粗細表示道路等級.

圖2　淮北市路網(wǎng)(單位：m)

根據(jù)K最短路算法，每個OD對的平均路徑為3.7個.將OD矩陣10%的交通流量逐步迭代到交通網(wǎng)絡(luò)中，分別以網(wǎng)絡(luò)平均速度小于10 km/h和30%的路段達到通行能力的90%為約束條件，計算在不同的道路偏好影響下路網(wǎng)容量，見圖3～4，α為路網(wǎng)容量的權(quán)重，路徑偏好為主干路相對于次干路的重要度.

結(jié)果表明，無論以路網(wǎng)平均速度還是以路段通行能力作為約束條件，路網(wǎng)容量隨著道路偏好權(quán)重的增加而減小.以路網(wǎng)平均速度為約束條件時，當?shù)缆菲眯∮?.3和大于1.7時，路網(wǎng)容量隨道路偏好的減小而顯著降低；當?shù)缆菲媒橛?.3～1.7之間時，路網(wǎng)容量相對穩(wěn)定.以路段通行能力作為約束條件時，路網(wǎng)容量與道路偏好呈線性負相關(guān).當?shù)缆菲孟嗟葧r，以路網(wǎng)平均速度為約束條件的路網(wǎng)容量低于以路段通行能力作為約束條件的路網(wǎng)容量.

表1　道路網(wǎng)絡(luò)數(shù)據(jù)表

圖3　以路網(wǎng)平均速度為約束條件的路網(wǎng)容量

圖4　以路段通行能力為約束條件的路網(wǎng)容量

此外，由于算法引入最大忍耐時間，極大的減少了無效路徑對于路網(wǎng)容量結(jié)果的影響，不僅增加了算法的科學(xué)性，也提高了模型的運算速度.與單層和雙層規(guī)劃模型相比，該算法能夠動態(tài)的反映道路運行效果對路徑選擇的影響.同時，該算法可得到唯一解，其收斂性和有效性也優(yōu)于單層和雙層規(guī)劃模型.

6結(jié)論

考慮道路通行效用和出行時間兩個主要因素，構(gòu)建了基于路網(wǎng)道路選擇偏好的道路網(wǎng)絡(luò)容量啟發(fā)式算法，得到了路徑選擇偏好對路網(wǎng)容量大小的影響.主要結(jié)論如下.

1) 路網(wǎng)容量隨著道路偏好權(quán)重的增加而減小.

2) 路網(wǎng)平均速度約束下的路網(wǎng)容量低于路段通行能力約束下的路網(wǎng)容量大小.

3) 所設(shè)計的啟發(fā)式算法，可得到唯一解，且收斂性和有效率優(yōu)于規(guī)劃模型.

參 考 文 獻

[1]滕生強,楊曉光,姚占春.關(guān)于城市道路交通設(shè)計若干問題的探討[J].中國市政工程，2000,90(9):1-5.

[2]邵正宇.城市道路網(wǎng)通行能力最大的道路類型優(yōu)化分配[J].中南公路工程，2004，29(4)：23-28.

[3]楊甜甜,石建軍,劉金超.基于雙層規(guī)劃模型下的路徑安排問題研究[J].黑龍江交通科技,2015(7):17-19.

[4]MATHEW T, SHARMA S. Capacity expansion problem for large urban transportation networks[J]. Journal of Transportation Engineering,2009,135(7):406-415.

[5]LONG J, GAO Z, ZHANG H, et al. A turning restriction design problem in urban road networks[J]. European Journal of Operational Research,2010,206(3):569-578.

[6]MENG Q, LEE D, YANG H, et al. Transportation network optimization problems with stochastic user equilibrium constraints[J]. Transportation Research Record: Journal of the Transportation Research Board, No 1882, Transportation Research Board of the National Academies, Washington, D.C.,2004(2):113-119.

[7]HAI Y, BELLB M, MENG Q. Modeling the capacity and level of service of urban transportation networks[J]. Transportation Research Part B: Methodological,2000,34(4):255-275.

[8]GAO Z, SUN H，SHAN L L. A continuous equilibrium network design model and algorithm for transit systems[J]. Transportation Research Part B: Methodological,2004,38(3)：235-250.

[9]KIMA S, and UZSOYB R. Exact and heuristic procedures for capacity expansion problems with congestion[J]. IIE Transactions,2008,40(12):1185-1197.

[10]LI Li, YU Quan, YANG Bian, et al. Stress test of roadway network capacity[J]. Computer Science and Information Engineering,2009 WRI World Congress on,2009(5):467-471.

A Heuristic Algorithm for Road Network Capacity Based on Route Choice Preferences

BAI Hua1)YE Xiaofei2)LING Lei1)ZHANG Xu1)

(JiangsuProvinceCommunicationsPlanningandDesignInstituteLimitedCompany,Nanjing210014,China)1)(SchoolofMaritimeandTransportation,NingboUniversity,Ningbo315211,China)2)

Abstract：In order to calculate the road network capacity accurately, the route choice preferences model considering the road preference and the travel time as the two main factors is established. A route generation method based on the maximum endurance time and a heuristic algorithm for traffic assignment based on the incremental load are put forward to explore the network capacity. Finally, the model and algorithm are verified by considering the road network of Huaibei city as an example. The results show that the network capacity decreases with the increase of road preference weight and network capacity under the restriction of road capacity is lower than the average speed of road network.

Key words：heuristic algorithm; route choice preference; network capacity; K-shortest path algorithm;; travel effect

收稿日期：2016-02-15

中圖法分類號：U412

doi:10.3963/j.issn.2095-3844.2016.03.017

白樺(1983- ):男，博士，工程師，主要研究領(lǐng)域為交通規(guī)劃、城市規(guī)劃

*國家自然科學(xué)基金項目資助(51408322，51408321)