Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
-->

UDC 519.8
V.P. Horbulin1, L.F. Hulianytskyi2, I.V. Sergienko3


1 National Academy of Sciences of Ukraine, Kyiv, Ukraine

horbulin@nas.gov.ua

2 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

leonhul.icyb@gmail.com

3 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

incyb@incyb.kiev.ua

PLANNING OF LOGISTICS MISSIONS OF THE «UAV+VEHICLE» HYBRID SYSTEM

Abstract. This paper considers the planning of logistics missions for hybrid transport systems, which include a car or other vehicle that can move from a base to other locations along a designated route, carrying one unmanned aerial vehicle (UAV). A meaningful formulation and mathematical models of optimization problems of distributing objects to bases, selecting bases, and generating UAV routes during the inspection or maintenance of a given set of objects in the presence of flight resource constraints are proposed. We have developed an algorithm based on ant colony optimization to solve the resulting combinatorial optimization problems. We present the results of a computational experiment.

Keywords: logistics mission planning, dynamic bases, route optimization, vehicle, UAV, ant colony optimization.


full text

REFERENCES

  1. Thibbotuwawa A., Bocewicz G., Nielsen P., Banaszak Z. Unmanned aerial vehicle routing problems: А literature review. Applied sciences. 2020. Vol.10, Issue 13. 4504. https://doi.org/10.3390/app10134504.

  2. Macrina G., Di Puglia Pugliese L., Guerriero F., Laporte G. Drone-aided routing: A literature review. Transportation Research Part C: Emerging Technologies. 2020. Vol. 120. 102762. https://doi.org/10.1016/j.trc.2020.102762.

  3. Liu W., Zhang T., Huang S., Li K. A hybrid optimization framework for UAV reconnaissance mission planning. Computers & Industrial Engineering. 2022. Vol. 173. 108653. https://doi.org/10.1016/j.cie.2022.108653 .

  4. Ahn N., Kim S. Optimal and heuristic algorithms for the multi-objective vehicle routing problem with drones for military surveillance operations. Journal of Industrial and Management Optimization. 2022. Vol. 18, Issue 3. P. 1651–1663. https://doi.org/10.3934/jimo.2021037.

  5. Golden B., Wang X., Wasil E. The Evolution of the Vehicle Routing Problem — A Survey of VRP Research and Practice from 2005 to 2022. In: The Evolution of the Vehicle Routing Problem. Synthesis Lectures on Operations Research and Applications. Cham: Springer, 2023. P. 1–64. https://doi.org/10.1007/978-3-031-18716-2_1 .

  6. Murray C.C., Chu A.G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies. 2015. Vol. 54. P. 86–109. https://doi.org/10.1016/j.trc.2015.03.005.

  7. Huang S.-H., Huang Y.-H., Blazquez C.A., Chen C.-Y. Solving the vehicle routing problem with drone for delivery services using an ant colony optimization algorithm. Advanced Engineering Informatics. 2022. Vol. 51. 101536. https://doi.org/10.1016/j.aei.2022.101536 .

  8. Montoya-Torres J.R., Franco J.L., Isaza S.N., Jimenez H.F., Herazo-Padilla N. A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering. 2015. Vol. 79. P. 115–129. https://doi.org/10.1016/j.cie.2014.10.029.

  9. Koс С., Laporte G. Vehicle routing with backhauls: Review and research perspectives. Computers & Operations Research. 2018. Vol. 91. P. 79–91. .

  10. Jayarathna N., Lanel J., Juman Z.A.M.S. Five years of multi-depot vehicle routing problems. Journal of Sustainable Development of Transport and Logistics. 2020. Vol. 5, N 2. P. 109–123. https://doi.org/10.14254/jsdtl.2020.5-2.10 .

  11. Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV team routes in the presence of alternative and dynamic depots. Cybernetics and Systems Analysis. 2020. Vol. 56, N 2. P. 195–203. https://doi.org/10.1007/s10559-020-00235-8.

  12. Ramos T.R.P., Gomes M.I., Povoa A.P.B. Multi-depot vehicle routing problem: A comparative study of alternative formulations. International Journal of Logistics Research and Applications. 2020. Vol. 23, Issue 2. P. 103–120. https://doi.org/10.1080/13675567.2019.1630374.

  13. Yoo W., Yu E., Jung J. Drone delivery: Factors affecting the public’s attitude and intention to adopt. Telematics and Informatics. 2018. Vol. 35, Issue 6. P. 1687–1700. https://doi.org/10.1016/j.tele.2018.04.014.

  14. Kyriakakis N.A., Stamadianos T., Marinaki M., Marinakis Y. The electric vehicle routing problem with drones: An energy minimization approach for aerial deliveries. Cleaner Logistics and Supply Chain. 2022. Vol. 4. 100041. https://doi.org/10.101/j.clscn.2022.100041.

  15. Kliushnikov I., Fesenko H., Kharchenko V., Illiashenko O., Morozova O. UAV fleet based accident monitoring systems with automatic battery replacement systems: Algorithms for justifying composition and use planning. International Journal of Safety and Security Engineering. 2021. Vol. 11, N 4. P. 319–328. https://doi.org/10.18280/ijsse.110404.

  16. Yakovlev S., Kartashov O., Mumrienko A. Formalization and solution of the maximum area coverage problem using library Shapely for territory monitoring. Radioelectronic and Computer Systems. 2022. N 2. P. 35–48. https://doi.org/10.32620/reks.2022.2.03.

  17. Gonzalez-R P.L., Canca D., Andrade-Pineda J.L., Calle M., Leon-Blanco J.M. Truck-drone team logistics: A heuristic approach to multi-drop route planning. Transportation Research Part C: Emerging Technologies. 2020. Vol. 114. P. 657–680. https://doi.org/10.1016/j.trc.2020.02.030.

  18. Poikonen S., Golden B. Multi-visit drone routing problem. Computers & Operations Research. 2020. Vol. 113. 104802. https://doi.org/10.1016/j.cor.2019.104802.

  19. Tamke F., Buscher U. The vehicle routing problem with drones and drone speed selection. Computers & Operations Research. 2023. Vol. 152. 106112. https://doi.org/10.1016/j.cor.2022.106112.

  20. Wang Z., Sheu J.B. Vehicle routing problem with drones. Transportation Research Part B: Methodological. 2019. Vol. 122. P. 350–364. https://doi.org/10.1016/j.trb.2019.03.005.

  21. Murray C.C., Raj R. The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies. 2020. Vol. 110. P. 368–398. https://doi.org/10.1016/j.trc.2019.11.003.

  22. Jeong H.Y., Lee S. Collaborative hybrid delivery system: Drone routing problem assisted by truck. In: Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems: IFIP WG 5.7 International Conference, APMS 2021 (Nantes, France, Sept. 5–9, 2021). Proc., Part III. Springer Int. Publ, 2021. P. 33–42.

  23. Loehr N.A. Combinatorics. Discrete Mathematics and its Applications (2nd Ed.). New York: Chapman and Hall/CRC, 2017. 642 p.

  24. Sttzle T., Dorigo M. Ant Colony Optimization: Overview and Recent Advances. Handbook of Metaheuristics. Third Edition. Gendreau V., Potvin J.-Y. (Eds). Cham: Springer, 2019. P. 311–351.

  25. Gulyanitsky L.F., Mulesa O.Yu. Applied methods of combinatorial optimization [in Ukrainian]. Kyiv: Kyiv University Publishing and Printing Center, 2016. 142 p.

  26. Reinelt G. TSPLIB 95. Technical report, Universitt Heidelberg. 1995. URL: https://icyb180.org.ua/experiments/Accessed 22 Feb 2023 .

  27. Stoyan Y.G., Yakovlev S.V. Theory and methods of euclidian combinatorial optimization: Current status and prospects. Cybernetics and Systems Analysis. 2020. Vol. 56, N 3. P. 366–379. https://doi.org/10.1007/s10559-020-00253-6.




© 2023 Kibernetika.org. All rights reserved.