基于多目标遗传算法的灾后可靠路径选择

李 清,胡志华

(1. 同济大学 经济与管理学院,上海200092；2. 上海海事大学 物流研究中心,上海201306)



基于多目标遗传算法的灾后可靠路径选择

李 清1,2,胡志华2

(1. 同济大学 经济与管理学院,上海200092；2. 上海海事大学 物流研究中心,上海201306)

为了尽快运出灾民、运进物资,灾后需要选择最短的运输路径；考虑到灾害对道路的损毁,安全的路径是道路选择中的重要因素,基于灾后道路的损毁状况,采用3种方法定义道路可靠性,以最小化路径长度、最大化路径可靠性为目标建立双目标优化模型,采用多目标遗传算法求解.分别求得3种情形下的解,开展2个目标的Pareto分析；分析交叉概率和变异概率对结果的影响：交叉概率增大,覆盖范围波动式变化,理想积波动式下降；变异概率增大,覆盖范围波动式变化,理想积缓慢增长后逐渐下降.采用遗传算法能够有效地解决最短和最可靠路径的搜索问题.

最短路问题；多目标遗传算法；优先权；可靠性

交通网络承担着大量旅客和货物的运输任务,对国民经济的发展起着至关重要的作用.突发事件的频繁发生不但延误了整个运输过程,而且导致道路中断、坍塌,造成大量经济损失[1].近年来,突发事件和自然灾害频发,交通系统不断遭受破坏,面临严重挑战.灾后需要及时将灾民疏散到安全区域,也需尽快将救援物资和人员运送到灾区,道路交通网络成为灾后救援的生命线.一方面,组织者选择最短的行驶路线,把握救援时间,提高救援效率；另一方面,道路因为灾害袭击受到不同程度的损坏,可靠、安全道路的选择成为运输时间之外的又一关键议题.在尽可能短的时间内进行安全、可靠的运输是管理者追求的目标.

最短路问题是网络设计优化的核心,在实际生活中有广泛的应用背景.Nazemi等[2]根据神经网络模型,建立最短路问题的线性规划模型,由神经网络模型的均衡点得到原问题的最优解.Festa等[3]简化了经典最短路问题中的时间多项式,提出2种求解策略.针对不完全信息下交通网络的最短路径问题,闫化海等[1]定义了关键边的概念,应用子树连通算法求解该问题.Amirteimoori[4]从实际问题出发,考虑了路段的多种属性(多种成本和收益),定义不同道路的相对效率,选择效率最高的路径.在突发事件背景下,对道路可靠性的要求应运而生.道路网可靠性是网络可靠性在道路交通中的具体应用,一些学者采用可靠性方法评价路网的连通可靠性、行程时间可靠性和通行能力可靠性等.Asakura等[5]定义行程时间可靠度函数,并以此反映道路交通网络的可靠性,讨论特定时间和交通需求水平下O-D(origin-destination)间成功到达的概率.Chen等[6]提出路网通行能力可靠度,以路网通行能力能成功适应一定交通需求和提供一定服务水平的概率来评价网络可靠性.

本文以最短路问题为原型,以最小化路径长度、最大化路径可靠度为目标,建立双目标优化模型,采用多目标遗传算法求解.分别得到3种方法定义的道路可靠性下的实验结果.

1 问题描述与定义

运输规划、旅行商路线安排和通信系统中的信息传递是最短路问题在实际生活中较常见的应用,这些问题往往给定2个特定的点(起点和终点),要求以较快、成本较少、较可靠的方式完成运输任务.可靠性路径优化问题是指：道路网络中包含有限数量的节点以及连接节点的弧(道路),存在一个起始点和一个终点.不同节点之间有道路连接,每条道路的长度和可靠性均不相同.现已知起点和终点的位置,已知节点间的连接关系及每条道路的长度和可靠性,求解一条从起点到终点长度最短、且可靠性最高的道路.

1.1 最短路问题求解方法

