Иллюстрация с мусоровозом и его маршрутом
Подобные задачи известны давно и называются задачами коммивояжера. В вычислительном плане задачи эти довольно сложные и кроме всего прочего сильно усложняются с ростом числа точек посещения.
Правда, особенного практического интереса в задаче, скажем, на 100 точек посещения и нет, поскольку непросто придумать проблему, требующую посетить сотню точек за один маршрут некоего единственного сервера.
Метод решения задачи не сложен, хотя до него не так просто додуматься.
Мусоровоз должен забрать контейнеры из 23-х точек и вернуться к первой из них, чтобы отправиться на полигон.
Данные о расстояниях между каждой парой точек (всего 529 вариантов, но вообще таблица расстояний симметрична относительно диагонали) первоначально оценены по их координатам, а потом поправлены с учетом реальных маршрутов проезда для ближайших друг к другу точек.
Требуется построить модель расчета кратчайшего маршрута посещения всех 23 точек за один рейс.

1

Зададим случайный набор точек забора мусора.

Не будем замыкаться в единственном варианте расположения точек, а сделаем для начала схему, задающую случайный набор таких точек посещения и заодно визуализируем их расположение на «карте».
Пусть все пункты расположены на участке размером 20х20 км. Смоделируем их координаты следующим образом.
Так как мусоровоз, скорее всего, увозит мусор на полигон, находящийся вне участка обслуживания, будем считать, что исходная точка находится на краю участка и припишем ей координаты (0;0).
Остальные координаты участков сгенерируем любым датчиком случайных чисел.
Обычно генератор выдает случайное число от 0 до 1, и если такое число умножить на 20, то в итоге получится набор случайных чисел от 0 до 20.
GO AND UPDATE YOUR BROWSER BEFORE YOU READ ON!
Cгенерировать координаты точек обслуживания удобно стандартной функцией Excel =СЛЧИС(). Эта функция выдает случайные числа величиной от 0 до 1. Умножив такое случайное число на 20, получим числа от 0 до 20.

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

Для отображения пунктов посещения на «карте» просто построим точечную диаграмму по координатам точек x и y.
Таблица в Excel со случайными координатами точек забора мусора
Получим такую картину
Изображение случайно задданных точек забора мусора на диаграмме

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

2

Вычислим расстояние между всеми точками посещения.

Для вычисления расстояния между всеми точками посещения создадим таблицу (n x n), в которой вычислим все расстояния между точками по известой математической формуле
R = КОРЕНЬ( (X1-X2)2+(Y1-Y2)2)
Шаблон таблицы для расчета расстояний между точками забора мусора GO AND UPDATE YOUR BROWSER BEFORE YOU READ ON!
Для построения таблицы расчета всех расстояний между точками посещения необходимо повторить случайные координаты по горизонтали.
Повторение координат удобнее всего организовать с помощью стандартной функции MS Excel =ТРАНСП(..), которая преобразует столбец в строку и наоборот.
Это функция массива!
Она предусматривает вывод данных сразу в целую группу ячеек.
Поэтому
    для ввода функции
  • нужно выделить сразу диапазон E4:AA4
  • в строке формул записать =ТРАНСП(C6:C28)
  • нажать Enter.
Аналогично в строке 5 вводим =ТРАНСП(D6:D28).
Организация таблицы в Excel для расчета расстояний между всеми точками посещения
Теперь в таблице E6:AA28 можно вычислять расстояния между точками по математической формуле
R = КОРЕНЬ( (X1-X2)2+(Y1-Y2)2),
введя эту формулу в каждую ячейку.
Для ячейки E26, например, получится формула Excel =КОРЕНЬ((E$4-$C26)^2+(E$5-$D26)^2).

Обратите внимание: для того, чтобы формулу можно было растянуть на всю таблицу E4:AA26 ссылки на строку 2 и 3 и столбцы C и D надо зафиксировать знаком $.

Так как при нулевых расстояниях мы должны ввести в ячейку большое число, например 10000, то удобнее в ячейку E6 записать формулу

=ЕСЛИ(КОРЕНЬ((E$4-$C6)^2+(E$5-$D6)^2)=0;10000;КОРЕНЬ((E$4-$C6)^2+(E$5-$D6)^2)),
а затем протянуть ее во все синие ячейки.
Эта формула фактически означает: если значение корня в ячейке равно 0, то запиши 10000, иначе запиши значение корня.

