Разработка средств построения маршрутов БПЛА при сборе данных мониторинга больших территорий тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Маткурбанов Тулкин Алимбоевич

• Маткурбанов Тулкин Алимбоевич
• кандидат наук
• 2026

Оглавление диссертации кандидат наук Маткурбанов Тулкин Алимбоевич

Введение

Глава 1. Актуальные проблемы сбора данных при мониторинге больших

территорий

1.1. Стратегии сбора данных для мониторинга

1.2. Архитектура сенсорной сети

1.3. Принципы построения сенсорной сети для целей мониторинга

1.4. Анализ существующих проблем при сборе данных с сенсорных сетей

1.5. Выводы по Главе

Глава 2. Математическая модель повышения эффективности траектории полета беспилотных летательных аппаратов при мониторинге больших

территорий

2.1. Расположение сенсорных узлов в мониторинге

2.2. Проблемы планирования траектории при мониторинге

2.3. Формализация задачи и математическая модель

2.4. Выводы по Главе

Глава 3. Планирование эффективной траектории сбора данных с датчиков,

расположенных на больших территориях

3.1. Классификация алгоритмов планирования маршрутов

3.2. Построение траектории полёта БПЛА на основе заданного расположения сенсоров

3.3. Эффективные методы планирования траектории БПЛА для сбора данных с датчиков на больших территориях

3.4. Выводы по Главе

Глава 4. Разработка программного комплекса для реализации предложенных

алгоритмов

4.1. Создание программного приложения на основе алгоритмов построения траекторий полёта БПЛА с учётом расположения датчиков на больших территориях

4.2. Создание программного интерфейса на основе алгоритмов планирования траектории полета БПЛА с радиопокрытием для мониторинга больших территорий

4.3. Выводы по Главе

Заключение

Использованная литература

Публикации автора по теме диссертации

Список рисунков

Список таблиц

Приложение

Приложение

Приложение А. Акты о внедрении

Введение

Мониторинг больших территорий становится все более важным в таких областях, как сельское хозяйство, экология и безопасность. Современные подходы предполагают комбинированное использование сетей наземных датчиков и беспилотные летательные аппараты (БПЛА) для сбора данных на больших территориях.

Объект исследования - Объектом данного научного исследования стал процесс сбора данных с помощью автоматизированных систем мониторинга на больших территориях (например, мониторинг, с помощью наземных датчиков, состояния сельскохозяйственных культур, выращиваемых на больших площадях).

Предмет исследования - Предметом исследования является модель повышения эффективности траектории сбора данных с сенсорной сети с использованием одного БПЛА и алгоритмы, разработанные на основе этой модели. То есть рассматривается задача поиска кратчайшего маршрута для одного беспилотного летательного аппарата для сбора информации с множества точек (датчиков) на большой территории, с учётом радиуса радиовидимости.

Введение диссертации (часть автореферата) на тему «Разработка средств построения маршрутов БПЛА при сборе данных мониторинга больших территорий»

Актуальность исследования

Вопрос эффективного сбора данных в системах мониторинга больших территорий весьма актуален. Использование стационарных датчиков состояния почвы и растений существенно повышает информативность наблюдений, однако обеспечение постоянной связи дорого и не всегда возможно. Приходится решать задачу периодического съёма данных, что возможно делать с применением БПЛА. Использование БПЛА требует расхода топлива или заряда батарей, что требует разработки методов маршрутизации, позволяющих минимизировать расходы, что приводит к задаче нахождения кратчайшего пути. Учёт радиуса радиовидимости позволяет снимать данные с нескольких датчиков одновременно, то есть нет необходимости облёта всех датчиков и тем самым осуществляется сокращение маршрута.

Исследования показывают, что путем разумного планирования траектории полета БПЛА, т. е. путем повышения эффективности траектории, можно повысить эффективность системы, в частности, снизить потребление энергии и задержки передачи данных. Поэтому определение эффективной траектории полета БПЛА для сбора данных в режиме, близком к реальному времени, над большими территориями имеет сегодня актуальное научное и практическое значение.

Целью данного исследования является разработка эффективной методики построения траектории для быстрого сбора данных с сети датчиков,

разбросанных на большой территории, с помощью беспилотного летательного аппарата по кратчайшим траекториям с учётом одновременного съёма данных от нескольких датчиков. Другими словами, это планирование эффективного маршрута полета БПЛА, который охватывает заданный набор точек датчиков за минимальное расстояние (или время). Потенциальная потребность создания соответствующего мобильного приложения требует использования по возможности простых алгоритмов. Задачи исследования:

1. Исследование и анализ существующих методов и подходов к сбору данных с использованием БПЛА на больших территориях (обзор литературы).

2. Разработка соответствующей математической модели (например, основанной на теории графов или аналогии с задачей коммивояжера (ТБР)) для математического моделирования и повышения эффективности движения одного БПЛА через сеть датчиков.

3. Разработка соответствующих математических алгоритмов для математического моделирования и оптимизации движения одного БПЛА через сеть датчиков. Алгоритмы должны предусматривать: а) возможность одновременного получения информации от нескольких датчиков; б) прокладку маршрута по местоположениям отдельных датчиков либо по предварительно вычисленным точкам, обеспечивающих полное покрытие датчиков кругами заданного радиуса (радиуса радиовидимости). Это предполагает использование эвристических методов, таких как алгоритмы решения задачи коммивояжёра, а также геометрических подходов (например, методов выпуклой оболочки или графов).

4. Тестирование разработанных алгоритмов с использованием компьютерного моделирования и экспериментальных примеров.

5. Демонстрация возможности практической реализации предлагаемого решения, т.е. разработка рекомендации по использованию в сельском хозяйстве, мониторинге окружающей среды или в системах безопасности.

Научная новизна

1. Разработан гибридный алгоритм построения эффективной траектории полёта БПЛА, сочетающий геометрические принципы и методы группировки точек, что обеспечивает повышение эффективности сбора данных с сенсорных узлов, расположенных на больших территориях.

2. Впервые предложена интеграция трёхточечного метода с геометрическим алгоритмом в задаче маршрутизации БПЛА, что позволило сократить длину маршрута без потери полноты покрытия наблюдаемых точек.

Практическая ценность исследования 1. Результаты исследования имеют практическое значение для эффективной организации систем управления и мониторинга сенсорных сетей

на больших территориях. Предложенные методы построения эффективной траектории позволяют сократить дальность и время полета БПЛА, а также сэкономить топливо или заряд аккумулятора. В результате такие практические задачи, как непрерывный мониторинг сельскохозяйственных культур, сбор данных об окружающей среде в режиме, близком к реальному времени, а также оперативная разведка в чрезвычайных ситуациях (например, пожары или нарушения границы), будут выполняться более эффективно.

2. Интеграция методов группировки точек и геометрического анализа с задачей коммивояжёра (TSP) позволяет формировать маршруты, близкие к оптимальным, даже с учётом ограничений по времени полёта, заряду аккумулятора и особенностям рельефа местности, что особенно актуально для применения в удалённых и труднодоступных регионах.

3. Разработанный графический интерфейс и архитектура программного обеспечения предоставляют планировщикам полетных заданий удобные инструменты, позволяющие производить интерактивную настройку параметров, визуализацию маршрута, оценку зоны покрытия и экспорт результатов в распространенные форматы (PNG, TXT, XLSX).

4. Метод планирования маршрута на основе радиуса покрытия применим не только к БПЛА, но и к наземным роботам, автоматизированным тележкам и другим мобильным платформам, что расширяет область применения результатов исследования.

Теоретическая ценность исследования заключается в том, что предложенный в работе подход вносит научный вклад в развитие задач комбинаторной оптимизации. В частности, получен опыт использования комбинации эвристических и аналитических методов для решения NP -трудных задач, таких как задача коммивояжёра и её варианты. Разработанная модель и алгоритмы повышения эффективности маршрута для отдельного БПЛА служат теоретической основой не только для данной работы, но и для последующих исследований в области моделирования и повышения эффективности сетей БПЛА в целом.

Основные результаты диссертации

1. Разработан гибридный подход к построению траекторий БПЛА, объединяющий методы группировки точек и геометрические алгоритмы с последующим решением различных формулировок задачи коммивояжёра. Предложенное решение учитывает требование простоты реализации, пространственную структуру размещения сенсоров и ограничения ресурсов беспилотных платформ, что способствует повышению эффективности мониторинга на больших территориях.

2. Разработан программный комплекс с графическим пользовательским интерфейсом (GUI), реализующий все этапы - от загрузки данных датчиков и

настройки параметров до построения и визуализации маршрута, расчета длины траектории и оценки зоны покрытия. Интерфейс позволяет использовать различные алгоритмы и сохранять результаты.

3. Были предложены и реализованы два алгоритма маршрутизации:

a Метод центроидов — основан на предварительной группировке сенсорных узлов с определением центров групп и построении маршрута между этими центрами. Такой подход обеспечивает сокращение количества точек посещения и уменьшение общей длины траектории.; b Геометрический трехточечный метод - основан на анализе пространственных взаиморасположений зон покрытия и применении эвристических правил для построения эффективной траектории.

4. Проведено комплексное сравнение эффективности различных подходов к маршрутизации (алгоритм ближайшего соседа, оптимальная вставка, двухэтапная вставка и т. д.) по критериям длины маршрута и количества контрольных точек для различных радиусов покрытия.

5. Введены и обоснованы математические модели, описывающие зоны покрытия БПЛА, формулы минимизации длины маршрута и уравнения минимальной ограничивающей окружности для эффективного геометрического покрытия заданных точек.

