Integrated Vehicle and Duty Scheduling in Public Transit

Vehicle scheduling and duty scheduling are important steps in the operational planning process of a public transport company. Today, many companies are solving these problems sequentially, often with a vehicles-first duties-second approach. In scenarios with few relief opportunities, however, sequential scheduling can run into severe difficulties in scheduling mandatory breaks for the drivers. Many public transport companies safeguard against such problems by inserting artificial idle periods into their vehicle schedules which later serve as break opportunities. In addition, they look after vehicle schedules that regularly visit a relief point or a depot. While such a procedure may result in feasible schedules, its drawback is that the vehicle schedules often contain more idle periods than actually needed. Integrated vehicle and duty scheduling exploits this potential.

Our approach to integrated vehicle and duty scheduling is based on an integrated model of the problem that combines a vehicle and a duty scheduling model by a coupling part that synchronizes the use of deadhead trips. The objective of the optimization can be an arbitrary mix of vehicle and duty costs.

The optimization algorithm decomposes the problem into its vehicle and duty scheduling part by relaxing the coupling constraints in a Lagrangean fashion. This results in a sequence of vehicle and a duty scheduling subproblems, which are solved using methods that we have developped in preceding projects on vehicle scheduling and duty scheduling. The Lagrange relaxation provides not only a lower bound for the costs of an optimal integrated schedule. Using a bundle approach to handle the relaxed coupling constraints, we can also produce an approximate primal LP solution. We use this information in a branch-and-bound-type heuristic in order to derive synchronized and cost efficient vehicle and duty schedules.