Designing enhanced bus driver rosters for Lugano Public Transport

Summary

TPL Bus

We consider the design of rosters for Lugano Public Transport (TPL) bus drivers. As the largest provider of public transportation in Lugano, TPL guarantees passenger services everyday from 6:00 to 24:00 by adhering to a fixed timetable. These services are periodic and more frequent on weekdays than on weekends. Approximately 60 drivers are assigned to 30 buses each day of the year. Currently, from a driver perspective, he/she is given a yearly schedule consisting of working days, free days, reserve shifts, and 4 or 5 weeks of holidays. As the day approaches, a reserve shift is transformed into either a working day or a free day. In fact, this uncertainty not only causes discontent for the drivers, but also creates a day-to-day managerial burden for TPL. To cope with this situation, and more generally, TPL's desire is to have rosters that reduce the discrepancy between a theoretical or planned roster and the actual one as well as incorporate individual driver preferences.

From a designer point of view, even finding a roster for a single driver is not such a simple task because of general labor laws and work agreements that considerable restrict the possibilities. This is further complicated by the goal of removing as many reserve shifts as possible and satisfying additional individual driver preferences. We tackle the problem by considering a covering integer programming formulation. This formulation has the property that can be easily decomposed driver by driver. The decomposed problem is a Lagrangean dual of the original formulation. We do not solve this problem, since it would only provide fractional solutions. Instead, we design sequential algorithms inspired by algorithms that solve the Lagrangean dual that at each iteration find the solution to a much simpler integer program and maintain an almost feasible integer solution for the original problem. We tested our algorithms with current data provided by TPL and preliminary computations show that the rosters generated by our algorithms achieve TPL goals.