6. Показано, как увеличение радиуса покрытия позволяет сократить протяженность маршрута.

7. Результаты численного моделирования и визуализации с использованием случайных данных (100 датчиков на площади 300*200) подтвердили практическую применимость предложенных алгоритмов для реальных задач мониторинга сельскохозяйственных и экологических территорий, согласно которым было подтверждено, что предложенный алгоритм двухшаговой интерполяции имеет на 10% лучшую производительность по длине пути по сравнению с алгоритмом ближайшего соседа.

Апробация работы.

Основные результаты работы были представлены на 8 международных и всероссийских конференциях, в их числе:

1. Международной конференции по информационным наукам и технологиям связи (2022 International Conference on Information Science and Communications Technologies - ICISCT). - Ташкент, Узбекистан, 28-30 сентября 2022 г.;

2. Международная конференция, 2023 IEEE XVI International Scientific and Technical Conference Actual Problems of Electronic Instrument Engineering (APEIE), Ургенч, Узбекистан, 06-07 октября 2023 г.;

3. IX Международной конференции «Знания - Онтологии - Теории» (ЗОНТ-2023), Новосибирск, Россия, 2-6 октября 2023 г.;

4. VIII Международная научно-практическая конференция «Инновации в информационных технологиях, машиностроении и автотранспорте» г. Кемерово, 21 - 23 ноября 2024 г.;

5. II Международная научно-практическая конференция «Молодёжная наука Севера» г. Ханты-Мансийск, 12-13 декабря 2024 г.;

6. 63-я Международная научная студенческая конференция МНСК-2025 г. Новосибирск, 16-22 апреля 2025 г.;

7. OPCS'25 Международная азиатская школа-семинар «Оптимизационные задачи сложных систем» Россия (Москва — Новосибирск), Казахстан (Алматы), Кыргызстан (Кара-Ой) (гибридный формат) 7-17 июля 2025 г.;

8. Международная конференция, 2025 IEEE XVII International Conference on Actual Problems of Electronic Instrument Engineering (APEIE), Новосибирск, Россия, 14-16 November, 2025 г.

Все доклады были сделаны мной лично.

Соответствие паспорту специальности. Диссертация соответствует следующим пунктам паспорта специальности 1.2.2. «Математическое моделирование, численные методы и комплексы программ»:

2) Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий;

3) Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента;

9) Постановка и проведение численных экспериментов, статистический анализ их результатов, в том числе с применением современных компьютерных технологий (технические науки).

Публикации. Основные результаты диссертационного исследования опубликованы в девяти научных работах, из которых две статьи размещены в научных журналах, рекомендованных ВАК РФ, а семь публикаций — в изданиях, индексируемых в международной базе данных Scopus, в том числе одна статья в журнале второго квартиля (Q2), две статьи в журналах четвёртого квартиля (Q4) и четыре публикации в сборниках трудов международных научных конференций, индексируемых в базе данных Scopus. Остальные материалы представлены в сборниках трудов международных и всероссийских научных конференций.

Объем и структура работы. Диссертация состоит из введения, 4 глав и заключения. Полный объем диссертации составляет 1 02 страниц, включая 43 рисунок и 4 таблиц. Список литературы содержит 72 наименований.

Глава 1. Актуальные проблемы сбора данных при мониторинге

больших территорий

В условиях стремительного развития технологий Интернета вещей (IoT), систем искусственного интеллекта и аналитики больших данных возрастает потребность в мониторинге обширных территорий в режиме реального времени. Особенно актуально это для таких сфер, как сельское хозяйство, экологический мониторинг, управление чрезвычайными ситуациями и обеспечение общественной безопасности. Эффективность подобных систем в значительной степени определяется такими характеристиками, как скорость, точность и надёжность процессов сбора, передачи и обработки информации [1].

Система сбора данных представляет собой структурированную совокупность сенсорных устройств и компонентов связи, предназначенную для автоматизированного получения информации о состоянии окружающей среды, технологических объектов или наблюдаемых процессов. Такая система, функционирующая на основе объединённых сенсоров и средств передачи данных, формирует сеть сбора данных (сенсорную сеть).

В состав сети входят измерительные устройства (датчики), устанавливаемые в целевых зонах наблюдения и фиксирующие параметры окружающей среды, такие как температура, влажность, освещённость, концентрация химических веществ и движение. Сенсорные узлы могут быть как пассивными, так и интеллектуальными, обладающими возможностями локальной обработки и передачи данных.

Передача информации внутри сети осуществляется с использованием различных коммуникационных технологий, включая беспроводные протоколы (ZigBee, LoRa, Wi-Fi), мобильные сети и радиоканалы. Конфигурация размещения сенсоров может быть регулярной, кластерной или случайной, что непосредственно влияет на плотность покрытия, надёжность связи и энергопотребление сети.

Сбор данных может осуществляться как через стационарные узлы (базовые станции и шлюзы), так и с использованием мобильных платформ, в частности беспилотных летательных аппаратов. В последнем случае ключевым аспектом становится задача планирования маршрута обхода зон размещения сенсоров. Данная задача естественным образом формулируется в виде задачи коммивояжёра с окрестностями (TSPN), в которой требуется обеспечить посещение не конкретных точек, а заданных областей покрытия сенсорных узлов. Применение моделей TSPN позволяет учитывать радиус действия сенсоров и существенно сократить длину маршрута БПЛА при сохранении полноты сбора данных.

Таким образом, сеть сбора данных представляет собой гибкую и масштабируемую инфраструктуру, объединяющую сенсорные технологии, коммуникационные средства и методы оптимизации маршрутов, включая ТБРК-подходы, что делает её ключевым элементом современных интеллектуальных систем мониторинга и управления большими территориями.

1.1 Стратегии сбора данных для мониторинга

При мониторинге больших территорий выбор стратегии сбора данных существенно влияет на эффективность всей системы. Такие системы применяются в сельском хозяйстве, экологическом контроле, системах безопасности и обнаружении техногенных угроз, используя стационарные и мобильные датчики, а также беспилотные летательные аппараты и другие источники данных [2]. Выбор стратегии определяется расположением датчиков, энергетическими ресурсами, возможностями связи и целями мониторинга. Ниже рассмотрены основные подходы к сбору данных.

Централизованная стратегия является одним из наиболее простых подходов к сбору данных, при котором все сенсорные узлы передают информацию в единую центральную точку (базовую станцию или узел-приёмник), где осуществляется её обработка и управление. Данная стратегия применяется преимущественно в небольших и средних сетях с развитой инфраструктурой связи и характеризуется высокой вычислительной нагрузкой на центральный узел [3].

Распределённая стратегия предполагает децентрализованный сбор данных, при котором сенсорные узлы взаимодействуют друг с другом, выполняя локальную обработку, агрегацию и передачу информации. Отсутствие обязательного центрального узла обеспечивает масштабируемость и устойчивость сети, что делает данный подход эффективным для больших и труднодоступных территорий [4].

Стратегия на основе БПЛА основана на использовании беспилотных летательных аппаратов в качестве мобильных сборщиков данных. В этом случае датчики накапливают информацию локально, а БПЛА собирает данные, следуя заданной траектории. Такой подход позволяет снизить энергопотребление сенсорных узлов и особенно эффективен в районах с ограниченной связью. Ключевой задачей данной стратегии является оптимизация маршрута полёта БПЛА для минимизации времени и энергозатрат [5].

Гибридная стратегия сочетает централизованный, распределённый и мобильный подходы к сбору данных. Использование различных стратегий в зависимости от условий эксплуатации повышает гибкость, надёжность и

эффективность системы мониторинга, что особенно важно для крупных и ресурсно-ограниченных территорий [6].

Стратегии Push и Pull - это две различные модели управления передачей данных в системах мониторинга, которые определяют, при каких условиях и когда узлы датчиков отправляют данные.

В модели push сенсорные узлы отправляют информацию независимо. Такая отправка осуществляется автоматически, либо по времени (например, каждые 10 минут), либо в зависимости от события (например, когда температура превышает 50°C). Датчики работают по заранее заданным правилам [7].

Рисунок 1. Блок-схема последовательности выполнения операций в автоматизированной

системе мониторинга

В модели pull данные отправляются на основе внешнего запроса. То есть сенсорный узел передает информацию только в ответ на запрос, отправленный центральным узлом или мобильным сборщиком данных (например, БПЛА). Датчик остается пассивным и реагирует только при необходимости.

Режимы Push и Pull часто используются в сочетании с централизованными, распределенными или мобильными стратегиями. Каждый режим выбирается на основе таких факторов, как частота связи, энергопотребление и скорость мониторинга.

Рассматриваемые стратегии управления позволяют сбалансировать активность, скорость реагирования и потребление ресурсов системы мониторинга. Системы мониторинга больших территорий должны обеспечивать достоверность информации, надёжность работы, минимальные затраты на обслуживание и длительный срок эксплуатации. В этой связи актуальной является разработка автоматизированных систем мониторинга на основе беспилотных летательных аппаратов, которые осуществляют сбор данных в заданных зонах и передают их на сервер для последующей обработки после возвращения на базовую станцию. На рисунке 1 представлена последовательность выполнения операций в автоматизированной системе мониторинга. В дальнейшем, когда БПЛА возвращается на станцию, полученные данные передаются на сервер в общую базу данных и обрабатываются [8]

