救援效率视角下灾后动态应急配送网络优化

doi:10.16182/j.issn1004731x.joss.20-0885

摘要/Abstract

摘要：

针对应急救援问题，在受灾点的位置、需求以及受灾人口等信息动态变化的情况下，建立动态有向救援网络，以救援效率最大化为目标构建数学模型。运用数据包络分析模型，对各段救援路线的效率进行评价；建立基于效率的动态路由模型，通过时间片的划分将动态路由转化为多阶段的静态路由；设计了改进的混合贪心蚁群优化算法对模型进行求解，并将该算法与遗传算法、粒子群算法以及基础的蚁群算法进行对比。实验结果表明：改进的混合贪心蚁群优化算法能够有效处理动态路由问题，寻求到更高的救援效率。

关键词: 救援效率, 动态网络, 应急物流, 混合贪心蚁群优化算法

Abstract:

Aiming at the emergency rescue, a dynamic directed rescue network is established with the dynamic changes of the location, demand, and affected population of disaster site, and a mathematical model is constructed with the maximum rescue efficiency. A data envelope analysis model is applied to evaluate the efficiency of each rescue route segment. An efficiency-based dynamic routing model is established to transform the dynamic routes into the multi-stage static routes through the time slice division. An improved hybrid greedy-ant colony optimization algorithm is designed to solve the model, and the proposed algorithm is compared with the genetic algorithm, particle swarm optimization and basic ant colony algorithm. The experimental results show that the improved hybrid greedy-ant colony optimization algorithm can effectively carry out the dynamic routing and the rescue efficiency is high.

Key words: rescue efficiency, dynamic network, emergency logistics, hybrid greedy-ant colony optimization algorithm

中图分类号:

TP391.9

高鑫宇, 倪静. 救援效率视角下灾后动态应急配送网络优化[J]. 系统仿真学报, 2022, 34(4): 806-816.

Xinyu Gao, Jing Ni. Optimization of Dynamic Post-disaster Emergency Distribution Network under Perspective of Rescue Efficiency[J]. Journal of System Simulation, 2022, 34(4): 806-816.

图/表 15

图1

表1

评价救援效率的输入输出因子

分类	变量	符号
输入因子	行驶距离	$D$
输入因子	行驶风险	$R$
输出因子	受灾人口数	$N$
	潜在次生灾害点	$M$
	基础设施损毁程度	$P$

表1

图2

图3

表2

参数的3组待选值以及最优组合

$α$	$β$	$γ$
0.5	1	1
1	2	2
2	3	3

表2

表3

表4

表5

表6

图4

图5

表7

表8

图6

表9

参考文献 15

1	Huang Kai, Jiang Yiping, Yuan Yufei, et al. Modeling Multiple Humanitarian Objectives in Emergency Response to Large-Scale Disasters[J]. Transportation Research Part E(S1366-5545), 2015, 75: 1-17.
2	Maharjan Rajali, Hanaoka Shinya. A Credibility-Based Multi-Objective Temporary Logistics Hub Location-Allocation Model for Relief Supply and Distribution under Uncertainty[J]. Socio-Economic Planning Sciencess(S0038-0121), 2020, 70: 100727.
3	项寅. 基于双层规划的反恐应急设施选址模型及算法[J]. 中国管理科学, 2019, 27(7): 147-157.
	Xiang Yin. A Bi-level Programming Model for Locating Terror Response Facilities[J]. Chinese Journal of Management Science, 2019, 27(7): 147-157.
4	付江月, 陈刚. 公平与效率权衡的双目标应急物资分配模型[J]. 系统工程, 2018, 36(6): 149-153.
	Fu Jiangyue, Chen Gang. A Bi-objective Emergency Resources Allocation Model Considering the Trade-off between Fairness and Efficiency[J]. Systems Engineering, 2018, 36(6): 149-153.
