Section:
New Results
Using CP for the Urban Transit Crew Rescheduling Problem
Scheduling urban and trans-urban transportation is an important issue for industrial societies. The Urban Transit Crew Scheduling Problem is one of the most important optimization problem related to this issue. It mainly relies on scheduling bus drivers workday respecting both collective agreements (see Figure 9 for an example of regulation rule) and the bus schedule needs. If this problem has been intensively studied from a tactical point of view, its operational aspect has been neglected while the problem becomes more and more complex and more and more prone to disruptions. In this way, this paper presents how the constraint programming technologies are able to recover the tactical plans at the operational level in order to efficiently help in answering regulation needs after disruptions (see CP conference paper).
Figure
9. Illustration of typical regulation rule in the Labcom project;
Shift 2 of an employee is composed of tasks 2, 3, and 4.
It is between shifts 1 and 3 of the same employee. A break of
duration 4 is scheduled between task 1 of shift 1 and
task 2 of shift 2, because the gap between these tasks is at
least a break of 4. Similarly, a break of duration 7 is
scheduled after task 4 of shift 2 and task 5 of shift 3.
No other breaks can be scheduled between the tasks of shift 2
because of the minimum break duration. The span of
shift 2 is 22 and does not exceed 27: it is
composed of tasks 2, 3, and 4, as well as of the two gaps
between these tasks.
|