电商行业的迅速发展使传统“最后一公里”配送面临挑战，无人机技术进步为卡车-无人机协同配送系统带来新的可能性。因此，研究多卡车-多异构无人机协同配送路径优化问题具有重要意义。

首先，本文在VRP-D模型基础上，考虑异构无人机、多访问、无人机能量消耗与载重、飞行时间的非线性关系，构建了以最小化完工时间为目标的混合整数规划模型。同时，为应对配送环境的不确定性，以行驶时间为不确定参数，通过分布式鲁棒优化方法对模型进行扩展。其次，针对卡车和无人机的两级路径特性，设计了两阶段初始解构造方法，并提出混合变邻域搜索与模拟退火算法（VNS-SA）进行求解优化。算法设计了四种邻域变换算子以扩大搜索范围，使用模拟退火算法避免陷入局部最优。

实验验证了模型和算法的有效性。在小规模算例中，与Gurobi求解器相比，随着规模增大VNS-SA求解速度和质量较好。在大规模算例中，较传统卡车配送模式显著缩短了配送时间。在配送区域较小时，无人机能量限制较低，完工时间更短；异构无人机能够各自发挥特点，进一步提升配送效果。此外，灵敏度分析显示，无人机性能对配送效率影响显著，但单一性能提升的作用有限。算子实验结果表明，无人机路径生成算子对算法性能的贡献最大，四个算子的协同作用提升了解的质量。最后，基于亚马逊“最后一公里”配送数据集，讨论了不同电池更换假设及不确定行程时间对配送效果的影响。本研究为多卡车-异构无人机协同配送路径优化提供了理论支持与技术实现方案。

In recent years, the rapid growth of the e-commerce industry has introduced substantial challenges to traditional last-mile delivery systems. The advent of drone-assisted delivery technology presents promising opportunities for truck-drone collaborative logistics. Consequently, optimizing multi-truck and multi-heterogeneous drone collaborative delivery systems holds significant importance for addressing these challenges.

This study develops a mixed-integer programming model based on the VRP-D framework, incorporating key factors such as heterogeneous drones, multiple visits, and the nonlinear relationships among drone energy consumption, payload, and flight time. To address uncertainties in the delivery environment, travel times for both trucks and drones are treated as uncertain parameters. A distributionally robust optimization approach is applied to extend the deterministic model, enhancing its adaptability to real-world conditions. Given the two-tiered routing characteristics of trucks and drones, the study proposes a two-stage initial solution construction method and a Hybrid Variable Neighborhood Search and Simulated Annealing (VNS-SA) algorithm for solution optimization. The algorithm integrates four types of neighborhood transformation operators to expand the search space, while simulated annealing is employed to mitigate the risk of being trapped in local optima.

The experiments validate the effectiveness of the proposed model and algorithm. In small-scale instances, the VNS-SA algorithm outperforms the Gurobi solver in both solution speed and solution quality as the case scale increases. In large-scale instances, the truck-drone collaborative delivery mode significantly reduces delivery time compared to the traditional truck-only mode. The experiments also demonstrate that in smaller delivery regions, the energy constraints of drones are less restrictive, resulting in shorter completion times. Heterogeneous drones can leverage their respective characteristics to further enhance delivery performance. Moreover, sensitivity analysis reveals that drone performance significantly impacts delivery efficiency, although the benefits of improving a single performance metric are limited. Operators experiment results indicate that the drone route generation operator contributes the most to algorithm performance, while the collaborative effect of all four operators improves solution quality. Finally, based on the Amazon last-mile delivery dataset, the impact of different battery replacement assumptions and uncertain travel times on delivery performance is discussed. This study provides theoretical support and practical implementation strategies for optimizing the routing of multi-truck and heterogeneous drone collaborative delivery systems.

[1]国家邮政局.2019年邮政行业发展统计公报[EB/OL].国家邮政局(2020-05-09).[2024-9-14]. https://www.spb.gov.cn/gjyzj/c100015/c100016/202005/3b737880d332463bb63e027d70fd4476.shtml.

[2]国家邮政局.2023年邮政行业发展统计公报[EB/OL].国家邮政局(2024-05-10)[2024-9-14]. https://www.spb.gov.cn/gjyzj/c100276/202405/ff1ab12da9d74425b7ddef9e38de8916.shtml.

