基于卡车-无人机协同的山区自然灾害应急物资调度优化决策研究

doi:10.16381/j.cnki.issn1003-207x.2023.1278

Abstract

Abstract:

Emergency material dispatch is a key link in post-disaster emergency response， and its dispatch efficiency directly affects the rescue effect. Sudden natural disasters are often accompanied by road damage， which seriously restricts the transportation of emergency supplies. In emergency material dispatch， trucks have large carrying capacity and long driving distances. drones do not depend on ground road conditions but are subject to battery and load constraints. The collaboration of the two can achieve complementary advantages. In order to improve the dispatching efficiency of emergency supplies， the post-disaster emergency supplies dispatching strategy of truck-drone collaboration is studied. Taking the shortest time for trucks and drones to complete all material transportation and return to the distribution center as the objective； considering the load and mileage constraints of trucks and drones， road damage and road congestion restrictions， a mixed integer programming model is established. Since the proposed model is an NP-hard problem and combines the advantages of genetic algorithm and dynamic programming algorithm， a new hybrid algorithm （hybrid method based on genetic algorithm and dynamic programming， HGADP） is proposed. Three different scale calculation examples of small， medium and large are designed for the proposed management problem scenario. By comparing the algorithm proposed in this paper with the Gurobi solver and the algorithm proposed in the previous study， the effectiveness of the algorithm proposed in this paper is verified. Through analysis of the calculation example results， it is found that compared with the traditional vehicle transportation model， the truck-drone collaborative transportation model proposed in this article can significantly save material transportation time. Finally， a sensitivity analysis on the drone load capacity and cruising range is conducted， and the impact of parameter changes on the efficiency of emergency material dispatching is analyzed. The emergency material dispatching strategy and is expanded a decision-making basis for emergency material dispatching decisions of emergency management departments is provided in this study.

Key words: material scheduling, genetic algorithms, dynamic programming, trucks and drones

CLC Number:

U492.3

Keyi Zhang, Yong Shi, Haixiang Guo, Yongzheng Sun. Optimal Decision-Making for Dispatching Emergency Supplies for Natural Disasters in Mountainous Areas Based on Truck-Drone Collaboration[J]. Chinese Journal of Management Science, 2025, 33(2): 150-160.

Figures/Tables 15

符号	说明
$V c = 1,2, …, c$	全部物资需求点集合
$V = V c ⋃ 0, c + 1$	全部节点集合，0、c+1表示同一配送中心
$V s$	配送中心的卡车集合
$θ i j$	从节点i到节点j路径的损毁率， $∀ i, j ∈ V$
$φ i j$	从节点i到节点j路径的拥堵系数， $∀ i, j ∈ V$
$Q T$	卡车的最大载重量
$L T$	卡车最大行驶距离
$Q D$	无人机的最大载重量
$L D$	无人机单次出动的续航里程
$V T$	卡车正常行驶设定速度
$V i j T$	考虑道路拥堵后卡车从点i到点j的行驶速度（考虑道路状况）， $∀ i, j ∈ V$
$V D$	无人机设定飞行速度
$c d i j$	从节点i到节点j的无人机飞行距离， $∀ i, j ∈ V$
$c t i j'$	从节点i到节点j以卡车为运输工具需要行驶的距离， $∀ i, j ∈ V$
$c t i j$	从节点i到节点j的卡车行驶的广义运输距离， $∀ i, j ∈ V$
$d i$	应急需求点的货物需求量， $∀ i ∈ V c$
M	足够大的正整数
$y i k j s = {0,1}$	当卡车s上的无人机在节点i发射，给需求点k配送物，在节点j收回时 $y i k j s$ 为1，否则为0。 $∀ i, j ∈ V, ∀ k ∈ V c, ∀ s ∈ V s$
$x i j s = {0,1}$	当卡车s从节点i到节点j时 $x i j s$ 为1，否则为0， $∀ i, j ∈ V, ∀ s ∈ V s$
$u i s = {0,1}$	当需求点i的物资由卡车s配送时 $u i s$ 为1，否则为0， $∀ i ∈ V c, ∀ s ∈ V s$
$v i s = {0,1}$	当需求点i的物资由卡车s搭载的无人机配送时 $v i s$ 为1，否则为0， $∀ i ∈ V c, ∀ s ∈ V s$
$t i s$	表示从配送中心出发到完成节点i的物资配送花费的时间， $∀ i ∈ V, ∀ s ∈ V s$
$f i s$	表示卡车到达节点i的顺序， $∀ i ∈ V, ∀ s ∈ V s$

