Планування маршрутів польоту безпілотних літальних апаратів шляхом розв’язання задачі комівояжера

Автор(и)

  • Vladimir Vorotnikov Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004, Україна https://orcid.org/0000-0001-8584-3901
  • Igor Gumenyuk Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004, Україна https://orcid.org/0000-0001-5853-3238
  • Pavel Pozdniakov Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004, Україна https://orcid.org/0000-0003-4188-9486

DOI:

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

Ключові слова:

задача комівояжера, мінімальний маршрут, планування маршрутів, безпілотні літальні апарати

Анотація

Розглянуто методи розв’язання задачі комівояжера для планування маршрутів польоту безпілотних літальних апаратів та проаналізовано результати роботи. Показано, що метод осереднених коефіцієнтів розв’язує задачу найоптимальніше за критерієм відстані, використання якого забезпечує мінімальні експлуатаційні витрати польоту безпілотних літальних апаратів та дає суттєвий виграш порівняно з іншими методами (5–10 %).

Біографії авторів

Vladimir Vorotnikov, Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004

Доктор технічних наук, доцент

Кафедра комп’ютерно-інтегрованих технологій та кібербезпеки

Igor Gumenyuk, Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004

Ад’юнкт

Кафедра комп’ютерно-інтегрованих технологій та кібербезпеки

Pavel Pozdniakov, Житомирський військовий інститут ім. С. П. Корольова, пр. Миру, 22, м. Житомир, Україна, 10004

Кандидат технічних наук, начальник науково-дослідної лабораторії

Науковий центр

Посилання

  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

##submission.downloads##

Опубліковано

2017-07-25

Як цитувати

Vorotnikov, V., Gumenyuk, I., & Pozdniakov, P. (2017). Планування маршрутів польоту безпілотних літальних апаратів шляхом розв’язання задачі комівояжера. Technology Audit and Production Reserves, 4(2(36), 44–49. https://doi.org/10.15587/2312-8372.2017.108537

Номер

Том 4 № 2(36) (2017): Інформаційно-керуючі системи

Розділ

Математичне моделювання: Оригінальне дослідження

Ліцензія

Авторське право (c) 2017 Igor Gumenyuk, Vladimir Vorotnikov, Pavel Pozdniakov

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.