В результате получается итоговая таблица - генератор расстояний и координат:
Таблица в Excel для расчета расстояний между всеми точками посещения
Вы можете скачать файл с готовой таблицей - генератором расстояний и координат (garbage_truck_route 1.xlsx)
Скачать файл с задачей Скачать файл garbage_truck_route 1.xlsx (примерно 185 Kб)

3

Построение задачи оптимизации маршрута.

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

Для решения задачи потребуется также таблица переменных. Это обычная для транспортных задач таблица, размером в таблицу расстояний, которая содержит бинарные переменные (0 или 1).
Из пункта n01 можно выехать и попасть только в единственное место, которое обозначается 1. Поэтому строка n01 будет содержать только одну ячейку с единицей, а в остальных ячейках этой строки будут нули. Тоже самое можно сказать про любую другую строку.
Фактически, решить данную задачу означает: поставить в каждой строке 1 таким образом, чтобы итоговый маршрут удовлетворял какому-то условию, например, имел наикратчайший путь.
Таблица расстояний
Таблица расстояний для задачи Построй маршрут
Таблица переменных
Таблица переменных для решения задачи Построй маршрут
Если задавать не единое разрешенное количество заходов в каждую точку (1 заход и 1 выход), а сравнивать число заходов с ячейками
1
, то можно выключать какие-то пункты посещения из списка просто обнулив число заходов в них
0
. Только следует учесть, что обнулять нужно и заход, и выход, т. е. суммы по вертикали и по горизонтали для выбранного пункта.
Таблица переменных в файле MS Excel строится под таблицей расстояний и выглядит так:
Таблица переменных с формулами в файле MS Excel

4

Решение задачи поиска оптимального маршрута.

Связываем таблицу расстояний и таблицу переменных.
Для решения задачи необходимо связать формулами Таблицу расстояний и Таблицу переменных.
Для этого нужно каждую ячейку строки n01 Таблицы расстояний умножить на соответствующую ячеку строки n01 Таблицы переменных и полученные произведения сложить.
В MS Excel это делает функция СУММПРОИЗВ(). Аналогичную операцию нужно проделать с остальными строками Таблицы переменных.
Как связать формулами Таблицу расстояний и Таблицу переменных и MS Excel
Поскольку в строке n01 Таблицы переменных будет только одна 1, а остальные 0, то произведение этой 1 на соответствующее расстояние в Таблице расстояний даст искомое расстояние от точки выезда n01до следующего пункта посещения. Найдя такие расстояния для каждой строки Таблицы переменных, мы получим длины всех звеньев маршрута. В ячейке AB29 все расстояния складываются, и получается пройденный мусоровозом путь, который мы будем минимизировать.

Итак, мы хотим найти оптимальный маршрут между точками забора мусора:
Графическое изображение точек забора мусора в декартовой системе координат Основная проблема подобной задачи – как заставить оптимизатор выбирать участки полного маршрута таким образом, чтобы получался связный замкнутый путь, а не отдельные участки.
Итак, мы имеем таблицу расстояний и таблицу переменных. Попробуем решить эту задачу как обычную транспортную задачу.
Так как в задаче 529 переменных, то решить её стандартным оптимизатором MS Excel Поиск решения нельзя, поэтому воспользуемся OpenSolver.
    Введем на панели OpenSolver - Model следующие данные:
  • Будем искать самый короткий маршрут, поэтому целевая ячейка $AB$29 должна иметь минимальное значение.
  • Определим переменные - это ячейки желтого цвета - диапазон $E$33:$AA$55
  • Введем ограничения:
    • сумма по каждой строке переменных для каждой точки выезда должна быть равна 1
      $AB$33:$AB$55 = $AS$33:$AC$55
    • сумма по каждому столбцу для каждой точки въезда должна быть равна 1
      $E$56:$AA$56 = $E$57:$AA$57
Установки OpenSolver при решении задачи оптимизации маршрута как обычной транспортной задачи
После сохранения Модели и запуска Solve получим решение:
Таблица с вапиантом решения задачи построения маршрута как обычной транспортной задачи
Отлично! Решение найдено, длина маршрута всего 64,96 км!
Но посмотрите на это решение на карте!
Анимированная карта поездок мусоровозов при найденном решении
Очевидно, что это СОВСЕМ НЕ ТО решение, которое мы ожидали!

Как исправить ситуацию?
Как заставить мусоровоз не возвращаться после первой посещенной точки?

    Для того, чтобы запретить возвраты после одного шага необходимо:
  • создать с помощью функции =ТРАНСП(…) новую таблицу, симметричную E33:AA55 относительно выделенной диагонали;
  • создать еще одну таблицу, в каждой ячейке которой сложить соответственные ячейки E33:AA55 таблицы переменных и транспонированной таблицы.
  • добавить ограничение в модели оптимизатора - все ячейки в последней таблице меньше или равны 1.