算例名称	Gurobi		HGADP算法				K-means+VNS算法
算例名称	Best (小时)	Time (秒)	Best (小时)	$μ 秒$	$σ$	Time (秒)	Best (小时)	$μ (小时)$	$σ$	Time (秒)	Gap (%)
6.5.1	0.245	0.435	0.245	0.245	0	0.14	0.259	0.259	0	0.2433	5.4
6.5.2	0.196	0.488	0.196	0.196	0	0.039	0.204	0.204	0	0.1701	3.9
6.10.1	0.445	0.953	0.445	0.445	0	0.025	0.445	0.554	0.079	0.1892	0.0
6.10.2	0.421	0.68	0.421	0.421	0	0.546	0.421	0.421	0	0.1968	0.0
6.20.1	0.703	0.427	0.703	0.703	0	0.082	0.703	0.792	0.047	0.1744	0.0
6.20.2	1.021	0.57	1.021	1.021	0	0.59	1.062	1.062	0	0.1735	3.9
8.5.1	0.236	20.16	0.236	0.236	0	0.028	0.254	0.27	0.009	0.2287	7.1
8.5.2	0.246	16.93	0.246	0.246	0	0.715	0.246	0.27	0.018	0.2194	0.0
8.10.1	0.534	31.17	0.534	0.538	0.006	0.078	0.548	0.586	0.015	0.2029	2.6
8.10.2	0.424	26.01	0.424	0.424	0	0.667	0.467	0.482	0.011	0.2069	9.2
8.20.1	1.16	18.69	1.16	1.179	0.019	0.057	1.218	1.382	0.063	0.2293	4.8
8.20.2	1.231	27.82	1.231	1.231	0	0.726	1.231	1.314	0.077	0.2488	0.0
10.5.1	0.179	1516.3	0.179	0.179	0	1.34	0.19	0.216	0.034	0.2918	5.8
10.5.2	0.223	1995.3	0.223	0.223	0	0.729	0.244	0.244	0	0.2514	8.6
10.10.1	0.443	2131.6	0.443	0.443	0	1.04	0.47	0.47	0	0.263	5.7
10.10.2	0.453	1715.6	0.453	0.453	0.004	0.915	0.474	0.474	0	0.2631	4.4
10.20.1	0.695	2279.4	0.695	0.695	0	0.949	0.732	0.732	0	0.2632	5.1
10.20.2	0.763	4805.2	0.763	0.766	0.004	0.867	0.835	0.876	0.068	0.2613	8.6

规模	算例	车辆数量	本文 $H G A D P$ 算法			k-means+VNS算法
规模	算例	车辆数量	Best (小时)	Time (秒)	$σ$	Best (小时)	$σ$	Gap (%)
中规模	20.5.1	3	0.180	0.970	0.0169	0.1949	0.01096	7.64
	20.5.2	3	0.187	0.6187	0.011	0.203	0.016	7.88
	20.10.1	3	0.346	0.443	0.0250	0.381	0.0275	9.19
	20.10.2	3	0.339	0.545	0.027	0.352	0.025	3.69
	20.20.1	3	0.718	0. 521	0.0479	0.785	0.0506	8.54
	20.20.2	3	0.687	0.522	0.0590	0.698	0.059	1.58
