Решение задачи коммивояжёра в трёхмерном пространстве

Актуальность

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

Задача является актуальной, так как к ней сводится множество различных бизнес-задач из разных областей, например, логистики. С развитием квадрокоптеров также появилась потребность в автоматическом построении маршрутов для них. В большинстве случаев такие задачи можно свести к задаче коммивояжёра в трёхмерном пространстве.

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

Задача относится к NP-полным, то есть у неё нет точного решения за полиномиальное время. Точно такие задачи можно решить только методом полного перебора, который невозможно применять для решения задач с большими исходными данными. В задаче коммивояжёра сложность метода полного перебора равна O(n!), то есть для 10 городов потребуется перебрать 3628800 решений, а для 20 – уже 2432902008176640000 решений. Из-за физических ограничений мощности устройств для решения задачи используются различные эвристические алгоритмы, которые не всегда дают оптимальный результат, но работают в разы быстрее. В данной работе будут исследоваться различные эвристические алгоритмы решения геометрической задачи коммивояжёра в пространстве.

Цель

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

Задачи

1.      Изучить различные алгоритмы оптимизации для решения задачи.

2.      Реализовать данные алгоритмы на языке Python.

3.      Исследовать эффективность алгоритмов.

4.      Предложить и реализовать свои модификации алгоритмов.

5.      Исследовать их эффективность.

Оснащение и оборудование, использованное при создании работы

• Компьютер

Описание

В решении задач проекта автор использовал следующие алгоритмы и методы.

Метод ближайшего соседа

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

Муравьиный алгоритм

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

Генетический алгоритм

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

Для решения задачи коммивояжёра использовался алгоритм, основанный на классическом генетическом алгоритме Джона Холланда. Работу алгоритма можно разбить на несколько этапов:

1. случайная генерация первого поколения;
2. отбор родителей;
3. скрещивание;
4. мутации;
5. создание нового поколения.

Пункты со 2-го по 5-й выполнялись до тех пор, пока не прошло заданное количество поколений.

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

Рисунок 11 - пример решения муравьиного алгоритма

Рисунок 13 - пример решения метода ближайшего соседа

Результаты работы/выводы

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