基于多目标演化算法的卡车无人机协同路径问题研究
Research on Cooperative Path Planning of Trucks and Unmanned Aerial Vehicles Based on Multi-Objective Evolutionary Algorithm
摘要: 卡车无人机协同配送作为一种新型的物流配送模式，被广泛应用在最后一公里配送中。本研究针对柔性时间窗下的多卡车多无人机协同配送路径问题，根据物流企业的具体需求，建立了一个最小化运输成本、最小化客户不满意度的多目标优化模型。针对该模型的优化问题，提出一种基于目标空间分解的改进MOEA/D算法(An Improved MOEA/D Algorithm Based on Objective Space Decomposition, MOEA/D-OSD)。通过目标空间分解策略、交配亲本选择策略、子种群更新策略等多种策略提高种群多样性，通过结合多个交叉和变异算子来加速算法的收敛，并针对具体问题特征设计染色体编码、解码方式以及遗传算子。最后，通过一组基准实例对算法性能进行评估，验证了该算法解决卡车无人机协同路径问题的有效性。
Abstract: The collaboration of trucks and drones for delivery has emerged as a new logistics model widely applied in last-mile delivery. This study addresses the multi-truck, multi-drone collaborative delivery routing problem under flexible time windows. Based on the specific needs of logistics companies, a multi-objective optimization model is established to minimize transportation costs and customer dissatisfaction. To solve this model, an improved MOEA/D algorithm based on objective space decomposition (MOEA/D-OSD) is proposed. This approach enhances population diversity through various strategies, including objective space decomposition, parent selection for mating, and subspace updating. Additionally, it accelerates algorithm convergence by combining multiple crossover and mutation operators while designing chromosome encoding, decoding methods, and genetic operators tailored to the specific problem characteristics. Finally, the algorithm’s performance is evaluated through a set of benchmark instances, demonstrating its effectiveness in solving the truck-drone collaborative routing problem.
文章引用：岳存慧. 基于多目标演化算法的卡车无人机协同路径问题研究[J]. 应用数学进展, 2025, 14(2): 430-447. https://doi.org/10.12677/aam.2025.142083

参考文献