最短路径问题是图论研究中的一个经典算法问题,旨在寻找图(由结点和路径组成)中两结点之间的最短路径.Ardakani等[7]采用A*算法研究动态网络中的最短路问题,使用递减方法减小网络规模,加快问题的优化过程.靳凯文等[8]采用蚁群算法解决车载导航系统中的最短路径搜索问题；Lozano等[9]采用精确算法求解大规模的有约束最短路问题.Cheng等[10]使用二阶锥规划求解连续松弛问题,应用分支定界法求解随机组合问题.以随机Dijkstra为基础,邹亮等[11]运用遗传算法求解动态路径诱导系统中的最短路径问题.Niksirat等[12]研究多重模式交通网络中的K最短可行路径问题,采用元启发式算法：贪婪算法模拟退火(GASA)和双向搜索蚁群算法求解(BACS).

在双目标优化问题方面,Hasuike[13]以最小化总成本、最大化置信区间变化范围为目标建立模型.采用模糊目标和聚合函数,考虑决策者在多目标决策中的偏好,利用基于Dijkstra算法的精确算法和基于Lagrange松弛算法的启发式算法求解.Chen等[14]采用分段线性函数估计道路成本中的非线性成本,根据有效路径集合更新问题的上界和下界,并从中确定子问题的解.

1.2 可靠性计算方法

对网络可靠性的研究一般从持续性、稳健性和有效性3个方面进行分析.持续性描述路网在随机因素干扰下的可靠性,稳健性指网络受到外界破坏后的可靠性,有效性指路网在阻塞情况下满足最低可接受服务水平的程度.

Lee等[15]假设路段通行能力服从正态分布,路段可靠性由下式计算：

(1)

对于串联系统S和并联系统P,可靠性分别由下式计算：

(2)

(3)

陈富坚等[16]综合人、车、路、环境和管理等因素全面评价路网运营安全状态,将道路交通系统按车辆数量和道路特征分成以下4类.UTS：由单车及其行驶的单元路段组成；USTS：由单元路段及其上的交通流组成；STS：由若干个单元路段及其上的交通流组成；NTS：由多条道路的路段交通系统组成.前3类交通系统的可靠性分别如下式所示：

Ruts=Rd·Rv·Rr.

(4)

Rusts=Rd,e·Rv,e·Rr.

(5)

(6)

式中：Rd、Rv、Rr分别为司机、车辆和道路的可靠度.USTS中分别用司机群体特征和路段上车辆群体特征可靠度的期望值表示司机和车辆的可靠度,STS由2个相反交通流的USTS组成.引入贝叶斯模型构造NTS的可靠性模型,分别确定人、车辆、道路和外界环境对道路交通系统可靠度的影响.

在交通网络中,每条路径由若干路段连接而成,侯立文等[17]定义路段的可靠性为一定时间内路段上行使的车辆数小于其通行能力的概率.根据交通流随机的特点,用非齐次泊松过程计算每一路段的可靠性,如下：

(7)

(8)

(9)

式中：rij为第i个OD对中第j条路径的可靠性,n为网络中OD对总数,m为第i个OD对中的路径总数.

1.3 路径可靠性衡量方法

在灾害及突发事件背景下,公路交通系统受到严重破坏,道路可靠性与其受破坏程度密切相关.秦军等[18]选择损毁类型、损毁规模、损毁比例3个因子评价道路损毁程度.损毁比例表示评估路段中损毁路程占总路段长度的比例；根据不同的道路损毁类型进行量化取值,形成受损系数指标；采用道路受损的绝对长度形成规模系数评价指标.

定义路段的可靠性为路段损毁度的倒数,分别用dij、pij、cij、fij表示连接i、j两点路段的损毁度、损毁比例、受损系数和规模系数.本文的路段可靠性定义如下：

(10)

1)最小值法.一条道路能否通行,往往取决于组成该道路的路段中损毁最严重的路段的状况.若道路中损毁最严重的路段可以使用,则该条路径可以保证车辆正常运行；若连接起讫点的路径中存在毁坏或严重破坏的路段,则该条路径不能使用.基于该定义OD间路径的可靠度为

最小值法适用于路径中存在严重损坏路段的情况.

2)平均值法.灾后运输物资、疏散灾民时,首先剔除损坏的路段,然后从可以使用的路段中选择一些连接起讫点.目标是从余下的路段中选择距离最短且可靠性最高的路段,组成连接起讫点的道路.当路径中的路段状态相似,所受破坏情形相差不大时,采用平均值法估计该条路径的整体可靠性：

