基于路徑選擇偏好的路網容量啟發式算法*

白　樺　葉曉飛　凌　鐳　張　旭

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

基于路徑選擇偏好的路網容量啟發式算法*

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

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

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

關鍵詞：啟發式算法；路徑選擇偏好；路網容量；K最短路徑算法；出行效用

0引言

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

2路徑選擇偏好模型

(1)

(2)

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

(3)

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

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

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

(4)

(5)

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

(6)

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

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

4道路網絡容量計算與評價

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

(7)

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

(8)

5案例分析

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

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

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

結果表明，無論以路網平均速度還是以路段通行能力作為約束條件，路網容量隨著道路偏好權重的增加而減小.以路網平均速度為約束條件時，當道路偏好小于1.3和大于1.7時，路網容量隨道路偏好的減小而顯著降低；當道路偏好介于1.3～1.7之間時，路網容量相對穩定.以路段通行能力作為約束條件時，路網容量與道路偏好呈線性負相關.當道路偏好相等時，以路網平均速度為約束條件的路網容量低于以路段通行能力作為約束條件的路網容量.

表1　道路網絡數據表

圖3　以路網平均速度為約束條件的路網容量

圖4　以路段通行能力為約束條件的路網容量

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

6結論

考慮道路通行效用和出行時間兩個主要因素，構建了基于路網道路選擇偏好的道路網絡容量啟發式算法，得到了路徑選擇偏好對路網容量大小的影響.主要結論如下.

1) 路網容量隨著道路偏好權重的增加而減小.

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

3) 所設計的啟發式算法，可得到唯一解，且收斂性和有效率優于規劃模型.

參 考 文 獻

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

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

[3]楊甜甜,石建軍,劉金超.基于雙層規劃模型下的路徑安排問題研究[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- ):男，博士，工程師，主要研究領域為交通規劃、城市規劃

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