Для сбора информации с сенсорных полей с применением БПЛА целесообразно использовать протоколы беспроводных сенсорных сетей. Мониторинг больших территорий с помощью БПЛА требует разработки современных моделей и методов сбора данных [9].

1.2. Архитектура сенсорной сети

Беспроводная сенсорная сеть (WSN) представляет собой информационную систему, состоящую из множества сенсорных узлов, объединённых беспроводной связью для измерения и анализа физических и экологических параметров, таких как температура, влажность, давление, освещённость, звук и движение. Архитектура WSN применяется в системах мониторинга, включая решения на основе беспилотных летательных аппаратов, пример организации которых представлен на рисунке 2. Как правило, WSN функционируют автономно, обеспечивая сбор, обработку и передачу данных между узлами и центром управления. Такие сети широко используются для мониторинга, сбора данных и дистанционного управления. Архитектура WSN имеет многоуровневую структуру и включает ряд основных компонентов.

Наземный сегмент (беспроводная сенсорная сеть) > общего пользова- <

Рисунок 2. Архитектура сенсорной сети

Архитектура беспроводной сенсорной сети (WSN) обычно строится по многоуровневому принципу и включает три основных функциональных уровня, каждый из которых выполняет определённую роль в процессах передачи данных и управления сетью [10]. Такой подход обеспечивает модульность, масштабируемость и гибкость системы при эксплуатации в различных условиях мониторинга.

В классической архитектуре WSN выделяют физический, канальный (MAC) и прикладной уровни. Физический уровень отвечает за передачу сигналов между сенсорными узлами и базовой станцией, канальный уровень обеспечивает надёжный доступ к среде передачи данных и управление соединениями, а прикладной уровень реализует обработку, агрегацию и передачу данных конечному пользователю. Для организации взаимодействия на прикладном уровне широко применяются протоколы ZigBee, MQTT и CoAP, ориентированные на работу в сетях с ограниченными ресурсами.

Основными элементами беспроводной сенсорной сети являются сенсорные узлы, включающие датчики, микроконтроллер, модуль беспроводной связи и источник питания. Узел сбора данных (шлюз) агрегирует информацию от сенсорных узлов и обеспечивает соединение сети с внешними информационными системами, тогда как базовая станция выполняет функции хранения, анализа и визуализации данных. Для обмена информацией в WSN используются различные технологии связи, такие как ZigBee, LoRa, Wi-Fi, Bluetooth/BLE, NB-IoT и 6LoWPAN. Выбор конкретной технологии определяется требованиями к дальности связи, скорости передачи данных и уровню энергопотребления [11].

Для маршрутизации данных в беспроводных сенсорных сетях применяются плоские, иерархические, географические и энергосберегающие подходы. Благодаря своей гибкости и энергоэффективности WSN широко используются в задачах мониторинга окружающей среды, сельского хозяйства и здравоохранения и рассматриваются как перспективная технология

современных информационно-коммуникационных систем [12]. Особый интерес представляют летающие сенсорные сети, в которых сбор данных с наземных сенсоров осуществляется с использованием беспилотных летательных аппаратов. Такой подход позволяет существенно расширить возможности мониторинга больших и труднодоступных территорий [13].

В типовой конфигурации WSN сенсорные узлы размещаются непосредственно в зонах мониторинга, а базовая станция или шлюз обеспечивает приём, обработку и передачу собранных данных внешним пользователям и информационным системам, как показано на рисунке 3 [14].

Рисунок 3. Структура беспроводной сенсорной сети

На рисунке 4 представлена типовая архитектура беспроводного сенсорного узла, включающая сенсорную подсистему с одним или несколькими датчиками и аналого-цифровыми преобразователями, подсистему обработки данных на основе микроконтроллера и памяти, радиомодуль для беспроводной передачи информации, а также источник питания [15].

Назначение датчиков заключается в преобразовании физических воздействий окружающей среды в электрические сигналы. Полученные сигналы, как правило, требуют предварительной обработки, включающей усиление, фильтрацию шумов и другие преобразования, необходимые для их последующей обработки и передачи.

Рисунок 4.Типовая архитектура сенсорного узла

В процессе измерения сигнал, сформированный датчиком, преобразуется из аналоговой формы в цифровую с помощью аналого-

цифрового преобразователя (АЦП) и далее передаётся в вычислительную систему для хранения и визуализации. Сенсорные узлы могут включать дополнительные компоненты, например системы позиционирования, однако в дальнейшем анализе они не рассматриваются как обязательные элементы [16]. Как правило, узлы функционируют в энергосберегающем режиме и активируются либо при возникновении определённого события, либо через заданные временные интервалы, после чего передают собранные данные в центр обработки информации.

Принципы функционирования сенсорных систем во многом аналогичны механизмам восприятия, присущим биологическим объектам. Пять чувств — зрение, слух, обоняние, вкус и осязание — традиционно рассматриваются как основные средства, с помощью которых человек и большинство животных воспринимают окружающий мир. Эти процессы реализуются посредством оптического (зрение), акустического (слух), химического (обоняние и вкус) и механического, или тактильного, восприятия (осязание). Вместе с тем живые организмы зависят не только от перечисленных органов чувств, но и от множества других сенсорных механизмов, позволяющих ощущать тепло, оценивать температуру, воспринимать боль и локализовать ощущения как на поверхности тела, так и внутри него [17]. Данные особенности подчёркивают многообразие сенсорных функций и служат основой для разработки технических средств измерения различных физических величин.

С учётом этого датчики и актуаторы классифицируются по ряду признаков, включая физические принципы работы и области применения. Одним из наиболее распространённых подходов является разделение датчиков на активные и пассивные [18]. Активные датчики требуют внешнего источника питания и формируют выходной сигнал за счёт изменения собственных параметров, тогда как пассивные датчики способны самостоятельно генерировать электрический сигнал, например термоэлектрические датчики. Кроме того, датчики подразделяются на контактные и бесконтактные, а выбор конкретного типа определяется условиями эксплуатации и требованиями мониторинговой системы [19].

1.3. Принципы построения сенсорной сети для целей мониторинга

Беспроводные сенсорные сети являются одним из ключевых компонентов современных систем мониторинга в реальном времени и широко применяются при наблюдении за большими и распределёнными территориями. Эффективность функционирования таких сетей определяется совокупностью технических факторов, включая архитектуру сети, размещение сенсорных узлов, энергоэффективность, устойчивость связи, синхронизацию времени, масштабируемость и безопасность передачи данных.

Список литературы диссертационного исследования кандидат наук Маткурбанов Тулкин Алимбоевич, 2026 год

Использованная литература

1. Т.А.Маткурбанов, К.С.Хайитбаев, Архитектура на основе интернета вещей для анализа энергетических объектов [текст]// Всероссийской научно-технической конференции //Наука. Технология. Производство - 2021, 23 апреля 2021 г.- Салават, Россия, 2021 г. - С. 63.

2. Ullo S. L., Sinha G. R. Advances in smart environment monitoring systems using IoT and sensors //Sensors. - 2020. - Т. 20. - №. 11. - С. 3113.

3. Du R. et al. The sensable city: A survey on the deployment and management for smart city monitoring //IEEE Communications Surveys & Tutorials. - 2018. -Т. 21. - №. 2. - С. 1533-1560.

4. Marin-Perianu M. et al. Decentralized enterprise systems: a multiplatform wireless sensor network approach //IEEE Wireless Communications. - 2007. - Т. 14. - №. 6. - С. 57-66.

5. Yao H., Qin R., Chen X. Unmanned aerial vehicle for remote sensing applications-A review //Remote sensing. - 2019. - Т. 11. - №. 12. - С. 1443.

6. Popescu D. et al. A survey of collaborative UAV-WSN systems for efficient monitoring //Sensors. - 2019. - Т. 19. - №. 21. - С. 4690.

7. Kapadia S., Krishnamachari B. Comparative analysis of push-pull query strategies for wireless sensor networks //International Conference on Distributed Computing in Sensor Systems. - Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. - С. 185-201.

8. Puri A. A survey of unmanned aerial vehicles (UAV) for traffic surveillance //Department of computer science and engineering, University of South Florida. -2005. - С. 1-29.

9. Manfreda S. et al. On the use of unmanned aerial systems for environmental monitoring //Remote sensing. - 2018. - Т. 10. - №. 4. - С. 641.

10. Egbogah E. E., Fapojuwo A. O. A survey of system architecture requirements for health care-based wireless sensor networks //Sensors. - 2011. - Т. 11. - С. 48754898.

11. Truong V. T., Nayyar A., Lone S. A. System performance of wireless sensor network using LoRa-Zigbee hybrid communication //Computers, Materials & Continua. - 2021. - Т. 68. - №. 2. - С. 1615-1635.

12. Кучерявый А. Е. Летающие сенсорные сети / А. Е. Кучерявый, А. Г. Владыко,Р. В. Киричек, А. И. Парамонов, А. В. Прокопьев, И. А. Богданов, А. А. Дорт-Гольц //Электросвязь. - 2015. - № 9. - С. 2-5.

13. Orfanus D., Eliassen F., Freitas E. P. de Self-Organizing Relay Network Supporting Remotely Deployed Sensor Nodes in Military Operations. 6 th ICUMT, Proceedings, 6-8October, St.Petersburg, Russia.

14. Bekmezci I., Sahingoz О. K., TemelS. Flying Ad-Hoc Networks: A Survey. AdHoc Networks, Elsevier, v. 11, issue 3, May 2013.

