Scientific Program > Talks by Speaker > Mesquita Marta

The driver rostering problem in public transit companies aims at assigning daily crew duties to each driver defining a sequence of workdays and days-off, the driver schedule, to be in force during a pre-determined rostering horizon. A roster is the set of all driver schedules, together with the particular work shifts that drivers must work on. The rosters must comply with labor regulations, drivers' union agreements and meet the demand for transport in specific urban areas, while minimizing costs and balancing the workload among drivers. During real-time control, absences of drivers call for an adjustment in the current roster, the re-rostering problem. Absent drivers must be substituted by reassigning daily crew duties to drivers, from the first day of drivers' absences, eventually, until the end of the rostering horizon. The resulting new roster should minimize the dissimilarities to the current roster so as to reduce the inconvenience of changing the previously assigned schedules besides ensuring workload demand, rostering constraints and maintaining the equilibrium of the roster.

In this talk, the rostering and re-rostering problems are formulated in a multilevel acyclic network through integer multi-commodity flow/assignment models. Taking advantage from the network and model characteristics, a decompose-and-fix heuristic is used to solve the rostering problem. This heuristic is easily adapted to solve re-rostering problems, by penalizing changes in crew duties previously assigned to drivers through the objective cost function, leading to an integrated framework for solving (re)rostering problems. Computational experience with instances derived from real world data is presented.