Что есть план, если ему не следуют? Системы планирования работы сотрудников представляют человека в виде последовательности операций: работа, обед, работа, сон. Иногда и того проще - оставляют без обеда. Такая саркастическая интерпретация жизни вызывает улыбку и наводит грусть.
Но в этой статье мы не будем уделять внимание сентиментам, а сосредоточимся на бездушном повествовании об одной из таких систем, а точнее - о задаче планирования графиков работы водителей на круговых маршрутах.

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

Бизнес-задача: оптимизация расписания водителей в транспортной логистике

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

Можно реализовать оптимизационную математическую модель, которая попробует сложить этот пазл перевозок в оптимальную картину (по затратам). Даже если это получится, будет ли гипотетическое решение воплотимым в жизнь?

Управленцы предприняли определённое количество попыток обуздать эту неопределённость. И кое-что из этого вышло! Что если из всех потоков выделить самые стабильные и насыщенные? Это позволит разбить исходную задачу на определённую и неопределённую (остаток) части. Причём первая будет забирать на себя бОльший объём, а вторая — бОльшую географию. Решить две задачи поменьше уже проще. По второй задаче сделаю отсылку к статье Задача о размещении хабов в сети, а первую еще немного поквантуем.

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

Пример: компания «Аэрофлот» перевозит пассажиров по направлению СПб — МСК, МСК — СПб по особому тарифу «шаттл». Какую проблему решила компания? Не нужно адаптировать расписание под часовой спрос, можно его адаптировать под ресурсы (самолёты).

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

Схема работы ТС на круговом маршруте следования
Схема работы ТС на круговом маршруте следования

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

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

Структура смены водителей
Структура смены водителей

Задача: определить минимальное количество графиков работы водителей, которые обеспечат непрерывное движение ТС на круге (направлении).

Ограничения на работу водителя из РТиО:

  • Время вождения Не более 56 часов в неделю;

  • Время вождения Не более 90 часов за две недели;

  • Межсменный отдых 11 часов;

  • Еженедельный отдых 24 часа (начинается после межсменного).

Дополнительное требование задачи — цикличность графиков работы водителей (при условии цикличности выездов ТС).

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

Данные задачи

Структура входных данных развивается параллельно развитию самого продукта-решения. Чтобы прийти к минималистичному набору данных потребовалось неоднократное переосмысление задачи.

Найм и планирование графиков работы водителей - это не решения уровня "сейчас". Согласование и внедрение графиков работы водителей долгосрочное решение с неповоротливыми механизмами типа трудового договора. Поэтому начальное состояние системы водителей не так важно и во входных данных опущено.

id

drive_time

drivers_req

dep_dir

dep_back

cycle

1

11;10;11;16;14;13

1;1;1;2;2;2

0;12

11;23

2

2

11;16;14;13

1;2;2;2

5;17

3;15

2

3

10;10;16;11;16;14;13

1;1;2;1;2;2;2

8;20

2;14

2

4

10;11;16

1;1;2

0;12

10;22

1

5

11;10;11;10;7;7;8;7;7

1;1;1;1;1;1;1;1;1

0;5;10

11;16;21

2

6

11;10;11;10

1;1;1;1

11;17;23

11;17;23

2

7

11;10;7;7;8;7;7

1;1;1;1;1;1;1

5;11;17

3;9;15

1

8

13;11

2;1

8;13;18

8;13;18

1

9

10;10;7;10;11;10;7;7;8;7;7

1;1;1;1;1;1;1;1;1;1;1

8;14;20

2;8;14

2

10

11;10;11;16;14;13

1;1;1;2;2;2

0;6;12

11;17;23

1

В таблице выше представлен набор сценариев, разберем по столбцам. Весь маршрут от пункта отправления до пункта назначения разбит на участки, каждый из которых могут преодолеть 1 или 2 водителя. Из-за географических особенностей (населенный пункт, безопасное место для стоянки) редко удается разбить маршрут на равные участки.

Время вождения между п��нктами, пересменки водителей округляются до целых часов и указываются списком в столбце drive_time, аналогичный список drivers_req задается для кол-ва водителей, требуемых на преодоление соответствующего участка. Столбцы dep_dir и dep_back содержат перечисление времен отправления ТС в прямом и обратном направлениях в сутки. Предполагается, что выходы регулярные и повторяются каждый день в течение недели. Цикличность графиков работы водителей задается в столбце cycle.

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

Мат. модели

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

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

Модель покрытия (Set Partitioning Problem)

  • Основана на выборе готовых графиков работы;

  • Эффективна при относительно небольшом количестве вариантов;

  • Гибкая к ограничениям на отдельные графики;

  • Требует предварительной генерации допустимых графиков.

Потоковая модель (Network Flow Problem)

  • Основана на построении сети потоков;

  • Позволяет учитывать динамические изменения;

  • Эффективна при сложной структуре ограничений.

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

Для бизнеса выгодно вриводить свои задачи к стандартным парадигмам математического программирования, как целочисленное программирования. Потому что часть работ снимает готовый набор алгоритмов - solver, меньше времени требуется на разработку алгоритмов поиска решения и его тестирование. Это позволяет быстрее доставлять результаты бизнесу.

Перейдем к моделям.

Модель покрытия

Модель покрытия подразумевает выбор готовых графиков работы водителей для покрытия всех планируемых работ. Основные вычисления приходятся на построение всех валидных графиков на основе планируемых работ. С ростом кол-ва участков и частоты отправки ТС экспоненциально растет кол-во валидных графиков работы.

Что из себя представляет полный набор валидных графиков работы водителей? Начало: водитель может начать свою работу в любой точке на любом участке на горизонте цикла графика. Последующие участки вождения определяются согласно локации высвобождения и времени. Кроме того, необходимо контролировать интегральные показатили общего времени работы водителя на уже созданной цепочки (время вождения за неделю и за 2 недели, еженедельный отдых в графике). Дополнительно - цикличность графика, т.е. по завершению цикла водитель должен оказаться на участке, с которого начинал.

Генерация набора графиков происходит путем перебора вариантов. Интересны как короткие графики (например, туда-обратно), так и длинные. В процессе генерации разумно добавлять логические отсечки, например, отсекать варианты, если понимаем, что график уводит водителя далеко от начальной локации (не успеет вернуться к завершению цикла). Отсечки позволяют сократить перебор.

Целочисленное программирование используется для выбора оптимального кол-ва цепочек-графиков. Каждая цепочка соответствует графику работы одного водителя.

Индексы

i \in I - множество графиков работы водителей;

j \in J - множество работ (участков движения);

J^i - множество работ в графике i;

Постоянные

c_j - кол-во водителей, необходимых для движения на участке j;

Переменные

x_i - бинарная переменная, принимает значение 1, если график работы i выбран, 0 в противном случае;

Ограничения

  • На каждый участок назначено не менее требуемого кол-ва водителей:

\sum_{i: j \in J^i} x_i \ge c_j, \quad \forall j \in J

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

Минимизация кол-ва водителей (графиков):

\sum_i x_i →\min

Формулировка выглядит лаконичной, задачу покрытия готовые MIP solver решают влет, даже очень объемные (см. Искусство создания эффективных математических моделей). Но основная нагрузка возлагается на генерацию графиков, что порой может занимать значительное время.

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

В модели используются бинарные переменные, для общего случая лучше использовать целочисленные переменные. Один график может быть назначит нескольким водителям. Но из-за специфики набора сценариев - рассматриваются бинарные переменные. Специфика заключается в том, что в основном участки требуют одного водителя.

Потоковая модель

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

Прежде чем перейти к формулировке задачи, предлагаю уточнить несколько нюансов. Узел сети - это пара (дата и время, направление отправки ТС) согласно предопределенному расписанию движения ТС. Ребро включает в себя время движения водителя на участке + послесменный отдых. Географически ребра связывают только соседние пункты пересменки водителей. Дополнительно вводятся ребра, включающие в себя еще еженедельный отдых.

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

Длина ребер ТС и водителей
Длина ребер ТС и водителей

*Еженедельный отдых можно программировать отдельно от вождения и послесменного отдыха, но в этом случае придется ввести новые события (отправка в еженедельный отдых). Такой сценарий допустим и не будет отличаться от предложенного ниже.

Индексы

N - множество узлов сети (отправка, время);

a=(i, j, t) \in A - множество направленных ребер сети (локация отправление, локация прибытие, время отправления);

d \in D - набор водителей;

A_w^k - набор ребер, которые находятся в неделе k;

A_{ww}^k - набор ребер, которые находятся в двухнедельном периоде k.

Постоянные

c_{ij} - кол-во водителей, необходимых для движения на участке a;

t_a - время вождения на ребре a;

T_w - допустимое время вождения за неделю;

T_{ww} - допустимое время вождения за две недели.

Переменные

x_{da} - бинарная переменная, равна 1, если водитель d работает на ребре a, 0 - в противном случае;

y_{da} - бинарная переменная, равна 1, если водитель d работает на ребре a и проводит еженедельный отдых в конечной точке ребра, 0 - в противном случае;

s_{dit} - бинарная переменная, равна 1, если водитель d ожидает в узле (i, t);

b_d - бинарная переменная, равна 1, если водитель d задействован в работах, 0 - в противном случае.

Ограничения

  • Уравнение баланса потоков. Поток, входящий в узел, равен исходящему потоку. Здесь A^x_a и A^y_a - это набор входящих ребер из соседних узлов с максимально поздним временем прибытия в узел отправки ребра a (см. схему выше):

