Поиск решения EXCEL (6.3). Задача коммивояжера (полный граф, линейная модель)

Решим один из вариантов задачи коммивояжера для небольшого количества городов (5-10) с помощью надстройки Поиск решения. Построим линейную модель.


Рассмотрим задачу коммивояжера (англ. 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). Кратчайший путь (неполный граф, линейная модель) .

Комментарии
Только для авторизованных пользователей

Аноним, 29 января 2017 г.
В составленной линейной моделе указано только одно ограничение (один вход и один выход), данная модель не исключает при решении образования циклов между несколькими городами и отсутствие одного единого контура Возможен такой вариант решения: https://upload.wikimedia.org/wikipedia/commons/0/09/TSP_short_cycles.png
Михаил, 29 октября 2017 г.
Просьба предоставить контр пример такого решения. Т.е. вы должны ввести некие исходные данные в модель файла примера, а поиск решения выдаст циклы между городами. Пожалуйста, продемонстрируйте.
Аноним, 27 декабря 2017 г.
Пример на 9 городов, координаты городов: № - x; y 1 - 0; 0 2 - 5; 0 3 - 5; 5 4 - 5; 10 5 - 0; 10 6 - 25; 25 7 - 25; 30 8 - 30; 30 9 - 30; 25 поиск решения находит длину кратчайшего пути - 50, образовалось два замкнутых независимых контура; 1-2-3-4-5-1 и 6-7-8-9-6 В данном случае ответ не верный, правильным будет маршрут 1-2-3-6-9-8-7-4-5-1 и длина - 96,6
Аноним, 2 марта 2018 г.
К сожалению, за два месяца так и не получил ответ или комментарий на свое высказывания. Можно сделать вывод, что построенная линейная модель не позволяет однозначно найти решение, нет гарантии получения одного непрерывного контура, необходимо ставить дополнительные ограничения, что может привести к составлению нелинейной модели либо таких ограничений будет очень много, что перечеркнет достоинство линейного программирования или просто невозможно его будет применить
(только для авторизованных пользователей)

© Copyright 2013 - 2020 Excel2.ru. All Rights Reserved