基于离散混合蛙跳算法的地震应急物资调度

doi:10.16182/j.issn1004731x.joss.22-0884

摘要/Abstract

摘要：

建立震后应急物资调度数学模型。该模型根据各灾区的受灾情况评估其救援紧急程度，并设计一种需求拆分供应的运输机制，提高车辆的利用效率。为求解该模型，提出一种多源信息学习的离散混合蛙跳算法。所提算法引入多种信息源以扩展算法的搜索方向，降低种群的同化速度。同时，让子组最差个体学习种群中的有效信息，提高算法的收敛精度。实验结果表明，所提算法能够搜索到精度更优的调度方案，对问题规模具有良好的可扩展性。

关键词: 应急物资调度, 混合蛙跳算法, 灾区紧急程度, 需求拆分供应, 车辆路径问题

Abstract:

A mathematical model of emergency material scheduling after earthquakes is built. The model evaluates the emergency degree of each disaster area based on the disaster situation and designs a method to split the demand of the disaster area, improving the efficiency of vehicle utilization. To solve the model, this paper proposes a discrete shuffled frog leaping algorithm with multi-resource learning. The multiple information sources introduced by the proposed algorithm can expand the search direction and reduce the assimilation speed of the population in the algorithm. Second, the worst individual in each subgroup can learn the effective information in the population to improve the convergence accuracy of the algorithm. Experimental results show that the proposed algorithm can obtain a higher-quality scheduling scheme and has good scalability for the scale of emergency material scheduling.

Key words: emergency material scheduling, shuffled frog leaping algorithm, emergency degree, split delivery, vehicle routing problem

中图分类号:

TP391.9

申晓宁,葛忠佩,姚铖滨等 . 基于离散混合蛙跳算法的地震应急物资调度[J]. 系统仿真学报, 2024, 36(1): 97-109.

Shen Xiaoning,Ge Zhongpei,Yao Chengbin,et al . Emergency Material Scheduling Based on Discrete Shuffled Frog Leaping Algorithm[J]. Journal of System Simulation, 2024, 36(1): 97-109.

图/表 11

表1

图1

表2

模型符号说明

符号		含义
集合	$P k$	车辆 $k$ 供应的所有灾区集合
参数	$n$	灾区数量
	$K$	车辆最大使用数量
	$Q$	每辆车的最大容量
	$D i$	灾区 $i$ 的物资需求量
	$s j k$	车辆 $k$ 供应灾区 $j$ 的物资量
	$d i j$	灾区 $i$ 到灾区 $j$ 的距离
	$D i s j k$	车辆 $k$ 的行驶路线上从物资储备中心出发到达灾区 $j$ 的距离
	$M i$	灾区 $i$ 的物资供应优先级得分
	$e i$	灾区 $i$ 的救援紧急程度
	$G k$	车辆 $k$ 的紧急度成本
	$o d j k$	灾区j在车辆k中的供应顺序
决策变量	$x i j k$	车辆k从灾区i行驶至灾区j则为1，否则为0
决策变量	$y i k$	灾区i的物资由车辆k负责供应为1，否则为0

表2

图2

图3

图4

图5

表3

表4

图6

表5

参考文献 27