式中：n为道路OD经过的路段数量.

2 模型的建立

(11)

道路的距离通过下式计算：

(12)

道路可靠性可以采用最小值、平均值和串联法进行计算,分别如下式所示：

(13)

(14)

(15)

根据道路可靠性的计算方法,得到[M1]～[M3]三个模型,如下：

(16)

(17)

(18)

3 多目标遗传算法设计

遗传算法模拟生物进化的过程是一种新的全局优化搜索算法,简单通用、鲁棒性强、适于并行处理且应用范围广[11].具体步骤主要如下：编码——生成初始种群——构造适应度评估函数——交叉——变异——选择——解码.

遗传算法通过多方位和全局的搜索方式获得种群中的解,是解决多目标优化问题的良好工具[19].非支配分类遗传算法(nondominated sorting genetic algorithm, NSGA-II)改进原多目标遗传算法中的等级程序,根据帕累托最优解划分种群的等级,分配共享适应度.分类个体的适应度函数值维持群体的多样性,采用随机剩余比例选择法.在帕累托前端面中,第一前端面上个体的适应度最高,能够保证较高的复制率.NSGA的性能优于多目标遗传算法(multi-objective genetic algorithm,MOGA)和仿帕累托遗传算法(Niched Pareto genetic algorithm,NPGA),它对已知区域有良好的搜索能力和较快的收敛能力.NSGA-II算法的主要步骤如下.

1)生成初始种群P′,随机生成N′的种群规模.

2)评估目标函数值,基于帕累托最优分类分配等级,产生子代种群.

3)采用二元锦标赛选择方法,重组、变异.

4)基于帕累托最优分类分配等级,产生非支配向量集,将第一个前端面上的解依次放入下一代,循环直到确定N′个个体在每个前端面上点与点间的拥挤距离.

5)重复4),直到迭代次数满足g(g为一设定的数,如100、300或500等).

6)选择较低等级前端面上且不在拥挤距离范围内的点,产生下一代,采用二元锦标赛选择方法,重组、变异.

3.1 编码和解码方法

采用基于优先权的编码和解码方法.基因位置上的数字表示节点的序列号,基因值表示节点的优先值,优先值随机生成,如图1所示.首先确定起点,寻找可与起点相连的其他节点,选择优先值最高的节点放入路径.根据该方法选择其他节点,直至构成一条连接起讫点的道路.基于优先权的编码方法具有如下优点：通过编码得到的任意排列都能与一条路径对应(可行性)；可以较容易地将现有的遗传算子应用于该方法；任一道路与一个编码相对应(合法性)；遗传搜索可以搜索到解空间的任意一点.

图1 基于优先权的编码和解码方法Fig.1 Coding and decoding method based on priority

图2 基于位置的交叉方法Fig.2 Position-based crossover

3.2 交叉算子

采用基于位置的交叉方法(position-based crossover, PX).PX交叉方法结合了均匀交叉与修复程序,是对顺序交叉方法的改变,该方法选择的交叉点不连续.如图2所示,首先从第一个父代中随机选择随机个位置,将这些位置的基因值复制到子代中相同的位置；然后从第二个父代中删除第一个父代中已被选中的基因,并将剩下的基因值按从左到右的顺序依次填入子代中的其他位置.

3.3 变异算子

采用逆转变异(inversion mutation)方法：首先从父代中随机选择2个位置,然后逆转这2个点内的子串.具体如图3所示.

图3 逆转变异方法Fig.3 Inversion mutation

3.4 多目标遗传算法性能衡量

1)一元绩效指标——体积比例(hypervolume ratio, HVR).

HVR综合衡量帕累托近似集的分布性和收敛性,用以判断帕累托前端面上个体的绝对质量,计算如下：

(19)

2)二元绩效指标——集合覆盖指标(C: set coverage)

二元绩效指标通过比较2个多目标算法产生的帕累托近似解集衡量2种方法的绩效,计算如下：

(20)

式中：p属于帕累托近似集P,q属于帕累托近似集Q,pq表示解p弱支配解q(在最小化目标值的问题中).式(21)表示：相对于帕累托近似集Ω,近似集P中解的平均质量.

