Drone-vehicle collaborative routing optimization with transfer operations in mountainous environments
Article Text (Baidu Translation)
-
摘要: 为解决山区及城镇末端环境下物流系统车辆可达性差、场景适应性不足的核心问题，探索了一种新型接驳式无人机-车辆的协同调度模式，由干线集散车辆搭载多架无人机组成的货运接驳系统，支持多架无人机从车辆同步起飞，且每次飞行中单架无人机可以为一个或多个客户提供同时取送货服务，系统订单的履行包括3个阶段，即取送货需求聚类、干线车辆线路设计、接驳式无人机路径决策。基于上述系统构建了考虑时间窗和多接驳式无人机-车辆协同的混合整数线性规划模型以最小化系统总成本，并针对大规模案例求解需求设计了一种改进交叉邻域搜索的人工蜂群算法；结合云南省高原山区场景，设计了不同规模的数值试验以验证模型和算法的有效性。研究结果表明：对比经典的无人机-卡车并行协同模型，所提出的模型在场景适应性和经济性方面表现出显著优势，能够将成本降低8.0%~46.7%；改进的人工蜂群算法在求解效率与成本上均优于CPLEX求解器及其他对比算法，尤其在问题规模较大时，对比CPLEX求解成本可降低1.4%~4.3%；灵敏度试验证明，模型具有较强的鲁棒性，并印证了在山区环境下采取宽松时间窗策略及增加无人机续航，能有效提升配送方案的效率与经济性。Abstract: To address the core issues of poor vehicle accessibility and insufficient scenario adaptability in logistics systems in mountainous areas and urban fringe environments, a novel collaborative scheduling model for transfer-based drones-vehicle systems is proposed. A freight transportation system consisting of multiple drones carried by mainline distribution vehicles is considered, allowing the simultaneous takeoff of multiple drones from vehicles, where each drone can provide simultaneous pickup and delivery services for one or more customers per flight. The fulfillment of system orders involves three stages: clustering pickup and delivery demands, designing mainline vehicle routes, and determining transfer-based drone routes. Based on the above system, a mixed-integer linear programming model considering time windows and multi-drone-vehicle collaborative operations with transfers is constructed to minimize the total system cost, and an improved artificial bee colony algorithm with cross-neighborhood search is designed to solve large-scale cases. Numerical experiments at different scales were designed based on the high-altitude mountainous areas of Yunnan Province to validate the effectiveness of the model and algorithm. Research results show that, compared with the classical drone-truck parallel collaboration model, the proposed model exhibits superior performance in scenario adaptability and cost efficiency, and reduces costs by 8.0% to 46.7%. Furthermore, the improved artificial bee colony algorithm outperforms the CPLEX solver and other comparative algorithms in both solution efficiency and cost. Particularly for large-scale problems, the solution cost is reduced by 1.4% to 4.3% compared with CPLEX. Finally, sensitivity experiments demonstrate that the model has strong robustness and confirm that adopting a relaxed time window strategy and increasing drone endurance in mountainous environments can effectively improve the efficiency and cost-effectiveness of distribution operations.
-
图 6 改进ABC算法与CPLEX求解结果比较
Figure 6. Comparison of solution results between improved ABC algorithm and CPLEX
表 1 改进ABC算法与CPLEX对比结果
Table 1. Comparison results between improved ABC algorithm and CPLEX
算例 CPLEX 改进ABC算法 百分比差值/% ID 需求规模 成本/元 无人机数量 运行时间/s 成本/元 无人机数量 运行时间/s 成本差值 数量差值 时间差值 IS-1 5 230.0 1 4.5 230.0 1 6.9 0.0 0.0 53.3 IS-2 5 232.0 2 4.8 232.0 2 6.8 0.0 0.0 41.7 IS-3 8 250.8 2 11.6 250.8 2 13.8 0.0 0.0 19.0 IS-4 8 258.9 2 11.9 258.9 2 14.0 0.0 0.0 17.6 IS-5 20 434.0 3 153.4 425.2 3 54.6 -1.4 0.0 -64.4 IS-6 20 439.5 3 156.2 428.6 3 55.2 -2.5 0.0 -64.7 IS-7 33 568.6 4 415.1 553.5 4 68.9 -2.1 0.0 -83.4 IS-8 33 570.0 4 420.4 561.8 4 66.3 -1.4 0.0 -84.2 IS-9 50 794.2 5 980.2 760.0 5 80.6 -4.3 0.0 -91.8 IS-10 50 800.7 6 994.9 768.5 5 82.4 -4.0 -16.7 -91.7 IS-11 80 923.2 6 97.2 IS-12 80 937.4 7 97.5 
下载: 导出CSV
表 2 其他启发式算法对比结果
Table 2. Comparison results of other heuristic algorithms
算例 改进ABC算法 ABC算法 ALNS算法 ID 需求规模 系统成本/元 运行时间/s 系统成本/元 运行时间/s 系统成本/元 运行时间/s IS-1 5 230.0 6.9 230.0 7.2 230.0 10.3 IS-3 8 250.8 13.8 252.5 14.0 250.8 16.5 IS-5 20 425.2 54.6 454.0 57.5 427.1 75.3 IS-7 33 553.5 68.9 589.4 67.6 558.3 92.8 IS-9 50 760.0 80.6 795.0 84.4 764.5 149.4 IS-11 80 923.2 97.2 981.0 94.1 935.0 198.0
下载: 导出CSV
表 3 模型总成本对比
Table 3. Comparison of total model costs
元 需求规模 5 8 20 33 50 80 MCDVRPTW 230 251 425 554 758 923 FSTSP 250 411 725 914 1 258 1 733 MTSP-D 216 378 704 840 1 102 1 501
下载: 导出CSV
-
[1] CHOUDHURY S, SOLOVEY K, KOCHENDERFER M J, et al. Efficient large-scale multi-drone delivery using transit networks[J]. Journal of Artificial Intelligence Research, 2021, 70: 757-788. doi: 10.1613/jair.1.12450 [2] SHE R F, OUYANG Y F. Efficiency of UAV-based last-mile delivery under congestion in low-altitude air[J]. Transportation Research Part C: Emerging Technologies, 2021, 122: 102878. doi: 10.1016/j.trc.2020.102878 [3] SHE R F, OUYANG Y F. Hybrid truck-drone delivery under aerial traffic congestion[J]. Transportation Research Part B: Methodological, 2024, 185: 102970. doi: 10.1016/j.trb.2024.102970 [4] 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. doi: 10.1016/j.trc.2015.03.005 [5] 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. [6] LUO Z H, POON M, ZHANG Z Z, et al. The multi-visit traveling salesman problem with multi-drones[J]. Transportation Research Part C: Emerging Technologies, 2021, 128: 103172. doi: 10.1016/j.trc.2021.103172 [7] YIN Y Q, YANG Y J, YU Y G, 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. doi: 10.1016/j.trb.2023.102781 [8] NGUYEN M A, HÀ M H. The parallel drone scheduling traveling salesman problem with collective drones[J]. Transportation Science, 2023, 57(4): 866-888. doi: 10.1287/trsc.2022.1192 [9] JUNG S. MILP-based cost and time-competitive vehicle routing problem for last-mile delivery service using a swarm of UAVs and UGVs[J]. Journal of Air Transport Management, 2025, 124: 102736. doi: 10.1016/j.jairtraman.2024.102736 [10] AGATZ N, BOUMAN P, SCHMIDT M. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52(4): 965-981. doi: 10.1287/trsc.2017.0791 [11] BOUMAN P, AGATZ N, SCHMIDT M. Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks, 2018, 72(4): 528-542. doi: 10.1002/net.21864 [12] THOMAS T, SRINIVAS S, RAJENDRAN C. Collaborative truck multi-drone delivery system considering drone scheduling and en route operations[J]. Annals of Operations Research, 2024, 339(1): 693-739. [13] XIONG H, LEI D, LI M. Multi-objective traveling salesman problem with drone: imperialist competitive algorithm[C]//CPS-CD. Proceedings of the 34th China Conference on Control and Decision (1). Beijing: CPS-CD, 2022: 148-153. [14] ROBERTI R, RUTHMAIR M. Exact methods for the traveling salesman problem with drone[J]. Transportation Science, 2021, 55(2): 315-335. doi: 10.1287/trsc.2020.1017 [15] 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, 2024, 12(4): 965-995. doi: 10.1007/s40305-023-00471-7 [16] MENG S S, LI D, LIU J Y, et al. The multi-visit drone-assisted routing problem with soft time windows and stochastic truck travel times[J]. Transportation Research Part B: Methodological, 2024, 190: 103101. doi: 10.1016/j.trb.2024.103101 [17] OSORIO J, OUYANG YF. To ride or to fly: Optimal freight-on-transit operations using drones[J]. Transportation Research Part E, 2025, 201: 104231-104231. doi: 10.1016/j.tre.2025.104231 [18] 万佳, 胡大裟, 蒋玉明. 多密度自适应确定DBSCAN算法参数的算法研究[J]. 计算机工程与应用, 2022, 58(2): 78-85.WAN Jia, HU Da-sha, JIANG Yu-ming. Research on method of multi-density self-adaptive determination of DBSCAN algorithm parameters[J]. Computer Engineering and Applications, 2022, 58(2): 78-85. [19] BÍRÓ P, KOVÁCS B B H, NOVÁK T, et al. Cluster parameter-based DBSCAN maps for image characterization [J]. Computational and Structural Biotechnology Journal, 2025, 27: 920-927. doi: 10.1016/j.csbj.2025.02.037 [20] KIM J, LEE H, KO Y M. Constrained Density-Based Spatial Clustering of Applications with Noise (DBSCAN) using hyperparameter optimization[J]. Knowledge-Based Systems, 2024, 303: 112436. doi: 10.1016/j.knosys.2024.112436 [21] 邓钦原. 考虑需求集中程度的需求响应公交调度优化研究[D]. 广州: 华南理工大学, 2021.DENG Qin-yuan. Research on demand responsive transit scheduling optimization considering demand concentration[D]. Guangzhou: South China University of Technology, 2021. [22] 包丹文, 陈卓, 姚馨宇, 等. 基于混合策略的机坪车辆主动式实时调度方法[J]. 交通运输工程学报, 2024, 24(3): 251-265. doi: 10.19818/j.cnki.1671-1637.2024.03.018BAO Dan-wen, CHEN Zhuo, YAO Xin-yu, et al. Pro-active real-time scheduling approach of apron vehicles based on mixed strategy[J]. Journal of Traffic and Transportation Engineering, 2024, 24(3): 251-265. doi: 10.19818/j.cnki.1671-1637.2024.03.018 [23] 熊慧, 葛邦鲁, 刘近贞, 等. 用于多无人机协同路径规划的改进黏菌蜂群算法[J]. 浙江大学学报(工学版), 2025, 59(8): 1698-1707, 1717.XIONG Hui, GE Bang-lu, LIU Jin-zhen, et al. Improved slime mould bee colony algorithm for multi-UAVs cooperative path planning[J]. Journal of Zhejiang University (Engineering Science), 2025, 59(8): 1698-1707, 1717. [24] KUO R J, LU S H, LAI P Y, et al. Vehicle routing problem with drones considering time windows[J]. Expert Systems with Applications, 2022, 191: 116264. doi: 10.1016/j.eswa.2021.116264 [25] NGUYEN M A, DANG G T, HÀ M H, et al. The Min-cost parallel drone scheduling vehicle routing problem[J]. European Journal of Operational Research, 2022, 299(3): 910-930. doi: 10.1016/j.ejor.2021.07.008 [26] COINDREAU M A, GALLAY O, ZUFFEREY N. Parcel delivery cost minimization with time window constraints using trucks and drones[J]. Networks, 2021, 78(4): 400-420. doi: 10.1002/net.22019 [27] LIU Y, SHI J M, LUO Z H, et al. Cooperated truck-drone routing with drone energy consumption and time windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2024, 25(12): 20390-20404. doi: 10.1109/TITS.2024.3478175 [28] 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. doi: 10.1016/j.trc.2019.02.018 -
图(12) / 表(3)
计量
- 文章访问数: 125
- HTML全文浏览量: 44
- PDF下载量: 19
- 被引次数: 0
