Будем рассматривать решение этой задачи на базе тех знаний и допущений, которые мы обсуждали на странице Построй маршрут. Все пункты расположены на участке размером 20х20 км.

1

Таблица расстояний задачи построения маршрута для двух мусоровозов.

Примем, что мусоровозы выезжают из одного и того же пункта – с точки зрения практической ситуации это вполне реалистическое предположение. Для этого совместим пункты п01 и п02 по координатам: оба пункта будут располагаться в точке (X=0, Y=0).
Расстояния между n01 и n02 примем равным 10000, чтобы эффективно запретить маршрут между ними.

Создадим Таблицу расстояний для решения задачи.
Для этого смоделируем координаты 22 точек посещения датчиком случайных чисел и вычислим расстояния между этими точками посещения.

Получим примерно такую Таблицу расстояний:

2

Таблица переменных задачи построения маршрутов двух мусоровозов.

Таблица переменных будет такой же, как мы рассматривали ранее

Желтое поле - ячейки
и оранжевые ячейки
- это область переменных. Именно эти ячейки мы будем указывать в качестве переменных в установках OpenSolver
Значения оранжевых ячеек
- при решении задачи всегда будут равны 0.

3

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

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

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

n01

второй подмаршрут начнется из точки n02. Поэтому, если точка n02 окажется в середине общего маршрута, ее номер посещения будет 11 или около того.
Используя соображение, сформулированное в предыдущем пункте, зададим нижнюю и верхнюю границы для номера посещения n02:
min=10 и max=12

В этом случае состав маршрутов будет различаться не более чем на 1-2 пункта.

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

4

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

Теперь все готово для решения задачи. Будем искать оптимальное решение с помощью OpenSolver.

