基于遗传算法的路网流量分配研究

徐 旭，汪鑫鑫

(上海大学 土木工程系，上海 200072)

基于遗传算法的路网流量分配研究

徐 旭，汪鑫鑫

(上海大学 土木工程系，上海 200072)

基于轴载次数采用蒙特卡罗法计算路面结构可靠度。将路面结构可靠度看作路段连通可靠度，用广度优先搜索方法求出路网连通可靠度。为了将服务水平低的路段等级提升，利用遗传算法以路网连通可靠度最高为目标进行流量分配，最终提升整个路网的服务水平。并对比流量分配前后的路网连通可靠度与路网服务水平，给管理者提供参考意见。通过实例表明：遗传算法可以对路网流量进行有效分配。

交通工程；结构可靠度；遗传算法；道路网络；服务水平

0 引 言

城市私家车的拥有量随着城市人口的增加和人们生活水平的提高而高速增长，城市交通拥挤的程度也越来越严重。目前解决交通拥挤的方法主要有：① 新建城市道路，增加城市交通承载能力；② 减少使用私家车次数，多乘用公共交通，使总车流量减少；③ 更好地利用不拥堵的路段，将拥挤路段的车流量分散到不拥挤的路段，实现对路网资源的充分利用。

笔者结合道路可靠度与服务水平对路网流量进行分配。道路可靠度的研究分为两个方向：一是路面结构可靠度；二是道路网络可靠度。在路面结构方面，目前计算路面结构可靠度的方法有直接积分法、一次二阶矩法、数值模拟法等。王褀国等[1]利用响应面法来计算路面结构可靠度；殷晓等[2]采用改进的直接积分法实现了对水泥道路可靠度的精确计算。网络可靠度计算是近些年才兴起的，通过不同的评价指标来确定。评价指标有很多，最早的是由H．MINE等[3]提出的连通可靠性指标和评价方法；Y．ASAKURA等[4]给出了行程时间可靠性的定义；A．CHEN等[5]对路网容量进行研究后提出容量可靠度的概念。这些评价指标各自侧重某些方面，但它们之间又相互联系。路面结构可靠度与路网可靠度往往分开研究，这就使得它们各自得出的数据不能相互参考、利用。徐旭等[6]通过车流量与路面结构可靠度和路网畅通可靠度的关系将这两者的研究结合了起来，使得路网可靠度的计算更加精确。

道路服务水平往往通过多方面来进行综合评价[7-9]，其主要是从管理者的角度来衡量路网可靠性。因此，笔者采用服务水平这个评价指标来衡量管理者对路网分流后路网状态变化。在路网车流量分配方面，最典型的是Logit模型。李军等[10]对Logit模型进行了改进；林鹰等[11]通过遗传算法实现了交叉口的流量转移。

鉴于遗传算法在分配优化方面的优势，笔者试着采用这个方法来对路段进行流量分配。笔者创新性在于将遗传算法应用于路网的流量分配。其他路网流量分配模型只能处理较小的路网，对大型路网的计算会非常繁琐，而遗传算法作为一种高效的搜索与优化方法，可以处理很大的路网。而且遗传算法可以通过控制参数得到不同的计算结果，因此可以针对路网的实际情况设置相应的参数，提高了此方法使用的灵活性与应用的广泛性。

1 路网服务水平

1.1 服务水平的评价方法

服务水平是一项指标，用来衡量驾驶员和乘客所感受的服务质量以及交通流运行状态。各国对路段服务水平的划分标准不一，美国根据其编制的《道路通行能力手册：HCM2000》[12]将服务水平划分为6个等级，我国参照美国的标准进行了修改，但基本是相对应的，具体标准如表1[13]。

表1 中国和美国路段服务水平划分标准Table 1 Classification standards of road service level in China and America

对服务水平的研究最早是交叉口的服务水平，接着是路段服务水平，最后是路网服务水平，前两者的研究已比较完善，对路网服务水平的研究还处于探索阶段。目前国内外评价路网服务水平的常用指标主要有：饱和度、平均车速、延误时间、车道占有率等。

1.2 路网服务水平的量化方法

笔者对路段服务水平的划分如表2。

表2 文中采用的路段服务水平划分标准

笔者从饱和度这个角度来对路网服务水平进行评价。路网服务水平的量化[14]可通过以下公式来衡量：

(1)

(2)

式中：Φ为路网服务水平，Φ值变化范围为[1, 4]，Φ值越低，则路网服务水平越高；φi为第i条路段服务水平，φi的值与其等级对应，为1、2、3、4；pi为第i条路段的权重系数；xi、li分别为第i条路段的车流量和该路段长度，二者的乘积表示此路段的交通量，所有路段的交通量相加表示路网的总交通量，总交通量是定值；m为路段数量之和。

