Задача коммивояжера (LibreOffice Calc)
Опубликовано 09 Сен 2018
Рубрика: О жизни | Комментариев нет
Странствующему торговцу необходимо побывать в нескольких близлежащих городах и вернуться домой. Требуется найти кратчайший путь следования. Расстояния между всеми городами известны. Примерно так формулируется один из вариантов очень популярной и...
...широко известной математической задачи — задачи коммивояжера.
Условия задачи могут изменяться: путь может быть незамкнутым, вместо расстояния между пунктами может быть стоимость проезда, но суть проблемы остается неизменной – найти лучший маршрут.
Материал, представленный далее, будет интересен тем, кто:
- занимается доставкой товаров или услуг по адресам;
- занимается прокладкой коммуникаций;
- много (или изредка) путешествует;
- хочет немного научиться экономить время и деньги.
Несмотря на значительные усилия математиков в течение последних 100 лет, задача коммивояжера не имеет точного алгоритма решения кроме метода полного перебора всех возможных вариантов.
Но количество возможных (замкнутых) маршрутов определяется по формуле:
N=(n-1)!/2,
где n – число городов (пунктов).
- при n=3 N=1 (один маршрут)
- при n=4 N=3
- при n=5 N=12
- при n=6 N=60
- при n=7 N=360
- при n=8 N=2 520
- при n=9 N=20 160
- при n=10 N=181 440
- при n=15 N=43 589 145 600
- при n=20 N=60 822 550 204 416 000
- при n=30 N=4 420 880 996 869 850 977 271 808 000 000
Огромное быстрорастущее количество вариантов пути делает метод полного перебора невозможным к применению уже при количестве городов более 15. Если даже предположить, что персональный компьютер может анализировать 10 миллионов маршрутов в секунду (невероятная скорость!), то для перебора вариантов для 20 городов необходимо почти 200 лет непрерывной работы!
Современные алгоритмы (муравьиный, имитации отжига, генетический), бурно развитые в последние 30 лет, спотыкаясь на ложных экстремумах многомерной функции, вводя в бой элитных муравьев с изменяемым уровнем феромонов, рои пчел, переменную вероятность мутаций и еще массу настраиваемых параметров, достигли весьма значительного прогресса в сокращении времени и повышении точности поиска решения задачи коммивояжера. Однако разобраться с настройкой порой десятка параметров, понять их влияние на ход поиска часто становится отдельной не простой задачей.
Рассмотрим более простой путь. Чем нам бесплатно сможет помочь в решении задачи коммивояжера надстройка «Решатель» LibreOffice Calc из широко распространенного офисного пакета?
Расчет маршрута в Московском метро.
Начнем с решения простой, но часто важной проблемы.
Условия задачи:
Вы приехали в командировку в Москву. Вам необходимо в течение одного дня выполнить несколько задач. Для этого нужно выехать из гостиницы, посетить 7 мест и вернуться. Требуется определить самый короткий по времени маршрут.
Перечень станций для посещения (в произвольном порядке):
- Партизанская (гостиница);
- Профсоюзная;
- Красные ворота;
- Марьина роща;
- Маяковская;
- Юго-западная;
- Охотный ряд;
- Багратионовская.
Решение:
Скачиваем файл LibreOffice Calc с программой «Расчет маршрута»: raschet-marshruta (ods 20,9KB).
В файле принят следующий порядок:
- в ячейках со светло-бирюзовой заливкой – исходные данные, которые вводит пользователь;
- в светло-желтых ячейках – формулы (не трогать!);
- в ячейках с ярко-желтой заливкой данные, которые вписывает «Решатель» (ничего можно не писать самостоятельно).
1. С помощью сервиса Яндекс Метро (metro.yandex.ru/moscow) была составлена матрица исходных данных в минутах. Заполнены ячейки B5…I12 со светло-бирюзовой заливкой! В ячейках матрицы записано время движения между станциями.
2. В таблице переменных – значения, которые определяют последовательность движения по маршруту. В B16 предварительно сделана запись: 0/8 – это начало и конец пути – станция №1 – Партизанская. Значения в ярко-желтых ячейках C16…I16, которые являются решением задачи, появились после выполнения поиска «Решателем»! Перед запуском поиска решения они были пусты.
3. Матрица переменных нужна для возможности создания ограничения количества въездов и выездов на станции. Нам необходимо чтобы на каждую станцию был строго 1 въезд и 1 выезд. В ячейки с яркой желтой заливкой B20…I27 значения записал «Решатель», до его работы они были пустыми. В J20…J27 записаны формулы суммирования значений строк матрицы переменных, а в B28…I28 – формулы суммирования значений столбцов.
4. Целевой функцией, минимум которой нашел «Решатель» является суммарное время в пути по найденному в п.2 маршруту — 165 минут. В объединенной ячейке G30 вписана формула, суммирующая произведение значений из диапазона исходных данных и диапазона переменных.
5. Дополнительная матрица ограничений нужна для контроля замкнутости маршрута. Она заполнена соответствующими формулами.
6. После того, как все ячейки кроме ярко-желтых были заполнены данными и формулами, был вызван (Сервис – Решатель) и настроен «Решатель».
После нажатия на кнопку «Решить» результат был получен через 5 секунд.
Ответ:
На первых двух рисунках, размещенных ниже, изображены маршруты, проложенные «вручную», а на третьем – путь, найденный с помощью программы LibreOffice Calc.
Третий маршрут продолжительностью 165 минут на 13 и 17 минут соответственно быстрее двух первых! Лучшее ли решение найдено? С высокой степенью вероятности – да.
Решение задачи коммивояжера Oliver30.
Посмотрим, на что годится LibreOffice при решении сложных задач.
Oliver30 – широко известная задача с 30 городами, которую часто используют программисты в качестве тестовой задачи.
Для Oliver30 известно точное решение: кратчайший путь равен 423,7406.
Посмотрите страницу «Oliver30» в файле с предыдущей задачей. «Решатель» LibreOffice Calc довольно шустро нашел одно из решений (не лучшее, но очень близкое к таковому): маршрут длиной 424,573. Это всего лишь на 0,2% больше самого короткого пути!
Вместо «0» в диагональ матрицы расстояний пришлось вписать «900» — значение существенно превышающие расстояние между любыми точками задачи. Иначе программа иногда сбивается на использование в решении нулевых расстояний, как наиболее оптимальных. Обратите внимание на этот момент!
Улучшить маршрут в тестовой задаче до известного кратчайшего пути изменением начальных параметров и перебором алгоритмов «Решателя» мне пока не удалось.
Тем не менее, очевидно, что использование «Решателя» LibreOffice Calc может быть экономически весьма эффективным и оправданным решением, как при ежедневных, так и при разовых разработках различных маршрутов. Решая задачу коммивояжера, можно добиться снижения реальных затрат времени и топлива на 10...15%.
Наличие в «Решателе» 4-х алгоритмов и отсутствие лимитов на количество переменных, ограничивающих условий и формул предоставляют пользователю широкие возможности для экспериментов и практической работы.
P.S.
При поиске источников точного времени движения поездов метро наткнулся на статью: habr.com/company/yandex/blog/301030/. Группа энтузиастов пару лет назад за 16 часов 22 минуты проехала по заранее рассчитанному с помощью генетического алгоритма маршруту через все 199 (на тот момент) станций Московского метрополитена с выходами для фотографирования на перрон каждой станции.
Самые комментируемые записи
Отзывы
Посетители: 2,1 млн
Ваш отзыв