基于路径选择偏好的路网容量启发式算法*

白　桦　叶晓飞　凌　镭　张　旭

(江苏省交通规划设计院股份有限公司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)