(21)

4 实验分析

4.1 实验数据

1)算例数据.灾后需要将灾民及时疏散到安全

区域,避免二次灾难对人员造成伤害.为了争取救援时间,提高救援效率,邻近灾民往往自行聚集到一个地点,等待救援.组织者在灾区附近的安全区域建立避难所,以供疏散的灾民临时居住.基于上述背景,搜集212个点的坐标及各点之间的连接关系,构成疏散物流网络的弧的数量是390.整个网络的分布如图4所示,设定212个地点的位置,连接这些地点的路段总共有390个.已知起点(图4的小圆点)和终点(图4的大圆点),要求选择长度最短且可靠性最高的道路完成疏散任务.在所研究的灾区,有2个地方受到灾害的破坏最严重,采用0.7+0.3(r/R)作为距离重灾中心为r的道路的可靠性,其中R为参考半径.由于道路上各点到重灾中心的距离不断变化,为了方便计算,采用道路中心点代表道路的位置,由此计算每条道路的可靠性.2个重灾中心及其辐射如图4的同心圆所示,路线的起点和终点如图4的深色圆圈所示.

图4 灾后路径选择实验背景地图Fig.4 Example’s base map for route selection after disaster

2)算法参数.遗传算法中主要涉及到以下参数,设置如表1所示,表中，ns为种群规模，ni为迭代次数，PP为帕累托概率，Pc、Pm分别为交叉概率和变异概率.

表1 遗传算法参数表

4.2 实验设计

设计如表2所示的6个实验.

表2 灾后路径选择实验目标、实验场景设置

4.3 实验结果及说明

1)实验1的结果如图5所示.

图5 采用最小值法计算道路可靠性Fig.5 Road reliability based on minimum value method

图6 采用平均值法计算道路可靠性Fig.6 Road reliability based on mean value method

分别选取Pareto front上的3点分析路线长度及可靠性.解1中路线长度为583,道路可靠性为0.701；解2中路线长度为883,道路可靠性为0.708；解3中路线长度为1 561,道路可靠性为0.709.

2)实验2的结果如图6所示.

分别选取Pareto front上的3点分析路线长度及可靠性.解1中路线长度为689,道路可靠性为0.701；解2中路线长度为969,道路可靠性为0.714；解3中路线长度为1 303,道路可靠性为0.721.

3)实验3的结果如图7所示.

图7 采用串联法计算道路可靠性Fig.7 Road reliability based on series connection method

分别选取Pareto front上的3点分析路线长度及可靠性.解1中路线长度为568,道路可靠性为0.001 88；解2中路线长度为712,道路可靠性为0.003 84；解3中路线长度为728,道路可靠性为0.016 46.

采用串联法时,道路的可靠性由构成道路的每条路段的可靠性相乘得到,串联法下道路的可靠性最小.当可靠性都为0.701时,采用最小值法模型得到的路线比平均值法模型短.随着道路可靠性的提高,路线长度显著增加.在串联法模型中,解2的可靠性比解1提高了104.26%,长度仅增加了25.35%；最小值模型中解2的可靠性比解1提高了1%,长度增加了51.46%；平均值模型中解2比解1的可靠性提高了1.85%,长度增加了40.64%.串联法中路线长度的小幅度增长能够带来道路可靠性的大幅提高.

4)实验4的结果如图8所示.

图8 理想的帕累托前端面Fig.8 Ideal Pareto front

采用平均值法计算道路可靠性,运行结束后将最后得到的染色体解码成相应的行驶路线.根据每条路线出现的频率大小进行排序,形成不同等级的解,据此绘制成不同等级的帕累托前端面.图8分别展示了2个等级的帕累托前端面.图中，rf、sf分别为前端面的比例和面积.图8(a)中前端面的比例为0.997 9,面积为686.267；图8(b)中比例为0.998 01,面积为686.344 2.不同等级的前端面上的解均是可行解,第一前端面上个体的适应度最高.

5)实验5的结果如图9所示.

图9 交叉概率的影响Fig.9 Influence of crossover ratio

