Хабр·Russia·Tuesday, September 15, 2026 at 07:04 AM

Спецтехника по объектам. При чем тут комбинаторика?

Translate

Lozkins21 минуту назад

Краны, экскаваторы, самосвалы, погрузчики — достаточно редко увидишь такую технику на дорогах общего пользования. Эта техника не ездит по расписанию, а «скачет» между объектами в окрестностях города. Цена плохого решения в распределении такой спецтехники считается не минутами простоя, а сотнями тысяч рублей на перегонах и упущенными возможностями по заказам.

Разберём, как с помощью точных методов мат. моделирования (MIP, CP-SAT) собрать систему распределения парка по заказам, которая не гоняет технику через весь город и может закрыть почти на 19% больше заказов, чем жадная логика «бери ближайшую заявку».

Материал будет полезен специалистам по математической оптимизации и разработчикам, которые ищут очередной практический кейс MIP/CP-SAT (будут тонкости). А диспетчерам и управленцам компаний-арендодателей спецтехники, возможно, будет интересно узнать, во сколько на самом деле обходится распределение «на глаз».

Что решаем?

Крупные проекты по строительству объектов (жилая, коммерческая недвижимость или дорожное строительство) или задачи в сельскохозяйственной промышленности используют спецтехнику. Такая техника предназначена для крупных/объёмных работ. Думаю, многие видели на стройках большие строительные краны, экскаваторы, самосвалы; в полях комбайны, тракторы, опрыскиватели, сеялки и другую технику. Нас будет интересовать — как она там оказалась. Сузим область до строительной спецтехники.

Начнём с того, что спецтехника — это не личный авто, которым один человек или семья пользуется ежедневно. Зачастую это точечный спрос на определённых этапах реализации проекта. Крупные компании с большим портфелем объектов на разных стадиях их реализации могут позволить себе содержать небольшой парк спецтехники, и это экономически разумно. В других ситуациях это нецелесообразно исходя из экономики или необходимости содержания и обслуживания. Поэтому существуют компании типа «СпецТехШеринг», которые предоставляют услуги аренды и операторов этой техники. Далее о задачах таких компаний.

Допустим, мы «СпецТехШеринг» с парком 40–50 единиц различной техники. Нам удалось собрать определённый пул заявок (заказов) на аренду спецтехники. Заявки разбросаны по разным локациям города и временным окнам. Некоторые типы спецтехники могут добираться своим ходом (автокран, самосвал, колёсный погрузчик — у них есть колёса и допуск на дороги общего пользования), некоторые нужно перевозить на трале (гусеничный экскаватор, гусеничный кран: скорость своим ходом ~3–5 км/ч, портят асфальт гусеницами, не имеют допуска на дороги общего пользования).

Подошли вплотную к одной из значимых задач компании «СпецТехШеринг»: грамотное распределение техники по заявкам. От этого решения зависят затраты на перегон, простои техники и объём выполненных заказов. Есть и другие важные задачи и статьи затрат: амортизация, ремонт, зарплаты операторам, но с точки зрения методов оптимизации — наибольший потенциал кроется в перегонах и назначениях.

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

P.S. Упоминал про тралы — они тоже спецтехника. Возникает дополнительная задача эффективной маршрутизации тралов — задача в задаче. К вашему разочарованию, это усложнение задачи мы опустим.

Что по данным

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

Заявки

Набор заявок/заказов/работ — это то, для чего содержится весь парк спецтехники и почему «СпецТехШеринг» вообще существует. В таблице приведу параметры, которые характеризуют заявку.

Параметр	Описание
order_id	идентификатор заявки. Две строки с одинаковым order_id — это один комбинированный заказ
required_type	требуемый тип спецтехники. В спецификацию техники вдаваться не будем, рассмотрим известные детям: экскаватор, кран, погрузчик, самосвал
min_capacity_class	требуемый класс спецтехники (меньше нельзя, больше можно)
location	идентификатор адреса объекта по заявке (ссылка на таблицу с адресами)
time_window_start	время начала подачи техники по заявке
time_window_end	крайне правое время подачи техники по заявке
duration_hours	длительность работ по заявке (в часах)
is_mandatory	метка, является заказ обязательным

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

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