Настройки OpenSolver - Model будут такими:
Панель OpenSolver - Model с настройками, запрещающими возврат после первой посещенной точки.
После запуска Solve получим новое решение:
Решение, полученное OpenSolver после запрета возврата после первой посещенной точки
Хорошо! Решение найдено, длина маршрута - 81,18 км!
А на карте решение выглядит так:
Анимация нового решения, найденного OpenSolver
Это решение, конечно, лучше предыдущего, но мы хотим найти единственный замкнутый маршрут!

Создаем таблицу специальных ограничений.
Для создания связанного маршрута мусоровоза добавим таблицу Специальных ограничений, в которой введем поле с новыми переменными (переменные находятся в
ячейках). Эти переменные будут определять порядок посещения точек по замкнутому маршруту. Сначала этот порядок можно задать произвольно, указав для начальной точки значение 0.
Макет таблицы специальных ограничений для решения задачи построения маршрута мусоровоза
Связываем таблицу специальных ограничений и таблицу переменных.
Проиллюстрируем формулу, которая должна быть введена в каждую
ячейку Таблицы специальных ограничений.
Иллюстрация связования Таблицы переменных и Таблицы специальных ограничений
В файле MS Excel эта формула может быть записана так:
Формула, связывающая таблицу переменных с таблицей специальных ограничений в файле Ms Excel
В ячейках AC58 и AD58 записаны параметры ограничений: за выключением начального пункта n01 в задаче остается 22 пункта посещения (ячейка AC58), между которыми будет 21 (=22-1) связь (ячейка AD58). Еще две связи из 23-х, это участки n01-X и X-n01.

Для установления специальных ограничений потребуются 23 добавочных целочисленных переменных AB60:AB82. Зададим им начальные значения от 0 до 22. В дальнейшем OpenSolver запишет в них порядок посещения пунктов маршрута числами от 0 до 22.

В строке E83:AA83 нужна формула =ТРАНСП(AB60:AB82), которая продублирует столбец AB60:AB82.

В ячейке E61 запишем формулу =$AB61-E$83+$AC$58*E34, которая свяжет переменные из таблицы переменных E33:AA55 и столбца AB60:AB82 таблицы специальных ограничений. Если формула записана аккуратно, то ее можно растянуть на всю таблицу до AA82.

Строку 60 оставляем пустой.


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

Установки OpenSolver для нахождения оптимального решения.
Фактически это ограничение означает выполнение неравенства A - B + C * D <= 21 для каждой ячейки таблицы специальных ограничений,
где A - порядковый номер посещения пунктов выезда;
B - порядковый номер посещения пунктов въезда;
C - количество пунктов посещения (22 в нашей задаче);
D - это наши бинарные переменные, которые могут принимать значение 0 или 1.
    Пусть D = 0
  • тогда A - B <= 21,
  • то есть порядковые номера въезда и выезда не могут отличаться друг от друга больше, чем на 21
    напомню, что 21 - это число связей между точками посещений
    Пусть D = 1
  • тогда A - B + 22 <= 21,
  • значит A - B <= -1,
  • или A <= B -1,
  • то есть порядковый номер въезда должен как минимум на 1 отличаться от порядкового номера выезда
Именно выполнение этих ограничений приводит к тому, что номера посещения идут подряд, без пропусков.


Панель OpenSolver с установками
После запуска Solver получим решение
Оптимальное решение задачи о построении связного маршрута мусоровоза В решении найден маршрут, длина которого 88,54 км. Порядок посещения точек можно определить по единичкам в таблице переменных: п01-п07-п16-п11…
Маршрут на карте:
Карта оптимального решения OpenSolver с длиной пути 88,54км Следует отметить, что целочисленная оптимизация не дает гарантированного наилучшего результата. Почти всегда имеет смысл попробовать провести оптимизацию с более высокой точностью и оценить возможную разницу.
Для этого щелкнем в модели задачи OpenSolver кнопку Options… (снизу) и заменим параметр Branch and Bound Tolerance (%), по умолчанию равный 5, на меньшую величину. После этого поиск оптимума будет производиться более тщательно и дольше, конечно.
Изменение значения параметра tolerance на панели OpenSolver
Поскольку на практике неплохо видеть схему маршрута, а рисовать ее по точкам на диаграмме контрпродуктивно, имеет смысл добавить к диаграмме с пунктами посещения линии маршрута. Чтобы уже довести инструмент до максимального удобства использования. Здесь я предлагаю один из вариантов, как можно это сделать.
    На одной диаграмме нужно выводить сразу два графика:
  • точки посещения
  • маршрут посещения
