Тема выпускной квалификационной работы: «Оптимизация маршрутов передвижения беспилотного летательного аппарата». Данная работа посвящена разбору методов решения задачи коммивояжера, их анализу, выбору оптимального метода и составлению программного приложения для формирования маршрута при заданных координатах. Задачи, которые решались в ходе исследования: 1) Обзор современного использования беспилотных летательных аппаратов. 2) Постановка и описание задачи коммивояжера; 3) Приведение и обзор четырех существующих методов решения задачи коммивояжера (метод полного перебора, метод ближайшего соседа, генетический алгоритм и жадный алгоритм); 4) Сравнение и анализ методов построения оптимального маршрута; 5) Разработка программного приложения, реализующего методы решения задачи коммивояжёра. В ходе выполнения работы были рассмотрены и проанализированы четыре различных метода решения задачи коммивояжера: метод полного перебора, алгоритм муравья, метод ближайшего соседа и генетический алгоритм.  Проведен сравнительный анализ методов с целью определить наиболее эффективный и оптимальный для формирования оптимального маршрута. Результаты  сравнительного  анализа  подтвердили, что  метод ближайшего соседа является наиболее точным и быстрым, обеспечивая оптимальное построение маршрута. На основе полученных результатов было разработано и реализовано программное приложение, предназначенное для формирования оптимального маршрута беспилотного летательного аппарата (БПЛА) в рамках поисково-спасательных операций при заданных координатах. Разработанное программное приложение успешно выполняет вычисление оптимального маршрута и предоставляет информацию о его длине. Кроме того, оно также позволяет сохранять HTML-карту с построенным маршрутом, что обеспечивает визуализацию и удобный доступ к результатам.

Theme of the final qualification work: “Optimization of routes of unmanned aerial vehicle movement”. This work is devoted to the analysis of methods for solving the problem of the traveling salesman, their analysis, selection of the optimal method and compilation of a software application for the formation of the route at given coordinates. The tasks that were solved during the research: 1) Review of the modern use of unmanned aerial vehicles; 2) Formulation and description of the traveling salesperson problem; 3) Introduction and review of four existing methods for solving the traveling salesperson problem (brute-force method, nearest neighbor method, genetic algorithm and greedy algorithm); 4) Comparison and analysis of the methods in constructing the optimal route; 5) Development of a software application that realizes the methods of solving the traveling salesperson problem. In the course of the work, we have considered and analyzed four different methods of solving the traveling salesperson problem: the method of complete search, the ant algorithm, the nearest neighbor method, and the genetic algorithm.  A comparative analysis of the methods was conducted to determine the most efficient and optimal one for forming the optimal route. The results of the comparative analysis confirmed that the nearest-neighbor method is the most accurate and fastest, providing optimal route construction. Based on the results obtained, a software application was developed and implemented to form the optimal route of an unmanned aerial vehicle (UAV) in search and rescue operations at given coordinates. The developed software application successfully calculates the optimal route and provides information about its length. In addition, it also allows saving an HTML map with the constructed route, which provides visualization and easy access to the results.

• ВВЕДЕНИЕ
• Глава 1 ПРОБЛЕМАТИКА ЭКСПЛУАТАЦИИ СОВРЕМЕННЫХ БПЛА
  • 1.2 Постановка задачи
  • 2.1 Теория оптимизации маршрутов БПЛА
  • 2.2 Задача коммивояжера
  • 2.3 Метод полного перебора
  • 2.4 Метод ближайшего соседа
  • 2.5 Генетический алгоритм
  • 2.6 Алгоритм муравья
• ГЛАВА 3 РЕАЛИЗАЦИЯ И СРАВНЕНИЕ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА.
  • 3.1 Выбор средств разработки
  • 3.2 Реализация метода ближайшего соседа
  • 3.3 Реализация генетического алгоритма
  • 3.4 Сравнение методов
• ГЛАВА 4 РАЗРАБОТКА ПРОГРАММЫ, РЕАЛИЗУЮЩЕЙ ПОИСК ОПТИМАЛЬНОГО МАРШРУТА.
  • 4.1 Реализация программы
  • 4.2 Валидация программы
  • 4.3 Работа программы
• ЗАКЛЮЧЕНИЕ
• СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
• Приложение 1. Код программы, реализующий метод ближайшего соседа
• Приложение 2. Код программы, реализующий метод генетического алгоритма
• Приложение 3. Код программы, реализующий поиск оптимального маршрута через заданные точки