5	朱莉, 曹杰, 顾珺, 等. 公平缓解灾民创伤下的应急物资动态调配研究[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.
6	Alinaghian Mahdi, Aghaie Mohammad, Sabbagh Mohammad S. A Mathematical Model for Location of Temporary Relief Centers and Dynamic Routing of Aerial Rescue Vehicles[J]. Computers Industrial Engineerings(S0360-8352), 2019, 131: 227-241.
7	Reza Sakiani, Abbas Seifi, Khorshiddoust Reza Ramazani. Inventory Routing and Dynamic Redistribution of Relief Goods in Post-Disaster Operations[J]. Computers & Industrial Engineerings(S0360-8352), 2020, 140: 106219.
8	Azzouz Radhia, Bechikh Slim, Lamjed Ben Said. A Dynamic Multi-Objective Evolutionary Algorithm Using a Change Severity-Based Adaptive Population Management Strategy[J]. Soft Computings(S1432-7643), 2017, 21(4): 885-906.
9	Nandy Anirban, Piyush Kumar Singh. Farm Efficiency Estimation Using a Hybrid Approach of Machine- Learning and Data Envelopment Analysis: Evidence from Rural Eastern India[J]. Journal of Cleaner Productions(S0959-6526), 2020, 267: 122106.
10	Liu Bingsheng, Sheu Jiuh Biing, Zhao Xue, et al. Decision Making on Post-Disaster Rescue Routing Problems from the Rescue Efficiency Perspective[J]. European Journal of Operational Researchs(S0377-2217), 2020, 286(1): 321-335.
11	Xiang Xiaoshu, Qiu Jianfeng, Xiao Jianhua, et al. Demand Coverage Diversity Based Ant Colony Optimization for Dynamic Vehicle Routing Problems[J]. Engineering Applications of Artificial Intelligences(S0952-1976), 2020, 91: 103582.
12	唐慧玲, 唐恒书, 朱兴亮. 基于改进蚁群算法的低碳车辆路径问题研究[J]. 中国管理科学, 2021, 29(7):118-127.
	Tang Huiling, Tang Hengshu, Zhu Xingliang. Research on Low-Carbon Vehicle Routing Problem Based on Modified Ant Colony Algorithm[J]. Chinese Journal of Management Science, 2021, 29(7): 118-127.
13	谈晓勇, 林鹰. 基于混沌蚁群算法的应急救援车辆调度优化[J]. 计算机应用研究, 2014, 31(9): 2640-2643.
	Tan Xiaoyong, Lin Ying. Vehicle Scheduling Optimization Based on Chaos Ant Colony System Algorithm in Emergency Rescue[J]. Application Research of Computers, 2014, 31(9): 2640-2643.
14	来学伟. 两种不同贪心算法在求解TSP问题中的应用和比较[J]. 河北北方学院学报(自然科学版), 2018, 34(7): 34-37.
	Lai Xuewei. Application and Comparison of Two Different Greedy Algorithms for Solving TSP Problem[J]. Journal of Hebei North University (Natural Science Edition), 2018, 34(7): 34-37.
15	张玉茹, 王晨旸. 引入变异算子的改进贪心和蚁群混合算法[J]. 计算机集成制造系统, 2020, 26(3): 860-870.
	Zhang Yuru, Wang Chenyang. Improved Greedy and Colony Algorithm with Mutation Operator for Traveling Salesman Problem[J]. Computer Integrated Manufacturing Systems, 2020, 26(3): 860-870.

路线	D/km	R	路线	D/km	R	路线	D/km	R
(0,6)	65	79	(3,11)	477	39	(6,8)	71	50
(0,8)	63	55	(4,5)	112	100	(6,9)	55	95
(0,9)	70	37	(4,7)	142	85	(6,10)	310	65
(1,3)	55.8	100	(4,9)	164	71	(7,8)	102	88
(1,4)	295	67	(4,10)	265	39	(7,9)	34	59
(1,6)	78	95	(4,11)	307	43	(7,10)	239	75
(1,7)	156	83	(4,12)	118	57	(7,11)	281	34
(1,12)	241	22	(5,6)	100	80	(7,12)	237	47
(2,4)	334	100	(5,7)	30	54	(8,9)	80	86
(2,5)	214	57	(5,8)	121	72	(8,10)	335	90
(2,6)	117	87	(5,9)	52	69	(9,12)	259	57
(2,10)	422	52	(5,10)	224	30	(11,12)	113	23
(3,6)	130	65	(5,11)	266	35
(3,9)	179	74	(6,7)	84	69

序号	受灾点	N(万人)	M	P
P₁	汶川	10.4	549	9
P₂	茂县	10.9	410	8
P₃	理县	4.6	278	4
P₄	北川	15.4	550	7
P₅	绵竹	51.4	414	5
P₆	都江堰	62.0	830	7
P₇	什邡	43.3	158	6
P₈	大邑	49.0	187	5
P₉	彭州	79.9	495	8
P₁₀	广元	310.4	833	2
P₁₁	青川	24.6	1 351	4
P₁₂	平武	18.0	359	2

E_ij	P₀	P₁	P₂	P₃	P₄	P₅	P₆	P₇	P₈	P₉	P₁₀	P₁₁	P₁₂
P₀	\	nv	0	nv	nv	nv	0.92	nv	0.53	1	nv	nv	nv
P₁	nv	\	nv	0.34	0.40	nv	0.76	0.34	nv	nv	nv	nv	0.38
P₂	0	nv	\	nv	0.29	0.38	0.56	nv	nv	nv	0.58	nv	nv
P₃	nv	0.69	nv	\	nv	nv	0.61	nv	nv	0.49	nv	0.59	nv
P₄	0	0.50	0.32	nv	\	0.33	nv	0.35	nv	0.51	0.84	0.53	0.25
P₅	0	nv	0.55	nv	0.45	\	0.64	0.85	0.34	0.79	1	0.66	nv
P₆	0	0.63	0.50	0.29	nv	0.40	\	0.50	0.53	0.62	0.70	nv	nv
P₇	nv	0.51	nv	nv	0.44	0.93	0.76	\	0.33	1	0.90	0.68	0.19
P₈	0	nv	nv	nv	nv	0.38	0.95	0.40	\	0.59	0.63	nv	nv
P₉	0	nv	nv	0.24	0.45	0.57	1	0.75	0.37	\	nv	nv	0.40
P₁₀	0	nv	0.44	nv	0.58	0.60	0.46	0.33	0.23	nv	\	nv	nv
P₁₁	0	nv	nv	0.26	0.52	0.51	nv	0.56	nv	nv	nv	\	0.41
P₁₂	nv	1	nv	nv	0.58	nv	nv	0.47	nv	0.56	nv	1	\

网络	效率	车辆	路线
SN	6.58	一车	{0, 6, 3, 1, 4, 0, 2, 0, 9, 12, 11, 0}
SN	6.58	二车	{0, 8, 7, 5, 10, 0}
DN	7.45	一车	{0, 6, 3, 1, 4, 10, 2, 0, 9, 0}
DN	7.45	二车	{0, 8, 7, 5, 12, 11, 0}

目标	救援网络	救援效率	救援时间/h
F₁	SN	6.58	34.63
F₁	DN	7.45	22.77
F₂	SN	5.38	30.03
F₂	DN	6.89	22.53