цель по-прежнему: найти самый короткий маршрут - значение ячейки $AB$29 должно быть минимальным;
все те же переменные в задаче - желтые ячейки в таблице переменных и желтые ячейки в таблице специальных ограничений
$E$33:$AA$55; $AB$60:$AB$82
ограничения задачи:
- переменные из таблицы переменных должны быть бинарными (принимать значение 0 или 1 -
  $E$33:$AA$55 bin
- суммы выездов из пунктов посещения и суммы въездов в каждый из них равны заданному числу -
  $AB$33:$AB$55 = $AC$33:$AC$55
  $E$56:$AA$56 = $E$57:$AA$57
- точка n02 должна быть в середине общего маршрута:
  $AB$61 >= $AD$60
  $AB$61 <= $AD$61
- условие, запрещающее короткие циклы
  $E$61:$AA$82 <= $AD$58
- ограничим переменные AB60:AB82 сверху
  $AB$60:$AB$82 <= $AC$58.
  
  Если этого не сделать, то оптимизатор найдет решение для одного связного маршрута: начнет отсчет от точки n02, присвоив ей значение, например, 10, а остальные номера будет отсчитывать от этого значения так, что последняя точка посещения будет иметь номер 33.

Введенные ограничения на панели OpenSolver-Model

5

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

После запуска OpenSolver выдаст решение, вычислит суммарный маршрут 107,33 км, длины каждого подмаршрута при оптимизации в нашей модели не вычисляются:

Таблица переменных с решением для двух машин

На карте решение выглядит так:

Для сравнения приведу маршрут, который получится, если убрать условие, что точка n02 должна быть в середине участка:

На картинке с одиночным маршрутом из-за фактического запрета участка n01-n02 возникает аппендикс n01-n10-n02, в иных условиях невыгодный, но суммарная длина этого маршрута - 99,49 км, что меньше, чем суммарная длина маршрута, найденного для двух мусоровозов. Как и можно было ожидать, добавление ограничений удлиняет общий путь, но при новой постановке маршрута более равномерная нагрузка важнее, чем увеличение пробега на 8%.

6

Можно ли изменить решение задачи оптимального маршрута для двух мусоровозов?

В решении с двумя маршрутами номер пункта n02 оказался равным 12 (при нумерации с 0!). Уменьшим верхнюю границу номера точки n02 до 11 (max= 11).
OpenSolver находит решение, однако длительность поиска этого оптимального решения значительно возрастает.

Если для маршрута одной машины решение находится за 1 сек даже с умолчальным солвером CBC, то первый маршрут на две машины оптимизируется 35 сек, а последний маршрут с более равными подмаршрутами требует уже более 35 минут расчетов.

При таких условиях подмаршруты меняются довольно радикально, при очень небольшом возрастании суммарной длины (107,68 км).

7

Оптимальный маршрут для трех мусоровозов.

В свете рассмотренного варианта с двумя машинами имеет смысл обсудить решения с тремя и более машинами, чтобы обобщить задачу.
Рассмотрим вариант задачи из 28 пунктов посещения. Для решения использовался солвер от Gurobi, так как оптимизация получается более сложной.
Итак, используем сразу три совпадающих пункта n01, n02 и n03 для моделирования подмаршрутов трех мусоровозов. Причем, для разнообразия, расположим исходный пункт в центре района (X=10 и Y=10). Наверное, для мусоровоза это не особенно реалистично, но для многих других случаев обхода точек обслуживания – вполне реальная ситуация.

Таблица расстояний для задачи построения маршрутов трех мусоровозов:

Таблица расстояний с 30 пунктами посещения

Подготовим таблицу переменных:

Таблица переменных для задачи с 30 пунктами посещения

Таблица специальных ограничений:

Решение с одним маршрутом.

Для получения решения с одним маршрутом (в качестве маршрута сравнения) выключим пункты n02 и n03 из обхода, записав 0 в ячейки AJ41 и AJ42. Вместе с ними нулевые значения должны получить и ячейки F71 и G71.

Таблица переменных для задачи с 30 пунктами посещения с выключенными точками n02 и n03

В установках OpenSolver ничего не меняем и для одиночного маршрута получаем следующее решение.

Длина найденного маршрута - 89,98 км

Решение с маршрутом для двух машин.

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

Таблица переменных для задачи с 30 пунктами посещения с выключенной точкой n02

Присвоение номера 14 посещения точки n02 в Таблице специальных ограничений

Добавляем в установки OpenSolver ограничения для n02:
AI75<=AK75 и AI75>=AK74,
где и нижнюю и верхнюю границу для номера в очереди посещений пункта n02 зададим равными 14.
Важно не забыть добавить требование, что все номера посещений не должны превышать 29 (при нумерации от 0 до 29):
AI74:AI103<= AI72.
Установки OpenSolver-Model:

Установки OpenSolver-Model для 30 точек посещения и двух маршрутов

Тогда для двух вариантов решения задачи получим следующую картину:

Как и в предыдущих случаях суммарная длина маршрута подрастает от 89,98 км до 95,85км.

Если чуть ослабить ограничение на номер n02 в порядке обхода и задать минимум 10 и максимум 18, решение изменится

В этом случае длина маршрута уменьшится до 94,94 км

Решение с маршрутом для трех машин.

Теперь модифицируем модель для получения варианта с тремя машинами.
Во-первых, разрешим посещение и пункта n02 и пункта n03 в столбце AJ.
Для обоих пунктов n02 и n03 нужно задать допустимые номера в очереди.
Заведомо ясно, что при равномерном распределении точек посещения по маршрутам номера посещения n02 и n03 должны быть около 10 и 20 соответственно. Зададим в столбце AK минимальные и максимальные номера как 9-10 и 19-20.

Таблица специальных огранияений для маршрута из 27 точек и трех машин

Добавим ограничения в установки OpenSolver.

Установки OpenSolver для 3 машин и маршрута из 27 точек

В результате оптимизации получим следующий вариант решения. Суммарная длина маршрута - 102,03км

Изменим немного границы для n02 и n03.
Пусть n02 имеет номер посещения больше 8, но меньше 11. А точка n03 - больше 18 и меньше 21.
Получим новый маршрут, длина которого 101,16 км:

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

1. Дублируем исходный пункт столько раз, сколько у нас серверов минус 1.

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

3. Требуем, чтобы все номера посещения в соответствующем столбце были не больше полного числа точек минус 1.