2 路面结构可靠度

路面结构可靠度是指路面在规定条件下能够正常使用的概率，通常根据JTG D50—2017《道路沥青路面设计规范》[15]来确定，表达式为：

Rl=P(ld>ls)

(3)

Rσ=P(σR>σs)

(4)

式中：Rl和Rσ分别为以弯沉值和弯拉应力为指标的路面结构可靠度；ld和ls分别为设计弯沉值和实际弯沉值；σR和σs分别为容许弯拉应力和实际弯拉应力。

弯沉值容易测量且精度较高，因此笔者采用弯沉值作为指标来计算路面可靠度。其计算流程为：统计得到实际车流量，转化为累计标准轴载次数，采用蒙特卡罗法对路面结构设计参数和轴载次数用正态分布随机取值，计算得到路面设计弯沉值和实际弯沉值，并对这两个值进行比较，循环计算指定次数，实际值小于设计值的次数除以总循环的次数得到的值，就可得到路面结构可靠度。此过程用MATLAB软件编程进行计算。

3 路网连通可靠度

用蒙特卡罗法计算得到的单条路面结构可靠度如式(5)：

R(i,j)=P(ld>ls)

(5)

式中：R(i,j)为示节点i到节点j的该条路段路面结构可靠度，这里将它假定为该路段的连通可靠度[16]。

目前大部分计算路网可靠度方法是先计算出路段连通可靠度，然后再由串并联方法依次计算出路径可靠度，OD对可靠度，路网可靠度。但这种方法效率低下而且精度也不高，路网越大这个缺点会越加明显。因此，笔者采用数值模拟的方法来计算路网可靠度。

为简化计算，笔者不考虑路段交叉口的可靠度，在求出路段连通可靠度后，在路网上用广度优先搜索方法结合蒙特卡罗法进行搜索。其步骤如下：

1)将实际路网形态映射到矩阵当中。举例说明：如果道路网络如图1(a)，则将其每个路段看作一个点，如图1(b)。

2)假定各路段单元需求连通可靠度服从[0,1]之间的均匀分布，当路段连通可靠度大于需求连通可靠度时，定义路段单元连通，令这条路段可靠度为1，否则为0。

3)用广度优先搜索方法对路网连通路段进行搜索，判断路网中任意两点，即任意两条路段能否连通，若连通，记1次，反之记0次。循环计算直到设定的模拟次数，最后连通的次数除以模拟次数得到路网的连通可靠度R。

图1 道路网络示例Fig.1 Road network schematic

4 遗传算法对路网流量的分配

4.1 分配模型

对路网流量分配的目的是对饱和度过大的路段进行分配，控制其路段服务水平在某个等级之上。为保证路网的可靠性，笔者以路网连通可靠度最大化为分配目标。

路网流量的分配考虑3个要素：各路段车流量、约束条件和目标函数。为方便遗传算法计算，这里将被分配流量的道路依次编号为：x1,x2,…,xn。约束条件为每条道路上限制的车流量范围以及参与分配的总流量。目标函数为路网的连通可靠度。

目标函数：

Rmax=f(x1,x2,…,xn)

(6)

约束条件：

(7)

式中：xi为第i条道路的车流量；R为路网连通可靠度；f(x1,x2,…,xn)为由车流量求路网连通可靠度的函数；m为路段总数量；q为参与分配车流量的总和；ximin和ximax分别为第i条道路上限制的车流量的最小值与最大值。

4.2 遗传算法

遗传算法是一种随机搜索算法，它通过模拟生物的繁衍进化进行计算。算法以一个种群的所有个体为对象，先将它们进行编码，接着模拟生物进化的过程：选择、交叉、变异、生成下一代。不停重复这一过程直到最终产生满足要求的个体，即问题的解。

实践证明，遗传算法在求解复杂系统优化问题方面非常有效。而路网流量的分配就属于组合优化问题。因此笔者尝试使用遗传算法来对路网流量进行分配优化。

5 实 例

笔者截取了上海某区域道路网络如图2(a)，其简化图如图2(b)。其中，1-21，6-11为主干道，其余的为次干道。主干道与次干道的通行能力分别为2 112、1 573 veh/h。各路段的参数见表3，实地调查统计得出的各道路在高峰时期的车流量以及饱和度见表4。

图2 道路网络Fig. 2 Road network