大规模	50.10.1	6	0.460	3.9404	0.0245	0.4613	0.0356	0.28
	50.10.2	6	0.490	11.702	0.029	0.496	0.0647	1.21
	50.20.1	6	0.904	4.3081	0.032	0.982	0.077	7.94
	50.20.2	6	0.828	7.7674	0.094	0.893	0.079	7.28
	50.30.1	6	1.398	4.9933	0.0930	1.408	0.0636	0.71
	50.30.2	6	1.171	7.1783	0.074	1.218	0.0674	3.86
	50.40.1	6	1.962	4.3265	0.1440	2.03	0.276	3.35
	50.40.2	6	1.914	6.188	0.12	1.944	0.093	1.54
	200.20.1	25	1.397	65.19	1.0982	1.361	0.302	-2.65
	200.20.2	25	0.881	190.01	1.0069	0.906	0.262	2.76
	200.30.1	25	2.580	76.546	1. 0340	2.501	0.0056	-3.16
	200.30.2	25	2.435	155.99	1.041	2.47	0.3272	1.42
	200.40.1	25	3.523	67.80	0.18549	3.714	0.752	5.14
	200.40.2	25	4.029	128.83	0.159	4.4	1.608	8.43

References 24

1	中华人民共和国应急管理部.应急管理部发布2022年全国十大自然灾害［EB/OL］.（2023-01-12）. .
	Ministry of Emergency Management of the People’s Republic of China. Ministry of Emergency Management Releases Top 10 National Natural Disasters for 2022 ［EB/OL］.（2023-01-12）. .
2	Macrina G， Di Puglia Pugliese L， Guerriero F， et al. drone-aided routing： A literature review［J］. Transportation Research Part C： Emerging Technologies， 2020， 120： 102762.
3	Zhang G， Jia N， Zhu N， et al. Robust drone selective routing in humanitarian transportation network assessment［J］. European Journal of Operational Research， 2023， 305（1）： 400-428.
4	中国政府网. 国务院关于印发“十四五”国家应急体系规划的通知［EB/OL］.（2022-02-14）. .
	China government website. Circular of the State Council on the Issuance of the 14th Five-Year Plan for the National Emergency Response System［EB/OL］.（2022-02-14）. .
5	Marinakis Y， Marinaki M， Migdalas A. A multi-adaptive particle swarm optimization for the vehicle routing problem with time windows［J］. Information Sciences， 2019， 481： 311-329.
6	Li Q， Tu W， Zhuo L. Reliable rescue routing optimization for urban emergency logistics under travel time uncertainty［J］. ISPRS International Journal of Geo-Information， 2018， 7（2）： 77.
7	Shiri D， Akbari V， Salman F S. Online routing and scheduling of search-and-rescue teams［J］. OR Spectrum， 2020， 42（3）： 755-784.
8	Petroianu L P.G.， Zabinsky Z B， Zameer M， et al. A light‐touch routing optimization tool （RoOT） for vaccine and medical supply distribution in Mozambique［J］. International Transactions in Operational Research， 2021， 28（5）： 2334-2358.
9	Khorsi M， Chaharsooghi S K， Bozorgi-Amiri A， et al. A multi-objective multi-period model for humanitarian relief logistics with split delivery and multiple uses of vehicles［J］. Journal of Systems Science and Systems Engineering， 2020， 29： 360-378.
10	范厚明，任晓雪，刘浩.带时间窗偏好的同时配集货且需求可拆分车辆路径问题［J］.运筹与管理，2022，31（11）：65-71.
	Fan H M， Ren X X， Liu H.Split delivery vehicle routing problem with simultaneous delivery and pick-up and time windows preference［J］. Operations Research and Management Science， 2022，31（11）：65-71.
11	Murray C C， Chu A G. The flying sidekick traveling salesman problem： Optimization of drone-assisted parcel delivery［J］. Transportation Research Part C： Emerging Technologies， 2015， 54： 86-109.
12	Wang Y， Wang Z， Hu X， et al. Truck-drone hybrid routing problem with time-dependent road travel time［J］. Transportation Research Part C： Emerging Technologies， 2022， 144： 103901.
13	Huang S H， Huang Y H， Blazquez C A， et al. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm［J］. Advanced Engineering Informatics， 2022， 51： 101536.
14	Wang D， Hu P， Du J， et al. Routing and scheduling for hybrid truck-drone collaborative parcel delivery with independent and truck-carried drones［J］. IEEE Internet of Things Journal， 2019， 6（6）： 10483-10495.
15	Zeng F， Chen Z， Clarke J P， et al. Nested vehicle routing problem： Optimizing drone-truck surveillance operations［J］. Transportation Research Part C： Emerging Technologies， 2022， 139： 103645.
16	颜瑞，陈立双，朱晓宁，等.考虑区域限制的卡车搭载无人机车辆路径问题研究［J］.中国管理科学，2022，30（5）：144-155.
	Yan R， Chen L S， Zhu X N， et al. Research on vehicle routing problem with truck and drone considering regional restriction［J］. Chinese Journal of Management Science，2022，30（5）：144-155.