[3]中共中央, 国务院.国家综合立体交通网规划纲要[EB/OL].国务院公报(2021-02-24)[2024-9-15].https://www.gov.cn/gongbao/content/2021/content_5593440.htm.

[4]国家发展改革委.“十四五”现代综合交通运输体系发展规划[EB/OL].国家发展改革委官网(2022-03-25)[2024-9-15].https://www.ndrc.gov.cn/fggz/fzzlgh/gjjzxgh/202203/t20220325_1320208_ext.html.

[5]工业和信息化部,科学技术部,财政部,中国民用航空局.通用航空装备创新应用实施方案（2024-2030年）[EB/OL].中国政府网,2024-03-27[2024-09-15].https://www.gov.cn/zhengce/zhengceku/202403/content_6942115.htm.

[6]Rose, C. Amazon's Jeff Bezos looks to the future[EB/OL]. CBS News, 2013[2024-9-20]. https://www.cbsnews.com/news/amazons-jeff-bezos-looks-to-the-future/.

[7]Chung S H, Sah B, Lee J. Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions[J]. Computers & Operations Research, 2020, 123: 105004.

[8]Macrina, G, Pugliese L D P, Guerriero F, et al. Drone-aided routing: A literature review[J]. Transportation Research Part C: Emerging Technologies, 2020, 120: 102762.

[9]Moshref-Javadi M, Winkenbach M. Applications and Research avenues for drone-based models in logistics: A classification and review[J]. Expert Systems with Applications, 2021, 177: 114854.

[10]Rojas Viloria D, Solano-Charris E L, Muñoz-Villamizar A, et al. Unmanned aerial vehicles/drones in vehicle routing problems: a literature review[J]. International Transactions in Operational Research, 2021, 28(4): 1626-1657.

[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]Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52(4): 965-981.

