1

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

Не будем замыкаться в единственном варианте расположения точек, а сделаем для начала схему, задающую случайный набор таких точек посещения и заодно визуализируем их расположение на «карте».
Пусть все пункты расположены на участке размером 20х20 км. Смоделируем их координаты следующим образом.

Так как мусоровоз, скорее всего, увозит мусор на полигон, находящийся вне участка обслуживания, будем считать, что исходная точка находится на краю участка и припишем ей координаты (0;0).
Остальные координаты участков сгенерируем любым датчиком случайных чисел.
Обычно генератор выдает случайное число от 0 до 1, и если такое число умножить на 20, то в итоге получится набор случайных чисел от 0 до 20.

Cгенерировать координаты точек обслуживания удобно стандартной функцией Excel =СЛЧИС(). Эта функция выдает случайные числа величиной от 0 до 1. Умножив такое случайное число на 20, получим числа от 0 до 20.

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

Для отображения пунктов посещения на «карте» просто построим точечную диаграмму по координатам точек x и y.

Таблица в Excel со случайными координатами точек забора мусора

Получим такую картину

Изображение случайно задданных точек забора мусора на диаграмме

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

2

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

Для вычисления расстояния между всеми точками посещения создадим таблицу (n x n), в которой вычислим все расстояния между точками по известой математической формуле
R = КОРЕНЬ( (X₁-X₂)²+(Y₁-Y₂)²)

в ячейках
укажем номера точек забора мусора
в ячейках
укажем X - координату каждой точки забора мусора
в ячейках
укажем Y - координату каждой точки забора мусора
в каждую ячейку
введем формулу: = КОРЕНЬ( (X₁-X₂)²+(Y₁-Y₂)²)
ячейки
- это расстояние от точки до самой себя.
По смыслу оно должно быть равно 0, но при прокладке кратчайшего маршрута нулевые расстояния окажутся очень привлекательными для алгоритмов оптимизации. В транспортных и многих других задачах стандартный способ запретить маршрут или операцию – приписать им очень высокую цену, превосходящую суммарные расстояния или издержки в задаче. Здесь следует поступить точно так же.
В нашем случае, даже при расстоянии между всеми точками 20 км, сумма расстояний будет менее 500 км (20*23=460). Так что в качестве запрещающего расстояния можно использовать 1000 или 10000 (перегибать палку и использовать очень большие числа не рекомендуется).

Для построения таблицы расчета всех расстояний между точками посещения необходимо повторить случайные координаты по горизонтали.
Повторение координат удобнее всего организовать с помощью стандартной функции MS Excel =ТРАНСП(..), которая преобразует столбец в строку и наоборот.

Это функция массива!
Она предусматривает вывод данных сразу в целую группу ячеек.
Поэтому

нужно выделить сразу диапазон E4:AA4
в строке формул записать =ТРАНСП(C6:C28)
нажать Enter.

Аналогично в строке 5 вводим =ТРАНСП(D6:D28).

Организация таблицы в Excel для расчета расстояний между всеми точками посещения

Теперь в таблице E6:AA28 можно вычислять расстояния между точками по математической формуле
R = КОРЕНЬ( (X₁-X₂)²+(Y₁-Y₂)²),
введя эту формулу в каждую ячейку.
Для ячейки 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 таким образом, чтобы итоговый маршрут удовлетворял какому-то условию, например, имел наикратчайший путь.

Таблица расстояний

Таблица переменных

Желтое поле - ячейки
- это область переменных. Именно эти ячейки мы будем указывать в качестве переменных в установках OpenSolver
Ячейки
- тоже переменные, значение которых при решении задачи всегда будут равны 0.
Ячейки
1
мы используем в качестве ограничений в установках OpenSolver. Единица означает, что из точки можно выехать 1 раз и въехать в нее 1 раз.
В ячейки
с правой стороны таблицы запишем формулу, которая считает сумму значений всех желтых ячеек в строке, а в ячейки такого же цвета внизу таблицы - сумму желтых ячеек в столбце. Очевидно, что для нахождения решения нужно потребовать,чтобы эти суммы были равны 1.

Если задавать не единое разрешенное количество заходов в каждую точку (1 заход и 1 выход), а сравнивать число заходов с ячейками

, то можно выключать какие-то пункты посещения из списка просто обнулив число заходов в них

. Только следует учесть, что обнулять нужно и заход, и выход, т. е. суммы по вертикали и по горизонтали для выбранного пункта.

Таблица переменных в файле 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 км!
А на карте решение выглядит так:

Это решение, конечно, лучше предыдущего, но мы хотим найти единственный замкнутый маршрут!

Создаем таблицу специальных ограничений.

Для создания связанного маршрута мусоровоза добавим таблицу Специальных ограничений, в которой введем поле с новыми переменными (переменные находятся в

ячейках). Эти переменные будут определять порядок посещения точек по замкнутому маршруту. Сначала этот порядок можно задать произвольно, указав для начальной точки значение 0.

Ячейки
внизу таблицы дублируют значения
желтого столбца.

Обратите внимание, что требуется не просто преобразовать
- столбец в
- строку, но и связать их формулой. Для этого в MS Excel используется функция ТРАНСП()
В ячейках
записаны параметры ограничений:
за выключением начального пункта п01у нас 22 пункта посещения, между которыми будет 21 (=22-1) связь. (Еще две связи из 23-х, это участки п01-X и X-п01, очевидно.)
В ячейки
должна быть введена формула, связывающая ячейки Таблицы специальных ограничений с ячейками Таблицы переменных

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

Связываем таблицу специальных ограничений и таблицу переменных.

Проиллюстрируем формулу, которая должна быть введена в каждую

ячейку Таблицы специальных ограничений.

Формулу не нужно вводить в строку, с которой начинается путь ( строка n01)
Ссылка на ячейку
C
должна быть неизменной в любой
ячейке Таблицы специальных ограничений.
При протягивании формулы вдоль строки вправо ссылка на ячейку
A
не меняется, а ссылки на ячеки
D
и
B
перемещаются также вдоль своих строк вправо.
При протягивании формулы вниз по столбцу ссылка на ячейку
A
также перемещается вниз по желтому столбцу, ссылка на ячеку
B
остается неизменной, а ссылка на ячеку
D
перемещаются также вниз по соответствующему столбцу.

В файле 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 для нахождения оптимального решения.

цель: найти самый короткий маршрут - значение ячейки $AB$29 должно быть минимальным;
переменные в задаче - это желтые ячейки в таблице переменных и желтые ячейки в таблице специальных ограничений
$E$33:$AA$55; $AB$60:$AB$82
ограничения задачи:
- переменные из таблицы переменных должны быть бинарными -
  $E$33:$AA$55 bin
- переменные из таблицы специальных ограничений должны быть целыми -
  $AB$60:$AB$82 int
  
  Это необязательное ограничение. Алгоритмы OpenSolver работают лучше, если это ограничение не вводить. При вводе данного ограничения искомый маршрут получается длиннее.
- суммы выездов из пунктов посещения и суммы въездов в каждый из них равны заданному числу -
  $AB$33:$AB$55 = $AC$33:$AC$55
  $E$56:$AA$56 = $E$57:$AA$57
- условие, запрещающее короткие циклы
  $E$61:$AA$82 <= $AD$58

Фактически это ограничение означает выполнение неравенства 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 отличаться от порядкового номера выезда

Именно выполнение этих ограничений приводит к тому, что номера посещения идут подряд, без пропусков.

После запуска Solver получим решение

В решении найден маршрут, длина которого 88,54 км. Порядок посещения точек можно определить по единичкам в таблице переменных: п01-п07-п16-п11…
Маршрут на карте:

Следует отметить, что целочисленная оптимизация не дает гарантированного наилучшего результата. Почти всегда имеет смысл попробовать провести оптимизацию с более высокой точностью и оценить возможную разницу.
Для этого щелкнем в модели задачи 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).
Протягиваем формулу до конца таблицы. Таблица будет иметь следующий вид:

В ячейку AG60 вводим формулу
=ВПР($AI60;$A$6:$D$28;3)
так как значения X-координаты записаны в 3 столбце таблицы расстояний, то просто поменяем 2 на 3 в формуле, которую мы использовали для заполнения столбца имя
протянем эту формулу вниз. Все x координаты попали в нашу динамическую таблицу

В ячейку AH введем формулу
=ВПР($AI60;$A$6:$D$28;4).
Протянем эту формулу до конца таблицы

По столбцам X и Y добавляем в имеющуюся диаграмму (щелчок правой кнопкой в диаграмме – Выбрать данные – Добавить) дублирующий набор данных AG60:AH83 с маркерами и линиями и подписи из столбца AF60:AF83. Так как все данные этой таблицы считываются с соответствующих ячеек, то при изменнении решения будут меняться, а диаграмма автоматически перерисовываться.
Получен довольно удобный шаблон построения диаграммы.

1