1

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

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

Таблица расстояний для этой задачи:

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

Подробно о том, как это сделать читайте на странице Построй маршрут

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

Если в настройках OpenSolver на вкладке Options... изменить значение Branch and Bound Tolerance на 0,1%, то получим новое решение

2

Замена одних точек маршрута другими

замените координаты выбранных точек новыми;
расстояния между точками пересчитаются автоматически;

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

3

Несимметричные маршруты

Может оказаться, что на местности имеются дороги с односторонним движением или какая-то сложная дорожная разметка, из-за чего некоторые маршруты от А к Б и от Б к А не совпадают по длительности.
В этом случае достаточно отразить это обстоятельство в таблице расстояний, сделав ее не симметричной.
Например, пусть расстояние от точки n02 до точки n05 6,5 км, а от точки n05 до точки n02 - 10,2 км. Тогда в синем поле таблицы расстояний в строке n05 для столбца n02 поставьте значение 10,2

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

4

Запрет отдельных участков маршрута.

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

Запретим в нашей задаче участок n01-n10. Это значит, что переменные в соответствующих строках и столбцах таблицы переменных должны быть равны 0.

Чтобы добиться нулевых значений в конкретных ячейках таблицы переменных, нужно в настройках OpenSolver-Model потребовать это явно.

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

В результате оптимизации получим новое решение с длиной маршрута 91,45 км

Разумеется, добавление ограничений всегда ухудшает целевую функцию.
Но это справедливо только тогда, когда оптимальное решение дествительно найдено.
При целочисленной оптимизации это не всегда так. Мы в обсуждении параметра tolerance могли видеть, что уменьшение tolerance с 5% до 0.1% для этого же набора пунктов посещения немного изменяет оптимальный маршрут с уменьшением его длины.
Нетрудно представить себе ситуацию, когда дополнительное ограничение приведет к нахождению более короткого маршрута именно потому, что наилучшее решение не было найдено при заданном уровне точности поиска tolerance. Если так произошло, просто знайте, что в исходном решении оптимум не был достигнут.

5

Отключение отдельных точек посещения.

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

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

Возможность отключения точек позволяет использовать один и тот же шаблон задачи с заведомо бОльшим, чем обычно требуется, количеством пунктов посещения, часть которых отключена.
При этом не требуется при каждом изменении количества точек посещения перестраивать задачу, что нудобно и не вносит ошибки в отлаженную модель.
Разумеется, при отключении части пунктов длина маршрута уменьшается.

6

Посещение каких-то точек раньше других.

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

Поэтому можно наложить ограничения прямо на переменные в этом столбце в установках OpenSolver-Model. Но поскольку любой маршрут фактически может быть получен и с прямым и с обратным порядком посещения, то при задании ограничения на пару пунктов максимум, что изменится - солвер предложит обратный порядок прохождения маршрута и условие выполнится.
Так что проверять работу подобных условий имеет смысл задавая не менее двух пар пунктов. Потребуем, например, чтобы n15 и n18 были посещены раньше, чем n07.
Установки OpenSolver-Model:

Ограничения OpenSolver-Model для задачи посещения одних пунктов раньше других

Получим решение

Все изложенные выше модели вы найдете в файле:

Скачать файл "garbage_truck_route 2.xlsx" (примерно 166 Кб)

модель решения задачи с 23 точками посещения, tolerance=5%
модель решения задачи с 23 точками посещения, tolerance=1%
модель решения задачи с запрещением прямого маршрута между точками n01 и n10, tolerance=5%
модель решения задачи с отключенными точками посещения n02, n19 и n20, tolerance=5%
модель решения задачи с требованием посетить точки n15, n18 раньше точки n07, tolerance=5%