随着交叉概率的逐渐增大,覆盖范围波动式变化,理想积波动式下降.当交叉概率为0.9时,覆盖范围最小；当交叉概率为0.1或0.8时,覆盖范围最大(见图9(a)).当交叉概率取0.9时,交叉操作较频繁,得到最小的理想积(见图9(b)).

6)实验6的结果如图10所示.图中，COV为覆盖范围，VI为理想积.

图10 变异概率的影响Fig.10 Influence of mutation ratio

随着变异概率的逐渐增大,覆盖范围波动式变化,理想积缓慢增长后逐渐下降.当变异概率为0.05时,覆盖范围最小；当变异概率为0.04时,覆盖范围最大(见图10(a)).当变异概率取0.09时,可以得到最小的理想积(见图10(b)).

5 结 语

基于最短路问题,本文考虑灾后道路损毁严重的情况,定义道路可靠性,构建双目标优化问题.一方面最小化给定起讫点间的道路长度,另一方面最大化道路的可靠性.本文给定212个点的坐标,设定各点间的连接关系,采用欧式距离计算两点间的距离,设定其中两个地方为重灾点.采用NSGA- II多目标遗传算法求解,在Matlab软件下进行仿真实验.分别得到3种不同可靠性确定方法下的解,开展2个目标的Pareto分析,最后分析交叉概率和变异概率对结果的影响.帕累托前端面上的解均为最优解,决策者可以根据其对某一目标的偏重选择合适的解；交叉概率和变异概率对结果的影响不明显,可能与选择的案例数据有关.未来的研究可以基于灾后的真实信息进行,实际考察灾区的道路状况,选择坡道转弯少的最短最可靠的道路完成物资输送、灾民疏散等任务,为灾后救援提供实际的参考.考虑道路修复等因素,实时衡量道路的可靠性,进行动态决策,更贴近实际生活.

[1] 闫化海, 徐寅峰. 不完全信息下交通网络最短路径关键边问题[J]. 系统工程, 2006, 24(2): 37-40． YAN Hua-hai, XU Yin-feng. The most vital edge of the shortest path with incomplete information in traffic networks [J]. Systems Engineering, 2006, 24(2): 37-40．

[2] NAZEMI A, OMIDI F. An efficient dynamic model for solving the shortest path problem [J]. Transportation Research Part C, 2013, 26(2013): 1-19．

[3] FESTA P, GUERRIERO F, LAGANA D, et al. Solving the shortest path tour problem [J]. European Journal of Operational Research, 2013, 230(2013): 464-474．

[4] AMIRTEIMOORI A. An extended shortest path problem: a data envelopment analysis approach [J]. Applied Mathematics Letters, 2012, 25(2012): 1839-1843．

[5] ASAKURA Y, KASHIWADANI M. Road network reliability caused by daily fluctuation of traffic flow [C]∥Proceedings of the 19th PTRC Summer Annual Meeting. Brighton: [s. n.], 1991: 73-84．[6] CHEN A, YANG H, LO H. Capacity reliability of a road network: an assessment methodology and numerical results [J]. Transportation Research Part B: Methodological, 2002, 36(3): 225-252．

[7] ARDAKANI M K, TAVANA M. A decremental approach with the A*algorithm for speeding-up the optimization process in dynamic shortest path problems [J]. Measurement, 2015, 60(2015) : 299-307．[8] 靳凯文, 李春葆, 秦前清.基于蚁群算法的最短路径搜索方法研究[J]. 公路交通科技, 2006, 23(3): 128-131． JIN Kai-wen, LI Chun-bao, QIN Qian-qing. Study on shortest path search method based on ant algorithm [J]. Journal of Highway and Transportation Research and Development, 2006, 23(3): 128-131．

[9] LOZANO L, MEDAGLIA A S L. On an exact method for the constrained shortest path problem [J]. Computers and Operations Research, 2013, 40(2013): 378-384．

[10] CHENG J, LISSER A.Maximum probability shortest path problem [J]. Discrete Applied Mathematics, 2015, 192(2015): 40-48．

[11] 邹亮, 徐建闽. 基于遗传算法的动态网络中最短路径问题算法[J]. 计算机应用, 2005, 25(4): 742-744． ZOU Liang, XU Jian-min. Method of shortest paths problem on dynamic network based on genetic algorithm [J]. Computer Applications, 2005, 25(4): 742-744．

