Решение задачи коммивояжера в excel

Обновлено: 04.07.2024

По условию задачи «коммивояжер» выезжает из некоторого начального города и посещает другие города в количестве n-1, где n – общее количество пунктов назначения. Задается матрица расстояний (Cij) между пунктами, где i и j изменяются от 1 до n. При этом необходимо учесть следующие ограничения:

- коммивояжер въезжает в любой пункт только 1 раз;

- коммивояжер выезжает из каждого пункта только 1 раз;

- маршрут является замкнутым, без петель.

Алгоритм решения задачи коммивояжера с использованием возможностей программы Microsoft Excel или OpenOffice Calc будет состоять из следующих пунктов:

1. Определение переменных - Хij. В задаче коммивояжера Хij может принимать одно из двух возможных значений: 1 (если поездка совершается из пункта i в пункт j) или 0 (если поездка не совершается), т.е. является булевым числом.

2. Составление целевой функции. Целевая функция задачи коммивояжера - это произведение матрицы расстояний (Cij) и матрицы переменных (Хij). В Excel предусмотрена функция СУММПРОИЗВ(Cij; Хij), в OpenOffice Calc - SUMPRODUCT(Cij; Хij).

3. Описание ограничений:

- для соблюдения ограничений того, что коммивояжер въезжает и выезжает из каждого пункта только 1 раз переменные задаются булевыми и сумма значений переменных по каждому столбцу (j) и каждой строке (i) должна быть равна единице;

- для задания замкнутости маршрута и отсутствия петель необходимо ввести дополнительные переменные U и задать на листе ограничение, соответствующее формуле:

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

4. Организация данных на листе Microsoft Excel или OpenOffice Calc.

5. Вызов надстройки Excel «Поиск решения»: Меню Данные – Анализ – Поиск решения (в более ранних версиях MS Excel Меню Сервис – Поиск решения) или надстройки Calc «Решатель»: Меню Сервис – Решатель.

6. Задание «Поиску решения» или «Решателю» всех необходимых данных.

7. Получение оптимального решения.

Соблюдение описанных действий позволит найти оптимальное решение задачи коммивояжера как в MS Excel, так и в OpenOffice Calc. Однако при выборе программы следует учитывать, что надстройка «Поиск решения» устанавливает жесткие рамки на количество ограничений решаемой задачи. В частности в MS Excel удобно решать задачи с небольшим количеством пунктов (до 10), общее количество формульных ограничений в которых не превысит 100 [2]. В «Решателе» подобных ограничений нет, но с добавлением каждого дополнительного пункта в задачу программе требуется все большее количество времени на нахождение оптимального маршрута.

Список используемых источников:

1. Серая, О.В. Применение процедуры кластеризации при решении задачи коммивояжера высокой размерности с использованием генетического алгоритма [Текст] / О.В. Серая // Вестник НТУ ХПИ. - 2006. - №23. - С.164-169.

ОПУБЛИКОВАНО

Студентова Е.А. Алгоритм решения задачи коммивояжера с использованием Microsoft Excel и Open Office Calc . // Современные проблемы науки и образования - 2014.-№6. (приложение "Технические науки"). - C. 40

Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата). Подобная задача решена в статье Поиск решения MS EXCEL (6.2). Задача коммивояжера (полный граф, нелинейная модель) с помощью нелинейной модели.

Задача

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

Создание модели

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).

Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$A16+1;1)-ИНДЕКС($C$7:$D$11;B$15+1;1))^2+(ИНДЕКС($C$7:$D$11;$A16+1;2)-ИНДЕКС($C$7:$D$11;B$15+1;2))^2)

Теперь создадим модель для Поиска решения .

Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

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

Ограничения (выделено синим) . Необходимо, чтобы из каждого города был 1 входящий и 1 исходящий маршрут.

Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

Найденное Решение

Поиск решения гарантировано найдет самый короткий маршрут, т.к. построенная нами модель линейная.

Данную задачу можно решить для максимального количества городов =20, т.к. число маршрутов (ребер) вычисляется по формуле n*(n-1)/2, а количество переменных у Поиска решения ограничено 200.

Также в файле примера приведено решение задачи для прохождения 5 городов по незамкнутому маршруту, а также задачу для 9 городов.