15. Маткурбанов Т. А. Датчики движения беспроводной сенсорной сети и их энергопотребления [Текст]// XV Всероссийская научно-практическая конференция молодых ученых «Россия молодая» 18-21 апреля 2023 г. Кемерово, Россия, 2021 г. - С, 021415.1- 021415.6

16. Ногин А. А. Основные элементы структурной архитектуры сенсорных узлов //Научный журнал. - 2018. - №. 5 (28). - С. 37-39.

17. Ida N. et al. Sensors, actuators, and their interfaces: a multidisciplinary introduction. - SciTech Publishing Inc, 2013. - №. 11040.

18. Маткурбанов Т. А. Классификация датчиков и актуаторов в беспроводных сенсорных сетях [Текст]// II Международной научно-практической Интернет-конференции. Информационные технологии в экономике: 22-23 марта 2023 г.- Луганск, Россия, 2023. - С. 63.

19. Anastasi G. et al. Energy conservation in wireless sensor networks: A survey //Ad hoc networks. - 2009. - Т. 7. - №. 3. - С. 537-568.

20. Amutha J., Sharma S., Nagar J. WSN strategies based on sensors, deployment, sensing models, coverage and energy efficiency: Review, approaches and open issues //Wireless Personal Communications. - 2020. - Т. 111. - №. 2. - С. 10891115.

21. Маткурбанов Т. А. Анализ энергопотребления беспроводной сенсорной сети на базе стандарта zigbee [Текст]// XXV Всероссийская с международным участием научно-техническая конференция «проблемы социального и научно-технического развития в современном мире» 21-22 апреля 2023 года. Рубцовск, Россия, 2023. - С.189-194

22. Галкин П. В. Анализ энергопотребления узлов беспроводных сенсорных сетей //ScienceRise. - 2014. - Т. 2. - №. 2. - С. 55-61.

23. M. Adil, R. Khan, J. Ali, B. -H. Roh, Q. T. H. Ta and M. A. Almaiah, "An Energy Proficient Load Balancing Routing Scheme for Wireless Sensor Networks to Maximize Their Lifespan in an Operational Environment," in IEEE Access, vol. 8, pp. 163209-163224, 2020, doi: 10.1109/ACCESS.2020.3020310

24. Boukerche A., Sun P. Connectivity and coverage based protocols for wireless sensor networks //Ad Hoc Networks. - 2018. - Т. 80. - С. 54-69.

25. U.K.Matyokubov, D.A.Davronbckov, T.A.Matqurbanov Development of Efficient PON Architecture Models for Small Areas [Текст]// IX Международной конференции "Знания Онтологии - Теории" (30HT-2023), г. Новосибирске, Россия, 2-6 октября 2023 года. С.356-364.

26. Kumari S., Tyagi A. K. Wireless sensor networks: An introduction //Digital Twin and Blockchain for Smart Cities. - 2024. - С. 495-528.

27. F. Wang and J. Liu, "Networked Wireless Sensor Data Collection: Issues, Challenges, and Approaches," in IEEE Communications Surveys & Tutorials, vol.

13, no. 4, pp. 673-687, Fourth Quarter 2011, doi: 10.1109/SURV.2011.060710.00066

28. Liu K., Zheng J. UAV trajectory optimization for time-constrained data collection in UAV-enabled environmental monitoring systems //IEEE Internet of Things Journal. - 2022. - T. 9. - №. 23. - C. 24300-24314.

29. D. A. Davronbekov, U. K. Matyokubov and T. A. Matqurbanov, "Analytical Expressions and Model of Optical Communication Network Reliability Index Estimation," 2022 International Conference on Information Science and Communications Technologies (ICISCT), Tashkent, Uzbekistan, 2022, pp. 1-6, doi: 10.1109/ICISCT55600.2022.10146912.

30. Yuan Z. et al. Ultra-reliable IoT communications with UAVs: A swarm use case //IEEE Communications Magazine. - 2018. - T. 56. - №. 12. - C. 90-96.

31. J. Poorvi, A. Kalita and M. Gurusamy, "Reliable and Efficient Data Collection in UAV based IoT Networks," in IEEE Communications Surveys & Tutorials, doi: 10.1109/C0MST.2025.3550274

32. Popescu D. et al. A collaborative UAV-WSN network for monitoring large areas //Sensors. - 2018. - T. 18. - №. 12. - C. 4202.

33. Popescu D. et al. A survey of collaborative UAV-WSN systems for efficient monitoring //Sensors. - 2019. - T. 19. - №. 21. - C. 4690.

34. Matin M. A., Islam M. M. Overview of wireless sensor network //Wireless sensor networks-technology and protocols. - IntechOpen, 2012.

35. Akyildiz, I.F. et al. "Wireless Sensor Networks for Precision Agriculture", Computer Networks, 2002.

36. J. Xie, L. R. G. Carrillo and L. Jin, "An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems," in IEEE Control Systems Letters, vol. 3, no. 1, pp. 67-72, Jan. 2019, doi: 10.1109/LCSYS.2018.2851661.

37. Beard R. W., McLain T. W. Small unmanned aircraft: Theory and practice. -Princeton university press, 2012.

38. Gao N. et al. Energy model for UAV communications: Experimental validation and model generalization //China Communications. - 2021. - T. 18. - №. 7. - C. 253-264.

39. Zeng Y., Zhang R. Energy-efficient UAV communication with trajectory optimization //IEEE Transactions on wireless communications. - 2017. - T. 16. -№. 6. - C. 3747-3760.

40. Nguyen M. T. et al. Uav-assisted data collection in wireless sensor networks: A comprehensive survey //Electronics. - 2021. - T. 10. - №. 21. - C. 2603.

41. Monwar M., Semiari O., Saad W. Optimized path planning for inspection by unmanned aerial vehicles swarm with energy constraints //2018 IEEE Global Communications Conference (GLOBECOM). - IEEE, 2018. - C. 1-6.

42. Nan Y, Chen S L, Yan H. A common numerical calculation method of optimizing the trajectory of space vehicles (in Chinese). Flight Dyn, 1996, 14(3): 20-26.

43. Chen C, Guan C Q, Shi H L. Survey of numerical methods of direct aircraft trajectory optimization (in Chinese). Contl Technol Tactical Miss, 2009, 31(2): 3340.

44. Yong E M, Chen L, Tang G J. A survey of numerical for trajectory optimization of spacecraft (in Chinese). J Astronaut, 2008, 29(2): 397-406.

45. Majeed A., Hwang S. O. A multi-objective coverage path planning algorithm for UAVs to cover spatially distributed regions in urban environments //Aerospace.

- 2021. - Т. 8. - №. 11. - С. 343.

46. Li K. et al. Many-objective optimization based path planning of multiple UAVs in oilfield inspection //Applied Intelligence. - 2022. - Т. 52. - №. 11. - С. 12668-12683.

47. Guven L, Yanmaz E. Multi-objective path planning for multi-UAV connectivity and area coverage //Ad Hoc Networks. - 2024. - Т. 160. - С. 103520.

48. Aggarwal S., Kumar N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges //Computer communications. - 2020.

- Т. 149. - С. 270-299.

49. Марков А. В., Симаньков В. И. Методика расчета траекторий полета беспилотных летательных аппаратов для наблюдения за местностью //Доклады Белорусского государственного университета информатики и радиоэлектроники. - 2019. - №. 4 (122). - С. 57-63.

50. Родионов А. С., Маткурбанов Т. А. Планирование траектории полета БПЛА при мониторинге большой области //Информатика и автоматизация. -2025. - Т. 24. - №. 3. - С. 791-827. https://doi.org/10.15622/ia.24.3.3

51. Gutin G., Punnen A. P. (ed.). The traveling salesman problem and its variations. - Springer Science & Business Media, 2006. - Т. 12.

52. Debnath D. et al. A Review of UAV Path-Planning Algorithms and Obstacle Avoidance Methods for Remote Sensing Applications //Remote Sensing. - 2024. -Т. 16. - №. 21. - С. 4019.

53. Ait Saadi A. et al. UAV path planning using optimization approaches: A survey //Archives of Computational Methods in Engineering. - 2022. - Т. 29. - №. 6. - С. 4233-4284.

54. Маткурбанов Т.А. Анализ алгоритмов по задаче поиска оптимальных путей в графе [Текст]// Всероссийской студенческой научно-практической конференции «Математические модели техники, технологий и экономики» Санкт-Петербург, Россия 15 мая 2024 г. C. 106-112.

55. Ab Wahab M. N., Nefti-Meziani S., Atyabi A. A comparative review on mobile robot path planning: Classical or meta-heuristic methods? //Annual Reviews in Control. - 2020. - Т. 50. - С. 233-252.

56. Abdulsaheb J. A., Kadhim D. J. Classical and heuristic approaches for mobile robot path planning: A survey //Robotics. - 2023. - Т. 12. - №. 4. - С. 93.

57. Mannan A. et al. Classical versus reinforcement learning algorithms for unmanned aerial vehicle network communication and coverage path planning: A systematic literature review //International Journal of Communication Systems. -2023. - Т. 36. - №. 5.

58. Khoufi I., Laouiti A., Adjih C. A survey of recent extended variants of the traveling salesman and vehicle routing problems for unmanned aerial vehicles //Drones. - 2019. - Т. 3. - №. 3. - С. 66.

59. Жук А. А., Булойчик В. М., Акулич С. В. Планирование оптимального маршрута движения беспилотного летательного аппарата по критерию минимума общего расхода топлива //Системный анализ и прикладная информатика. - 2022. - №. 3. - С. 43-49.