По некоторым заявкам может требоваться несколько единиц разной техники одновременно (например, экскаватор + самосвал) — это комбинированные заказы. В данных они представлены двумя (или более) строками с одинаковым order_id: у каждой строки свой required_type, остальные параметры (локация, окно, длительность, обязательность) одинаковые. Для выполнения такого заказа нужно подать все связанные строки сразу, отдельной единицей техники на каждую.

География заказов в разрезе типа спецтехники. Размер окружности отражает кол-во заявок в этой локации.

Отмечу ещё одно упрощение, иногда целесообразно привлекать парк конкурентов для закрытия сервисных заявок (например, в пик спроса, когда своего парка недостаточно). Продолжаем упрощать и здесь.

Парк

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

Параметр	Описание
equipment_id	уникальный идентификатор спецтехники
type	тип спецтехники (экскаватор, кран, погрузчик, самосвал)
capacity_class	класс спецтехники (лёгкая, средняя, тяжёлая)
depot_location	идентификатор адреса текущего или прогнозного высвобождения техники
available_from	время начала доступности техники для использования по заявкам
available_until	доступность техники в планируемом периоде

Другие

Также потребуется матрица затрат на перегон и матрица длительностей перемещения между техникой и заявками. Расстояние как таковое модели не нужно — оно участвовало только на этапе получения этих двух матриц (тариф на перегон и оценка времени в пути), а дальше в задаче используются уже готовые $c_{o_1o_2}$ (затраты на перегон) и $\tau(i,j)$ (время перегона).

Откуда данные?

Данные — синтетика. Взял в основу средний размер компании с парком в 40 единиц техники; 150 заказов, из которых 96 обязательных, горизонт планирования: 4 дня. Набор данных для экспериментов положил сюда.

Моделирование

Классы техники, обязательные и комбинированные заявки — это факторы, которые создают комбинаторную задачу. Если их убрать, то жадное распределение техники будет совпадать с оптимальным. Жизнь заставляет усложнять задачу, за этим тянется и усложнение поиска решения.

В качестве инструмента решения задачи подойдёт как целочисленное линейное программирование, так и программирование в ограничениях; можно пойти через VRP, но здесь уже придётся поколдовать. Ранее уже рассматривал CP-SAT солвер, Pyomo + SCIP, PuLP + SCIP; в этот раз попробуем новый open source MIP солвер HiGHS с нативным API.

Добавим спецэффектов. Чтобы почувствовать «Оптимальное решение», аргументация «для решения используются точные математические методы» не убедительна. Поэтому предлагаю параллельно в качестве baseline алгоритма рассмотреть жадный алгоритм: ставим на ближайшую заявку. Это позволит почувствовать «оптимальность».

MIP постановка

Сформулируем задачу. Здесь структурировано пропишу правила/ограничения и их математический эквивалент в виде формул.

В данных по заявкам есть поле is_mandatory. Эта метка подсвечивает уровень обязательств компании перед клиентом. Если моделировать обязательные заявки строгим ограничением на выполнение, то можем поймать infeasible (неразрешимость задачи). Такой сценарий данных легко может получиться, например, когда недостаточно собственного парка для выполнения всех заявок. Такие обязательства моделируются через штрафную функцию (мягкое ограничение).

Выделю два пути моделирования: задача о покрытии множества или потоковая задача. Немного прокомментирую оба пути ниже.

Задача о покрытии множества. Если сгенерировать все допустимые маршруты техники по заявкам, тогда задача будет заключаться в выборе оптимальных маршрутов. А это уже позволяет сформулировать задачу как максимизацию покрытия заявок и минимизацию затрат на перемещение. Вопрос: получится ли сгенерировать все маршруты? Выглядит, что много памяти потребуется. Можно алгоритм генерации столбцов применить — запомним как альтернативу.

Потоковая (сетевая) постановка Заявки — это узлы сети во времени (time-space network), а возможные переброски техники между заявками — это рёбра. Баланс входа и выхода из узлов будет основным связующим ограничением перетекания техники из узла в узел (от заявки к заявке). Целевая функция в терминах рёбер будет выглядеть как максимизация кол-ва рёбер (перебросы техники на заявки) и минимизация суммарной длины активированных рёбер. Однако окна подачи по заявкам мешают воспользоваться этой концепцией напрямую. Поэтому далее буду указывать «модель с элементами потоковой постановки».

В текущем сценарии набора данных (кол-во техники, расслоение техники по типам и классам, кол-во заявок) оба варианта подходов справятся с задачей. Но второй вариант будет более элегантным и простым в реализации. Посмотрим, как будет выглядеть модель.

Индексы

Обозначение	Смысл
$o \in O$	множество всех заказов
$e \in E$	множество всех единиц техники
$t \in T$	множество типов техники: `{excavator, crane, loader, dump_truck}`
$E_t \subseteq E$	единицы техники типа
$k \in K$	множество классов техники: `[light, medium, heavy]`
$E_o \subseteq E$	единицы техники, которые удовлетворяют условиям заказа
$O_e \subseteq O$	набор заказов, которые могут быть выполнены единицей техники

Постоянные

Обозначение	Смысл
	время перегона техники между локациями и в часах
	длительность работ по заказу
	затраты на перегон техники с заказа на заказ
$m_{o}$	вес в целевой функции за выполнение заказа
$a^{s}_e, a^{e}_e$	окно доступности единицы техники
	окно подачи техники по заказу

Переменные

Переменная	Тип	Область определения
$x_{eo}$	бинарная	индикатор назначения техники на заявку; принимает значение 1, если единица выполняет заказ
$u_{eo}$	бинарная	индикатор назначения первой работы (нужно для отсчёта); принимает значение 1, если — первая работа единицы
$y_{eo_1o_2}$	бинарная	индикатор последовательности выполнения заказов; принимает значение 1, если единица выполняет сразу после
	непрерывная	время начала работ по заказу

Ограничения

1. Не более одной единицы техники на (строку) заказа — для комбинированного заказа это ограничение действует на каждую его строку отдельно, а не на заказ в целом:

$\sum_{e \in E_o} x_{eo} \le 1, \quad \forall o \in O$

2. У спецтехники может быть не более одной «первой работы»:

$\sum_{o \in O_e} u_{eo} \le 1, \quad \forall e \in E$

3. Балансирование назначений на заявки. Заказ $o \in O_{e}$ может быть первым у единицы , либо продолжает работу с предыдущей заявки $o' \in O_e$ , либо не выполняет этот заказ вообще:

$u_{eo} + \sum_{o' \in O_e} y_{eo'o} = x_{eo}, \quad \forall e \in E, o \in O_e$

4. Баланс входа и выхода. Не более одного заказа после выполнения текущего:

$\sum_{o' \in O_e} y_{eoo'} \le x_{eo}, \quad \forall e \in E, o \in O_e$

5. Планируемая цепочка работ должна завершиться в окне доступности техники. Так как у нас есть переменные времени начала выполнения заявок и есть переменные-индикаторы кто выполняет заявку, то можем сформировать следующее ограничение с выключателем. Если не назначен на заказ , тогда ограничение всегда будет выполняться (благодаря ):

$s_o + d_o \le a^{e}_e + M(1-x_{eo}), \quad \forall e \in E, o \in O_e$

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

$s_{o_2} \ge s_{o_1} + d_{o_1} + \tau(o_1, o_2) - M(1-y_{eo_1o_2}), \quad \forall e \in E, o_1, o_2 \in O_e$

7. Инициализация времени начала выполнения «первой» заявки:

$s_o \ge a^{s}_e + \tau(e, o) - M(1-u_{eo}), \quad \forall e \in E, o \in O_e$

8. Для комбинированных заказов добавим два типа ограничений: одинаковый статус выполнения заказов и одинаковое время начала выполнения заказа. Множество — пары строк с одинаковым order_id (собирается напрямую из входных данных, отдельного справочника пар не нужно):

$\sum_{e \in E} x_{eo_1} = \sum_{e \in E} x_{eo_2}, \quad \forall (o_1, o_2) \in Comb$ $s_{o_1} = s_{o_2}, \quad \forall (o_1, o_2) \in Comb$

9. Ограничения окна начала выполнения заказа:

$s_o \in [w^s_o, w^e_o - d_o]$

Отдельный нюанс — вес в целевой функции (см. ниже): если считать его для каждой строки комбинированного заказа, один и тот же реальный заказ засчитается в ЦФ несколько раз. (8) и так гарантирует, что строки заказа выполняются только вместе — поэтому у всех строк заказа, кроме одной, занулён.

Целевая функция

Целевая функция (ЦФ) имеет несколько критериев. Выполнение сервисного обязательства редко удаётся привести в экономику (оценка штрафов, потеря клиента как дополнительный риск, репутационные риски и т.п.). В нашей задаче выстраивается следующий приоритет из критериев: обязательные заказы → спотовые заказы → затраты. Целесообразность забирать спотовый заказ можно перевести в экономику (через ожидаемую выручку), но мы не будем расширяться в этом направлении. Заведомо считаем, что спотовый заказ выгоден (невыгодные оставили за рамками входных данных).

Упомянутые критерии можно учесть жёстко: последовательно считать задачу для ЦФ согласно приоритету, затем фиксировать её значение через ограничение «не хуже» в следующем запуске.

Мы пойдём через общий котёл: все показатели в одну ЦФ закинем. Это позволительно делать, если сбалансировать веса показателей.

$\max Z = \underbrace{\sum_{e \in E}\sum_{o \in O} m_o x_{eo}}_{\text{выполненные заказы}} - \underbrace{\sum_{e \in E}\sum_{o \in O} c_{eo} u_{eo}}_{\text{перегон к первой работе}} - \underbrace{\sum_{e \in E}\sum_{o_1 \in O} \sum_{o_2 \in O} c_{o_1o_2} y_{eo_1o_2}}_{\text{перегон между заказами}}$

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

Некоторые рассуждения

Потоковая модель — очень хороший вариант типовой модели, но у нашей модели из-за ограничений (1) и (2) теряется целочисленная LP-релаксация (вышли за рамки полной унимодулярности). Поэтому решение расслабленной задачи не совпадает с целочисленным решением (разве что выиграли в лотерею). Придётся честно считать branch-and-bound.

Представление заявок в виде узлов, а перегоны в качестве рёбер — способ объяснить работу модели. Но это не потоковая постановка в чистом виде, скорее VRPTW (Vehicle Routing Problem with Time Windows) с элементами потоковой структуры.

Думаю достаточно рассуждений, предлагаю перейти к расчётам. Далее: насколько жадный уступает точному решению, и почему для задачи подходит CP-SAT, и как мы к этому пришли.

Что получилось?

Моделирование проводил в Python с использованием MIP решателя HiGHS. Если взглянуть на ранее сформулированную математическую задачу, бросаются в глаза ограничения типа переключатель 5–7. Такого рода ограничения эффективнее моделировать в концепции программирования в ограничениях (OnlyEnforceIf, NoOverlap). Поэтому предлагаю ещё одну реализацию рассмотреть с использованием OR-Tools CP-SAT солвера. Тем более что мат. постановка практически не меняется. Код решения здесь.

Посмотрим на свод по входным данным:

Метрика	Значение
Всего заказов	150
— обязательных	96
— опциональных	54
— комбинированных (2 типа техники)	24
Всего техники	40
— excavator	16
— loader	10
— crane	8
— dump_truck	6

Расчёты провёл для жадного алгоритма, MIP (HiGHS) и CP-SAT. Замерил основные метрики по результатам каждого расчета.

Метрика	Greedy	CP-SAT	MIP (HiGHS)
Выполнено заказов, шт.	114	142	142
Выполнено заказов, %	76.0	94.7	94.7
из них обязательных, шт.	90	94	94
Затраты на перегон, ₽	923242.4	995334.4	995334.4
Затраты на 1 заказ, ₽	8098.62	7009.4	7009.4
Время решения, с	0.2	16.26	60.0
Статус	—	Optimal	Optimal

Вот здесь можно наблюдать «оптимальность». Жадный алгоритм упустил 28 заказов (в том числе 4 обязательных) по сравнению с доказанным оптимальным решением.

Маршруты для самосвалов. Решение жадного алгоритма (слева) и решение MIP. Один и тот же парк выполняет 23 против 34 заявки, соответственно.

В случае MIP/CP-SAT есть невыполненные заказы — это обусловлено недостаточностью парка для закрытия пиковых нагрузок. Ниже на диаграмме отображена нагрузка на парк в разрезе техники по окнам подачи на заявки (верхняя граница нагрузки). Окна заявки однозначно не позволяют определить спрос в конкретный момент времени, поэтому добавил слой диаграммы как спрос закрывает MIP (HiGHS) решение (понять, где точно упёрлись в парк).

Оценка нагрузки на парк по окнам заявок; загрузка парка исходя из MIP решения; доступное кол-во парка с учетом окон работы техники

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

Заказ	Тип техники	Класс	Окно, с (ч)	Окно, по (ч)	Длительность, ч	Обязательный
ORD-066	погрузчик	средний	82.8	96.0	8.0	да
ORD-103	кран + погрузчик	средний + средний	84.5	91.9	7.0	да
ORD-047	самосвал + экскаватор	тяжёлый + тяжёлый	80.7	88.0	6.0	нет
ORD-006	погрузчик	тяжёлый	81.6	90.1	7.0	нет
ORD-018	погрузчик	тяжёлый	81.9	95.9	7.0	нет
ORD-095	самосвал + экскаватор	лёгкий + лёгкий	82.3	96.0	8.0	нет
ORD-085	погрузчик	лёгкий	82.5	96.0	9.0	нет
ORD-038	самосвал	лёгкий	83.4	96.0	8.0	нет

Период пика выпал на промежуток с 82–95 час. Слетели три (2+1) заявки с участием самосвалов и пять (1+4) заявок с погрузчиками. Эту информацию можно использовать для принятия решения:

увеличить окно доступности погрузчиков (позволит закрыть несколько дополнительных заявок);
обсудить сдвиг окон заявки с заказчиком (особенно с сервисными клиентами);
найти на рынке недостающие ресурсы.

MIP vs CP-SAT? Оба солвера получили одинаковые решения, но CP-SAT сделал это быстрее ~4x. Это не потому что CP-SAT лучше в целом, а потому что часть ограничений (5–7, disjunctive-ограничениями) более естественно ложатся в концепцию парадигмы программирования в ограничениях.

Заключение

Задача о назначениях, объединённая с маршрутизацией, порождает новый кластер задач, который требует отдельные адаптированные алгоритмы. В статье рассмотрел практический вариант такой задачи применительно к маршрутизации спецтехники на строительные объекты.

Рассмотрел три варианта решения задачи: жадный алгоритм, целочисленное линейное программирование (MIP) и программирование в ограничениях (CP). Что-то отработало быстрее, что-то качественнее, а CP и то и другое.

Затронул вопрос «оптимальности»: в чём заключается эффект от применения математической оптимизации (MIP/CP-SAT) в процессах компании. В рамках моего эксперимента эффект получился в 28 дополнительно выполненных заявках, что составляет почти +19% и сокращение пробега на выполнение одной заявки на -13%.

View the original on Хабр →

KioskNews shows a cleaned-up reading view extracted from the publisher’s page — the original always lives on their site, not ours.