大规模区域下车载无人机的作业路径规划两阶段算法
作者单位:

长安大学

基金项目:

港珠澳大桥智能化运维技术集成应用


A two-stage route planning algorithm for vehicle-mounted UAVs in large areas
Author:
Affiliation:

1.Chang&2.amp;3.#39;4.&5.an university;6.Chang'7.'

Fund Project:

Integrated application of intelligent operation and maintenance technology for Hong Kong-Zhuhai-Macao Bridge

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [22]
  • | |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    无人机已广泛用于各个领域,具有安全系数小和低成本的优势。然而,由于无人机续航时间有限,无法到达较远的距离,一种新的解决方案是利用车辆来携带和发射无人机,即无人机与车辆协同方式,以完成整个的总时间最小为目标。该论文提出了一种两阶段算法来解决无人机与车辆协同作业的路径规划问题。在第一阶段中,利用聚类算法对目标区域进行划分,以确定车辆的分配情况。在第二阶段中,设计并改进了传统的教学优化算法HTLBO,以提高搜索效率,在每个目标区域里求得无人机的行进航线,确保航线的优化性。最后,通过与其他对比算法进行实验结果比较表明,车辆与无人机联合作业模型及HTLBO算法的可行性与鲁棒性,对各个大规模区域下的复杂动态提供了一些思路和参考。

    Abstract:

    Unmanned aerial vehicles (UAVs) have been widely used in various fields and have the advantages of low safety factor and low cost. However, due to the limited endurance of the UAV, it is impossible to reach a long distance, a new solution is to use the vehicle to carry and launch the UAV, that is, the collaborative way of the UAV and the vehicle, in order to complete the total time of the minimum as the goal. In this paper, a two-stage algorithm is proposed to solve the path planning problem of UAV-vehicle cooperative operation. In the first stage, the target area is divided using a clustering algorithm to determine the distribution of vehicles. In the second stage, the traditional teaching optimization algorithm HTLBO is designed and improved to improve the search efficiency, and the route of the UAV is obtained in each target area to ensure the optimization of the route. Finally, the experimental results compared with other comparison algorithms show that the vehicle-UAV joint operation model and HTLBO algorithm are feasible and robust, and provide some ideas and references for complex dynamics in various large-scale areas.

    参考文献
    [1] 许菱,杨林超,朱文兴,等.农村电商物流下无人机与车辆协同配送路径优化研究[J].计算机工程与应用,2024,60(01):310-318.Xu Ling, Yang Linchao, Zhu Wenxing, et al. Research on Cooperative Delivery Route Optimization of Drones and Vehicles in Rural E-commerce Logistics [J]. Computer Engineering and Applications, 2024, 60(01): 310-318.
    [2] 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.
    [3] David Sacramento, David Pisinger, Stefan Ropke, An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones,Transportation Research Part C: Emerging Technologies, 2019, Pages 289-315, https://doi.org/10.1016/j.trc.2019.02.018.
    [4] Sung Hoon Chung, Bhawesh Sah, Jinkun Lee, Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions, Computers Operations Research, 2020, https://doi.org/10.1016/j.cor.2020.105004.
    [5] Mohammad Moshref-Javadi, Matthias Winkenbach, Applications and Research avenues for drone-based models in logistics: A classification and review, Expert Systems with Applications, 2021, https://doi.org/10.1016/j.eswa.2021.114854.
    [6] Wang X Y,Poikonen S,GOLDEN B.Thevehicle routingproblem with drones:several worst-case results[J].OptimizationLetters,2017,11(4):679-97.
    [7] 马华伟,闫伯英.面向防疫物资分区配送车机协同路径规划问题[J/OL].系统仿真学报,1-10[2024-09-13].https://doi.org/10.16182/j.issn1004731x.joss.23-1022. Ma, H.,
    [8] Tu, P., Dat, N., Dung, P., 2018. Traveling salesman problem with multiple drones. In: Proceedings of the Ninth International Symposium on Information and Communication Technology. ACM, pp. 46–53.
    [9] Agatz, N., Bouman, P., Schmidt, M., Jul-Aug 2018.. Optimization approaches for the traveling salesman problem with drone. Transp. Sci. 52 (4), 965–981.
    [10] Liu, Y., Liu, Z., Shi, J., Wu, G., Pedrycz, W., Dec 2021. Two-echelon routing problem for parcel delivery by cooperated truck and drone. IEEE Trans. Syst. Man Cybernet.-Syst. 51 (12), 7450–7465.
    [11] Ferrandez, S.M., Harbison, T., Weber, T., Sturges, R., Rich, R., 2016. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm. J. Ind. Eng. Manag. 9 (2), 374.
    [12] CHANG Y S, LEE H J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route[J]. Expert Systems with Applications, 2018, 104:307-317.
    [13] YOON J J. The Traveling salesman problem with multiple drones: an optimization model for last-mile delivery[D]. Cambridge: Massachusetts Institute of Technology, 2018,
    [14] Guomin Shao, Wenting Han, Huihui Zhang, Liyuan Zhang, Yi Wang, Yu Zhang, Prediction of maize crop coefficient from UAV multisensor remote sensing using machine learning methods, Agricultural Water Management, Volume 276, 2023, https://doi.org/10.1016/j.agwat.2022.108064.
    [15] Zhao, K., He, T., Wu, S. et al. Application research of image recognition technology based on CNN in image location of environmental monitoring UAV. J Image Video Proc. 2018, 150 (2018). https://doi.org/10.1186/s13640-018-0391-6
    [16] 曹峰,崔少华,荆治家,等.面向巡检车与无人机协同电力巡检的车辆路径规划方法[J].交通运输工程与信息学报,2022,20(02):95-104.DOI:10.19961/j.cnki.1672-4747.2021.07.043. Cao Feng, Cui Shaohua, Jing Zhijia, et al. Vehicle Path Planning Method for Cooperative Power Inspection of Inspection Vehicles and Drones [J]. Journal of Transportation Engineering and Information Science, 2022, 20(02): 95-104. DOI: 10.19961/j.cnki.1672-4747.2021.07.043.
    [17] Natalia Rylko, Micha? Stawiarz, Pawel Kurtyka, Vladimir Mityushev, Study of anisotropy in polydispersed 2D micro and nano-composites by Elbow and K-Means clustering methods,Acta Materialia,2024, https://doi.org/10.1016/j.actamat.2024.120116.
    [18] Prins C. A simple and effective evolutionary algorithm for the vehicle routing problem [J]. Computers
    [19] 段帆利. 基于改进的教学优化算法的物流无人机群送取货航线规划问题研究[D].长安大学,2019. Duan Fanli. Research on the Route Planning Problem of Logistics Unmanned Aerial Vehicle Group Delivery and Pickup Based on Improved Teaching Optimization Algorithm [D]. Chang'an University, 2019.
    Hansen P., Mladenovi? N. Variable neighborhood search: Principles and applications [J]. European Journal of Operational Research, 2001, 130(3):449- 467.
    [21] Pan Q. K., Tasgetiren M. F., Liang Y C.. A discrete particle swarm optimization algorithm for the no- wait flowshop scheduling problem [J]. Computers and Operations Research, 2008, 35(9):2807-2839.6
    [22] Augerat. (2013). The VRP Web. [Online]. Available: https://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文
分享
文章指标
  • 点击次数:163
  • 下载次数: 0
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2024-07-10
  • 最后修改日期:2024-09-14
  • 录用日期:2024-10-28
文章二维码