Emergency Material Scheduling Based on Discrete Shuffled Frog Leaping Algorithm

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

CLC Number:

TP391.9

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

Figures/Tables 11

Table 1

Fig. 1

Table 2

Mathematical notations and their descriptions

符号		含义
集合	$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

Table 2

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Table 3

Table 4

Fig. 6

Table 5

References 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]	Li Zhang, Mingling He, Qiushuang Yin, Ning Li, Le'an Yu. Research on Period Emergency Supply Distribution Optimization Under Uncertainty [J]. Journal of System Simulation, 2023, 35(8): 1669-1680.
[2]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[3]	Zhang Yingyu, Wu Liyun, Jia Shengtai. Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time Windows [J]. Journal of System Simulation, 2023, 35(11): 2464-2475.
[4]	Chen Xue, Hu Rong, Wang Hui, Li Zuocheng, Qian Bin, Li Yixu. Learning-based Ant Colony Optimization Algorithm for Solving a Kind of Complex 2-Echelon Vehicle Routing Problem [J]. Journal of System Simulation, 2023, 35(11): 2476-2495.
[5]	Nan Li, Rong Hu, Bin Qian, Huaiping Jin, Naikang Yu. Research on Time-dependent Vehicle Routing Problem with Multiple Time Windows [J]. Journal of System Simulation, 2022, 34(8): 1775-1788.
[6]	Rong Hu, Wen Jiang, Bin Qian, Naikang Yu. Two Stage Optimization Algorithm to Solve the Green Packing Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(7): 1490-1505.
[7]	Weiquan Wang, Ding Ding, Shuyan Cao. Hybrid Variable Neighborhood Search algorithm for the Multi-trip and Heterogeneous-fleet Electric Vehicle Routing Problem [J]. Journal of System Simulation, 2022, 34(4): 910-919.
[8]	Tao Ning, Tao Gou, Xiangdong Liu. Simulation on Cold Chain Distribution Path of Fresh Agricultural Products Under Low-carbon Constraints [J]. Journal of System Simulation, 2022, 34(4): 797-805.
[9]	Weiquan Wang, Ding Ding, Linsha Yan. Path-Based Model for the Heterogeneous-Fleet Electric Vehicle Routing Problem with Partial Linear Recharging [J]. Journal of System Simulation, 2022, 34(3): 614-623.
[10]	Zhenping Li, Guang Yang, Qianqian Han. Vehicle Routing Problem with Refined Oil Secondary Distribution Considering Workload Balance [J]. Journal of System Simulation, 2022, 34(2): 221-233.
[11]	Hu Rong, Chen Wenbo, Qian Bin, Guo Ning, Xiang Fenghong. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem [J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
[12]	Zhang Qian, Xiong Ying, He Mingke, Zhang Hao. Multi-objective Model of Distribution Route Problem for Fresh Electricity Commerce under Uncertain Demand [J]. Journal of System Simulation, 2019, 31(8): 1582-1590.
[13]	Xing Zhiwei, Tang Yunxiao. Flight Support Service Time Estimation of Hub Airport [J]. Journal of System Simulation, 2017, 29(11): 2856-2865.
[14]	Ma Xiangguo, Liu Tongjuan, Yang Pingzhe, Jiang Rongfen. Vehicle Routing Optimization Model of Cold Chain Logistics Based on Stochastic Demand [J]. Journal of System Simulation, 2016, 28(8): 1824-1833.
[15]	Ning Tao, Guo Chen, Chen Rong, Jin Hua. Simulation Study on Scheduling Strategy of Dynamic Vehicle Routing Problem [J]. Journal of System Simulation, 2015, 27(12): 2942-2947.