17	高娇娇，郭秀萍.考虑卡车无人机协同配送模式下的车辆路径问题研究［J/OL］.工业工程与管理..
	Gao J J， Guo X P. Research on vehicle routing problem considering truck-UAV cooperative distribution mode［J/OL］. Industrial Engineering and Management..
18	蒋丽，王洪艳，梁昌勇，等. 农村地区卡车与无人机协同配送路径优化［J］. 计算机工程与应用， 2023， 59（14）： 306-314.
	Jiang L， Wang H Y， Liang C Y， et al. Optimization of truck and drone collaborative distribution route in rural areas［J］. Computer Engineering and Applications，2023， 59（14）： 306-314.
19	吴廷映，陶新月，孟婷.“卡车+无人机”模式下带时间窗的取送货车辆路径问题［J］.计算机集成制造系统，2023，29（7）：2440-2448.
	Wu T Y， Tao X Y， Meng T. Pickup and delivery problem with time windows in mode of “truck+drone”［J］. Computer Integrated Manufacturing Systems，2023，29（7）：2440-2448.
20	孙华丽，曹文倩，薛耀锋，等. 考虑路径风险的需求不确定应急物流定位-路径问题［J］. 运筹与管理， 2018， 27（7）： 37-42.
	Sun H L， Cao W Q， Xue Y F， et al. Emergency location-routing model with uncertain demands under path risks［J］. Operations Research and Management Science， 2018， 27（7）： 37-42.
21	杜茂康，罗娟，李博文.基于多车场的车载无人机协同配送路径优化［J］.系统工程，2021，39（6）：90-98.
	Du M K， Luo J， Li B W. Research on cooperative delivery route optimization of vehicle-carried drones based on multi-depot［J］. Systems Engineering，2021，39（6）：90-98.
22	许文鑫，张敏，熊国文.配送车与无人机的农村物流配送路径优化仿真［J］.计算机仿真，2022，39（6）：151-157.
	Xu W X， Zhang M， Xiong G W. Optimization simulation of rural logistics distribution path based on distribution vehicle and UAV［J］. Computer Simulation，2022，39（6）：151-157.
23	Sacramento D， Pisinger D， Ropke S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones［J］. Transportation Research Part C： Emerging Technologies， 2019， 102： 289-315.
24	彭勇，张永辉，黎元钧.考虑无人机辅助的卡车配送路径优化［J］.工业工程与管理，2023，28（2）：31-39.
	Peng Y， Zhang Y H， Li Y J. Optimization of truck distribution route considering drone-assisted［J］. Industrial Engineering and Management，2023，28（2）：31-39.

算例	卡车-无人机运输时间/h	卡车运输时间/h	节约百分比（%）
6.5.1	0.245	0.354	30.79
6.10.1	0.445	0.812	45.20
6.20.1	0.703	1.239	43.26
8.5.1	0.236	0.376	37.23
8.10.1	0.534	0.881	39.39
8.20.1	1.160	1.701	31.80
20.5.1	0.180	0.309	41.75
20.10.1	0.346	0.534	35.21
20.20.1	0.690	0.863	20.05
50.10.1	0.460	0.668	31.14
50.20.1	0.904	1.399	35.38
50.30.1	1.398	2.057	32.04
200.20.1	1.397	2.806	50.21
200.30.1	2.580	4.064	36.52
200.40.1	3.523	5.523	36.21

