|Table of Contents|

Routing problem of truck-drones joint distribution in initial stage of emergency response(PDF)

长安大学学报（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

Issue:
2024年1期
Page:
105-119
Research Field:
交通工程
Publishing date:

Info

Title:
Routing problem of truck-drones joint distribution in initial stage of emergency response
Author(s):
HU Da-wei;  ZHANG Shi-peng;  LIU Hui-tian;  WANG Yin
(School of Transportation Engineering, Chang'an University, Xi'an 710064, Shaanxi, China)
Keywords:
traffic engineering;  variable neighborhood search algorithm;  truck-drone mode delivery;  emergency supply
PACS:
U492.3
DOI:
10.19721/j.cnki.1671-8879.2024.01.010
Abstract:
In order to timely deliver emergency supplies to disaster stricken areas, reduce casualties, and minimize property damage during the early stages of emergency response, a truck-drone combined delivery mode for emergency supplies was proposed by combining the characteristics of relatively large truck capacity and fast drone operation speed. A model for the truck-drone routing problem(VRP-D)was developed based on the vehicle routing problem, with the objective of minimizing the total delivery time. The effectiveness of the model was validated through small-scale examples using the LINGO optimization solver, and it was compared with the traditional emergency supply delivery vehicle routing problem(VRP). The model was solved using a designed variable neighborhood search algorithm(VNS), and its performance was compared with the traditional genetic algorithm(GA). A sensitivity analysis was conducted on the drone's endurance range and maximum payload. The results show that the VNS algorithm has certain advantages in solving the model in terms of speed, accuracy, and stability. The quality of the solutions obtained by the VNS algorithm can be improved by up to 7.24% compared to those obtained by the GA algorithm. The quality of the solutions of the VRP-D model can be improved by up to 63.57% compared to the VRP model. Therefore, in the initial stages of emergency response, the use of the truck-drone combined delivery mode for emergency supplies is more efficient. When the drone's endurance range is increased to 70 min, the total waiting time at the disaster points no longer decreases. Similarly, when the drone's maximum payload is increased to 35 kg, the total waiting time at the disaster points also ceases to decrease, reflecting the inherent trade-off between the drone's endurance range and maximum payload. The study providing a theoretical basis for innovating new modes of emergency supply delivery.9 tabs, 14 figs, 28 refs.

References:

[1] MURRAY C C,CHU A G.The flying sidekick traveling salesman problem:Optimization of drone-assisted parcel delivery[J].Transportation Research Part C,2015,54:86-109.
[2]SAVURAN H,KARAKAYA M.Efficient route planning for an unmanned air vehicledeployed on a moving carrier[J].Soft Computing,2016,20(7):2905-2920.
[3]WANG X Y,POIKONEN S,GOLDEN B.The vehicle routing problem with drones:Several worst-case results[J].Optimization Letters,2017,11(4):679-697.
[4]CAMPBELL J F,SWEENEY D,ZHANG J.Strategic design for delivery with trucks and drones[J].Supply Chain Analytics Report SCMA,2017,1(4):14-18.
[5]AGATZ N,BOUMAN P,SCHMIDT M.Optimization approaches for the traveling salesmanproblem with drone[J].Transportation Science,2018,52(4):965-981.
[6]HA Q M,DEVILLE Y,PHAM Q D,et al.On the min-cost traveling salesman problem withdrone[J].Transportation Research Part C,2018,86:597-621.
[7]YONG S C,LEE H J.Optimal delivery routing with wider drone-delivery areas along ashorter truck-route[J].Expert Systems With Applications,2018,104:307-317.
[8]SCHERMER D,MOEINI M,WENDT O.A matheuristic for the vehicle routing problem withdrones and its variants[J].Transportation Research Part C,2019,106:166-204.
[9]MOSHREF-JAVADI M,HEMMATI A,WINKENBACH M.A truck and drones model forlast-mile delivery:A mathematical model and heuristic approach[J].Applied MathematicalModelling,2020,80:290-318.
[10]JEON A,KANG J,CHOI B,et al.Unmanned aerial vehicle last-mile delivery consideringbackhauls[J].IEEE Access,2021,9:85017-85033.
[11]PUGLIESE L P,GUERRIERO F,SCUTELLA M.The last-mile delivery process with trucksand drones under uncertain energy consumption[J].Journal of Optimization Theory andApplications,2021,191(1):31-67.
[12]PAVITHRAN R,LALITH V,NAVEEN C,et al.A prototype of fixed wing UAV for delivery of medical supplies[J].IOP Conference Series:Materials Science andEngineering,2020,995(1):012015.
[13]MACIAS J E,ANGELOUDIS P,OCHIENG W.Optimal hub selection for rapid medicaldeliveries using unmanned aerial vehicles[J].Transportation Research Part C,2020,110:56-80.
[14]熊传明.基于无人机和货车协同送货的调度与路径规划算法研究[D].武汉:华中科技大学,2018.
XIONG Chuan-ming.Research on scheduling and path planning algorithm based on cooperativedelivery of UAV and truck[D].Wuhan:Huazhong University of Science and Technology,2018.
[15]胡运霞.卡车与无人机联合配送下物流调度的优化研究[D].成都:西南交通大学,2020.
HU Yun-xia.Research on optimization of logistics scheduling under joint distribution of truck andUAV[D].Chengdu:Southwest Jiaotong University,2020.
[16]马业骥.多无人车多无人机协同运输路径规划算法研究[D].哈尔滨:哈尔滨工业大学,2022.
MA Ye-ji.Research on cooperative transportation path planning algorithm of multi-unmannedvehicles and multi-unmanned vehicles[D].Harbin:Harbin Institute of Technology,2022.
[17]胡觉亮,杨 航,张田会,等.无人机与卡车协同配送优化研究[J].浙江理工大学学报(社会科学版),2020,44(5):489-497.
HU Jue-liang,YANG Hang,ZHANG Tian-hui,et al.Research on optimization of collaborativedistribution between UAV and truck[J].Journal of Zhejiang Sci-Tech University(SocialSciences Edition),2020,44(5):489-497.
[18]周爱莲,蒋 利,侯夏杰.应急物流中无人机配送线路优化[J].长沙理工大学学报(自然科学版),2020,17(2)54-60.
ZHOU Ai-lian,JIANG Li,HOU Xia-jie.Optimization of UAV distribution routes in emergencylogistics[J].Journal of Changsha University of Science and Technology(NaturalScience),2020,17(2)54-60
[19]王 新,王 征,徐 伟.面向多个无人机站点的车辆与无人机联合配送路径问题研究[J].运筹与管理,2021,30(5)31-37.
WANG Xin,WANG Zheng,XU Wei.Vehicle and drone joint distribution routing problem withmultiple drone hubs[J].Operations Research and Management Science,2021,30(5)31-37.
[20]郭秀萍,胡运霞.卡车与无人机联合配送模式下物流调度的优化研究[J].工业工程与管理,2021,26(1):1-8.
GUO Xiu-ping,HU Yun-xia.Research on optimization of logistics scheduling under the jointdistribution mode of truck and drones[J].Industrial Engineering and management,2021,26(1):1-8.
[21]胡大伟,陈海妹,梁一为,等.车辆与无人机混合编队的路径优化问题模型构建[J].长安大学学报(自然科学版),2021,41(1):78-89.
HU Da-wei,CHEN Hai-mei,LIANG Yi-wei,et al.Mathematical model construction for routingoptimization problem of vehicle-drone hybrid formation[J].Journal of Chang'an University(Natural Science Edition),2021,41(1):78-89.
[22]陈海妹.基于“卡车+无人机”模式农村电商物流配送路径优化研究[D].西安:长安大学,2021.
CHEN Hai-mei.Research on rural E-commerce logistics distribution path optimization based on“Truck+UAV” mode[D].Xi'an:Chang'an University,2021.
[23]蒋 利.基于应急物流的“卡车+无人机”协同配送线路优化研究[D].长沙:长沙理工大学,2020.
JIANG Li.Research on optimization of “Truck+UAV” collaborative distribution route based onemergency logistics[D].Changsha:Changsha University of Science & Technology,2020.
[24]彭 勇,黎元钧.考虑疫情影响的卡车无人机协同配送路径优化[J].中国公路学报,2020,33(11):73-82.
PENG Yong,LI Yuan-jun.Optimization of truck-drone collaborative distribution route consideringimpact of epidemic[J].China Journal of Highway and Transport,2020,33(11):73-82.
[25]梁一为.“车辆-无人机”串联模式下的应急物资配送路线问题研究[D].西安:长安大学,2021.
LIANG Yi-wei.Research on emergency material distribution route under the series mode of“vehicle-unmanned aerial vehicle”[D].Xi'an:Chang'an University,2021.
[26]THOMPSON P M,PSARAFTIS H N.Cyclic transfer algorithm for multivehicle routing andscheduling problems[J].Operations Research,1993,41(5):935-946.
[27]POLACEK M,HARTL R F,DOERNER K,et al.A variable neighborhood search for the multidepot vehicle routing problem with time windows[J].Journal ofHeuristics,2004,10(6):613-627.
[28]ZHAO J,HU H,HAN Y,et al.A review of unmanned vehicle distribution optimization models and algorithms[J].Journal of Traffic and Transportation Engineering(English Edition),2023,10(4):548-559.

Memo

Memo:
-
Last Update: 2024-01-10