60. Kizilate§ G., Nuriyeva F. On the nearest neighbor algorithms for the traveling salesman problem //Advances in Computational Science, Engineering and Information Technology: Proceedings of the Third International Conference on Computational Science, Engineering and Information Technology (CCSEIT-2013), KTO Karatay University, June 7-9, 2013, Konya, Turkey-Volume 1. - Springer International Publishing, 2013. - С. 111-118.

61. Goutham M. et al. A convex hull cheapest insertion heuristic for the non-euclidean tsp //arXiv preprint arXiv:2302.06582. - 2023.

62. Rosenkrantz D. J., Stearns R. E., Lewis, II P. M. An analysis of several heuristics for the traveling salesman problem //SIAM journal on computing. - 1977. - Т. 6. - №. 3. - С. 563-581.

63. Voudouris C., Tsang E. Guided local search and its application to the traveling salesman problem //European journal of operational research. - 1999. - Т. 113. -№. 2. - С. 469-499.

64. Родионов А.С., Маткурбанов Т. А., Кхаируллаев У. Б. Оптимизация траектории полета БПЛА для мониторинга сельскохозяйственных земель //Проблемы информатики, 2025, № 1, с.5-17. DOI: 10.24412/2073-0667-2025-15-17. - EDN: XFUXBA

65. Welzl E. Smallest enclosing disks (balls and ellipsoids) //New Results and New Trends in Computer Science: Graz, Austria, June 20-21, 1991 Proceedings. -Berlin, Heidelberg : Springer Berlin Heidelberg, 2005. - С. 359-370.

66. Markov, A. V., & Simankov, V. I. (2019). A methodology for calculating UAV flight trajectories for area observation. Reports of the Belarusian State University of Informatics and Radioelectronics, No. 4 (122), 57-63.

67. Dasdan, A. (2025). The Kernighan-Lin Search Algorithm. arXiv preprint, arXiv:2502.00316.

68. Stefas N., Plonski P. A., Isler V. Approximation algorithms for tours of orientation-varying view cones //The International Journal of Robotics Research. -2020. - Т. 39. - №. 4. - С. 389-401.

69. D. -S. Jang, H. -J. Chae and H. -L. Choi, "Optimal control-based UAV path planning with dynamically-constrained TSP with neighborhoods," 2017 17th International Conference on Control, Automation and Systems (ICCAS), Jeju, Korea (South), 2017, pp. 373-378, doi: 10.23919/ICCAS.2017.8204468.

70. G. I. Boutselis, Z. Wang and E. A. Theodorou, "Constrained Sampling-based Trajectory Optimization using Stochastic Approximation," 2020 IEEE International Conference on Robotics and Automation (ICRA), Paris, France, 2020, pp. 25222528, doi: 10.1109/ICRA40945.2020.9197284.

71. S. Krishnan, M. Nemati, S. W. Loke, J. Park and J. Choi, "Energy-Efficient UAV-Assisted IoT Data Collection via TSP-Based Solution Space Reduction," GLOBECOM 2023 - 2023 IEEE Global Communications Conference, Kuala Lumpur, Malaysia, 2023, pp. 6189-6194, doi: 10.1109/GL0BEC0M54140.2023.10437381

72. Xiao B. et al. Algorithms for disk covering problems with the most points //Proc. IASTED Int'l Conf. Parallel and Distributed Computing and Systems. -2003. - С. 541-546.

Публикации автора по теме диссертации

SCOPUS

1. G'ayratovich Samandarov. B., Alimboevich Matkurbanov. T., Rustamovna Yangibayeva. M. Developing methods of allocation resource in the servers of IMS subsystem //International Journal of Innovative Technology and Exploring Engineering. - 2019. - Т. 9. - №. 1. - С. 4606-4609. https://www.ijitee.org/wp-content/uploads/papers/v9i1/L31271081219.pdf

2. D. A. Davronbekov, U. K. Matyokubov and T. A. Matqurbanov, "Analytical Expressions and Model of Optical Communication Network Reliability Index Estimation," 2022 International Conference on Information Science and Communications Technologies (ICISCT), Tashkent, Uzbekistan, 2022, pp. 1-6, doi: 10.1109/ICISCT55600.2022.10146912.

3. Rodionov A. S., Matkurbanov T. A., Yagibayeva M. R. Application of a Genetic Algorithm in Planning the Optimal Route of Unmanned Aerial Vehicles Used for Large Area Monitoring //2023 IEEE XVI International Scientific and Technical Conference Actual Problems of Electronic Instrument Engineering (APEIE). - IEEE, 2023. - С. 1560-1564. DOI: 10.1109/APEIE59731.2023.10347781

4. Родионов А. С., Маткурбанов Т. А. Планирование траектории полета БПЛА при мониторинге большой области //Информатика и автоматизация. -2025. - Т. 24. - №. 3. - С. 791-827. https://doi.org/10.15622/ia.24.3.3

5. Tulkin Matkurbanov, Akhmet Utegenov, Mengliyev Davlatyor, Dilshod Matkurbonov. Advanced Trajectory Planning for Unmanned Aerial Vehicles in the Context of Data Collection from Spatially Distributed Wireless Sensor Networks// CYBERNETICS AND INFORMATION TECHNOLOGIES, 2025, Volume 25, No 3. - С. 186-208. DOI: 10.2478/cait-2025-0029

6. T. Matkurbanov, A. Rodionov and D. Mengliev, "UAV Trajectory Planning for Efficient Data Collection in Large-Scale Monitoring," 2025 21st International Asian School-Seminar on Optimization Problems of Complex Systems (OPCS), Novosibirsk, Russian Federation, 2025, pp. 1-5, doi: 10.1109/OPCS67346.2025.11219373.

7. T. Matkurbanov, A. Khayrullaev and T. Delov, "Advanced Route Planning for Effective Data Acquisition in Distributed Sensor Networks for Environmental Monitoring," 2025 IEEEXVIIInternational Scientific and Technical Conference on Actual Problems of Electronic Instrument Engineering (APEIE), Novosibirsk, Russian Federation, 2025, pp. 1-6, doi: 10.1109/APEIE66761.2025.11289306. Список ВАК

8. Родионов А.С., Маткурбанов Т. А., Кхаируллаев У. Б. Оптимизация траектории полета БПЛА для мониторинга сельскохозяйственных земель //Проблемы информатики, 2025, № 1, с.5-17. DOI: 10.24412/2073-0667-2025-15-17. - EDN: XFUXBA

9. Маткурбанов Т. А. Фундаментальная роль кластеризации в организации эффективного мониторинга обширных пространств // Современная наука: актуальные проблемы теории и практики. Серия: Естественные и Технические Науки. -2025. -№06/3. -С. 116-123 DOI 10.37882/2223-2966.2025.06-3.22 РИНЦ

10. Т.А.Маткурбанов, К.С.Хайитбаев, Архитектура на основе интернета вещей для анализа энергетических объектов [текст]// Всероссийской научно-технической конференции //Наука. Технология. Производство - 2021, Салават, Россия, 23 апреля 2021 г.— С. 63. (https://slv.rusoil.net/b/files/images/nauka/NTP2021-sbornik30.04.2021.pdf)

11. Маткурбанов Т. А. Классификация датчиков и актуаторов в беспроводных сенсорных сетях [Текст]// II Международной научно-практической Интернет-конференции. Информационные технологии в экономике: Луганск, Россия, 22-23 марта 2023 г.— С. 207-212. (https://ecps.turbo.site/collections)

12. Маткурбанов Т. А. Датчики движения беспроводной сенсорной сети и их энергопотребления [Текст]// XV Всероссийская научно-практическая конференция молодых ученых «Россия молодая» Кемерово, Россия, 18-21 апреля 2023 г.- С, 021415.1- 021415.6 (https://elibrary.ru/bvbtbe)

13. Маткурбанов Т. А. Анализ энергопотребления беспроводной сенсорной сети на базе стандарта zigbee [Текст]// XXV Всероссийская с международным участием научно-техническая конференция «Проблемы социального и научно-технического развития в современном мире» Рубцовск, Россия, 21-22 апреля 2023 года.- С.189-194 (www.rubinst.ru/sites/default/files/files/science/conference_materials/stud_conf-23.pdf)

14. U.K.Matyokubov, D.A.Davronbekov, T.A.Matqurbanov Development of Efficient PON Architecture Models for Small Areas [Текст]// IX Международной конференции "Знания Онтологии - Теории" (30HT-2023), г. Новосибирске, Россия, 2-6 октября 2023 года. С.356-364. (https://elibrary.ru/mszoxm)

15. Маткурбанов Т. А. Математические основание экологического мониторинга больших территорий на основе современных технологий [Текст]// III Всероссийской научно-практической конференции «Энергетика, управление и автоматизация: инновационные решения проблем» / Санкт-Петербург, Рассия, 22 декабря 2023 года. С.301-309. (https://elibrary.ru/item.asp?id=65583945)

16. Маткурбанов Т.А. Анализ существующих подходов к решению задачи коммивояжера// III Международной научно-практической конференции. Теоретические и прикладные аспекты естественно-научного образования в эпоху цифровизации - Брянск, Россия, 11-12 апреля 2024 г.-с.140-144. (https://elibrary.ru/item.asp?id=65670032)

17. Маткурбанов Т.А. Анализ алгоритмов по задаче поиска оптимальных путей в графе [Текст]// Всероссийской студенческой научно-практической конференции «Математические модели техники, технологий и экономики» Санкт-Петербург, Россия, 15 мая 2024 г. C. 106-112. (https://elibrary.ru/item.asp?id=68519522)