s_{dit'} + \sum_{a'\in A^x_a} x_{da'} + \sum_{a'\in A^y_a} y_{da'} = s_{dit} + x_{da} + y_{da}, \quad \forall (i, j, t) = a \in A, d \in D

  • Ограничение на время работы водителя за одну/две недели:

\sum_{a \in A^k_w} t_a(x_{da} + y_{da}) \le T_w, \quad \forall d \in D, \forall k\sum_{a \in A^k_{ww}} t_a(x_{da} + y_{da}) \le T_{ww}, \quad \forall d \in D, \forall k

  • Покрытие водителями всех работ:

\sum_{d \in D} (x_{da} + y_{da}) \ge c_a, \quad \forall a \in A

  • По крайней мере один еженедельный отдых в неделю, если водитель участвует в работах:

\sum_{a \in A^k_w} y_{da} \ge b_d, \quad \forall d \in D, \forall k

  • Один исток. Если водитель задействован в работах, то у него должен быть ровно один исток. Исток кодируется переменными s_{di0}:

\sum_{i} s_{di0} = b_d, \quad \forall d \in D

  • Цикличность графиков водителей. Сопоставим ребру a аналогичное ребро, но со временем выезда через цикл. Обозначим такое ребро a^e:

x_{da} = x_{da^e}, \quad \forall d \in D, a \in Ay_{da} = x_{da^e}, \quad \forall d \in D, a \in A

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

Критерий оптимизации не отличается от критерия из модели покрытия. Необходимо минимизировать кол-во водителей:

\sum_d b_d →\min

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

Производительность моделей

Эксперименты проводили на машине CPU 4.2GHz, RAM 64GB, Cores 4, Linux. Код разрабатывали на Python, в качестве решателя использовали готовый коммерческий MIP solver. Лимит по времени на одну задачу - 2 часа.

Расчеты проводили на 63 сценариях с рассмотрением недельного и двухнедельного цикла работы водителей (переодичность графика). Сценарии можно посмотреть здесь в ранее представленном формате.

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

Ниже представлена таблица в разбивке по кол-ву решенных, нерешенных и с допустимыми решениями сценариев для каждого типа моделей:

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

  • NFP потоковая модель.

  • NFP_init потоковая модель с частичной фиксацией переменных (вспомогательное ограничение 3).

  • NFP_sym1 потоковая модель с устранением симметрии типа 1.

  • NFP_sym2 потоковая модель с устранением симметрии типа 2.

Расчеты проводили для случая с недельным циклом графика.

SPP

NFP

NFP_init

NFP_sym1

NFP_sym2

Solved

51

33

35

29

19

Unsolved

12

18

11

22

33

With Gap

0

12

17

12

11

Для случая двух недельного цикла урезали набор моделей до SPP и NFP в связи с ограниченностью мощностей под эксперименты.

SPP

NFP

Solved

21

14

Unsolved

42

42

With Gap

0

7

Выводы из полученных результатов:

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

  • Наиболее эффективная модификация NFP - частичная фиксация переменных NFP_init. Остальные подходы по устранению симметрии провалились с треском.

  • Заметно сильное влияние цикличности графиков работы на сложность задачи. Это объясняется повышением вариативности - водитель может дальше уезжать от своей первоначальной точки дислокации.

Опустимся детальнее в результаты, рассмотрим длительность поиска оптимального решения для каждого сценария в отдельности. Достаточно крупное пересечение 33 решенных сценариев есть у SPP, NFP и NFP_init, рассмотрим их поближе.

Ниже представлена точечная диаграмма, где по оси X длительность оптимизации сценариев, а по оси Y указан процент от максимальной длительности расчета для рассмотренных моделей. Из-за проблем с масштабом, столбчатая диаграмма не очень показательна, поэтому прибегнул к такого рода визуализации. Как читать диаграмму? Пример интерпретации, 59s на 100% модель NFP - для нее поиск оптимального решения длился 59 секунд; для SPP поиск оптимального решения занял 80% времени, т.е. 59*0.8=47.2 секунды; для NFP_init около 6 секунд.

Выводы:

  • Модель NFP_init ни разу не аутсайдер. В большинстве сценариев поиск оптимального решения происходил более чем в 4 раза быстрее, по сравнению с худшей моделью;

  • Модель SPP малоэффективна на "коротких забегах", но на длительных расчетах вырывается вперед;

  • Модель NFP - самая неудобная формулировка для MIP солвера из рассмотренных.

Полезность моделей

Краткое резюме о полезности моделей в боевом использовании.

Цикл графиков. Ранее отметил, что размер цикла графиков работы водителей влияет на вариативность задачи. Что насчет качественной характеристики результата? Провели расчет на 23 сценариях с циклом графиков в одну и две недели. В случае цикла в одну неделю требуются 281 водитель, тогда как для двухнедельного цикла - 274. Таким образом, эффект размера цикла можно оценить в ~2.5%. При этом, для большинства сценариев кол-во водителей остается неизменным.

Экономический эффект. Процесс внедрения такого рода решения не вызывает сложностей, так как не требует оперативного отклика и интеграции с текущими системами. Этот инструмент напоминает продвинутый калькулятор. Использование калькулятора позволило сэкономить 14% на зацикленных маршрутах с длинными плечами перевозки. В эффекте учтены не только экономия водителей в сравнении с ручными графиками, но и возможность проигрывать набор сценариев (экспериментировать). Изменение времени выезда, разбиение маршрута на участки или цикла рабочего графика позволяют значительно оптимизировать ресурсы на зацикленном маршруте. Калькулятор в комбинации с умелым пользователем показал свою полезность и отработал свои инвестиции.

Заключение

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

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

Ссылки