[12] NIKSIRAT M, GHATEE M, HASHEMI S M. Multimodal K-shortest viable path problem in Tehran public transportation network and its solution applying ant colony and simulated annealing algorithms [J]. Applied Mathematical Modeling, 2012, 36(2012): 5709-5726．

[13] HASUIKE T.Robust shortest path problem based on a confidence interval in fuzzy bicriteria decision making [J]. Information Sciences, 2013, 221(2013): 520-533．

[14] CHEN P, NIE Y. Bicriterion shortest path problem with a general nonadditive cost [J]. Procedia-Social and Behavioral Sciences, 2013, 80(2013): 553-575．

[15] LEE S, MOON B, ASAKURA Y.Reliability analysis and calculation on large scale transport networks, in reliability of transport networks [M]. England: Research Studies Press Limited, 2000: 173-189．

[16] 陈富坚, 柳本民, 郭忠印, 等. 基于贝叶斯分析的道路交通系统可靠性模型[J]. 同济大学学报：自然科学版, 2011, 39(2): 220-225． CHEN Fu-jian, LIU Ben-min, GUO Zhong-yin, et al. Reliability models of road traffic systems based on Bayesian analysis [J]. Journal of Tongji University: Natural Science, 2011, 39(2): 220-225．

[17] 侯立文, 蒋馥. 城市道路网络可靠性的研究[J]. 系统工程, 2000, 18(5): 44-48． HOU Li-wen, JIANG Fu. Study on the reliability of urban road network [J]. Systems Engineering, 2000, 18(5): 44-48．

[18] 秦军, 曹云刚, 耿娟. 汶川地震灾区道路损毁度遥感评估模型[J]. 西南交通大学学报, 2010, 45(5): 768-774． QIN Jun, CAO Yun-gang, GENG Juan. Evaluation model for damage extent of roads in Wenchuan earthquake-stricken areas based on remote sensing information [J]. Journal of Southwest Jiaotong University, 2010, 45(5): 768-774．

[19] GEN M, CHENG R, LIN L. Network models and optimization: multiobjective genetic algorithm approach[M]. Germany:Springer, 2008: 15-74.

Reliable path selection after disaster based on multi-objective genetic algorithm

LI Qing1,2, HU Zhi-hua2

(1.SchoolofEconomicsandManagement,TongjiUniversity,Shanghai200092,China; 2.LogisticsResearchCenter,ShanghaiMaritimeUniversity,Shanghai201306,China)

The shortest path is needed to transport victims and materials as soon as possible. Safe path becomes the critical factor in road selection considering the road damage in the disaster. Three means were adopted to define the road reliability based on the damage condition of roads after a disaster, and a bi-objective optimization model was established. The model tries to minimize the length of road and maximize the roads’ reliability. The priority-based multi-objective genetic algorithm was used to handle the problem. The solutions were respectively got under three situations. Pareto analysis was conducted. The impacts of crossover rate and mutation rate on the results were analyzed. With the crossover ratio increases, the coverage fluctuates and the fluctuated ideal volume decreases. With the mutation ratio increases, the coverage fluctuates and the ideal volume grows slowly and then gradually declines. The genetic algorithm can effectively solve the shortest and most reliable path problem．

shortest path problem; multi-objective genetic algorithm; priority; reliability

2015-02-17. 浙江大学学报(工学版)网址： www.journals.zju.edu.cn/eng

国家自然科学基金青年资助项目(71101088)；国家自然科学基金面上项目(71171129)；国家自然科学基金资助项目(71390521)；上海市曙光计划资助项目(13SG48)；教育部博士点基金资助项目(20113121120002，20123121110004)；上海市科委资助项目(11510501900，12510501600，12ZR1412800)；上海市教委科研创新资助项目(14YZ100)；上海海事大学研究生学术新人培育项目(YXR2014075).

李清(1991-)，女，硕士生，从事应急物流的研究.ORCID: 0000-0001-7134-4941.E-mail：mzsq126@126.com 通信联系人：胡志华，男，副教授.E-mail: zhhu@shmtu.edu.cn

10.3785/j.issn.1008-973X.2016.01.006

U 491

A

1008-973X(2016)01-0033-08