结构层类型回弹模量厚度分布均值/MPa变异系数分布均值/cm变异系数主干道面层正态16000.15正态100.1基层正态10000.15正态750.1路基正态400.15正态——次干道面层正态14000.15正态80.1基层正态10000.15正态650.1路基正态250.15正态——

表4 各条道路上的车流量及饱和度

5.1 路面结构可靠度

由式(5)可得到各个道路的路面结构可靠度。其计算结果如表5。

表5 各条道路结构可靠度

5.2 路网连通可靠度

用MATLAB自编的计算路网连通可靠度的程序得出路网可靠度R=0.535 8。

5.3 路网服务水平

由表4的数据得到各路段服务水平，代入式(1)，得到路网服务水平Φ=2.834。

5.4 各路段流量分配

由表4可看出：主干道1-21，6-11这几条路段的服务水平在4级，饱和度较高。其他路段饱和度较低，现在对主干道进行流量限制，将多余的车流量分配到其他路段。笔者通过使用遗传算法工具箱来求解问题。

5.4.1 适应度函数

遗传算法工具箱是求解函数最小值，而笔者要求路网可靠度最大值，故采用适应度函数如式(8)：

Fit[f(x)]=1-f(x)

(8)

遗传算法要求适应度函数不能为负，而路网可靠度的范围为0～1，故用1减目标函数作为适应度函数。

5.4.2 约束条件

以路段服务水平为标准，将主干道1-21，6-11的服务水平提升到3级，即饱和度在0.75～0.90之间。而其他路段的服务水平也必须在3级及以上，因此饱和度范围设为0～0.9。

为简化计算，认为分配前与分配后的总交通量相同[17]，即：

(9)

本例中各条路段的长度相近，为简化计算，假定各路段长度相同，将式(9)中等式两端的li消去，就得到分配前与分配后各路段车流量的和相等，即为35 477 veh/h。路网中路段总条数为27条，前17条为次干道，后10条为主干道。

所以约束条件为：

(10)

式中：xi∈[1, 17]，j∈[18, 27]，i，j为整数；xiC，xjC分别为第i条与第j条道路的通行能力。

5.4.3 初始参数设定

种群规模：种群规模大小对遗传算法的收敛性和计算效率有直接影响，规模较小，容易收敛到局部最优解；规模较大，计算效率降低。其数值一般设置在10～200之间。本例设置为50。

最大代数：设置最大代数是遗传算法终止条件之一，还可通过设置时间限制、适应度函数限制等条件来终止遗传算法。本例通过多次计算，发现30代以后适应度平均值和最佳值就基本保持不变，为节省计算时间，因此将最大代数设置为30代。

其他主要参数还有交叉、变异。交叉是产生新个体的主要方法；变异具有改善遗传算法局部搜索的能力，并且可以维持群体多样性，防止出现早熟现象。由于本例变量是整数，在MATLAB中将这些参数设为默认值。

5.4.4 结果分析(图3)

图3中，实线代表种群最佳值，虚线代表种群平均值。由图3可看出：第5代以后最佳值就趋于稳定，说明已经到达了最佳解的附近。获得的第30代的最佳值为0.477 4，即可靠度R=1-0.477 4=0.522 6。分配后各道路的车流量如表6。

分配后路网的服务水平Φ=2.544。

图3 适应度值与迭代次数的关系Fig.3 Relationship between fitness value and iteration times

道路编号车流量/(veh·h-1)饱和度/(v·c-1)可靠度道路编号车流量/(veh·h-1)饱和度/(v·c-1)可靠度2-39980.6340.63514-178860.5630.6493-413070.8310.55410-168200.5210.6734-512610.8020.57516-1912410.7890.56512-1311470.7290.5861-517230.8160.75013-1411790.7490.5795-916990.8040.76414-157450.4740.6729-1517120.8110.75815-1611000.6990.59815-1816380.7760.76817-189150.5820.64618-2116550.7840.76618-1911550.7340.5976-716300.7720.76119-2013560.8620.5627-817090.8090.7603-711680.7430.5818-917160.8130.7617-137250.4610.6919-1016890.7990.7634-813080.8320.56810-1117250.8170.7628-1412700.8070.572

5.5 结果对比分析

在对主干道进行流量限制后，其饱和度降低，路段可靠度提高，但其余次干道由于增加了车流量，饱和度增加，路段可靠度降低。

路网车流量分配后，路网可靠度R由0.535 8降到了0.522 6，而路网的服务水平由2.834变为2.544(数值越低，服务水平越高)。

