Логотип HCXL Масштаб задачи
Интереснее всего увидеть не как решается классическая задача коммивояжера, а как при решении можно учесть разные реалистичные дополнительные условия.
На этой странице мы рассмотрим, как учесть в нашей модели решения задачи коммивояжера различные осложнения, которые могут возникнуть в реальном бизнесе.

1

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

Рассмотрим задачу нахождения связного оптимального маршрута для точек:
Набор из 23 точек посещения. Таблица расстояний для этой задачи:
Таблица расстояний для 23 точек посещения. Подготовим таблицы переменных и таблицу специальных ограничений, внесем данные в OpenSolver - Model.
Подробно о том, как это сделать читайте на странице Построй маршрут
После запуска OpenSolver получим решение:
Маршрут для 23 точек.Расстояние 90,42 км. Если в настройках OpenSolver на вкладке Options... изменить значение Branch and Bound Tolerance на 0,1%, то получим новое решение
Маршрут для 23 точек.Расстояние 89,37 км.

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 км
Маршрут для 23 точек.Расстояние 91,45 км.
Разумеется, добавление ограничений всегда ухудшает целевую функцию.
Но это справедливо только тогда, когда оптимальное решение дествительно найдено.
При целочисленной оптимизации это не всегда так. Мы в обсуждении параметра tolerance могли видеть, что уменьшение tolerance с 5% до 0.1% для этого же набора пунктов посещения немного изменяет оптимальный маршрут с уменьшением его длины.
Нетрудно представить себе ситуацию, когда дополнительное ограничение приведет к нахождению более короткого маршрута именно потому, что наилучшее решение не было найдено при заданном уровне точности поиска tolerance. Если так произошло, просто знайте, что в исходном решении оптимум не был достигнут.

5

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

Допустим, что завтра нам не нужно посещать пункты п02, п19 и п20. Для того, чтобы исключить их из маршрута достаточно в таблице переменных в соответствующих строках и столбцах поставить 0.
Изменения в Таблице переменных для отключения трех точек посещения .
Если поставить 0, только в столбце или только в строке, то OpenSolver не найдет решения. Ведь мы запретили из этих пунктов выезжать, но требуем, чтобы маршрут в них зашел.
Если все сделано аккуратно, получим следующий маршрут.
Маршрут для 23 точек.Расстояние 86,48 км.
Возможность отключения точек позволяет использовать один и тот же шаблон задачи с заведомо бОльшим, чем обычно требуется, количеством пунктов посещения, часть которых отключена.
При этом не требуется при каждом изменении количества точек посещения перестраивать задачу, что нудобно и не вносит ошибки в отлаженную модель.
Разумеется, при отключении части пунктов длина маршрута уменьшается.

6

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

Как потребовать, чтобы в одни пункты машина заехала раньше, чем в другие?
Порядок посещения точек определяют переменные в желтом поле в таблице специальных ограничений. Маршрут для 23 точек.Расстояние 86,48 км. Поэтому можно наложить ограничения прямо на переменные в этом столбце в установках OpenSolver-Model. Но поскольку любой маршрут фактически может быть получен и с прямым и с обратным порядком посещения, то при задании ограничения на пару пунктов максимум, что изменится - солвер предложит обратный порядок прохождения маршрута и условие выполнится.
Так что проверять работу подобных условий имеет смысл задавая не менее двух пар пунктов. Потребуем, например, чтобы n15 и n18 были посещены раньше, чем n07.
Установки OpenSolver-Model:
Ограничения OpenSolver-Model для задачи посещения одних пунктов раньше других
Получим решение
Маршрут для 23 точек.Расстояние 91,14 км. Все изложенные выше модели вы найдете в файле:
Скачать файл garbage_truck_route 2.xlsx Скачать файл "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%

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