Такой вывод позволит не перестраивать диаграмму даже в том случае, если заезд в какую-либо точку будет запрещен. При этом сама точка останется на карте, а маршрут мусоровоза пройдет мимо.

Организуем динамическую таблицу, данные которой позволят строить нужную диаграмму.
Напомню, что результатом решения задачи является, в частности, столбц переменных AB60:AB82, в ячейки которого записываются цифры от 0 до 22 (причем 0 - это вторая точка маршрута, ведь первая n01, а 22 - это последняя точка маршрута, т.е. опять n01). И эти цифры в столбце записаны не по порядку. Поэтому сначала организуем порядок посещения формулами.
Сначала в строке 31 от ячейки E31 до ячейки AA31 запишем числа от 1 до 23:
Записываем числа от 1 до 23 над таблицей переменных
Теперь, если умножить каждую ячейку этой строки на соответствующую ячейку строки, например, n01(33 строка), а результаты сложить, то получим номер посещения (в данном примере 7).

Организация таблицы маршрута с очередностью посещения
    Формирование столбца с номерами пунктов посещения прямо по порядку следования:
  • Запишем в AI60 единичку – поскольку начало маршрута всегда пункт п01.
  • В ячейку AI61 введем формулу
    =СУММПРОИЗВ(EE33:AA33;$E$31:$AA$31)
    определяем номер посещения следующей точки маршрута.
  • В ячейку AI62 введем формулу
    =ЕСЛИ(AI<=1;0;СУММПРОИЗВ(СМЕЩ($E$33:$AA$33;AI61-1;0);$E$31:$AA$31))
    эта формула позволяет нам, используя симметричность таблицы, сместиться на строку, номер которой был вычислен на предыдущем шаге и найти сумму произведений именно этой строки на значения 31 строки. Таким образом определится следующий номер посещения.
    Кроме того, в формуле предусмотрено не указывать номера после того, как будет встречен номер 1.
  • Протянем последнюю формулу вниз
Таким образом, мы сформировали столбец Последовательность посещения нашей динамической таблицы.
Столбец последовательность посещения в динамической таблице
    Теперь мы должны заполнить столбец имя
  • немного изменим первую таблицу - таблицу расстояний. Пронумеруем каждую строку от 1 до 23.
    Пронумеровать строки в таблицу расстояний
  • В ячейку AF60 введем формулу
    =ВПР($AI60;$A$6:$D$28;2)
    Эта формула считывает значение ячейки AI60 (это 1), затем в таблице растоянний находит в первом столбце такое значение и считывает значение ячейки второго столбца в этой строке (это n01).
  • Протягиваем формулу до конца таблицы. Таблица будет иметь следующий вид:
    Вставить формулу ВПР и заполнить столбец Имя
    Аналогичным образом заполняем столбец X
  • В ячейку AG60 вводим формулу
    =ВПР($AI60;$A$6:$D$28;3)
    так как значения X-координаты записаны в 3 столбце таблицы расстояний, то просто поменяем 2 на 3 в формуле, которую мы использовали для заполнения столбца имя
  • протянем эту формулу вниз. Все x координаты попали в нашу динамическую таблицу
    Вставить формулу ВПР и заполнить столбец X
    Теперь заполним столбец Y:
  • В ячейку AH введем формулу
    =ВПР($AI60;$A$6:$D$28;4).
  • Протянем эту формулу до конца таблицы
    Вставить формулу ВПР и заполнить столбец Y
По столбцам X и Y добавляем в имеющуюся диаграмму (щелчок правой кнопкой в диаграмме – Выбрать данные – Добавить) дублирующий набор данных AG60:AH83 с маркерами и линиями и подписи из столбца AF60:AF83. Так как все данные этой таблицы считываются с соответствующих ячеек, то при изменнении решения будут меняться, а диаграмма автоматически перерисовываться.
Получен довольно удобный шаблон построения диаграммы.
Скачать файл с задачей Скачать файл "garbage_truck_route 1.xlsx" (примерно 185 Кб)
В следующей части рассмотрим оптимизацию для задач с 30-ю и 51-м пунктами посещения.
✉ Если у вас появились вопросы или замечания, вы можете предложить лучшее решение, то пишите мне на электронную почту.