Перейти к основному содержимому

Модель маршрутизации

Модель маршрутизации предназначена для построения оптимальных маршрутов на графе узлов: классической задачи коммивояжёра (TSP), задачи о маршрутах транспортных средств (VRP) и её расширений — мульти-депо, грузоподъёмность, временные окна, погрузка-доставка, дизъюнкции. Решатель самостоятельно подбирает порядок объезда узлов и распределяет их между транспортными средствами так, чтобы итоговая стоимость всех маршрутов была минимальной.

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

Жизненный цикл модели — три этапа: Построитель параметров → Модель → Решение. Через построитель добавляются узлы и транспортные средства; затем создаётся объект модели, в который через менеджеры добавляются транзиты, ресурсы, ограничения, целевая функция; затем модель решается.

Область применения​

Модель подходит для задач, в которых нужно объехать множество точек одной или несколькими «единицами доставки» при наличии ограничений на ресурсы и порядок обхода. Типовые сценарии:

  • Логистика доставки: распределение заказов между курьерами или машинами с учётом грузоподъёмности и временных окон;
  • Выездное обслуживание: построение маршрутов для бригад с учётом длительности визитов и графика клиентов;
  • Инкассация и сбор: объезд точек выгрузки/загрузки с ограничением на количество остановок или общее время;
  • Сервисные обходы: техническое обслуживание оборудования, отбор проб, проверка торговых точек;
  • Сборные перевозки: погрузка груза в одной точке и доставка в другую одной и той же машиной.

Типовые задачи​

Задача коммивояжёра (TSP)​

Один маршрут, начинается и заканчивается в одной точке, обходит все остальные точки ровно один раз. Минимизируется общая длина (или стоимость) маршрута. В терминах модели — одно транспортное средство и одна стоимостная матрица.

Задача о маршрутах транспортных средств (VRP)​

Несколько транспортных средств обслуживают множество клиентов. Каждый клиент посещается ровно одним транспортным средством и ровно один раз. Минимизируется суммарная стоимость всех маршрутов.

VRP с грузоподъёмностью (CVRP)​

К базовому VRP добавляется ограничение: суммарный вес/объём заказов на одном маршруте не должен превышать ёмкость транспортного средства. Реализуется через ресурс с ёмкостью.

VRP с временными окнами (VRPTW)​

К каждому клиенту привязан интервал допустимого времени прибытия. Транспортное средство обязано приехать в этот интервал (при необходимости — ожидать у точки до начала окна). Реализуется через ресурс «время» и жёсткие границы значения ресурса в точке маршрута.

Задача с погрузкой и доставкой (PDP)​

Заказы — пары узлов: точка погрузки и точка доставки. Оба узла одной пары должны обслуживаться одним и тем же транспортным средством, причём погрузка — раньше доставки. Часто комбинируется с грузоподъёмностью.

Задача с опциональными узлами​

Не все узлы обязательны к посещению — за пропуск узла платится штраф. Решатель сам решает, выгоднее ли «крюк» к узлу или штраф за его пропуск. Реализуется через дизъюнкции.

Глоссарий​

ТерминОпределение
УзелТочка, которую нужно посетить или которая является пунктом старта/финиша. В терминах модели — обычная позиция на графе; «депо» — это узел, на который ссылается транспортное средство.
Транспортное средствоЕдиница логистики, обходящая некоторое подмножество узлов. Имеет стартовый и конечный узел, может иметь фиксированную стоимость использования.
Построитель параметров моделиОбъект, через который собираются узлы и транспортные средства до создания модели. Возвращает готовый объект модели вызовом СоздатьМодель().
ДугаНаправленный переход из одного узла в другой. Каждой дуге соответствуют значения транзитов (приростов ресурсов) и коэффициенты целевой функции.
МаршрутПоследовательность узлов, которую обходит одно транспортное средство — от стартового узла до конечного.
Точка маршрутаПозиция в маршруте конкретного транспортного средства. Узел и точка маршрута — разные сущности: один узел-Депо порождает разные точки маршрута для каждого транспортного средства (стартовая точка ТС1, стартовая точка ТС2 и т. д.). Жёсткие границы и значения ресурсов адресуются по точкам маршрута, а не по узлам.
ТранзитПравило расчёта прироста ресурса при переходе по дуге i → j. Задаётся одной из трёх форм: матрицей (значение для каждой пары узлов), вектором (значение зависит только от исходного узла) или константой (одно значение на все дуги).
РесурсСчётчик, накапливающийся вдоль маршрута: вес груза, прошедшее время, пройденное расстояние, число остановок. Значение ресурса в конкретной точке маршрута называют «значением ресурса в точке» и адресуют через объект точки маршрута.
ВыражениеЛинейная комбинация переменных модели — основа выражений-ограничений и сложных целевых функций.
Временное окноДопустимый интервал значений ресурса «время» в точке маршрута, заданный жёсткими границами в этой точке.
Группа альтернативных узловНабор узлов, из которого обязательно посетить заданное число (по умолчанию — все, если не задана норма) или меньше; за каждый непосещённый узел платится штраф.
Пара погрузки и доставкиДва связанных узла, которые должны обслуживаться одним транспортным средством, причём погрузка — раньше доставки.

Принцип работы​

Модель собирается из нескольких слоёв описания. Топология (узлы и ТС) задаётся через построитель до создания модели, остальное — через менеджеры-аксессоры объекта модели:

  1. Топология — узлы и транспортные средства: что обходить и кто обходит. Задаётся через построитель параметров модели.
  2. Транзиты — матрицы, векторы, константы: правила расчёта приростов ресурсов при переходах между узлами.
  3. Ресурсы — какие счётчики (вес, время, расстояние, число остановок) поддерживаются на маршрутах и какие у них ёмкости и резервы ожидания.
  4. Целевая функция — коэффициенты стоимости по транзитам и ресурсам, фиксированные стоимости использования ТС, штрафы за нарушение мягких границ, балансировка нагрузки.
  5. Ограничения — какие узлы опциональны (дизъюнкции), какие узлы образуют пары погрузки-доставки, какие узлы обслуживаются только частью транспортных средств, жёсткие границы значений ресурсов в точках маршрута и выражения-ограничения.
  6. Продвинутые средства — выражения для произвольных линейных условий, интервалы для планирования внутри маршрута, переменные для прямого доступа к решающим переменным.
  7. Параметры поиска — подсказки решателю о том, как искать решение.

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

Когда использовать​

  • Если в задаче есть физическая интерпретация маршрута — последовательность точек, которые нужно объехать;
  • Если применимы понятия транспортных средств или их аналогов (курьеров, бригад, исполнителей);
  • Если ограничения естественно формулируются через накопление по маршруту (общий вес груза, прошедшее время) или через временные окна на точках маршрута;
  • Если в задаче есть погрузка-доставка, опциональные узлы со штрафом, разные ёмкости у разных машин.

Когда не использовать​

  • Если задача — чисто комбинаторная без понятия маршрута (раскраска графа, размещение, расписание сотрудников). Используйте модель ограничений;
  • Если решение — это набор количеств с дробными значениями (планирование производства, распределение ресурсов). Используйте линейные модели;
  • Если требуется выбрать оптимальный набор предметов в один контейнер без учёта порядка. Используйте задачу о рюкзаке;
  • Если задача сводится к потоку или потоку минимальной стоимости на графе без понятия «маршрут одной единицы».

Составные части модели​

Программный интерфейс​

Полное описание методов модели маршрутизации см. в разделе Программный интерфейс — Модель маршрутизации.