[1]	Zihao Chu,Zhe Xu,Dongning Liu. Model and Algorithm on Stochastic Scheduling Problem with Activity Overlapping [J]. Chinese Journal of Management Science, 2024, 32(7): 84-94.
[2]	Hongmei Li,Xiangyue Zhang,Taibo Luo,Yinfeng Xu. Minsum k-sink Location Problem on Dynamic Path Networks with Non-confluent Flow Constraint [J]. Chinese Journal of Management Science, 2024, 32(2): 108-118.
[3]	LI Fei-fei, XU Zhe. Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation [J]. Chinese Journal of Management Science, 2022, 30(12): 38-51.
[4]	ZHANG Xue-wei, WANG Xi-jie. Study on the Matching of Best Division's Relatedness under Internal Capital Market Inter-temporal Allocation——An Interpretation of the Internal Logic of the Merger and Acquisition Integration of Diversified Enterprises [J]. Chinese Journal of Management Science, 2021, 29(9): 25-35.
[5]	FEI Wei-yin, ZHANG Fan-hong, YANG Xiao-guang. The Impact of Inflation on Executive's Equity Incentive and Work Effort [J]. Chinese Journal of Management Science, 2020, 28(11): 1-11.
[6]	FENG Ling, LEI Li-mei. Research on the Pricing of Treasury Bond Futures Based on Lattice Field Theory and Dynamic Programming [J]. Chinese Journal of Management Science, 2019, 27(9): 36-46.
[7]	ZHAO Rong, LIU Ke-yan, REN Pei-yu. Min-max Multiple Sink Location Problem in Dynamic Path Networks with Different Traffic Capacity Constraint [J]. Chinese Journal of Management Science, 2017, 25(9): 133-140.
[8]	HE Xiao-bo, WANG Dong-mei, ZENG Shi-hong. Valuation for Forestry Investment Projects with Carbon Sequestration Benefits——Based on Real Option Pricing Theory [J]. Chinese Journal of Management Science, 2017, 25(3): 39-48.
[9]	ZHANG Peng, ZHANG Wei-Guo, ZHANG Yi-fei. Multi-period Mean-semivariance Portfolio Selection with Minimum Transaction Lots Constraints [J]. Chinese Journal of Management Science, 2016, 24(7): 11-17.
[10]	ZHANG Peng, ZHANG Wei-Guo, ZHANG Yi-fei. Multi-period Mean-semivariance Portfolio Selection with Minimum Transaction Lots Constraints [J]. Chinese Journal of Management Science, 2016, 24(7): 11-17.
[11]	TIAN Jun, LI Li-fang, BAI Jian, FENG Geng-zhong. Modular Design of Emergency Task Executive Processes Based on DSM [J]. Chinese Journal of Management Science, 2014, 22(8): 100-107.
[12]	CHANG Hao. Investment and Consumption Model with the Zero-Coupon Bond under the Ho-Lee Interest Rate Model [J]. Chinese Journal of Management Science, 2014, 22(10): 29-37.
[13]	LI Yan-ni, RAN Mao-sheng. The Study of Commercial Bank Liquidity Risk Management Method and Improvement——Application of Dynamic Programs with Simple Recourse Under Fuzzy Qualitative Constraints [J]. Chinese Journal of Management Science, 2011, 19(3): 19-25.
[14]	WU Gang, WEI Yi-Ming. The Optimal Strategies of China’s Strategic Petroleum Reserves in Emergency [J]. Chinese Journal of Management Science, 2011, 19(2): 140-146.
[15]	LI Jian-bin, YANG Rui-na. Optimal Strategies of Procurement Risk Management with Correlated Demand and Spot Price [J]. Chinese Journal of Management Science, 2011, 19(1): 12-20.

Optimal Decision-Making for Dispatching Emergency Supplies for Natural Disasters in Mountainous Areas Based on Truck-Drone Collaboration

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 24

Related Articles 15

Metrics

Comments

Recommended 0

算法	路径	最优结果/小时	求解时间/秒
HGADP	卡车：0→4→8→3→5→0	0.534	0.078
HGADP	无人机：4→6→8、8→1→3、3→7→5、5→2→0	0.534	0.078
GUROBI	卡车：0→4→8→3→5→0	0.534	31.17
GUROBI	无人机：4→6→8、8→1→3、3→7→5、5→2→0	0.534	31.17