对路网流量分配后，各路段的饱和度趋于均匀，各路段服务水平均在3级以上，路网服务水平也有所提高，达到了管理者对路网流量分配的目的,而路网连通可靠度会降低。路网连通可靠度的范围是[0, 1]，可靠度降低了1.32%，路网服务水平的范围是[1, 4]，服务水平提高了9.67%，说明此分配方案是可以采用的，也说明遗传算法分配的有效性。

6 结 论

6.1 结 语

笔者以车流量为纽带，将路段、路网服务水平和路段、路网可靠度这4者联系起来。为提高拥挤路段的服务水平，将车流量分配到其他路段。各路段车流量发生变化导致路段可靠度发生变化，进而路网可靠度也因此发生变化。在满足路段服务水平的前提下，通过遗传算法以路网连通可靠度最高为目标求得各路段分配后的流量。以路网连通可靠度小幅度降低为代价，达到了管理者对路网流量的分配控制和路网服务水平的提升。

6.2 不足及展望

1)文中路段和路网的可靠度都是由蒙特卡罗法计算得到，而蒙特卡罗法是不确定性算法，要想得到高精度解就得增加模拟次数。笔者在计算路段与路网可靠度时，模拟次数取一万次。对于高性能计算机，提高模拟次数，可有效降低误差，得出的结果也会更加精确。

2)在计算路网可靠度时，笔者没有考虑交叉口的可靠度，而交叉口的拥堵往往是导致道路和路网拥堵的重要因素，所以需要综合考虑路段和交叉口的可靠度。

3)路网的服务水平应该由多种因素综合后计算得出，笔者只选取了其中一种因素，以后还可将另一个重要因素平均车速考虑进来。

4)在流量分配时将路网总交通量设为定值，而对路网流量强制分配后出行者选择的路径可能比原路径要长，即要占用更多的路网资源，这样满足相同人次的出行需求所需要的交通量会比原来的大。因此在分配时可以将分配后的总交通量适当提高，这样更符合实际情况。

5)遗传算法中对参数的设定没有规定，对不同的问题就要设定不同的参数。对同一个问题可以控制其中一个参数的变化来确定这个参数的最佳值。本例的参数大多是默认值，所以在参数的取值上还需要更多的研究。遗传算法具有强大的寻优能力，本例只是一个小型路网，对于大型路网，其同样可以找到最优解，随着计算机计算能力的提高，这种方法可以越来越广泛地使用。

[1] 王褀国，徐旭．响应面方法在路面可靠度分析中的应用[J]．中外公路，2006，26(4)：62-65． WANG Qiguo, XU Xu. Response surface method in reliability analysis of pavement [J].JournalofChina&ForeignHighway, 2006, 26(4): 62-65.

[2] 殷晓，徐旭．基于路网系统的水泥混凝土道路的可靠度研究[J]．上海大学学报(自然科学版)，2013，19(5)：513-519． YIN Xiao, XU Xu. Research on reliability of cement concrete pavement based on road network system [J].JournalofShanghaiUniversity(NaturalScience), 2013, 19(5): 513-519.

[3] MINE H, KAWAI H.MathematicsforReliabilityAnalysis[M]. Tokyo: Asakurashoten, 1982: 12-14.

[4] ASAKURA Y, KASHIWADANI M. Road network reliability caused by daily fluctuation of traffic flow [C]//Proceedingsofthe19thPTRCSummerAnnualMeeting. Brighton: [s. n.], 1991: 73-84.

[5] CHEN A, YANG Hai, LO H K, et al. A capacity related reliability for transportation networks [J].JournalofAdvancedTransportation, 1999, 33(2): 183-200.

[6] 徐旭，付蓉．道路网络结构可靠度的研究[J]．中外公路，2013，33(1)：72-76． XU Xu, FU Rong. The study of road network reliability [J].JournalofChina&ForeignHighway, 2013, 33(1): 72-76.

[7] 况爱武，钱红波，张伟．道路服务水平的模糊综合评判[J]．中南公路工程，2003，28(4)：36-38． KUANG Aiwu, QIAN Hongbo, ZHANG Wei. Fuzzy comprehensive assessment of serviceability of roads [J].CentralSouthHighwayEngineering, 2003, 28(4): 36-38.

