Please wait a minute...
浙江大学学报(工学版)
土木工程、交通工程     
基于多目标遗传算法的灾后可靠路径选择
李清1,2,胡志华2
1. 同济大学 经济与管理学院,上海200092;2. 上海海事大学 物流研究中心,上海201306
Reliable path selection after disaster based on multi objective genetic algorithm
LI Qing1,2, HU Zhi hua2
1. School of Economics and Management, Tongji University, Shanghai 200092, China;2. Logistics Research Center, Shanghai Maritime University, Shanghai 201306, China
 全文: PDF(3087 KB)   HTML
摘要:
为了尽快运出灾民、运进物资,灾后需要选择最短的运输路径;考虑到灾害对道路的损毁,安全的路径是道路选择中的重要因素,基于灾后道路的损毁状况,采用3种方法定义
道路可靠性,以最小化路径长度、最大化路径可靠性为目标建立双目标优化模型,采用多目标遗传算法求解.分别求得3种情形下的解,开展2个目标的Pareto分析;分析交叉概率和变异概率对结果的影响:交叉概率增大,覆盖范围波动式变化,理想积波动式下降;变异概率增大,覆盖范围波动式变化,理想积缓慢增长后逐渐下降.采用遗传算法能够有效地解决最短和最可靠路径的搜索问题.
Abstract:
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.
出版日期: 2016-03-31
:  U 491  
基金资助:
国家自然科学基金青年资助项目(71101088);国家自然科学基金面上项目(71171129);国家自然科学基金资助项目(71390521);上海市曙光计划资助项目(13SG48);教育部博士点基金资助项目(20113121120002,20123121110004);上海市科委资助项目(11510501900,12510501600,12ZR1412800);上海市教委科研创新资助项目(14YZ100);上海海事大学研究生学术新人培育项目(YXR2014075).
通讯作者: 胡志华,男,副教授.     E-mail: zhhu@shmtu.edu.cn
作者简介: 李清(1991-),女,硕士生,从事应急物流的研究.ORCID:0000 0001 7134 4941.E-mail:mzsq126@126.com
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

李清,胡志华. 基于多目标遗传算法的灾后可靠路径选择[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2016.01.006.

LI Qing, HU Zhi hua. Reliable path selection after disaster based on multi objective genetic algorithm. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2016.01.006.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2016.01.006        http://www.zjujournals.com/eng/CN/Y2016/V50/I1/33

[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): 742744.
[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.
[1] 倪玲霖, 张帅超, 陈喜群. 基于手机信号令数据的居民出行空间效应[J]. 浙江大学学报(工学版), 2017, 51(5): 887-895.
[2] 曲昭伟, 曹宁博, 陈永恒, 白乔文, 康萌, 陈明涛. 信号交叉口的行人信号提前建模[J]. 浙江大学学报(工学版), 2017, 51(3): 538-544.
[3] 王福建, 龚成宇, 马东方, 郭伟伟, 王殿海. 采用交通出行量数据的多点联动瓶颈控制方法[J]. 浙江大学学报(工学版), 2017, 51(2): 273-278.
[4] 王韩麒, 陈红, 冯微, 刘玮蔚. 基于CPT的异质通勤者多维出行决策模型[J]. 浙江大学学报(工学版), 2017, 51(2): 297-303.
[5] 于谦, 李铁柱, 任彦铭. 乘客载重量对柴油公交车尾气排放影响分析[J]. 浙江大学学报(工学版), 2016, 50(10): 2009-2017.
[6] 付凤杰,龚越,王殿海,马东方. 基于高清智能卡口路段行程时间的数据质量分析[J]. 浙江大学学报(工学版), 2016, 50(9): 1761-1767.
[7] 王力,张立立,潘科,李正熙. 基于状态可控性分析的交叉口信号切换控制[J]. 浙江大学学报(工学版), 2016, 50(7): 1266-1275.
[8] 李明达,隗海林,门玉琢,包翠竹. 基于实际换挡规律的卡车列队行驶起步控制[J]. 浙江大学学报(工学版), 2016, 50(5): 887-892.
[9] 楼齐峰, 马晓龙, 叶盈, 梅振宇. 基于出行成本的停车收费和供给政策影响分析[J]. 浙江大学学报(工学版), 2016, 50(2): 257-264.
[10] 莫元富, 于德新, 宋军, 郭亚娟. 基于信道负载阈值的车联网信标消息生成策略[J]. 浙江大学学报(工学版), 2016, 50(1): 21-26.
[11] 王卫东,李俊杰,王京,傅庆湘,康文泓. 基于未确知测度的公路交通效率评价[J]. 浙江大学学报(工学版), 2016, 50(1): 48-54.
[12] 马明辉,杨庆芳,梁士栋,邢茹茹. 高速公路主线瓶颈区域的协调控制模型[J]. 浙江大学学报(工学版), 2015, 49(9): 1700-1706.
[13] 周旦, 马晓龙, 金盛, 王殿海. 混合非机动车交通流超车次率影响因素模型[J]. 浙江大学学报(工学版), 2015, 49(9): 1672-1678.
[14] 王福建, 戴美伟, 孙凌涛, 金盛. 基于多类跟驰行为的车头时距混合分布模型[J]. 浙江大学学报(工学版), 2015, 49(7): 1288-1294.
[15] 赵伟明, 王殿海, 朱文韬, 戴美伟. 基于改进NJW算法的交通控制时段划分[J]. 浙江大学学报(工学版), 2014, 48(12): 2259-2265.