卡车-无人机协同的洪灾应急选址-路径鲁棒优化问题

doi:10.3778/j.issn.1002-8331.2410-0289

摘要/Abstract

摘要： 为提高洪灾应急物资配送效率，提出卡车-无人机动态协同配送应急物资。考虑洪灾环境特征，以应急物资配送的总时间最短为目标，构建卡车-无人机动态协同的应急物资配送选址-路径鲁棒优化模型。使用改进的禁忌搜索算法求解模型。在改进算法中，设计了多种交叉、逆转的邻域算子来扩大邻域搜索范围，并加入修复算子以保证路径可行且实现选址决策。实验结果表明：提出的模型能有效解决洪灾应急物资配送选址-路径问题；鲁棒优化模型可有效保证卡车行驶时间波动下路径的可行性；与遗传算法、模拟退火算法以及粒子群算法相比，改进禁忌搜索算法具有更优的性能。

关键词: 洪灾应急物流, 选址-路径问题, 卡车-无人机动态协同, 鲁棒优化, 禁忌搜索算法

Abstract: To enhance the efficiency of emergency material distribution, this paper addresses the dynamic optimization problem of truck-drone collaboration for flood emergency material delivery. Considering the characteristics of the flood environment, the objective is to minimize the total delivery time for emergency supplies. A robust location-routing optimization model is developed for dynamic truck-drone collaboration in emergency logistics. The model is solved using an improved tabu search algorithm (ITS). In ITS, various crossover and reversal neighborhood operators are designed to expand the search space, and repair operators are introduced to ensure route feasibility and location decisions. Experimental results demonstrate that the proposed model effectively solves the location-routing problem for flood emergency distribution. The robust optimization model ensures route feasibility under fluctuations in truck travel times. Compared to genetic algorithm and simulated annealing algorithm, ITS exhibits superior performance.

Key words: flood emergency logistics, location-routing problem, dynamic truck-drone collaboration, robust optimization, tabu search algorithm

龚英, 涂熳熳, 周愉峰. 卡车-无人机协同的洪灾应急选址-路径鲁棒优化问题[J]. 计算机工程与应用, 2025, 61(14): 307-321.

GONG Ying, TU Manman, ZHOU Yufeng. Truck-Drone Collaborated Location-Routing Robust Optimization Problem for Flood Emergency Response[J]. Computer Engineering and Applications, 2025, 61(14): 307-321.

参考文献

