Combinatorial optimization algorithm of rapid road repair and material distribution after disaster
-
摘要: 为了在有限的时间内同时获得最佳抢修效益和物资配送方案, 提高救灾工作效率, 针对灾后道路抢修与救灾物资配送问题, 利用时空网络流动技巧, 构建了两者相应的时空网络, 在考虑两者的相关性后, 建立了多目标的灾后道路抢修工程与紧急物资配送混合整数多重网络规划模型, 提出了分解启发式求解方法。算例计算结果表明, 用CPLEX数学规划软件直接求解, 在求解到106.9 h时, 才可求得最优解, 而分解启发式方法只需31.8 min即可求得最优解, 其求解效率大幅提高, 求解时间对于实际的救灾工作是可以接受的。Abstract: In order to obtain the highest road repair benefit and the optimized material distribution project within limited time, and enhance relief efficiency after disaster, the problems of rapid road repair and material distribution after disaster were analyzed, their time-space networks were respectively constructed by using the flowing technique of time-space network, the relativity between rapid road repair and material distribution was considered, a multi-objective mixed integer-multiple network programming model was founded relating with rapid road repair engineering and urgency material distribution after disaster, and a decomposition heuristic algorithm was put forward.The calculated result of an instance shows that it takes 106.9 h to obtain the optimized solution of the model with CPLEX math programming software, while it only takes 31.8 min with the algorithm.Its calculation efficiency is high, and the calculation time is acceptable in actual relief work after disaster.
-
表 2 抢修工时
Table 2. Repair man-hour
灾点编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 抢修工时/15min 16 8 16 4 8 4 4 4 12 12 16 16 8 16 12 16 8 16 14 4 12 12 8 4 
下载: 导出CSV
表 3 距离转换结果
Table 3. Distance conversion result
时点 0 1 2 3 4 5 6 7 8 9 10 距离/km 0.0~3.0 3.1~7.5 7.6~15.0 15.1~22.5 22.6~30.0 30.1~37.5 37.6~45.0 45.1~52.5 52.6~60.0 60.1~67.5 67.6~75.0
下载: 导出CSV
表 4 救灾物资供需量输入值
Table 4. Input value of disaster rescue material
配送中心编号 Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 供给量(当量) 3 000 5 000 4 000 2 000 1 000 物资需求点编号 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 需求量(当量) 5 500 6 200 2 200 6 500 200 200 500 100
下载: 导出CSV
表 5 直接求解的输出结果
Table 5. Output result of direct solution
权重比 单目标值/h 总目标值/h Ω/% 求解时间/h α β R V 0.5 0.5 41.0 33.0 37.0 68 48.0 39.0 17.0 28.0 0 106.9 注: Ω为目前所得的整数最优解与整数约束松弛下的有限最优解的差距。
下载: 导出CSV
表 6 启发解法的输出结果
Table 6. Output result of heuristic algorithm
权重比 单目标值/h 总目标值/h 求解时间/min α β 求解顺序 R V 0.5 0.5 1 39.0 18.0 28.5 26.1 2 — — — 0.6 3 39.0 18.0 28.5 0.8 4 39.0 18.0 28.5 5.0 启发解 39.0 18.0 28.5 31.8 注: 1为分区域求解, 所求得的可行解作为下一步骤的最终时点, 以缩小网络规模; 2求解顺序为: 自由点→限制点→有前置限制点; 3求解顺序为: 限制点→有前置限制点→自由点; 4求解顺序为: 有前置限制点→限制点→自由点。
下载: 导出CSV
-
[1] 宋瑞, 何世伟, 杨永凯, 等. 公交时刻表设计与车辆运用综合优化模型[J]. 中国公路学报, 2006, 19 (3): 70-76. https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200603012.htmSong Rui, He Shi-wei, Yang Yong-kai, et al. Integrated optimization model of transit scheduling plan and bus use[J]. China Journal of Highway and Transport, 2006, 19 (3): 70-76. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-ZGGL200603012.htm [2] Yan Shang-yao, Chen Hao-lei. A scheduling model and a solution algorithm for intercity bus carriers[J]. Transportation Research: Part A, 2002, 36 (9): 805-825. [3] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters[J]. Safety Science, 2000, 35 (1): 41-57. [4] 张建雄, 唐万生. 基于混沌遗传算法的一类非线性两层混合整数规划问题求解[J]. 系统工程理论方法应用, 2005, 14 (5): 429-433. https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL200505008.htmZhang Jian-xiong, Tang Wan-sheng. Chaos genetic algorithm method for a class of nonlinear bilevel mixed integer-programming problem[J]. Systems Engineering Theory Methodology Applications, 2005, 14 (5): 429-433. (in Chinese) https://www.cnki.com.cn/Article/CJFDTOTAL-XTGL200505008.htm [5] 刘德新, 吴兆麟, 贾传荧. 多层次多目标重点避让船模糊优选模型[J]. 交通运输工程学报, 2005, 5 (1): 49-52. http://transport.chd.edu.cn/article/id/200501012Liu De-xin, Wu Zhao-lin, Jia Chuan-ying. Multi-layers and multi-objects fuzzy opti mization model of main target ship[J]. Journal of Traffic and Transportation Engineering, 2005, 5 (1): 49-52. (in Chinese) http://transport.chd.edu.cn/article/id/200501012 [6] 韩世莲, 李旭宏, 刘新旺. 物流运输网络模糊最短路径的偏好解[J]. 交通运输工程学报, 2005, 5 (2): 122-126. http://transport.chd.edu.cn/article/id/200502029Han Shi-lian, Li Xu-hong, Liu Xin-wang. Preference solution of fuzzy shortest pathinlogistics transportation networks[J]. Journal of Traffic and Transportation Engineering, 2005, 5 (2): 122-126. (in Chinese) http://transport.chd.edu.cn/article/id/200502029 [7] Yan Shang-yao, Huo Jun-ming. Optimization of multiple objective gate assignments[J]. Transportation Research: PartA, 2001, 35 (5): 413-432. [8] 杨瑞臣, 周永付, 云庆夏. 寻找车辆最优路径的混合算法[J]. 交通运输工程学报, 2005, 5 (1): 102-105. doi: 10.3321/j.issn:1671-1637.2005.01.024Yang Rui-chen, Zhou Yong-fu, Yun Qing-xia. Hybrid algorithm of vehicles optimal route[J]. Journal of Traffic and Transportation Engineering, 2005, 5 (1): 102-105. (in Chi-nese). doi: 10.3321/j.issn:1671-1637.2005.01.024 [9] 陈松岩, 今井昭夫. 物流网络选址与路径优化问题的模型与启发式解法[J]. 交通运输工程学报, 2006, 6 (3): 118-121. http://transport.chd.edu.cn/article/id/200603025Chen Song-yan, I mai Akio. Model and heuristic solution for location routing problems of logistics network[J]. Journal of Traffic and Transportation Engineering, 2006, 6 (3): 118-121. (in Chinese) http://transport.chd.edu.cn/article/id/200603025 [10] Chang S E, Noji ma N. Measuring post-disaster transportation system performance: the 1995 Kobe earthquake in comparative perspective[J]. Transportation Research: Part A, 2001, 35 (6): 475-494. -
点击查看大图
图(2) / 表(6)
计量
- 文章访问数: 252
- HTML全文浏览量: 82
- PDF下载量: 647
- 被引次数: 0
