РЕШЕНИЕ ЗАДАЧИ КОММИВОЯЖЁРА С ПОМОЩЬЮ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ

​SOLVING THE TRAVELING SALESMAN PROBLEM USING INTEGER PROGRAMMING

Maria Zhurba

Student, Department of Operational Work Management, St. Petersburg State University of Railway Transport,

Russia, St. Petersburg

АННОТАЦИЯ

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

ABSTRACT

This article will examine some solutions to the Traveling Salesman Problem. Several algorithms have been implemented to find the Hamiltonian cycle of minimum length, passing through each city exactly once with a return to the starting city. Examples of algorithm results are provided, and an assessment of solution accuracy is conducted.

Ключевые слова: задача коммивояжёра, целочисленное программирование, метод ближайшего соседа, алгоритм повторяющегося ближайшего соседа, жадный алгоритм, Wolfram Mathematica.

Keywords: Traveling Salesman Problem, Integer Programming, Nearest Neighbor Method, Repeated Nearest Neighbor Algorithm, Greedy Algorithm, Wolfram Mathematica.

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

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

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

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

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

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

Дано:  – множество городов, матрица попарных расстояний между городами – , где .

Переменные задачи:

Целевая функция:

Ограничения:

или

В данной статье будет представлены решения задачи коммивояжера, написанные на языке Wolfram Mathematica. Для небольшого числа городов () задачу можно решить точно с помощью методов целочисленного программирования. Решение задачи представлено на рисунке 1.

Рисунок 1. Исходный код точного решения задачи коммивояжёра

Рисунок 2. Пример точного решения задачи коммивояжера

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

Поскольку задача коммивояжёра относится к классу NP полных, что означает, что время на решение задачи растет экспоненциально с ростом n, то имеет смысл использовать приближенные алгоритмы. Метод ближайшего соседа заключается в том, чтобы на каждом шаге выбирать наиболее близкий к коммивояжёру город, а самый первый город выбрать случайно. Реализация алгоритма представлена на рисунке 3.

Рисунок 3. Исходный код метода ближайшего соседа

Пример решения задачи коммивояжёра методом ближайшего соседа представлено на рисунке 4.

Рисунок 4. Пример решения, полученного методом ближайшего соседа

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

Рисунок 5. Исходный код метода повторяющегося ближайшего соседа

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

Рисунок 6. Пример решения, полученного методом повторяющегося ближайшего соседа

Эвристический алгоритм

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

Рисунок 7. Исходный код жадного алгоритма

Граф, отражающий решение задачи коммивояжёра с помощью жадного алгоритма, представлен на рисунке 8.

Рисунок 8. Пример решения, полученного жадным алгоритмом

Заключение

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

Рисунок 9. Исходный код первого метода оценки нижней границы

Рисунок 10. Исходный код второго метода оценки нижней границы

Для того чтобы оценить эффективность алгоритмов была построена таблица с оценками эффективности алгоритмов.

Таблица 1.

Оценка эффективности алгоритмов

Список литературы:

1. Гомори Р.е., Бомоль У.Д. Целочисленное программирование и оценки. В сб. «Численные методы оптимального планирования. Экономико-математическая серия». Вып. 1: Новосибисрк, Изд-во Сиб. Отд. АН СССР, 1962.
2. Мудров В.И. Задача о коммивояжёре. Издание 2, Изд-во УРСС, 2013
3. Wolfram [электронный ресурс] — Режим доступа. — https://www.wolfram.com/language/fast-introduction-for-math-students/ru///