Совет : Решение задачи о поиске кратчайшего пути между 2-мя заданными городами можно найти в статье Поиск решения MS EXCEL (6.4). Кратчайший путь (неполный граф, линейная модель) .

Задача

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

Решение

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).

Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$F7+1;1)-ИНДЕКС($C$7:$D$11;G$6+1;1))^2 +(ИНДЕКС($C$7:$D$11;$F7+1;2)-ИНДЕКС($C$7:$D$11;G$6+1;2))^2)

Теперь создадим модель для Поиска решения .

Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

Переменные (выделено зеленым) . В качестве переменных модели следует взять номера городов. Так как начальная и конечная точка известны (Город0), то переменных будет 4. Ограничения (выделено синим) . Необходимо, чтобы номера городов не повторялись. Это означает, что количество уникальных (неповторяющихся) номеров городов должно быть равно 4. Для этого используется формула для подсчета уникальных значений : = СУММПРОИЗВ(1/СЧЁТЕСЛИ(B16:B19;B16:B19))

Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

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

Найденное Решение

Поиск решения найдет (должен найти) самый короткий маршрут, т.е. последовательность 0-1-4-2-3-0 (или обратную).

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

Совет . Таблицы перебора перестановок от 1 до 5, от 1 до 6, … от 1 до 9 можно найти в этой статье Перебор всех возможных Перестановок в MS EXCEL .

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

Обнулите значения переменных модели на Листе 11 городов, запустите Поиск решения. После окончания поиска (может занять несколько минут) опять обнулите значения переменных и перезапустите Поиск решения: найденные решения могут серьезно отличаться.

Совет . Иногда, для того чтобы улучшить найденное решение, помогает следующий прием: запустите Поиск решения , сохраните найденное решение, измените параметры поиска (например, размер совокупности), повторно запустите Поиск решения.

В файле примера также приведено решение задачи для замкнутого и незамкнутого маршрута посещения 9 городов. Решения найдены с помощью Эволюционного метода со следующими параметрами: Целочисленная оптимальность 0%, Использовать автоматическое масштабирование, Скорость изменения варьировалась 0,25-0,5; Размер совокупности варьировался 10-50. Оба решения проверены с помощью таблиц перебора всех маршрутов (см. таблицы перебора перестановок ). Если при первом прогоне Поиска решения не удавалось найти оптимальное решение, то он запускался повторно, при этом 1 или 2 параметра изменялись. После второго прогона оптимальное решение, как правило, было найдено.

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

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

Задача

Имеется 11 городов, координаты которых известны. Маршруты проложены только между некоторыми городами (неполный граф). Найти кратчайший путь между 2-мя заданными городами. Построить Линейную модель.

Создание модели

Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера ).

Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);1)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);1))^2 +(ИНДЕКС($C$7:$D$17;ПОИСКПОЗ($A30;$A$7:$A$17;0);2)-ИНДЕКС($C$7:$D$17;ПОИСКПОЗ(B$29;$A$7:$A$17;0);2))^2)

Теперь создадим линейную модель для решения задачи с помощью Поиска решения .

Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .

Переменные (выделено зеленым) . В качестве переменных модели следует взять номера маршрутов между городами: если маршрут включен в кратчайший путь, то переменная =1, если нет, то =0. Ограничения (выделено синим) . Необходимо, чтобы из каждого города, в котором побывал путешественник, был входящий и выходящий маршрут. Так как входящий маршрут обозначается 1, а исходящий -1, то их сумма, равная 0, будет означать, что в город вошли и вышли (включен в кратчайший путь). Исключение составляют город – начальная точка путешествия (сумма =-1) и город – конечная точка (сумма =1). Изменяя ограничение в синем столбце, можно задавать начальные и конечные пункты путешествия. Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.

Примечание : для удобства настройки Поиска решения используются именованные диапазоны .

Выберите Линейный метод поиска решения, т.к. созданная модель является линейной.

Найденное Решение

Поиск решения гарантировано найдет самый короткий маршрут, т.к. модель линейная.

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

Будьте внимательны, не все пары конечных и начальных пунктов допустимы. Например, задав путешествие из Москвы в Копенгаген, Поиск решения не найдет маршрут, т.к. для этого потребуется «двигаться назад», а в маршрутах между городами обратные пути не прописаны (маршруты, конечно, можно добавить в столбцы J:M, но не забудьте изменить и другие формулы).

Читайте также: