Поиск кратчайшего пути
В разделе математики под названием "теория оптимизации" есть несколько задач, связанных с расчётом траектории движения объектов. В прошлом я уже делал разбор решения транспортной задачи на примере оптимизации доставки товаров со складов в магазины. Теперь же давайте попробуем использовать Microsoft Excel для решения другой классической задачи из того же раздела - прокладки кратчайшего маршрута из пункта А в пункт Б через несколько промежуточных точек транспортной сети. Частным случаем такой задачи ещё называют "задачу коммивояжера", когда нам нужно по кратчайшему маршруту обойти все точки, не заходя ни в одну из них дважды, а затем вернуться обратно в пункт отправления.
Таблица расстояний
Первое, что нам потребуется для создания модели - это, конечно же, таблица расстояний между пунктами нашей транспортной сети или матрица смежности, как ещё её называют в математике:
Это квадратная таблица со списком городов в первом столбце и этими же городами в шапке, где на пересечении строки и столбца хранится расстояние между соответствующими пунктами.
Сразу уточним, что:
- в общем случае эта таблица может хранить не обязательно расстояния, а просто некую метрику или вес отрезка между пунктам, которую мы оптимизируем - это может быть время перемещения, стоимость билетов, средняя скорость, грузоподъемность и т.д.
- в ячейках на диагонали специально размещены заведомо большие значения (999999), чтобы алгоритм не выбрал в качестве кратчайшего пути этот же самый пункт (самый короткий путь - никуда не ходить, да);
- у нас эта таблица симметрична относительно диагонали, но, опять же, в общем случае симметрии может и не быть, т.е. путь туда и обратно может различаться по весу (например, стоимость билетов туда и обратно может быть разной);
- таблица может быть избыточной, т.е. в ней могут быть пункты, которые мы не собираемся посещать, но могут заинтересовать нас в будущем.
Для удобства работы с таблицей, давайте сразу конвертируем её в динамическую "умную" сочетанием клавиш Ctrl+T или командой Главная - Форматировать как таблицу (Home - Format as Table) и на вкладке Конструктор (Design) дадим ей имя Расстояния.
Модель маршрута
Теперь можно набросать модель маршрута, которую мы потом будем оптимизировать.
Предположим, что мы хотим выехать из Москвы и посетить в любом порядке следующие пункты: Владимир, Рязань, Ярославль, Муром, Клин. После чего вернуться обратно в Москву, в точку старта. Визуально это можно представить вот такой простой таблицей:
Если захочется добавить наглядности, то можно нанести эти точки на карту и отобразить её прямо в Excel. Для этого можно воспользоваться бесплатной надстройкой Bing Maps через Главная - Надстройки (Home - Add-ins). После вставки карты нужно выделить список наших пунктов и нажать на кнопку Показать местоположения (Show locations) в правом верхнем углу, чтобы отобразить наши города на местности.
Поскольку Excel удобнее при оптимизации работать с числами, а не с текстом, так что давайте присвоим каждому промежуточному пункту уникальный номер - целочисленный ID от 1 до 5, соответственно. Обратите внимание, что это не порядок, в котором мы будем проходить эти пункты, а просто код каждого города.
Рассчитаем длину маршрута, если мы решим посещать эти города для начала именно в таком (очевидно не самом оптимальном) порядке. Для этого нам потребуется найти расстояние от предыдущего до текущего пункта, т.е. число с пересечения строки и столбца нашей матрицы связности Расстояния. Лучше всего для этого подойдет классическая функция ИНДЕКС (INDEX) в связке с функциями ПОИСКПОЗ (MATCH):
Первый аргумент этой функции - это наша матрица расстояний, а второй и третий - это номер строки и столбца, с пересечения которых мы хотим извлечь значение расстояния. Эти номера мы вычисляем с помощью функций ПОИСКПОЗ, находя позицию текущего и предыдущего городов в первом столбце и в шапке таблицы соответственно.
Останется лишь подсчитать общую длину получившегося маршрута, используя функцию СУММ (SUM):
Таким образом, теперь мы можем менять последовательность обхода городов, меняя их ID в зелёных ячейках, и получать в красной ячейке длину получившегося маршрута.
Оптимизация
Теперь - самое интересное и главное. В каком же порядке нам нужно посетить эти 5 городов, чтобы общая длина маршрута оказалась минимальной? Т.е. другими словами, в каком именно порядке в зелёных ячейках должны располагаться, не повторяясь, целые числа от 1 до 5, чтобы в красной ячейке был минимум?
Для этого нам придётся использовать "тяжелую артиллерию" - встроенную в Microsoft Excel оптимизационную надстройку Поиск решения (Solver). Чтобы её подключить, воспользуемся кнопкой Надстройки Excel на вкладке Разработчик (Developer - Excel Add-ins):
После подключения надстройки на вкладке Данные (Data) в правом верхнем углу должна появиться новая кнопка - Поиск решения (Solver), которая нам и нужна.
В открывшемся окне необходимо задать следующие настройки:
- в качестве целевой ячейки задать розовую ячейку с общей длиной маршрута, уточнив ниже, что мы хотим её минимизировать;
- в качестве изменяемых ячеек переменных задать пять зелёных ячеек с номерами промежуточных пунктов, которыми мы "играем" на входе в нашу модель;
- нажимая на кнопку Добавить (Add) задать три ограничения для зелёных ячеек - они должны быть <=5, они должны быть целыми и они должны быть разными, т.е. не повторяться;
- в выпадающем списке в нижней части окна выбрать алгоритм эволюционного поиска решения.
Если результат вам не нравится, то в этом окне можно вернуться к исходным значениям до оптимизации. Если нравится, то сохранить их на листе или же сохранить их как один из сценариев (кнопка Сохранить сценарий) для последующего анализа и сравнения, например, с другими сценариями. Доступ ко всем сохранённым сценариям можно получить на вкладке Данные - Анализ "что если" - Диспетчер сценариев (Data - "What if" analysis - Scenario manager).
Но с ходу очевидно, что подобранный вариант гораздо лучше исходного - 1209 км вместо 1879!
Ссылки по теме
- Оптимизация доставки (транспортная задача)
- Симулятор лотереи в Excel
- 5 вариантов использования функции ИНДЕКС (INDEX) в Excel
Немного скуфской духоты от меня: так любимое всеми выражение "самый оптимальный" бессмысленно, т.к. оптимум подразумевает уникальность. Не бывает "самых" и "не самых" оптимальных решений - оптимальное решение только одно. Спасибо, извините )))
Насчёт "самый оптимальный" - согласен, масло масляное
Можно получить достаточно неплохое решение относительно быстро, но которое не будет глобальным оптимумом.
В реальных задачах данного типа часто бывает необходимость относительно быстро найти решение, которое будет отличатся от оптимального не более чем на несколько процентов. В условиях того что временные затраты на поиск "самого оптимального" (в терминологиях данной статьи) решения будут очень большие.
Задача коммивояжера относится к классу NP-трудных задач, и относится к числу уже при относительно небольшом числе городов (>66), если решать ее полным перебором всех перестановок.
"Поиск решения" спотыкается, долго считает и застрял в локальном оптимуме и не может улучшить решение и это решение далеко от лучшего почти в два раза, путь составил - 109401
Альтернативное решение, используемое жадные алгоритмы + оптимизацию + оптимизацию, смогло найти путь длиной - 57177 (не обязательно, что данное решение является глобальным оптимумом)
Различные алгоритмы по реализации задачи коммивояжера публиковал
Найденный маршрут на исходных данных из примера длиною в 57177 можно посмотреть
UPD: решение алгоритмом - 56990