| Civil Engineering, Transportation Engineering |
|
|
|
|
| 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 |
|
|
|
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．
|
|
Published: 31 March 2016
|
|
|
基于多目标遗传算法的灾后可靠路径选择
为了尽快运出灾民、运进物资,灾后需要选择最短的运输路径；考虑到灾害对道路的损毁,安全的路径是道路选择中的重要因素,基于灾后道路的损毁状况,采用3种方法定义
道路可靠性,以最小化路径长度、最大化路径可靠性为目标建立双目标优化模型,采用多目标遗传算法求解.分别求得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): 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. |
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