[8] 李相勇，蒋葛夫．城市道路服务水平的模糊综合评判[J]．交通运输系统工程与信息，2002，2(3)：48-50． LI Xiangyong,JIANG Gefu.Fuzzy comprehensive assessment of service level for urban roads[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2002, 2(3): 48-50.

[9] 沙玉峰，廖秀斋，李之红，等．基于智能公交的城市道路服务水平实时评价与预测[J]．重庆交通学院学报，2004，23(2)：79-84． SHA Yufeng, LIAO Xiuzhai, LI Zhihong, et al. To evaluate and forecast real-timely city highway service level based on intelligent public traffic [J].JournalofChongqingJiaotongUniversity, 2004, 23(2): 79-84.

[10] 李军，聂培林，余志．全路径Logit交通分配模型的求解方法[J]．中山大学学报自然科学版，2004，43(5)：124-126． LI Jun, NIE Peilin, YU Zhi. Solving all-path Logit assignment problem by iteration method [J].ActaScientiarumNaturaliumUniversitatisSunyatseni, 2004, 43(5): 124-126.

[11] 林鹰，苏日娜．基于遗传算法求解转移流量的多目标规划方法[J]．重庆交通大学学报(自然科学版)，2007，26(增刊)：147-150． LIN Ying, SU Rina. Method to transition traffic flow problem by multiple objectives programming model based on genetic algorithm [J].JournalofChongqingJiaotongUniversity(NaturalScience), 2007, 26(Sup): 147-150.

[12] 美国交通研究委员会．美国道路通行能力手册：HCM2000[M]．任福田，刘小明，荣建，译．北京：人民交通出版社，2007． Transportation Research Board.HighwayCapacityManual:HCM2000[M].Ren Futian,LIU Xiaoming,RONG Jian, translate. Beijing: China Communications Press, 2007.

[13] 王炜，徐吉谦，杨涛，等．城市交通规划理论及其应用[M]．南京：东南大学出版社，1998． WANG Wei, XU Jiqian, YANG Tao, et al.TheoryandApplicationofUrbanTrafficPlanning[M].Nanjing:Southeast University Press, 1998.

[14] 侯立文，蒋馥．基于路网可靠性的路网服务水平[J]．系统工程理论方法应用，2002，12(3)：248-252． HOU Liwen, JIANG Fu. Study on reliable level of service to road network based on road network reliability[J].SystemsEngineering-TheoryMethodologyApplications, 2002, 12(3): 248-252.

[15] 中交路桥技术有限公司．公路沥青路面设计规范：JTG D50—2017[S]．北京：人民交通出版社，2017． CCCC Road and Bridge Consultants Co. Ltd.SpecificationsforDesignofHighwayAsphaltPavement:JTGD50—2017[S].Beijing:China Communications Press, 2017.

[16] 徐旭，郑伟舜．蚁群算法下容量限制分配的路网结构可靠度分析[J]．重庆交通大学学报(自然科学版)，2016，35(5)：127-132． XU Xu, ZHENG Weishun. Analysis on reliability of road network structure by traffic allocation due to limited capacity using ant colony algorithm [J].JournalofChongqingJiaotongUniversity(NaturalScience), 2016, 35(5): 127-132.

[17] 孙秋霞，孙璐，刘新民．基于出行个体行为的交通网络效率研究[J]．重庆交通大学学报(自然科学版)，2016，35(2)：110-113． SUN Qiuxia, SUN Lu, LIU Xinmin. Study of the traffic network efficiency based on individual traveler’s behavior [J].JournalofChongqingJiaotongUniversity(NaturalScience), 2016, 35(2): 110-113.

(责任编辑：刘韬)

RoadNetworkTrafficFlowAllocationBasedonGeneticAlgorithm

XU Xu, WANG Xinxin

(Department of Civil Engineering, Shanghai University, Shanghai 200072, P.R.China)

Based on the axial load times, Monte Carlo method was used to calculate pavement structure reliability. Taking pavement structure reliability as road connection reliability, the road network connection reliability was solved by BFS. In order to improve the service level of a road with low service level, the genetic algorithm was used to allocate traffic flow with the target of the highest road network connection reliability. The service level of the whole road network was improved finally. Compared with road network service level and road network connection reliability before and after the traffic flow allocation, manager could acquire some referential advice. The case study shows that genetic algorithm can effectively allocate road network traffic flow.

traffic engineering; structure reliability; genetic algorithm; road network; service level

U491.1+13

：A

：1674-0696(2017)09-085-06

10.3969/j.issn.1674-0696.2017.09.16

2016-06-12；

：2016-09-12

徐 旭(1968—)，男，江苏南通人，教授，博士，主要从事复杂道路网络系统方面的研究。E-mail：xxu@mail.shu.edu.cn。

汪鑫鑫(1992—)，男，江苏南通人，硕士研究生，主要从事复杂道路网络系统方面的研究。E-mail：1527895446@qq.com。