[13]Liu Y, Liu Z, Shi J, et al. Two-echelon routing problem for parcel delivery by cooperated truck and drone[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2020, 51(12): 7450-7465.

[14]Campuzano G, Lalla-Ruiz E, Mes M. A Multi-start VNS Algorithm for the TSP-D with Energy Constraints[C]//International conference on computational logistics. Cham: Springer International Publishing, 2021: 393-409.

[15]Jeong H Y, Song B D, Lee S. Truck-drone hybrid delivery routing: Payload-energy dependency and No-Fly zones[J]. International Journal of Production Economics, 2019, 214: 220-233.

[16]Murray C C, Raj R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones[J]. Transportation Research Part C: Emerging Technologies, 2020, 110: 368-398.

[17]Raj R, Murray C. The multiple flying sidekicks traveling salesman problem with variable drone speeds[J]. Transportation Research Part C: Emerging Technologies, 2020, 120: 102813.

[18]Gu R, Poon M, Luo Z, et al. A hierarchical solution evaluation method and a hybrid algorithm for the vehicle routing problem with drones and multiple visits[J]. Transportation Research Part C: Emerging Technologies, 2022, 141: 103733.

[19]Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, et al. Multiple traveling salesman problem with drones: Mathematical model and heuristic approach[J]. Computers & Industrial Engineering, 2019, 129: 14-30.

[20]Masmoudi M A, Mancini S, Baldacci R, et al. Vehicle routing problems with drones equipped with multi-package payload compartments[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 164: 102757.

[21]Wang X, Poikonen S, Golden B. The vehicle routing problem with drones: Several worst-case results[J]. Optimization Letters, 2017, 11: 679-697.

[22]Schermer D, Moeini M, Wendt O. A matheuristic for the vehicle routing problem with drones and its variants[J]. Transportation Research Part C: Emerging Technologies, 2019, 106: 166-204.

[23]Xia Y, Zeng W, Zhang C, et al. A branch-and-price-and-cut algorithm for the vehicle routing problem with load-dependent drones[J]. Transportation Research Part B: Methodological, 2023, 171: 80-110.

[24]Dorling K, Heinrichs J, Messier G G, et al. Vehicle routing problems for drone delivery[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2016, 47(1): 70-85.

[25]Ha Q M, Deville Y, Pham Q D, et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C: Emerging Technologies, 2018, 86: 597-621.

[26]Tu, P. A., Dat, N. T., Dung, P. Q. Traveling Salesman Problem with Multiple Drones[C]. Proceedings of the Ninth International Symposium on Information and Communication Technology. ACM Press, 2018. https://doi.org/10.1145/3287921.3287932.

[27]Carlsson J G, Song S. Coordinated logistics with a truck and a drone[J]. Management Science, 2018, 64(9): 4052-4069.

[28]罗志浩. 车载无人机双层协同路径规划问题研究[D]. 国防科技大学, 2017.

[29]Cavani S, Iori M, Roberti R. Exact methods for the traveling salesman problem with multiple drones[J]. Transportation Research Part C: Emerging Technologies, 2021, 130: 103280.

[30]Tamke F, Buscher U. The vehicle routing problem with drones and drone speed selection[J]. Computers & Operations Research, 2023, 152: 106112.

[31]Kuo R J, Edbert E, Zulvia F E, et al. Applying NSGA-II to vehicle routing problem with drones considering makespan and carbon emission[J]. Expert Systems with Applications, 2023, 221: 119777.

[32]Di Puglia Pugliese L, Guerriero F. Last-mile deliveries by using drones and classical vehicles[C]//Optimization and Decision Science: Methodologies and Applications: ODS, Sorrento, Italy, September 4-7, 2017 47. Springer International Publishing, 2017: 557-565.

[33]Di Puglia Pugliese L, Macrina G, Guerriero F. Trucks and drones cooperation in the last‐mile delivery process[J]. Networks, 2021, 78(4): 371-399.

[34]Gonzalez-R P L, Canca D, Andrade-Pineda J L, et al. Truck-drone team logistics: A heuristic approach to multi-drop route planning[J]. Transportation Research Part C: Emerging Technologies, 2020, 114: 657-680.

[35]Poikonen S, Golden B. Multi-visit drone routing problem[J]. Computers & Operations Research, 2020, 113: 104802.

[36]Wang Z, Sheu J B. Vehicle routing problem with drones[J]. Transportation research part B: methodological, 2019, 122: 350-364.

[37]马华伟,马凯,郭君.考虑多投递的带无人机车辆路径规划问题研究[J].计算机工程,2022,48(08):

[38]Kitjacharoenchai P, Min B C, Lee S. Two echelon vehicle routing problem with drones in last mile delivery[J]. International Journal of Production Economics, 2020, 225: 107598.

[39]Li H, Wang H, Chen J, et al. Two-echelon vehicle routing problem with time windows and mobile satellites[J]. Transportation Research Part B: Methodological, 2020, 138: 179-201.

[40]Lu Y, Yang C, Yang J. A multi-objective humanitarian pickup and delivery vehicle routing problem with drones[J]. Annals of Operations Research, 2022, 319(1): 291-353.

[41]Luo Z, Gu R, Poon M, et al. A last-mile drone-assisted one-to-one pickup and delivery problem with multi-visit drone trips[J]. Computers & Operations Research, 2022, 148: 106015.

[42]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.

[43]Meng S, Guo X, Li D, et al. The multi-visit drone routing problem for pickup and delivery services[J]. Transportation Research Part E: Logistics and Transportation Review, 2023, 169: 102990.

[44]Rave A, Fontaine P, Kuhn H. Drone location and vehicle fleet planning with trucks and aerial drones[J]. European Journal of Operational Research, 2023, 308(1): 113-130.

[45]Yin Y, Li D, Wang D, et al. A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows[J]. European Journal of Operational Research, 2023, 309(3): 1125-1144.

[46]Jiang J, Dai Y, Yang F, et al. A multi-visit flexible-docking vehicle routing problem with drones for simultaneous pickup and delivery services[J]. European Journal of Operational Research, 2024, 312(1): 125-137.

[47]Meng S, Chen Y, Li D. The multi-visit drone-assisted pickup and delivery problem with time windows[J]. European Journal of Operational Research, 2024, 314(2): 685-702.

[48]Moshref-Javadi M, Lee S, Winkenbach M. Design and evaluation of a multi-trip delivery model with truck and drones[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 136: 101887.

[49]Bruni M E, Khodaparasti S, Moshref-Javadi M. A logic-based Benders decomposition method for the multi-trip traveling repairman problem with drones[J]. Computers & Operations Research, 2022, 145: 105845.

[50]Di Puglia Pugliese L, Guerriero F, Scutellá M G. The last-mile delivery process with trucks and drones under uncertain energy consumption[J]. Journal of Optimization Theory and Applications, 2021, 191(1): 31-67.

[51]Zhao L, Bi X, Dong Z, et al. Robust traveling salesman problem with drone: balancing risk and makespan in contactless delivery[J]. International Transactions in Operational Research, 2024, 31(1): 167-191.

[52]Yang Y, Yan C, Cao Y, et al. Planning robust drone-truck delivery routes under road traffic uncertainty[J]. European Journal of Operational Research, 2023, 309(3): 1145-1160.

[53]Yin Y, Yang Y, Yu Y, et al. Robust vehicle routing with drones under uncertain demands and truck travel times in humanitarian logistics[J]. Transportation Research Part B: Methodological, 2023, 174: 102781.

[54]Ghiasvand M R, Rahmani D, Moshref-Javadi M. Data-driven robust optimization for a multi-trip truck-drone routing problem[J]. Expert Systems with Applications, 2024, 241: 122485.

[55]Deng M, Li Y, Ding J, et al. Stochastic and robust truck-and-drone routing problems with deadlines: A Benders decomposition approach[J]. Transportation Research Part E: Logistics and Transportation Review, 2024, 190: 103709.

[56]Mirzapour Al-e-Hashem S M J, Hejazi T H, Haghverdizadeh G, et al. Optimizing last-mile delivery services: a robust truck-drone cooperation model and hybrid metaheuristic algorithm[J]. Annals of Operations Research, 2024: 1-31.

[57]Ha Q M, Deville Y, Pham Q D, et al. A hybrid genetic algorithm for the traveling salesman problem with drone[J]. Journal of Heuristics, 2020, 26: 219-247.

[58]Ponza A. Optimization of drone-assisted parcel delivery[J]. 2016.

[59]Zhang S, Li L. The multi-visits drone-vehicle routing problem with simultaneous pickup and delivery service[J]. Journal of the Operations Research Society of China, 2023: 1-31.

[60]Wang K, Pesch E, Kress D, et al. The Piggyback Transportation Problem: Transporting drones launched from a flying warehouse[J]. European Journal of Operational Research, 2022, 296(2): 504-519.

[61]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.

[62]de Freitas J C, Penna P H V. A variable neighborhood search for flying sidekick traveling salesman problem[J]. International Transactions in Operational Research, 2020, 27(1): 267-290.

[63]Mladenović N, Hansen P. Variable neighborhood search[J]. Computers & operations research, 1997, 24(11): 1097-1100.

[64]Metropolis N, Rosenbluth A W R M N, Rosenbluth M, et al. Simulated annealing. Journal of Chemical Physics,1953,21(161-162), 1087-1092.

[65]Wei L, Zhang Z, Zhang D, et al. A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints[J]. European Journal of Operational Research, 2015, 243(3): 798-814.

[66]Xu Z, Cai Y. Variable neighborhood search for consistent vehicle routing problem[J]. Expert Systems with Applications, 2018, 113: 66-76.

[67]Redi A A N P, Jewpanya P, Kurniawan A C, et al. A simulated annealing algorithm for solving two-echelon vehicle routing problem with locker facilities[J]. Algorithms, 2020, 13(9): 218.

[68]Karagul K, Sahin Y, Aydemir E, et al. A simulated annealing algorithm based solution method for a green vehicle routing problem with fuel consumption[J]. Lean and Green Supply Chain Management: Optimization Models and Algorithms, 2019: 161-187.

[69]Croes G A. A method for solving traveling-salesman problems[J]. Operations research, 1958, 6(6): 791-812.

[70]Merchán D, Arora J, Pachon J, et al. 2021 Amazon last mile routing research challenge: Data set[J]. Transportation Science, 2024, 58(1): 8-11.

[71]Masmoudi M A, Mancini S, Baldacci R, et al. Vehicle routing problems with drones equipped with multi-package payload compartments[J]. Transportation Research Part E: Logistics and Transportation Review, 2022, 164: 102757.

[72]Bouman P, Agatz N, Schmidt M. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks, 2018, 72(4): 528-542.

[73]Karak A, Abdelghany K. The hybrid vehicle-drone routing problem for pick-up and delivery services[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 427-449.

[74]Cheng C, Adulyasak Y, Rousseau L M. Drone routing with energy function: Formulation and exact algorithm[J]. Transportation Research Part B: Methodological, 2020, 139: 364-387.