Optimization model of fuzzy location-routing problem for searching trapped personnels in flood disaster
-
摘要: 为保障洪灾被困人员搜救效果, 分析了救援过程的特性, 建立了一个带时间窗和模糊搜救时间的定位-路径问题优化模型, 并提出一种遗传求解算法, 采取三段式实数编码, 设计了与编码相应的交叉和变异操作, 在迭代过程中添加替代操作以加快收敛速度, 最后对模型及算法进行了验证。研究结果表明: 采用MATLAB编程实现该算法时, 将程序运行10次, 平均运行时间为42.95 s, 最差解和最好解与平均值的偏差仅分别为1.56%和3.48%。可见, 算法是高效、收敛和稳定的, 模型可行。Abstract: For ensuring the search-and-rescue effect of trapped personnel in flood disaster, the characteristics of rescue process were analyzed, an optimization model of location-routing problem (LRP) with time windows and fuzzy rescue time was established, and a genetic algorithm was introduced. The algorithm used three-segment real-code and designed matching crossover and mutation operations, and a replacement operation was added in the iterative process to accelerate convergence. A numerical example was given to validate the model and the algorithm. Analysis result shows that the average running time of ten times is 42.95 s when a MATLAB program is designed to realize the algorithm, and the deviations of the worst and the best to the average value are 1.56% and 3.48% respectively. So the algorithm is efficient, convergent and stable, and the model is feasible.
-
表 1 被搜救点数据
Table 1. Data of rescue points
编号 坐标/km 被搜救点人数 救援一个人所用时间/min 最晚到达时刻 1 (3, 42) 18 (1.0, 1.2, 1.5) 1:30 2 (11, 40) 46 (1.0, 1.2, 1.5) 1:00 3 (19, 69) 13 (1.0, 1.2, 1.5) 2:00 4 (37, 53) 11 (1.0, 1.2, 1.5) 2:00 5 (49, 64) 8 (1.0, 1.2, 1.5) 2:00 6 (55, 79) 12 (1.0, 1.2, 1.5) 1:30 7 (47, 87) 29 (1.0, 1.2, 1.5) 2:00 8 (40, 89) 9 (1.0, 1.2, 1.5) 2:00 9 (41, 9) 11 (1.0, 1.2, 1.5) 1:30 10 (47, 3) 12 (1.0, 1.2, 1.5) 2:00 11 (45, 16) 8 (2.9, 3.0, 3, 5) 1:30 12 (54, 3) 7 (2.9, 3.0, 3, 5) 2:00 13 (55, 21) 33 (2.9, 3.0, 3, 5) 1:30 14 (61, 30) 9 (2.9, 3.0, 3, 5) 2:30 15 (64, 52) 11 (2.9, 3.0, 3, 5) 2:00 16 (72, 45) 9 (2.9, 3.0, 3, 5) 3:00 17 (74, 31) 7 (2.9, 3.0, 3, 5) 3:00 18 (85, 60) 37 (2.9, 3.0, 3, 5) 2:00 19 (88, 66) 8 (2.9, 3.0, 3, 5) 2:00 20 (93, 62) 12 (2.9, 3.0, 3, 5) 3:00 
下载: 导出CSV
表 2 候选避难所数据
Table 2. Data of candidate shelters
编号 坐标/km 容量/人 1 (30, 28) 50 2 (75, 80) 50 3 (12, 60) 100 4 (38, 77) 100 5 (62, 13) 100 6 (68, 33) 50 7 (87, 49) 50 8 (95, 97) 50
下载: 导出CSV
表 3 船只停靠点
Table 3. Docking points of boats
编号 坐标/km 拥有船只编号 1 (19, 32) 1~5 2 (45, 36) 6~11 3 (71, 69) 12~20
下载: 导出CSV
表 5 最好解搜救路径
Table 5. Rescue routes of best solution
船只编号 搜救路径 船只编号 搜救路径 1 1-2-3-3 11 2-14-17-6 2 1-2-3 12 3-15-16-6 3 1-1-3 13 3-18-7 4 1-2-3 14 3-19-20-7 5 15 3-18-7 6 2-13-5 16 3-4-5-4 7 2-10-12-5 17 8 2-11-5 18 3-6-4 9 2-9-5 19 3-7-4 10 2-13-5 20 3-7-8-4 注: 搜救路径编写格式为船只停靠点编号-被搜救点编号-避难所编号。
下载: 导出CSV
-
[1] MI N H, JAYARAMAN V, SRI VASTAVA R. Combinedlocation-routing problems: a synthesis and future researchdirections[J]. European Journal of Operational Research, 1998, 108 (1): 1-15. doi: 10.1016/S0377-2217(97)00172-0 [2] 汪寿阳, 赵秋红, 夏国平. 集成物流管理系统中的定位-运输路线安排问题的研究[J]. 管理科学学报, 2000, 3 (2): 69-75. https://www.cnki.com.cn/Article/CJFDTOTAL-JCYJ200002010.htmWANG Shou-yang, ZHAO Qiu-hong, XIA Guo-ping. Researchon combined location-routing problems in integrated logisticssystems[J]. Journal of Management Sciences in China, 2000, 3 (2): 69-75. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JCYJ200002010.htm [3] 林岩, 胡祥培, 王旭茵. 物流系统优化中的定位-运输路线安排问题(LRP) 研究评述[J]. 管理工程学报, 2004, 18 (4): 45-49. https://www.cnki.com.cn/Article/CJFDTOTAL-GLGU200404009.htmLI N Yan, HU Xiang-pei, WANG Xu-yin. Review on loca-tion-routing problems (LRP) in systematic opti mization oflogistics[J]. Journal of Industrial Engineering and Engineering Management, 2004, 18 (4): 45-49. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GLGU200404009.htm [4] NAGY G, SALHI S. Location-routing: issues, models andmethods[J]. European Journal of Operational Research, 2007, 177 (2): 649-672. doi: 10.1016/j.ejor.2006.04.004 [5] 张潜, 高立群, 刘雪梅, 等. 定位-运输路线安排问题的两阶段启发式算法[J]. 控制与决策, 2004, 19 (7): 773-777. https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200407012.htmZHANG Qian, GAO Li-qun, LI U Xue-mei, et al. A two-phase heuristic approach to the location routing problem[J]. Control and Decision, 2004, 19 (7): 773-777. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-KZYC200407012.htm [6] 张长星, 党延忠. 定位-运输路线安排问题的遗传算法研究[J]. 计算机工程与应用, 2004, 40 (12): 65-68, 183. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200412020.htmZHANG Chang-xing, DANG Yan-zhong. A novel geneticalgorithm for location-routing problem[J]. ComputerEngineering and Applications, 2004, 40 (12): 65-68, 183. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200412020.htm [7] 胡大伟, 朱志强, 胡勇. 车辆路径问题的模拟退火算法[J]. 中国公路学报, 2006, 19 (4): 123-126. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604022.htmHU Da-wei, ZHUZhi-qiang, HU Yong. Simulated annealing algorithm for vehicle routing problem[J]. China Journal of Highway and Transport, 2006, 19 (4): 123-126. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604022.htm [8] 张潜, 李钟慎, 胡祥培. 基于模糊优化的物流配送路径(MLRP) 问题研究[J]. 控制与决策, 2006, 21 (6): 689-692. doi: 10.3321/j.issn:1001-0920.2006.06.018ZHANG Qian, LI Zhong-shen, HU Xiang-pei. Research onmulti-objective location routing problem based on fuzzy opti-mization[J]. Control and Decision, 2006, 21 (6): 689-692. (in Chinese) doi: 10.3321/j.issn:1001-0920.2006.06.018 [9] 张建勇, 李军. 具有同时配送和回收需求的车辆路径问题的混合遗传算法[J]. 中国公路学报, 2006, 19 (4): 118-122. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604021.htmZHANGJian-yong, LI Jun. Hybrid genetic algorithmto vehiclerouting problem with si multaneous delivery and pick-up[J]. China Journal of Highway and Transport, 2006, 19 (4): 118-122. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200604021.htm [10] YI Wei, OZDAMAR L. Adynamic logistics coordination modelfor evacuation and support in disaster response activities[J]. European Journal of Operational Research, 2007, 179 (3): 1177-1193. doi: 10.1016/j.ejor.2005.03.077 [11] 徐琴, 马祖军, 李华俊. 城市突发公共事件在应急物流中的定位-路径问题研究[J]. 华中科技大学学报: 社会科学版, 2008, 22 (6): 36-40. https://www.cnki.com.cn/Article/CJFDTOTAL-HZLS200806012.htmXU Qin, MA Zu-jun, LI Hua-jun. Location-routing problemin emergency logistics for public emergencies[J]. Journal ofHuazhong University of Science and Technology: SocialScience Edition, 2008, 22 (6): 36-40. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-HZLS200806012.htm [12] 郑斌, 马祖军, 方涛. 应急物流系统中的模糊多目标定位-路径问题[J]. 系统工程, 2008, 27 (8): 21-25. https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200908005.htmZHENG Bin, MAZu-jun, FANG Tao. Fuzzy multi-objectivelocation-routing problemin emergency logistics systems[J]. Systems Engineering, 2008, 27 (8): 21-25. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-GCXT200908005.htm [13] 曾敏刚, 崔增收, 余高辉. 基于应急物流的减灾系统LRP研究[J]. 中国管理科学, 2010, 18 (2): 75-80. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201002011.htmZENG Min-gang, CUI Zeng-shou, YU Gao-hui. Research onlocation-routing problemof relief systembased on emergencylogistics[J]. Chinese Journal of Management Science, 2010, 18 (2): 75-80. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGK201002011.htm [14] 代颖, 马祖军, 郑斌. 突发公共事件应急系统中的模糊多目标定位-路径问题研究[J]. 管理评论, 2010, 22 (1): 121-128. https://www.cnki.com.cn/Article/CJFDTOTAL-ZWGD201001017.htmDAI Ying, MA Zu-jun, ZHENG Bin. Fuzzy multi-objectivelocation-routing problemin emergency systems for unexpectedpublic emergency[J]. Management Review, 2010, 22 (1): 121-128. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZWGD201001017.htm [15] 许瑞丽, 徐泽水. 模糊数排序的一种新方法[J]. 数学的实践与认识, 2008, 38 (17): 111-120. https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200817019.htmXU Rui-li, XU Ze-shui. A new method for ranking fuzzynumbers[J]. Mathematics in Practice and Theory, 2008, 38 (17): 111-120. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-SSJS200817019.htm -
点击查看大图
图(3) / 表(5)
计量
- 文章访问数: 666
- HTML全文浏览量: 117
- PDF下载量: 561
- 被引次数: 0
