Расписание водителя (общественный транспорт): соблюдение 30-минутного перерыва после 4-х часов времени вождения

Question

Мы боремся с некоторыми аспектами следующей проблемы:

• расписание автобусов общественного транспорта состоит из смен (~ отрезков пути), каждое с фиксированным временем начала и окончания

• драйверы автобусов должны быть назначены для каждой из этих смен

• [рассматриваемое ограничение] законодательные нормы требуют, чтобы у каждого водителя автобуса был 30-минутный перерыв после 4 часов вождения (т.е. после смены вождения)

• Другими словами, водитель накапливает время вождения при смене вождения, которое не должно превышать 4 ч, если только водитель не делает перерыв в 30 минут, и в этом случае начисленное время составляет «Сброс на ноль»

Таким образом, нам нужно отследить начисленное время вождения каждого водителя, чтобы отменить назначения смены для обеспечения 30-минутного перерыва.

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

• Как и проблемы магазина вакансий , он имеет смены (или задачи, задания) со множеством ограничений на перекрытие и приоритетность между ними ...

• ... НО наши смены (~ задачи / задания) предварительно не назначаются водителям; в отличие от задач цеха, задачи (~ смены) должны выполняться на определенных машинах (~ драйверах) и, следовательно, предварительно назначаться, поэтому их назначение не является частью проблемы

• Как и задачи назначения , нам нужно назначить смены как можно меньшему числу водителей ...

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

Итак, мой вопрос: как лучше смоделировать вышеуказанное ограничение в задаче ограничения с помощью or-tools ?

Заранее спасибо!

Answer 1

Одним из общих методов указания шаблонов в программировании ограничений является регулярное ограничение (в Gecode , Choco , MiniZinc , среди прочих, неуверенный в статусе для or-tools), где шаблоны переменных указываются с использованием конечных автоматов (DFA и NFA) или регулярных выражений.

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

Состояния:

• Состояния вождения Dn, представляющие n единиц времени вождения (для некоторого разрешения единиц времени), до n = 4 часа.
• Состояния разрыва DnBm для разрыва длины m после n единиц времени вождения, до m = 30 минут.
• Начальное состояние D0.

Переходы:

• Вождение: При движении на 1 единицу времени переходите из состояния Dn в D (n + 1) и из перерыва короче 30 минут из DnBm в D (n + 1).
• Перерыв на 1 единицу времени, переход от DnBm к DnB (m + 1), если не было достигнуто 30-минутное время перерыва, для которого переход возвращается к D0.
• В основном выполняются другие действияв качестве самоконтроля, в зависимости от желаемой семантики.

Конечно, детали будут различаться для вашего конкретного варианта использования.