1	Liberatore F, Ortuño M T, Tirado G, et al. A Hierarchical Compromise Model for the Joint Optimization of Recovery Operations and Distribution of Emergency Goods in Humanitarian Logistics[J]. Computers & Operations Research, 2014, 42: 3-13.
2	安基文, 李晓丽, 范熙伟, 等. 面向地震应急的救援路径规划模型[J]. 交通运输系统工程与信息, 2019, 19(1): 172-178.
	An Jiwen, Li Xiaoli, Fan Xiwei, et al. Rescue Path Planning Model for Earthquake Emergency[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(1): 172-178.
3	都雪静, 王爱辉, 孙菲菲. 突发事件下公路应急物资调度优化[J]. 交通信息与安全, 2021, 39(4): 52-59.
	Du Xuejing, Wang Aihui, Sun Feifei. The Optimized Scheduling of Emergency Supplies in Highways Under Emergencies[J]. Journal of Transport Information and Safety, 2021, 39(4): 52-59.
4	苑津莎, 马姿, 杨宏. 地震救灾初期应急物资智能调度问题的研究[J]. 科学技术与工程, 2020, 20(21): 8702-8708.
	Yuan Jinsha, Ma Zi, Yang Hong. Research on Intelligent Dispatching of Emergency Materials in the Early Stage of Earthquake Relief[J]. Science Technology and Engineering, 2020, 20(21): 8702-8708.
5	Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.
6	Fleszar Krzysztof, Osman Ibrahim H, Hindi Khalil S. A Variable Neighbourhood Search Algorithm for the Open Vehicle Routing Problem[J]. European Journal of Operational Research, 2009, 195(3): 803-809.
7	Wang Xinyu, Choi T M, Liu Haikuo, et al. A Novel Hybrid Ant Colony Optimization Algorithm for Emergency Transportation Problems During Post-disaster Scenarios[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 48(4): 545-556.
8	邬开俊, 王铁君. 带时限的多出救点应急物资调度模型及算法[J]. 计算机工程与应用, 2012, 48(30): 19-23.
	Wu Kaijun, Wang Tiejun. Model and Optimization Algorithm of Multi-depot Emergency Materials Dispatching with Time Limits[J]. Computer Engineering and Applications, 2012, 48(30): 19-23.
9	Qi Chengming, Hu Lishuan. Optimization of Vehicle Routing Problem for Emergency Cold Chain Logistics Based on Minimum Loss[J]. Physical Communication, 2020, 40: 101085.
10	Eusuff M M, Lansey K E. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm[J]. Journal of Water Resources Planning and Management, 2003, 129(3): 210-225.
11	He Zhenxue, Xiao Limin, Wang Xiang. Minimization for Ternary Fixed Polarity Reed-muller Expressions Based on Ternary Quantum Shuffled Frog Leaping Algorithm[J]. Applied Soft Computing, 2021, 110: 107647.
12	Cai Jingcao, Zhou Rui, Lei Deming. Dynamic Shuffled Frog-leaping Algorithm for Distributed Hybrid Flow Shop Scheduling with Multiprocessor Tasks[J]. Engineering Applications of Artificial Intelligence, 2020, 90: 103540.
13	Dash Rajashree. Performance Analysis of a Higher Order Neural Network with an Improved Shuffled Frog Leaping Algorithm for Currency Exchange Rate Prediction[J]. Applied Soft Computing, 2018, 67: 215-231.
14	Guo Yuxue, Tian Xin, Fang Guohua, et al. Many-objective Optimization with Improved Shuffled Frog Leaping Algorithm for Inter-basin Water Transfers[J]. Advances in Water Resources, 2020, 138: 103531.
15	曹彦波, 李永强, 李兆隆, 等. 地震紧急救援区域优先度判定模型研究[J]. 自然灾害学报, 2014, 23(3): 181-189.
	Cao Yanbo, Li Yongqiang, Li Zhaolong, et al. Discrimination Model of Priority of Seismic Emergency Rescue zone[J]. Journal of Natural Disasters, 2014, 23(3): 181-189.
16	Bernabé Dorronsoro Díaz. The VRP Web[EB/OL]. [2022-06-30]. .
17	Kaur Parmeet, Mehta Shikha. Resource Provisioning and Work Flow Scheduling in Clouds Using Augmented Shuffled Frog Leaping Algorithm[J]. Journal of Parallel and Distributed Computing, 2017, 101: 41-50.
18	Tang Jianxin, Zhang Ruisheng, Wang Ping, et al. A Discrete Shuffled Frog-leaping Algorithm to Identify Influential Nodes for Influence Maximization in Social Networks[J]. Knowledge-Based Systems, 2020, 187: 104833.
19	Zhang Xinming, Kang Qiang, Wang Xia. Hybrid Biogeography-based Optimization with Shuffled Frog Leaping Algorithm and Its Application to Minimum Spanning Tree Problems[J]. Swarm and Evolutionary Computation, 2019, 49: 245-265.
20	Jadidoleslam Morteza, Ebrahimi Akbar. Reliability Constrained Generation Expansion Planning by a Modified Shuffled Frog Leaping Algorithm[J]. International Journal of Electrical Power & Energy Systems, 2015, 64: 743-751.
21	Zhang Xiaodan, Zhang Yifeng, Shi Yuhui, et al. Power Control Algorithm in Cognitive Radio System Based on Modified Shuffled Frog Leaping Algorithm[J]. AEU-International Journal of Electronics and Communications, 2012, 66(6): 448-454.
22	Huang Yao, Shen Xiaoning, You Xuan. A Discrete Shuffled Frog-leaping Algorithm Based on Heuristic Information for Traveling Salesman Problem[J]. Applied Soft Computing, 2021, 102: 107085.
23	Altabeeb Asma M, Mohsen Abdulqader M, Ghallab Abdullatif. An Improved Hybrid Firefly Algorithm for Capacitated Vehicle Routing Problem[J]. Applied Soft Computing, 2019, 84: 105728.
24	Jiang Hao, Lu Mengxin, Tian Ye, et al. An Evolutionary Algorithm for Solving Capacitated Vehicle Routing Problems by Using Local Information[J]. Applied Soft Computing, 2022, 117: 108431.
25	朱莉, 曹杰, 顾珺, 等. 公平缓解灾民创伤下的应急物资动态调配研究[J]. 系统工程理论与实践, 2020, 40(9): 2427-2437.
	Zhu Li, Cao Jie, Gu Jun, et al. Dynamic Emergency Supply Distribution Considering Fair Mitigation of Victim Suffering[J]. Systems Engineering-Theory & Practice, 2020, 40(9): 2427-2437.
26	Jiao Lei, Peng Zhihong, Xi Lele, et al. A Multi-stage Heuristic Algorithm Based on Task Grouping for Vehicle Routing Problem with Energy Constraint in Disasters[J]. Expert Systems with Applications, 2023, 212: 118740.
27	Luo Jianping, Chen Minrong. Improved Shuffled Frog Leaping Algorithm and Its Multi-phase Model for Multi-depot Vehicle Routing Problem[J]. Expert Systems with Applications, 2014, 41(5): 2535-2545.

1级指标	权重值(W¹)	2级指标	权重值(W²)	3级指标	得分(S)
评估因子	0.4	烈度	0.35	Ⅵ/ Ⅶ/ Ⅷ/ Ⅸ/ Ⅹ/ Ⅺ	0/0/1/2/3/4
		震亡人数	0.23	各灾区震亡人数的归一化数值	5
		受伤人数	0.11	各灾区受伤人数的归一化数值	5
		次生地质灾害风险等级	0.13	微度/ 轻度/ 中度/ 重度/ 特重	0/0/1/4/5
客观因子	0.6	人口密度	0.03	大于平均/ 小于平均	7/3
		震中距灾区县城距离/km	0.04	≤ 5/ 6 ~ 10/ 11 ~ 20/ 21 ~ 30/ > 31	5/3/1.5/0.5/0
		人口聚集度	0.06	密集/ 均值/ 稀疏	6/3/1
		震中位置	0.05	灾区是否位于震中	1/0

算例 VRP-n-k	DSFLAMRL		DSFLAMRL-M		DSFLAMRL-I
算例 VRP-n-k	Avg.	Best	Avg.	Best	Avg.	Best
A-36-5	645.15	634.80	644.28-	594.29	676.58+	673.67
A-46-7	604.01	574.48	601.84-	554.01	646.97+	574.42
A-60-9	527.12	512.41	532.27=	515.65	572.97+	528.99
A-69-9	575.56	548.91	645.43+	551.35	622.06+	569.12
A-80-10	572.53	537.74	623.21+	580.46	601.27+	573.77
E-101-14	379.76	362.65	426.33+	410.54	392.37=	366.42
F-135-7	1 036.04	983.50	1 168.66+	1 104.19	1 110.77+	1 038.29
X-153-22	872.94	824.43	936.38+	886.47	899.01+	832.90
X-204-19	1 249.53	1 136.49	1 500.23+	1 351.05	1 367.48+	1 266.23
X-251-28	1 354.70	1 285.53	1 522.68+	1 468.85	1 391.88+	1 308.68
实例	463.92	398.8	494.68+	412.48	503.24+	456.66
+/方正汇总行-/=			8/2/1		10/0/1

测试算例 VRP-n-k		DSFLAMRL	GA	CVRP-FA	MSVR-TG	RMEA	ISFLA
A-36-5	Avg.	645.15	726.66+	723.30+	718.29+	664.00+	951.04+
A-36-5	Best	634.80	684.95	651.33	681.76	636.43	819.18
A-46-7	Avg.	604.01	784.08+	721.91+	724.83+	639.36+	828.91+
A-46-7	Best	574.49	721.03	623.22	674.18	599.99	681.71
A-60-9	Avg.	527.12	832.16	701.08+	957.89+	825.85+	1 071.59+
A-60-9	Best	512.41	830.41	610.64	881.93	750.70	958.42
A-69-9	Avg.	575.56	938.70+	831.63+	631.18+	673.70+	1 248.71+
A-69-9	Best	548.91	901.57	729.87	588.13	598.44	1 028.54
A-80-10	Avg.	572.53	831.43+	760.95+	861.86+	670.35+	1 028.87+
A-80-10	Best	537.74	725.24	619.68	880.94	647.147	911.02
E-101-14	Avg.	379.76	680.44+	527.52+	464.04+	409.58+	546.24+
E-101-14	Best	362.65	641.03	456.10	433.60	364.28	491.32
F-135-7	Avg.	1 036.04	1 784.79+	1 900.74+	1 625.01+	1 168.94+	2 233.08+
F-135-7	Best	983.50	1 718.17	1 666.77	1 406.65	1 002.65	1 976.00
X-153-22	Avg.	872.94	1 691.34+	1 952.14+	1 175.80+	985.58+	2 024.78+
X-153-22	Best	824.43	1 588.69	1 755.52	1 102.80	874.83	1 856.17
X-204-19	Avg.	1 249.53	1 966.86+	2 106.84+	1 830.44+	1 357.56+	2 153.37+
X-204-19	Best	1 136.49	1 187.12	1 898.59	1 756.87	1 238.26	2 036.13
X-251-28	Avg.	1 354.70	1 696.93+	2 043.92+	1 586.89+	1 513.34+	2 034.64+
X-251-28	Best	1 285.53	1 532.42	1 691.48	1 405.95	1 321.36	1 930.67
实例	Avg.	463.92	812.89+	727.34+	661.53+	700.15+	739.79+
实例	Best	398.87	752.83	609.65	521.35	623.93	607.73
+/-/=			11/0/0	11/0/0	11/0/0	11/0/0	11/0/0

算法	最优目标值	实际路程
DSFLAMRL	463.92	398.87
GA	812.89	552.12
CVRP-FA	727.34	431.23
MSVR-TG	661.53	472.13
RMEA	700.15	519.25
ISFLA	739.79	591.38

[1]	张立, 贺明玲, 尹秋霜, 李宁, 余乐安. 不确定条件下多周期应急物资配送优化研究[J]. 系统仿真学报, 2023, 35(8): 1669-1680.
[2]	吴玉文, 牛智越, 李珍萍. 基于改进遗传算法的货箱机器人拣选路径规划[J]. 系统仿真学报, 2023, 35(5): 1086-1097.
[3]	张颖钰, 吴立云, 贾胜钛. 带时间窗的多中心半开放式VRPSDP问题研究[J]. 系统仿真学报, 2023, 35(11): 2464-2475.
[4]	陈雪, 胡蓉, 王辉, 李作成, 钱斌, 李熠胥. 学习型蚁群算法求解一类复杂两级车辆路径问题[J]. 系统仿真学报, 2023, 35(11): 2476-2495.
[5]	李楠, 胡蓉, 钱斌, 金怀平, 于乃康. 时间依赖型多时间窗车辆路径问题研究[J]. 系统仿真学报, 2022, 34(8): 1775-1788.
[6]	胡蓉, 江文, 钱斌, 于乃康. 两阶段优化算法求解绿色装箱车辆路径问题[J]. 系统仿真学报, 2022, 34(7): 1490-1505.
[7]	宁涛, 苟涛, 刘向东. 考虑低碳约束的生鲜农产品冷链物流策略仿真研究[J]. 系统仿真学报, 2022, 34(4): 797-805.
[8]	王伟权, 丁鼎, 颜林莎. 线性充电策略下多车型电动车辆路径模型研究[J]. 系统仿真学报, 2022, 34(3): 614-623.
[9]	李珍萍, 杨光, 韩倩倩. 考虑工作量均衡的成品油二次配送车辆路径问题[J]. 系统仿真学报, 2022, 34(2): 221-233.
[10]	胡蓉, 陈文博, 钱斌, 郭宁, 向凤红. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
[11]	张晓星, 王艳, 严大虎, 纪志成. 改进的混合蛙跳算法求解柔性作业车间调度[J]. 系统仿真学报, 2017, 29(9): 2093-2099.
[12]	邢志伟, 唐云霄. 枢纽机场航班保障服务时间估计[J]. 系统仿真学报, 2017, 29(11): 2856-2865.
[13]	马向国, 刘同娟, 杨平哲, 蒋荣芬. 基于随机需求的冷链物流车辆路径优化模型[J]. 系统仿真学报, 2016, 28(8): 1824-1833.
[14]	宁涛, 郭晨, 陈荣, 金花. 一种动态车辆路径问题解决策略仿真研究[J]. 系统仿真学报, 2015, 27(12): 2942-2947.