[1] Chung, S.H., Sah, B. and Lee, J. (2020) Optimization for Drone and Drone-Truck Combined Operations: A Review of the State of the Art and Future Directions. Computers & Operations Research, 123, Article 105004. [Google Scholar] [CrossRef] 
[2] Murray, C.C. and Chu, A.G. (2015) The Flying Sidekick Traveling Salesman Problem: Optimization of Drone-Assisted Parcel Delivery. Transportation Research Part C: Emerging Technologies, 54, 86-109. [Google Scholar] [CrossRef] 
[3] Agatz, N., Bouman, P. and Schmidt, M. (2018) Optimization Approaches for the Traveling Salesman Problem with Drone. Transportation Science, 52, 965-981. [Google Scholar] [CrossRef] 
[4] Ha, Q.M., Deville, Y., Pham, Q.D. and Hà, M.H. (2018) On the Min-Cost Traveling Salesman Problem with Drone. Transportation Research Part C: Emerging Technologies, 86, 597-621. [Google Scholar] [CrossRef] 
[5] Luo, Z., Liu, Z. and Shi, J. (2017) A Two-Echelon Cooperated Routing Problem for a Ground Vehicle and Its Carried Unmanned Aerial Vehicle. Sensors, 17, Article 1144. [Google Scholar] [CrossRef] [PubMed]
[6] Mbiadou Saleu, R.G., Deroussi, L., Feillet, D., Grangeon, N. and Quilliot, A. (2018) An Iterative Two-Step Heuristic for the Parallel Drone Scheduling Traveling Salesman Problem. Networks, 72, 459-474. [Google Scholar] [CrossRef] 
[7] Chen, P. and Wang, Q. (2024) Learning for Multiple Purposes: A Q-Learning Enhanced Hybrid Metaheuristic for Parallel Drone Scheduling Traveling Salesman Problem. Computers & Industrial Engineering, 187, Article 109851. [Google Scholar] [CrossRef] 
[8] Teimoury, E. and Rashid, R. (2023) The Paired Pickup and Delivery Problem with Profit in a Two-Echelon Delivery System with Multiple Trucks and Drones. Transportation Letters, 16, 1171-1187. [Google Scholar] [CrossRef] 
[9] Ham, A.M. (2018) Integrated Scheduling of M-Truck, M-Drone, and M-Depot Constrained by Time-Window, Drop-Pickup, and M-Visit Using Constraint Programming. Transportation Research Part C: Emerging Technologies, 91, 1-14. [Google Scholar] [CrossRef] 
[10] Lin, M., Lyu, J., Gao, J. and Li, L. (2020) Model and Hybrid Algorithm of Collaborative Distribution System with Multiple Drones and a Truck. Scientific Programming, 2020, 1-16. [Google Scholar] [CrossRef] 
[11] Wang, K., Yuan, B., Zhao, M. and Lu, Y. (2019) Cooperative Route Planning for the Drone and Truck in Delivery Services: A Bi-Objective Optimisation Approach. Journal of the Operational Research Society, 71, 1657-1674. [Google Scholar] [CrossRef] 
[12] Luo, Q., Wu, G., Ji, B., Wang, L. and Suganthan, P.N. (2022) Hybrid Multi-Objective Optimization Approach with Pareto Local Search for Collaborative Truck-Drone Routing Problems Considering Flexible Time Windows. IEEE Transactions on Intelligent Transportation Systems, 23, 13011-13025. [Google Scholar] [CrossRef] 
[13] Luo, Q., Wu, G., Trivedi, A., Hong, F., Wang, L. and Srinivasan, D. (2023) Multi-Objective Optimization Algorithm with Adaptive Resource Allocation for Truck-Drone Collaborative Delivery and Pick-Up Services. IEEE Transactions on Intelligent Transportation Systems, 24, 9642-9657. [Google Scholar] [CrossRef] 
[14] 曹庆奎, 张雪飞, 任向阳. 货车和无人机联合配送路径优化研究[J]. 廊坊师范学院学报(自然科学版), 2022, 22(1): 5-13.
[15] Zhang, Q.F. and Li, H. (2007) MOEA/D: A Multi-Objective Evolutionary Algorithm Based on Decomposition. IEEE Transactions on Evolutionary Computation, 11, 712-731.
[16] Liu, H., Gu, F. and Zhang, Q. (2014) Decomposition of a Multiobjective Optimization Problem into a Number of Simple Multiobjective Subproblems. IEEE Transactions on Evolutionary Computation, 18, 450-455. [Google Scholar] [CrossRef] 
[17] Bi, X. and Wang, C. (2016) An Improved NSGA-III Algorithm Based on Objective Space Decomposition for Many-Objective Optimization. Soft Computing, 21, 4269-4296. [Google Scholar] [CrossRef] 
[18] Das, I. and Dennis, J.E. (1998) Normal-Boundary Intersection: A New Method for Generating the Pareto Surface in Nonlinear Multicriteria Optimization Problems. SIAM Journal on Optimization, 8, 631-657. [Google Scholar] [CrossRef] 
[19] Hartigan, J.A. and Wong, M.A. (1979) Algorithm as 136: A K-Means Clustering Algorithm. Applied Statistics, 28, 100-108. [Google Scholar] [CrossRef] 
[20] Li, K., Hang, Q.F., Kwong, S., et al. (2014) Stable Matching-Based Selection in Evolutionary Multi-Objective Optimization. IEEE Transactions on Evolutionary Computation, 18, 909-923.
[21] Dong, N. and Dai, C. (2019) An Improvement Decomposition-Based Multi-Objective Evolutionary Algorithm Using Multi-Search Strategy. Knowledge-Based Systems, 163, 572-580. [Google Scholar] [CrossRef] 
[22] Yuan, Y., Xu, H. and Wang, B. (2014) An Improved NSGA-III Procedure for Evolutionary Many-Objective Optimization. Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Vancouver, 12-16 July 2014, 661-668. [Google Scholar] [CrossRef] 
[23] Zhang, S., Liu, S., Xu, W. and Wang, W. (2022) A Novel Multi-Objective Optimization Model for the Vehicle Routing Problem with Drone Delivery and Dynamic Flight Endurance. Computers & Industrial Engineering, 173, Article 108679. [Google Scholar] [CrossRef] 
[24] Cordeau, J., Laporte, G. and Mercier, A. (2001) A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows. Journal of the Operational Research Society, 52, 928-936. [Google Scholar] [CrossRef] 
[25] Potvin, J. (1996) Genetic Algorithms for the Traveling Salesman Problem. Annals of Operations Research, 63, 337-370. [Google Scholar] [CrossRef] 
[26] Zitzler, E. and Thiele, L. (1999) Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach. IEEE Transactions on Evolutionary Computation, 3, 257-271. [Google Scholar] [CrossRef] 
[27] Gao, J., Zhen, L. and Wang, S. (2023) Multi-Trucks-and-Drones Cooperative Pickup and Delivery Problem. Transportation Research Part C: Emerging Technologies, 157, Article 104407. [Google Scholar] [CrossRef] 
[28] Li, H., Wang, H., Chen, J. and Bai, M. (2020) Two-Echelon Vehicle Routing Problem with Time Windows and Mobile Satellites. Transportation Research Part B: Methodological, 138, 179-201. [Google Scholar] [CrossRef] 
[29] Moshref-Javadi, M., Hemmati, A. and Winkenbach, M. (2020) A Truck and Drones Model for Last-Mile Delivery: A Mathematical Model and Heuristic Approach. Applied Mathematical Modelling, 80, 290-318. [Google Scholar] [CrossRef] 
[30] Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T. (2002) A Fast and Elitist Multiobjective Genetic Algorithm: Nsga-II. IEEE Transactions on Evolutionary Computation, 6, 182-197. [Google Scholar] [CrossRef] 

为你推荐