[1] 2022全球自然灾害评估报告[R]. 北京: 中华人民共和国应急管理部, 2023.
2022 Global natural disaster assessment report[R]. Beijing: Ministry of Emergency Management of the People’s Republic of China, 2023.
[2] NAJY W, ARCHETTI C, DIABAT A. Collaborative truck-and-drone delivery for inventory-routing problems[J]. Transportation Research Part C: Emerging Technologies, 2023, 146: 103791.
[3] LUO Q, WU G, TRIVEDI A, et al. Multi-objective optimization algorithm with adaptive resource allocation for truck-drone collaborative delivery and pick-up services[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(9): 9642-9657.
[4] GAO J, ZHEN L, WANG S. Multi-trucks-and-drones cooperative pickup and delivery problem[J]. Transportation Research Part C: Emerging Technologies, 2023, 157: 104407.
[5] 颜瑞, 陈立双, 朱晓宁, 等. 考虑区域限制的卡车搭载无人机车辆路径问题研究[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.
[6] LU M, LIAO X, YUE H, et al. Optimizing distribution of droneports for emergency monitoring of flood disasters in China[J]. Journal of Flood Risk Management, 2020, 13(1): 12593.
[7] ZAFAR Z, AWAIS M, JALEEL A, et al. A distributed framework of autonomous drones for planning and execution of relief operations during flood situations[J]. International Arab Journal of Information Technology, 2021, 18(1): 16-24.
[8] 叶立威, 吴钧皓, 戚远航, 等. 改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题[J]. 计算机应用研究, 2024, 41(8): 2336-2342.
YE L W, WU J H, QI Y H, et al. Improved hybrid particle swarm optimization algorithm for vehicle routing problem with drone and time window[J]. Application Research of Computers, 2024, 41(8): 2336-2342.
[9] CHU J C, SHUI C S, LIN K H. Optimization of trucks and drones in tandem delivery network with drone trajectory planning[J]. Computers & Industrial Engineering, 2024, 189: 110000.
[10] LONG Y, XU G, ZHAO J, et al. Dynamic truck-UAV collaboration and integrated route planning for resilient urban emergency response[J]. IEEE Transactions on Engineering Management, 2023(99): 1-13.
[11] GARRIDO R A, LAMAS P, PINO F J. A stochastic programming approach for floods emergency logistics[J]. Transportation Research Part E: Logistics and Transportation Review, 2015, 75: 18-31.
[12] ZHANG D, ZHANG Y, LI S, et al. Bi-objective robust optimisation on relief collaborative distribution considering secondary disasters[J]. International Journal of Production Research, 2023, 62(7): 1-20.
[13] GENG S, HOU H, ZHOU Z. A dynamic multi-objective model for emergency shelter relief system design integrating the supply and demand sides[J]. Natural Hazards, 2024, 120: 2379-2402.
[14] THEEB A N, MURRAY C. Vehicle routing and resource distribution in postdisaster humanitarian relief operations[J]. International Transactions in Operational Research, 2017, 24(6): 1253-1284.
[15] LIU Y, LEI H, ZHANG D, et al. Robust optimization for relief logistics planning under uncertainties in demand and transportation time[J]. Applied Mathematical Modelling, 2018, 55: 262-280.
[16] 周愉峰, 胡欢庆, 陈良勇. 不确定环境下采血点定位-资源配置集成决策的鲁棒优化[J]. 运筹与管理, 2024, 33(8): 72-78.
ZHOU Y F, HU H Q, CHEN L Y. Robust optimization of location-resource allocation integrated decision robust optimization of location-resource allocation integrated decision[J]. Operations Research and Management Science, 2024, 33(8): 72-78.
[17] BERTSIMAS D, SIM M. The price of robustness[J]. Operations Research, 2004, 52(1): 35-53.
[18] 孙艺萌, 邱若臻. 服务水平约束下基于可调节鲁棒优化的供应链分销网络设计模型[J]. 管理工程学报, 2021, 35(3): 158-171.
SUN Y M, QIU R Z. Supply chain distribution network design under service level constraint using affinely adjustable robust optimization[J]. Journal of Industrial Engineering and Engineering Management, 2021, 35(3): 158-171.
[19] 于逸然, 赖惠成, 高古学, 等. 基于遗传算法和A*算法的多农机协同作业优化方法[J/OL]. 系统仿真学报: 1-12[2025?06?28].https://doi.org/10.16182/j.issn1004731x.joss.
24-0453.
YU Y R, LAI H C, GAO G X, et al. Optimization method for multi agricultural machinery collaborative operation based on genetic algorithm and A* algorithm[J/OL]. 系统仿真学报: 1-12[2025-06-28].https://doi.org/10.16182/j.issn1004731x.joss.24-0453.
[20] 邵良杉, 王振, 李昌明. 基于模拟退火与改进粒子群的矿井通风优化算法[J]. 系统仿真学报, 2021, 33 (9): 2085-2094.
SHAO L S, WANG Z, LI C M. Optimization algorithm of mine ventilation based on SA-IPSO[J]. Journal of System Simulation, 2021, 33(9): 2085-2094.
[21] 陈峰, 丁泉, 吴乐, 等. 混合驱动的粒子群算法[J]. 计算机工程与应用, 2024, 60(8): 78-89.
CHEN F, DING Q, WU L, et al. Hybrid driven particle swarm algorithm[J]. Computer Engineering and Applications, 2024, 60(8): 78-89.
[22] 刘志, 宋威. 搜索引导网络辅助的动态粒子群优化算法[J]. 计算机科学与探索, 2024, 18(12): 3189-3202.
LIU Z, SONG W. Search guidance network assisted dynamic particle swarm optimization algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(12): 3189-3202.