18. Маткурбанов Т.А. Анализ траектории мониторинга больших территорий в зависимости от метода кластеризации [Текст]// II Международной научно-практической конференции «Молодёжная наука севера» Санкт-Петербург, Россия, 12-13 декабря 2024 г. C. 15-23. (https://elibrary.ru/item.asp?id=82389952)

19. Маткурбанов Т.А. Построение траектории полета БПЛА для мониторинга сельскохозяйственных земель [Текст] // Материалы 63-й Международной научной студенческой конференции (МНСК-2025). -Новосибирск: Издательско-полиграфический центр НГУ, 2025. - С. 232-233. - ISBN 978-5-4437-1797-5. - DOI: 10.25205/978-5-4437-1797-5.

Список рисунков

Рисунок 1 Блок-схема последовательности выполнения операций в автоматизированной системе мониторинга 10

Рисунок 2 Архитектура сенсорной сети 12

Рисунок 3 Структура беспроводной сенсорной сети 13

Рисунок 4 Типовая архитектура сенсорного узла 13

Рисунок 5 Пример наличия точек между окрестностями 28

Рисунок 6 Классификация подходов планирования пути 31

Рисунок 7 Схема алгоритма работы программы маршрутизации полетов БПЛА по произвольно выбранным точкам. 34

Рисунок 8 Построение маршрутов было выполнено с использованием 10 случайно выбранных точек и трёх различных алгоритмов: ближайшего соседа, оптимальной вставки и двухшагового перехода. 36

Рисунок 9 Построение маршрута с использованием 3 методов TSP на основе 100 случайно выбранных точек на площади 400 х 300. 36

Рисунок 10 Сравнение маршрутов, построенных по различным алгоритмам решения задачи коммивояжёра 37

Рисунок 11 График зависимости расчета общей длины траектории от количества точек программ а), график времени расчета эффективной траектории для каждой точки для программ б), созданных с использованием 3 алгоритмов: ближайшего соседа, оптимальной вставки 38

Рисунок 12 Сравнительный анализ траекторий, построенных по различным алгоритмам при радиусе покрытия г = 10 39

Рисунок 13 График зависимости изменения величины радиуса покрытия программ на основе трех алгоритмов для статической стратегии от длины траектории и времени расчета алгоритмов 39

Рисунок 14. Траектории движения БПЛА, построенные на основе динамической стратегии при радиусе радиопокрытия г = 10 40

Рисунок 15. Сравнительный анализ характеристик трёх алгоритмов в рамках динамической стратегии 40

Рисунок 16. Изображение траектории полета беспилотного летательного аппарата с определенным радиусом действия 42

Рисунок 17. Алгоритм поиска эффективного маршрута на основе метода центроида 44

Рисунок 18. Алгоритм поиска эффективного маршрута на основе трехточечного метода 45

Рисунок 19. Полное покрытия всех точек при заданном радиусе покрытия 10 единиц по методу центроида 47

Рисунок 20 Полное покрытия всех точек при заданном радиусе покрытия 20 единиц по методу центроида 47

Рисунок 21 Польное покрытиявсех точек при заданном радиусе покрытия 30 единиц по методу центроида 47

Рисунок 22 Полное покрытие всех точек при заданном радиусе покрытия 10 условных единиц с использованием трехточечного метода. 48

Рисунок 23 Полное покрытие всех точек при заданном радиусе покрытия 20 условных единиц с использованием трехточечного метода 48

Рисунок 24 Полное покрытие всех точек при заданном радиусе покрытия 30 условных единиц, реализованное с использованием трёхточечного метода 48

Рисунок 25 Полное покрытие всех сенсорных точек при радиусе охвата 10 условных единиц, реализованное с использованием тангенциального метода 49

Рисунок 26 Полное покрытие всех сенсорных точек при радиусе охвата 20 условных единиц, реализованное с использованием тангенциального метода 49

Рисунок 27 Полное покрытие всех сенсорных точек при радиусе охвата 30 условных единиц, реализованное с использованием тангенциального метода 50

Рисунок 28 Полное покрытие всех точек датчика при условном радиусе покрытия 10 единиц, иллюстрация реализации с использованием метода окрестного выбора. 50

Рисунок 29 Полное покрытие всех сенсорных точек при радиусе охвата 20 условных единиц, полученное с использованием метода окрестного выбора точек на границе зоны покрытия 51

Рисунок 30 Полное покрытие всех сенсорных точек при радиусе охвата 30 условных единиц, полученное с использованием метода окрестного выбора точек на границе зоны покрытия. 51

Рисунок 31 Полное покрытие всех точек при заданном радиусе покрытия 10 условных единиц было реализовано с использованием метода жадного покрытия 52

Рисунок 32 Полное покрытие всех точек при заданном радиусе покрытия 20 условных единиц было реализовано с использованием метода жадного покрытия 52

Рисунок 33 Полное покрытие всех точек при заданном радиусе покрытия 30 условных единиц было реализовано с использованием метода жадного покрытия. 53

Рисунок 34 График зависимости длины пути от радиуса покрытия, построенный на основе результатов моделирования алгоритмов, разработанных на основе каждого из четырех методов, 53

Рисунок 35 График зависимости времени расчета от радиуса покрытия программ, разработанных на основе четырех методов. 54

Рисунок 36 График зависимости точек маневра от радиуса покрытия по результатам программ, разработанных на основе четырех методов. 54

Рисунок 37 Первичная форма графического пользовательского интерфейса в составе программного комплекса 59

Рисунок 38 Элемент интерфейса программного комплекса для ввода координат датчиков (точек). 60

Рисунок 39 Элемент интерфейса программного комплекса для выбора алгоритма 61

Рисунок 40 Представление траектории, сформированной на основе выбранного алгоритма, в графическом пользовательском интерфейсе программного комплекса 62

Рисунок 41 Графическое представление траектории и маршрута, сформированных на основе выбранного алгоритма, в графическом пользовательском интерфейсе программного комплекса) 62

Рисунок 42 Раздел сохранения данных в графическом пользовательском интерфейсе программного комплекса 63

Рисунок 43 Первоначальный вид графического пользовательского интерфейса программного комплекса, реализующего алгоритмы планирования траектории полёта радиоуправляемого БПЛА для мониторинга больших территорий 65

Список таблиц

1. Анализ методов установки датчиков............................................33

2. Характерные примеры размещения сенсоров в различных сценариях мониторинга..................................................................................35

3. Сравнение сложности алгоритмов двухшагового перехода, ближайшего соседа и оптимальной вставки...........................................................46

4. Сравнение методов друг с другом...............................................68

Приложении 1.

main.spec.

a = Analysis( ['main.py'], pathex=[], binaries=[],

datas=[('tsp_algorithms.py', '.')],

hiddenimports=[],

hookspath=[],

hooksconfig={},

runtime_hooks=[],

excludes=[],

noarchive=False,

optimize=0,

)

pyz = PYZ(a.pure) exe = EXE(

py^

a.scripts, a.binaries, a.datas, [],

name='main', debug=False,

bootloader_ignore_signals=False,

strip=False,

upx=True,

upx_exclude=[],

runtime_tmpdir=None,

console=False,

disable_windowed_traceback=False,

argv_emulation=False,

target_arch=None,

codesign_identity=None,

entitlements_file=None,

)

main.py:

import sys

import matplotlib.pyplot as plt

from matplotlib.backends.backend_qt5agg import FigureCanvasQTAgg as FigureCanvas from matplotlib.figure import Figure from PyQt5.QtWidgets import (

QApplication, QMainWindow, QWidget, QVBoxLayout, QHBoxLayout, QPushButton, QLineEdit, QLabel, QFileDialog, QComboBox, QTextEdit

)

from PyQt5.QtCore import Qt import os

from tsp_algorithms import nearest_neighbor, optimal_insertion, two_step_insertion from matplotlib.image import imread class TSPGui(QMainWindow):

def_init_(self):

super()._init__()

self.setWindowTitle("Поиск кратчайшего маршрута") self. setGeometry( 100, 100, 1300, 700) self.points = [] self.route = []

self.bg_path = "background.png" self.start_point = None self.start_point_index = None self.initUI() def initUI(self):

central_widget = QWidget()

self.setCentralWidget(central_widget)

main_layout = QVBoxLayout(central_widget)

self.coord_input = QTextEdit()

self.coord_input.setFixedHeight(60)

self.start_x = QLineEdit()

self.start_y = QLineEdit()

self.start_x.setPlaceholderText("X")

