Задача коммивояжера (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 мест и вернуться. Требуется определить самый короткий по времени маршрут.



Перечень станций для посещения (в произвольном порядке):

  1. Партизанская (гостиница);
  2. Профсоюзная;
  3. Красные ворота;
  4. Марьина роща;
  5. Маяковская;
  6. Юго-западная;
  7. Охотный ряд;
  8. Багратионовская.

Решение:

Скачиваем файл LibreOffice Calc с программой «Расчет маршрута»: raschet-marshruta (ods 20,9KB).

В файле принят следующий порядок:

  • в ячейках со светло-бирюзовой заливкой – исходные данные, которые вводит пользователь;
  • в светло-желтых ячейках – формулы (не трогать!);
  • в ячейках с ярко-желтой заливкой данные, которые вписывает «Решатель» (ничего можно не писать самостоятельно).

Расчет маршрута в LibreOffice Calc1. С помощью сервиса Яндекс Метро (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.

Задача коммивояжера решение 1

Задача коммивояжера решение 2

Задача коммивояжера решение 3

Третий маршрут продолжительностью 165 минут на 13 и 17 минут соответственно быстрее двух первых! Лучшее ли решение найдено? С высокой степенью вероятности – да.

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

Посмотрим, на что годится LibreOffice при решении сложных задач.

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

Для Oliver30 известно точное решение: кратчайший путь равен 423,7406.

Oliver30 кратчайший маршрут

Посмотрите страницу «Oliver30» в файле с предыдущей задачей. «Решатель» LibreOffice Calc довольно шустро нашел одно из решений (не лучшее, но очень близкое к таковому): маршрут длиной 424,573. Это всего лишь на 0,2% больше самого короткого пути!

Вместо «0» в диагональ матрицы расстояний пришлось вписать «900» — значение существенно превышающие расстояние между любыми точками задачи. Иначе программа иногда сбивается на использование в решении нулевых расстояний, как наиболее оптимальных. Обратите внимание на этот момент!

Oliver30 маршрут LibreOffice Calc

Улучшить маршрут в тестовой задаче до известного кратчайшего пути изменением начальных параметров и перебором алгоритмов «Решателя» мне пока не удалось.

Тем не менее, очевидно, что использование «Решателя» LibreOffice Calc может быть экономически весьма эффективным и оправданным решением, как при ежедневных, так и при разовых разработках различных маршрутов. Решая задачу коммивояжера, можно добиться снижения реальных затрат времени и топлива на 10...15%.

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

P.S.

При поиске источников точного времени движения поездов метро наткнулся на статью: habr.com/company/yandex/blog/301030/. Группа энтузиастов пару лет назад за 16 часов 22 минуты проехала по заранее рассчитанному с помощью генетического алгоритма маршруту через все 199 (на тот момент) станций Московского метрополитена с выходами для фотографирования на перрон каждой станции.

Другие статьи автора блога

На главную


Введите Ваш e-mail:

Самые комментируемые записи

Отзывы

Ваш отзыв




  • Подписчики: 5,7 тыс.

  • Посетители: 1,1 млн