应急响应初期“卡车-无人机”联合配送路径问题  

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

作　　者：胡大伟[1] 张世鹏 刘慧甜 王茵 HU Da-wei;ZHANG Shi-peng;LIU Hui-tian;WANG Yin(School of Transportation Engineering,Chang'an University,Xi'an 710064,Shaanxi,China)

机构地区：[1]长安大学运输工程学院,陕西西安710064

出　　处：《长安大学学报（自然科学版）》2024年第1期105-119,共15页Journal of Chang’an University(Natural Science Edition)

基　　金：国家重点研发计划项目(2020YFC1512004);陕西省自然科学基础研究计划项目(2021JZ-20);中央高校基本科研业务费专项资金项目(300102229304)。

摘　　要：为了在应急响应初期,将应急物资及时送达受灾地区、降低人员伤亡以及减少财产损失,结合卡车相对运量大、无人机运行速度快等特点,提出“卡车-无人机”联合配送应急物资模式,构建以车辆路径问题为基础,总配送时间最短为目标的“卡车-无人机”路径问题模型(vehicle routing problem-drones,VRP-D)。采用小规模算例,使用LINGO优化求解器对模型求解进行了有效性验证,并与传统应急物资配送车辆路径问题(vehicle routing problem,VRP)进行了对比分析。设计变邻域搜索算法(variable neighborhood search,VNS)对模型进行求解,并与传统遗传算法(genetic algorithm,GA)进行了对比分析。对无人机续航里程和最大载质量进行灵敏度分析。结果表明:VNS算法求解本文模型时在求解速度、精度以及稳定性方面具有一定优势;VNS算法解的质量比GA算法最大可改善7.24%;VRP-D模型比VRP模型解的质量最大可改善63.57%。故在应急响应初期,采用“卡车-无人机”联合配送应急物资的配送效率更高。当无人机续航里程增加到70 min后,受灾点总等待时间不再减少;当无人机最大载质量增加到35 kg后,受灾点总等待时间也不再减少,反映出无人机续航里程和最大载质量之间相互制约的内在关系。该研究为创新应急物资配送新模式提供了理论依据。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.

关 键 词：交通工程 变邻域搜索算法 “卡车-无人机”联合配送 应急物流 

分 类 号：U492.3[交通运输工程—交通运输规划与管理]