self.start_y.setPlaceholderText("Y)

self. start_x. setFixedWidth(60)

self. start_y. setFixedWidth(60)

self.algorithm_box = QComboBox()

self.algorithm_box.addItems(["Ближайший сосед", "Оптимальная вставка", "Двушаговой переход"])

self.length_label = QLabel(" Длина маршрута: -")

self.route_label = QLabel("Маршрут: -")

self.route_label.setWordWrap(True)

button_layout = QHBoxLayout()

btn_coords = QPushButton("Точки")

btn_coords.clicked.connect(self.load_coords)

btn_start = QPushButton("Начальная точка")

btn_start.clicked.connect(self.set_start_point)

btn_algo = QPushButton(" Алгоритм")

btn_build = QPushButton("Построить")

btn_build.clicked.connect(self.build_route)

btn_length = QPushButton(" Длина")

btn_length.clicked.connect(self.show_length)

btn_route = QPushButton("Маршрут")

btn_route.clicked. connect(self. show_route)

btn_save = QPushButton("Сохранить")

btn_save.clicked.connect(self.save_data)

button_layout.addWidget(btn_coords)

button_layout.addWidget(btn_start)

button_layout.addWidget(btn_algo)

button_layout.addWidget(btn_build)

button_layout.addWidget(btn_length)

button_layout.addWidget(btn_route)

button_layout.addWidget(btn_save)

main_layout.addLayout(button_layout)

input_layout = QHBoxLayout()

left_col = QVBoxLayout()

left_col.addWidget(QLabel("Введите координаты (x, y):")) left_col.addWidget(self. coord_input) middle_col = QVBoxLayout()

middle_col.addWidget(QLabel("Начальная точка (X,Y):"))

row = QHBoxLayout()

row.addWidget(self.start_x)

row.addWidget(self.start_y)

middle_col.addLayout(row)

right_col = QVBoxLayout()

right_col.addWidget(self.algorithm_box)

input_layout.addLayout(left_col)

input_layout.addLayout(middle_col)

input_layout.addLayout(right_col)

main_layout.addLayout(input_layout)

graph_layout = QHBoxLayout()

self.figl = Figure(figsize=(5, 4))

self.axl = self.fig1.add_subplot(111)

self.canvasl = FigureCanvas(self.fig1)

self.fig2 = Figure(figsize=(5, 4))

self.ax2 = self.fig2.add_subplot(111)

self.canvas2 = FigureCanvas(self.fig2)

graph_layout.addWidget(self.canvas1)

graph_layout.addWidget(self.canvas2)

main_layout.addLayout(graph_layout) main_layout.addWidget(self. length_label) main_layout.addWidget(self. route_label) self.canvas1.mpl_connect("button_press_event", self.on_click) def on_click(self, event): if event.xdata and event.ydata: clicked = (int(event.xdata), int(event.ydata)) for i, pt in enumerate(self.points):

if abs(pt[0] - clicked[0]) < 5 and abs(pt[1] - clicked[1]) < 5: del self.points[i] self.update_coord_field() self.redraw() return

self.points.append(clicked) self.update_coord_field() self.redraw() def update_coord_field(self): lines = []

for idx, (x, y) in enumerate(self.points):

lines.append(f"{idx}: {x}, {y}") self.coord_input.setPlainText("\n".join(lines)) def load_coords(self) : text = self.coord_input.toPlainText().strip().splitlines() self.points = [] for line in text: if ':' in line: idx_and_coords = line.split(":", 1) coords = idx_and_coords[1] else:

coords = line parts = coords.split(",") if len(parts) == 2: try:

x = int(parts[0].strip()) y = int(parts[1].strip()) self.points.append((x, y)) except: pass self.redraw() def set_start_point(self): try:

x0, y0 = int(self.start_x.text()), int(self.start_y.text()) self.start_point = (x0, y0)

self.start_point_index = self.points.index(self.start_point) self.redraw() except: pass def redraw(self): self.ax1.clear()

if os.path.exists(self.bg_path): bg = imread(self.bg_path) self.ax1.imshow(bg, extent=[0, 400, 0, 300]) for idx, (x, y) in enumerate(self. points): color = 'red'

if self.start_point and (x, y) == self.start_point:

color = 'black' self.ax1.scatter(x, y, c=color)

self.ax1.annotate(str(idx), (x, y), textcoords="offset points", xytext=(0, 10), ha='center', fontsize=8) self.canvas1 .draw() def build_route(self) : self.load_coords() if not self.points: return

start = 0 try:

x0, y0 = int(self.start_x.text()), int(self.start_y.text()) start = self.points.index((x0, y0)) except: pass

algo = self.algorithm_box.currentText() if algo == "Ближайший сосед":

self.route = nearest_neighbor(self.points, start) elif algo == "Оптимальная вставка":

self.route = optimal_insertion(self.points, start) else:

self.route = two_step_insertion(self.points, start) self.redraw_route() def redraw_route(self): self.ax2.clear()

if os.path.exists(self.bg_path): bg = imread(self.bg_path) self.ax2.imshow(bg, extent=[0, 400, 0, 300]) if not self.route: return

xs = [self.points[i][0] for i in self.route + [self.route[0]]] ys = [self.points[i][1] for i in self.route + [self.route[0]]] self.ax2.plot(xs, ys, marker='o', color='blue') for idx in self.route: x, y = self.points[idx]

self.ax2.annotate(f"{idx} ({x},{y})", (x, y), textcoords="offset points", xytext=(0, 10), ha='center', fontsize=8)

self.canvas2.draw() def show_length(self): if not self.route:

return total = 0

for i in range(len(self.route)): p1 = self.points[self.route[i]] p2 = self.points[self.route[(i + 1) % len(self.route)]] total += ((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)**0.5 self.length_label.setText(f'Длина маршрута: {total:.2f}") def show_route(self): if not self.route:

return lines = []

for idx in self.route: x, y = self.points[idx] lines.append(f"{idx} ({x},{y})") self.route_label.setText("Маршрут: \n" + " ^ ".join(lines)) def save_data(self): if not self.route: return

fname, _ = QFileDialog.getSaveFileName(self, "Сохранить маршрут", "", "PNG (*.png);;TXT (*.txt);;Excel (*.xlsx)")

if fname.endswith(".png"): self.fig2. savefig(fname) elif fname.endswith(".txt"): with open(fname, "w", encoding="utf-8") as f: for i in self.route: x, y = self.points[i] f.write(f"{i}: ({x}, {y})\n") elif fname.endswith(".xlsx"): import pandas as pd

df = pd.DataFrame([(i, *self.points[i]) for i in self.route], columns=["Index", "X", "Y"]) df.to_excel(fname, index=False) if name == " main ":

app = QApplication(sys.argv) window = TSPGui() window.show() sys.exit(app.exec_())

tsp_algorithms.py:

def nearest_neighbor(points, start=0): unvisited = set(range(len(points))) route = [start] unvisited.remove(start) while unvisited: last = route[-1]

next_city = min(unvisited, key=lambda i: (points[i][0] - points[last][0]) ** 2 + (points[i][1] - points[last][1]) **

2)

route.append(next_city) unvisited.remove(next_city) return route def optimal_insertion(points, start=0): if len(points) < 3:

return list(range(len(points))) route = [start]

unvisited = set(range(len(points))) - {start}

next_city = min(unvisited, key=lambda i: (points[i][0] - points[start][0]) ** 2 + (points[i][1] - points[start][1]) **

2)

route.append(next_city) unvisited.remove(next_city) while unvisited: best_increase = float('inf) best_pos = None best_city = None for city in unvisited:

for i in range(len(route)): p1 = points[route[i]] p2 = points[route[(i + 1) % len(route)]]

increase = dist(p1, points[city]) + dist(points[city], p2) - dist(p1, p2) if increase < best_increase: best_increase = increase best_pos = i + 1 best_city = city route.insert(best_pos, best_city) unvisited.remove(best_city) return route def two_step_insertion(points, start=0): route = [start]

unvisited = set(range(len(points))) - {start} while unvisited:

best_city = min(unvisited, key=lambda i: min((points[i][0] - points[j][0]) ** 2 + (points[i][1] - points[j][1]) ** 2 for j in route))

route.append(best_city) unvisited.remove(best_city) return route def dist(p1, p2): return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5

backgrounding

Приложении 2.

main.spec

a = Analysis( ['main.py'], pathex=[], binaries=[],

datas=[('centroid_algorithm.py', '.'), ('three_points_algorithm.py', '.'), ('tsp_algorithm.py', '.'), Cbackground.png',

hiddenimports=[],

hookspath=[],

hooksconfig={},

runtime_hooks=[],

excludes=[],

noarchive=False,

optimize=0,

)

pyz = PYZ(a.pure) exe = EXE(

pyz,

a.scripts, a.binaries, a.datas, [],

name='main', debug=False,

bootloader_ignore_signals=False,

strip=False,

upx=True,

upx_exclude=[],

runtime_tmpdir=None,

console=False,

disable_windowed_traceback=False,

argv_emulation=False,

target_arch=None,

codesign_identity=None,

entitlements_file=None,

)

main.py

import sys import os

import numpy as np import pandas as pd import matplotlib.pyplot as plt

from PyQt5.QtWidgets import (QApplication, QMainWindow, QWidget, QVBoxLayout, QHBoxLayout, QPushButton, QLineEdit, QLabel, QFileDialog, QComboBox, QTextEdit) from PyQt5.QtCore import Qt

from matplotlib.backends.backend_qt5agg import FigureCanvasQTAgg as FigureCanvas

from matplotlib.figure import Figure

from matplotlib.image import imread

from tsp_algorithm import optimal_insertion

from centroid_algorithm import run_centroid_algorithm

from three_points_algorithm import run_three_points_algorithm

class TSPNGUI(QMainWindow):

def_init_(self):

super()._init__()

self.setWindowTitle("Формирование траектории покрытия точек поля на основе радиуса покрытия") self. setGeometry( 100, 100, 1200, 700) self.points = []

self.bg_path = "backgrounding" self.initUI() def initUI(self): central = QWidget() self. setCentralWidget(central) main_layout = QVBoxLayout(central) menu_layout = QHBoxLayout() self.coord_input = QTextEdit() self.coord_input.setFixedHeight(60)

self.coord_input.textChanged.connect(self.on_text_input_changed)

self.start_x = QLineEdit("0")

self.start_x.setFixedWidth(50)

self.start_y = QLineEdit("0")

self. start_y. setFixedWidth(50)

self.radius_input = QLineEdit("10")

self.radius_input.setFixedWidth(50)

self.algorithm_box = QComboBox()

self.algorithm_box.addItems(["TSP", "Сентроид", "Триточки"]) build_btn = QPushButton("Построить") build_btn.clicked.connect(self.build_trajectory) save_btn = QPushButton("Сохранить") save_btn.clicked.connect(self.save_outputs) self.length_label = QLabel(" Длина: -") self.route_output = QTextEdit() self.route_output.setFixedHeight(60) menu_layout.addWidget(QLabel("Точки")) menu_layout.addWidget(self.coord_input) menu_layout.addWidget(QLabel("Начальная точка")) menu_layout.addWidget(self.start_x) menu_layout.addWidget(self. start_y) menu_layout.addWidget(QLabel(" Алгоритм")) menu_layout.addWidget(self.algorithm_box) menu_layout.addWidget(QLabel("Радиус")) menu_layout.addWidget(self.radius_input) menu_layout.addWidget(build_btn) menu_layout.addWidget(self.length_label) menu_layout.addWidget(QLabel("Маршрут")) menu_layout.addWidget(self.route_output) menu_layout.addWidget(save_btn) main_layout.addLayout(menu_layout) graph_layout = QHBoxLayout() self.fig1 = Figure(figsize=(5, 4)) self.ax1 = self.fig1.add_subplot(111) self.canvas1 = FigureCanvas(self.fig1) self.fig2 = Figure(figsize=(5, 4)) self.ax2 = self.fig2.add_subplot(111) self.canvas2 = FigureCanvas(self.fig2) graph_layout.addWidget(self.canvas1) graph_layout.addWidget(self.canvas2) main_layout.addLayout(graph_layout) self.canvas1.mpl_connect("button_press_event", self.on_click) self.redraw_points() self.redraw_empty_trajectory() def on_click(self, event): if event.xdata and event.ydata:

click_point = np.array([event.xdata, event.ydata]) for i, pt in enumerate(self.points):

if np.linalg.norm(click_point - np.array(pt)) < 10: # Она будет отключена, если поблизости находится 10 устройств.

del self.points[i]

self.update_coord_field()

self.redraw_points()

self.redraw_empty_trajectory()

return

# В противном случае добавляется новая точка. x, y = round(event.xdata), round(event.ydata) self.points.append((x, y)) self.update_coord_field()

self. redraw_points() self. redraw_empty_trajectory() def on_text_input_changed(self): self.load_points_from_input() self.redraw_points() self.redraw_empty_trajectory() def update_coord_field(self):

text = "\n".join(f"{i+1}: {x}, {y}" for i, (x, y) in enumerate(self.points)) self.coord_input.blockSignals(True) self.coord_input.setPlainText(text) self.coord_input.blockSignals(False) def load_points_from_input(self) : lines = self.coord_input.toPlainText().splitlines() self.points = [] for line in lines: try:

if ":" in line:

line = line.split(" :")[1].strip() x, y = map(float, line.split(",")) self.points.append((x, y)) except: continue def redraw_points(self): self.ax1.clear()

if os.path.exists(self.bg_path): bg = imread(self.bg_path) self.ax1.imshow(bg, extent=[0, 300, 0, 200]) if self.points: pts = np.array(self.points) self.ax1.scatter(pts[:, 0], pts[:, 1], c='red', s=8) for i, (x, y) in enumerate(self.points):

self.ax1.annotate(str(i + 1), (x, y), textcoords="offset points", xytext=(0, 8), ha='center') self.ax1.set_title("Точки") self.ax1.grid(True) self.ax1.axis("equal")

self.ax1.scatter(0, 0, color='black', s=100, label-Начальная точка') self.canvas1 .draw() def redraw_empty_trajectory(self):

# Нарисуется точки, выделенные красным цветом, на окне 2. self.ax2.clear()

if os.path.exists(self.bg_path): bg = imread(self.bg_path) self.ax2.imshow(bg, extent=[0, 300, 0, 200]) if self.points: pts = np.array(self.points)

self.ax2.scatter(pts[:, 0], pts[:, 1], c='red', s=6) for i, (x, y) in enumerate(self.points):

self.ax2.annotate(str(i + 1), (x, y), textcoords="offset points", xytext=(0, 6), ha='center') self.ax2.set_title("Траектория") self.ax2.grid(True) self.ax2.axis("equal") self.ax2.scatter(0, 0, color='black', s=100) self.canvas2.draw() def build_trajectory(self): self.load_points_from_input() if not self.points: print(" Nuqtalar yo'q") return try:

x0, y0 = float(self.start_x.text()), float(self.start_y.text()) except:

x0, y0 = 0, 0 try:

r = float(self.radius_input.text()) except: r = 10.0

points = [(x0, y0)] + self.points.copy() algo = self.algorithm_box.currentText().strip() рпй("Выбранный алгоритм:", repr(algo)) # 1-PRINT try:

if algo == "TSP": print("TSP выбрано ")

optimal_insertion(points, self.ax2, self.length_label, self.route_output) elif algo == "Сентроид": print(" Centroid tanlandi")

trajectory, length, route_str = run_centroid_algorithm(points, r) self.draw_trajectory(trajectory, r) self.length_label.setText(f" Длина: {length:.2f}") self.route_output.setPlainText(route_str) elif algo == "Триточки":

printe^raPHTM ТРОЙНОЙ ТОЧКИ ЗАПУЩЕН ") trajectory, length, route_str = run_three_points_algorithm(points, r)

printO^YHKU™ РАБОТАЕТ ") # 3-PRINT ( ,three_points_algorithm.py4 Если его там нет, то поместите его здесь.)

self.draw_trajectory(trajectory, r) self.length_label.setText(f" Длина: {length:.2f}") self.route_output.setPlainText(route_str)

except Exception as e: import traceback

print("ПРОИЗОШЛА ОШИБКА:\п", traceback.format_exc()) def draw_trajectory(self, traj_points, r): self.ax2.clear()

if os.path.exists(self.bg_path): bg = imread(self.bg_path) self.ax2.imshow(bg, extent=[0, 400, 0, 300])

# Точки в окне 1 рисуем также и в окне 2 (красным цветом) if self.points:

pts = np.array(self.points) self.ax2.scatter(pts[:, 0], pts[:, 1], c='red', s=10) for i, (x, y) in enumerate(self.points):

self.ax2.annotate(str(i + 1), (x, y), textcoords="offset points", xytext=(0, 7), ha='center')

# Маршрут (траектория) обозначен красным цветом.

traj_points = np.array(traj_points) if traj_points.size > 0:

x_min, x_max = traj_points[:, 0].min() - 20, traj_points[:, 0].max() + 20 y_min, y_max = traj_points[:, 1].min() - 20, traj_points[:, 1].max() + 20 self.ax2.set_xlim(x_min, x_max) self.ax2.set_ylim(y_min, y_max) self.ax2.plot(traj_points[:, 0], traj_points[:, 1], '-o', color='blue') self.draw_parallel_lines_on_canvas(self.ax2, traj_points, r) for pt in traj_points:

circle = plt.Circle(pt, r, color='orange', fill=False, linestyle='--') self. ax2. add_artist(circle) for i, pt in enumerate(traj_points):

self.ax2.annotate(str(i), pt, textcoords="offset points", xytext=(0, 10), ha='center') self.ax2.scatter(0, 0, color='black', s=100) self.ax2.grid(True) self.ax2.axis("equal") self.canvas2.draw() def draw_parallel_lines_on_canvas(self, ax, path, offset): for i in range(len(path) - 1): start = np.array(path[i]) end = np.array(path[i + 1]) vector = end - start norm = np.linalg.norm(vector) if norm == 0:

continue unit_vector = vector / norm

normal_vector = np.array([-unit_vector[1], unit_vector[0]]) for direction in [1, -1]:

new_start = start + direction * offset * normal_vector new_end = end + direction * offset * normal_vector ax.plot([new_start[0], new_end[0]], [new_start[1], new_end[1]], color='orange', linestyle='--', linewidth=1) def save_outputs(self): path, _ = QFileDialog.getSaveFileName(self, "Сохранить", "", "PNG Files (*.png)") if not path:

return self.fig2. savefig(path) txt_path = path.replace(".png", ".txt") xlsx_path = path.replace(".png", ".xlsx") with open(txt_path, "w") as f: for pt in self.points:

f.write(f"{pt[0]}, {pt[1]}\n") df = pd.DataFrame(self.points, columns=["X", "Y"]) df.to_excel(xlsx_path, index=False)

if_name_== "_main_":

app = QApplication(sys.argv) window = TSPNGUI() window.show() sys.exit(app.exec_()) # tsp_algorithm.py

def optimal_insertion(points, ax, length_label, route_output): import numpy as np import os

from matplotlib.image import imread def dist(p1, p2):

return ((p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2) ** 0.5 if len(points) < 3 :

route = list(range(len(points))) else: start = 0 route = [start]

unvisited = set(range(len(points))) - {start}

next_city = min(unvisited, key=lambda i: dist(points[i], points[start])) route.append(next_city) unvisited.remove(next_city) while unvisited: best_increase = float('inf) best_pos = None best_city = None for city in unvisited:

for i in range(len(route)): pi = points[route[i]] p2 = points[route[(i + 1) % len(route)]]