公交辅助无人机的城市物流配送模式研究

doi:10.3778/j.issn.1002-8331.2212-0252

摘要/Abstract

摘要： 电子商务迅猛发展倒逼物流行业不断转型升级，针对各地政府鼓励公共交通发展，倡导绿色低碳的物流配送方式，研究了一种公交辅助无人机的配送模式。对问题做出说明后，构建了以配送成本最小的数学模型，并设计了智能通用变邻域搜索算法对问题求解，同时为提高算法求解效率，引入K-means分簇与贪婪算法生成初始解。针对不同规模算例，进行多种局部搜索策略、多种算法对比实验，验证了算法有效性；选取标准CVRP算例，将单卡车配送、卡车无人机协同配送与公交辅助无人机配送模式进行对比，证明其成本、时间优势；选取北京快速公交2号线及周边客户点，通过改变公交站点间距、发车间隔做出敏感度分析，实验结果证明增大站点间距的影响大于发车间隔的改变。

关键词: 城市物流, 公交辅助无人机, 智能通用变邻域搜索, 路径优化

Abstract: The rapid development of e-commerce forces the continuous transformation and upgrading of the logistics industry. In view of the fact that local governments encourage the development of public transport and advocate green and low-carbon logistics distribution mode, a distribution mode of bus-assisted drone is studied. After explaining the problem, a mathematical model with the lowest distribution cost is constructed, and a heuristic algorithm of smart general variable neighborhood search metaheuristic is designed to solve the problem. At the same time, in order to improve the efficiency of the algorithm, K-means clustering and greedy algorithm are introduced to generate the initial solution. Firstly, aiming at different scale examples, a variety of local search strategies and a variety of algorithms are compared to verify the effectiveness of the algorithm. Secondly, by selecting the standard CVRP as example, the single truck distribution mode and truck-drone collaborative distribution mode are compared with the distribution mode of bus-assisted drone to prove its cost and time advantages. Finally, Beijing Bus Rapid Transit Line 2 and its surrounding customer points are selected, and sensitivity analysis is made by changing the bus stop spacing and departure interval, result shows that the impact of increasing the stop spacing is greater than the change of departure interval.

Key words: urban logistics, bus-assisted drone, smart general variable neighborhood search, path optimization

彭勇, 任志. 公交辅助无人机的城市物流配送模式研究[J]. 计算机工程与应用, 2024, 60(7): 335-343.

PENG Yong, REN Zhi. Research on Urban Logistics Distribution Mode of Bus-Assisted Drones[J]. Computer Engineering and Applications, 2024, 60(7): 335-343.

参考文献

[1] KAPSER S, ABDELRAHMAN M. Acceptance of autonomous delivery vehicles for last-mile delivery in Germany-Extending UTAUT2 with risk perceptions[J]. Transportation Research, Part C: Emerging Technologies, 2020, 111: 210-225.
[2] CAMPBELL J F, SWEENEY D, ZHANG J. Strategic design for delivery with trucks and drones[J]. Supply Chain Analytics Report SCMA, 2017: 47-55.
[3] MURRAY 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.
[4] LU Y, YANG C, YANG J. A multi-objective humanitarian pickup and delivery vehicle routing problem with drones[J]. Annals of Operations Research, 2022: 1-63.
[5] ZHANG J, LI Y. Collaborative vehicle-drone distribution network optimization for perishable products in the epidemic situation[J]. Computers & Operations Research, 2023, 149: 106039.
[6] 彭勇, 黎元钧. 考虑疫情影响的卡车无人机协同配送路径优化[J]. 中国公路学报, 2020, 33(11): 73-82.
PENG Y, LI Y J. Optimization of truck-drone collaborative distribution route considering impact of epidemic[J]. China Journal of Highway and Transport, 2020, 33(11): 73-82.
[7] 杨雷博, 周俊. 限制区下货车联合无人机配送路径问题研究[J]. 计算机工程与应用, 2023, 59(12): 326-332.
YANG L B, ZHOU J. Research on distribution path problem of truck combined with UAV in restricted area[J]. Computer Engineering and Applications, 2023, 59(12): 326-332.
[8] 温廷新, 吕艳华. 考虑客户价值的卡车与无人机联合配送时变路径优化方法[J]. 计算机应用研究, 2022, 39(10): 2984-2988.
WEN T X, LV Y H. Research on time-varying route optimization method for truck and UAV joint delivery considering customer value[J]. Application Research of Computers, 2022, 39(10): 2984-2988.
[9] 蒋丽, 王洪艳, 梁昌勇, 等. 农村地区卡车与无人机协同配送路径优化[J]. 计算机工程与应用, 2023, 59(14): 306-314.
JIANG L, WANG H Y, LIANG C Y , et al. Optimization of truck and drone collaborative distribution route in rural areas[J]. Computer Engineering and Applications, 2023, 59(14): 306-314.
[10] YOO H D, CHANKOV S M. Drone-delivery using autonomous mobility: an innovative approach to future last-mile delivery problems[C]//2018 IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), 2018: 1216-1220.
[11] HUANG H, SAVKIN A V, HUANG C. Scheduling of a parcel delivery system consisting of an aerial drone interacting with public transportation vehicles[J]. Sensors, 2020, 20(7): 2045.
[12] 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.
[13] HANSEN P, MLADENOVI? N, TODOSIJEVI? R, et al. Variable neighborhood search: basics and variants[J]. EURO Journal on Computational Optimization, 2017, 5(3): 423-454.
[14] 郭超, 陈香玲, 郭鹏, 等. 基于通用变邻域搜索的多AGV分拣调度优化[J]. 河北科技大学学报, 2021, 42(5): 523-534.
GUO C, CHEN X L, GUO P, et al. General variable neighborhood search for the multi-AGV scheduling problem with sorting operations[J]. Journal of Hebei University of Science and Technology, 2021, 42(5): 523-534.
[15] 尚正阳, 顾寄南, 王建平. 求解带能力约束车辆路径优化问题的改进模拟退火算法[J]. 计算机集成制造系统, 2021, 27(8): 2260-2269.
SHANG Z Y, GU J N, WANG J P. lmproved simulated annealing algorithm for capacitated vehicle routing problem[J]. Computer Integrated Manufacturing Systems, 2021, 27(8): 2260-2269.
[16] ICHOUA S, GENDREAU M, POTVIN J Y. Vehicle dispatching with time-dependent travel times[J]. European Journal of Operational Research, 2003, 144(2): 379-396.