Planning the flight routes of the unmanned aerial vehicle by solving the travelling salesman problem

Authors

DOI:

https://doi.org/10.15587/2312-8372.2017.108537

Keywords:

traveling salesman problem, minimum route, route planning, unmanned aerial vehicles

Abstract

The methods for solving the traveling salesman problem: Monte Carlo, reduction of rows and columns, averaged coefficients for planning the flight paths of unmanned aerial vehicles, and the results of the work are analyzed. The solution of the traveling salesman problem allows to reduce the time for decision making and UAV costs when planning flights.

It is established that the first two solve the problem with some errors, and, when using the Monte Carlo method, these errors tend to increase, and the method of reduction of rows and columns minimizes. When using the method of averaged coefficients, the traveling salesman problem is solved more optimally in comparison with the methods considered by the distance and time criterion for solving the problem. This method gives a significant gain (5–10 %) for these criteria.

The relevance and importance of the application of this method is in civil or military operations using UAVs in the face of limited decision-making time in the planning and energy resources of the aircraft.

Author Biographies

Vladimir Vorotnikov, Korolyov Zhytomyr Military Institute, 22, Myr ave, Zhytomyr, Ukraine, 10004

Doctor of Technical Science, Associate Professor

Department of Computer Integrated Technologies and Cyber Security

Igor Gumenyuk, Korolyov Zhytomyr Military Institute, 22, Myr ave, Zhytomyr, Ukraine, 10004

Adjunct

Department of Computer Integrated Technologies and Cyber Security

Pavel Pozdniakov, Korolyov Zhytomyr Military Institute, 22, Myr ave, Zhytomyr, Ukraine, 10004

PhD, Chief of Research Laboratory

Research Centre 

References

  1. Bondarev, D. І., Kucherov, D. P., Shmelova, T. F. (2016). Modelling of group flights of unmanned aerial vehicles using graph theory. Scientific Works of Kharkiv National Air Force University, 3 (48), 61–66.
  2. Aldoshin, D. V. (2013). Spatial planning of routes for UAVs using search on graphs. Youth Science and Technology Herald of the Bauman MSTU, 2. Available: http://sntbul.bmstu.ru/doc/551948.html
  3. Gurnik, A., Valuiskii, S. (2013). Use of intellectual sensor technics for monitoring and search-and-rescue operations. Eastern-European Journal Of Enterprise Technologies, 3(9(63)), 27–32. Available: http://journals.uran.ua/eejet/article/view/14845
  4. Podlipian, P. E., Maksimov, N. A. (2010). Kombinirovannyi algoritm resheniia transportnoi zadachi v sisteme planirovaniia poleta gruppy bespilotnyh letatel'nyh apparatov. Tezisy dokladov 9 Mezhdunarodnoi konferentsii «Aviatsiia i kosmonavtika – 2010». St. Petersburg: Masterskaia pechati, 138–139.
  5. Bopardikar, S. D., Smith, S. L., Bullo, F., Hespanha, J. P. (2010). Dynamic Vehicle Routing for Translating Demands: Stability Analysis and Receding-Horizon Policies. IEEE Transactions on Automatic Control, 55 (11), 2554–2569. doi:10.1109/tac.2010.2049278
  6. Sariel-Talay, S., Balch, T. R., Erdogan, N. (2009). Multiple Traveling Robot Problem: A Solution Based on Dynamic Task Selection and Robust Execution. IEEE/ASME Transactions on Mechatronics, 14 (2), 198–206. doi:10.1109/tmech.2009.2014157
  7. Gao, P.-A., Cai, Z.-X., Yu, L.-L. (2009). Evolutionary Computation Approach to Decentralized Multi-robot Task Allocation. 2009 Fifth International Conference on Natural Computation. IEEE, 415–419. doi:10.1109/icnc.2009.123
  8. Pehlivanoglu, Y. V. (2012). A new vibrational genetic algorithm enhanced with a Voronoi diagram for path planning of autonomous UAV. Aerospace Science and Technology, 16 (1), 47–55. doi:10.1016/j.ast.2011.02.006
  9. Rahimi-Vahed, A., Crainic, T. G., Gendreau, M., Rei, W. (2013). A path relinking algorithm for a multi-depot periodic vehicle routing problem. Journal of Heuristics, 19 (3), 497–524. doi:10.1007/s10732-013-9221-2
  10. Murray, C. C., 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. doi:10.1016/j.trc.2015.03.005
  11. Hawary, A. F., Chipperfield, A. J. (2016). Routeing Strategy for Coverage Path Planning in Agricultural Monitoring Activity using UAV. Eminent Association of Pioneers (EAP) August 22-24, 2016 Kuala Lumpur (Malaysia). Eminent Association of Pioneers (EAP), 68–74. doi:10.17758/eap.eap816005
  12. Johnson, D. S., McGeoch, L. A. (1995, November 20). The Traveling Salesman Problem: A Case Study in Local Optimization. Available: http://www.uniriotec.br/~adriana/files/TSPchapter.pdf

Downloads

Published

2017-07-25

How to Cite

Vorotnikov, V., Gumenyuk, I., & Pozdniakov, P. (2017). Planning the flight routes of the unmanned aerial vehicle by solving the travelling salesman problem. Technology Audit and Production Reserves, 4(2(36), 44–49. https://doi.org/10.15587/2312-8372.2017.108537

Issue

Vol. 4 No. 2(36) (2017): Information and Control Systems

Section

Mathematical Modeling: Original Research

License

Copyright (c) 2017 Igor Gumenyuk, Vladimir Vorotnikov, Pavel Pozdniakov

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.