Integrated scheduling in public transit deals with the simultaneous construction of operation schedules for vehicles and crews. This kind of scheduling is particularly important for regional bus operations, where the lack of relief opportunities in the countryside binds drivers and vehicles together. Traditional sequential scheduling (vehicles first, drivers second or vice versa) is not well suited for this specific situation.
The result of this project is an optimization system for integrated scheduling that is based on set partitioning/covering and multiflow models. As the present state-of-the-art does not allow the exact solution of such problems, we aim at heuristic Lagrange methods to compute good approximate solutions.
We developped the system in cooperation with the software companies IVU Traffic Technologies AG and Mentz Datenverarbeitung GmbH, who will integrate it in their respective commercial planning systems. The Regensburger Verkehrsbetriebe GmbH, a regional German carrier, participates as a "Lead User".
Problem
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.
Method
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.
Results
We have tested our method on industrial large-scale scenarios provided by the Regensburger Verkehrsverbund GmbH (RVV). The RVV is an urban public transport company with a star-shaped network. There are only four relief points in the center of the network, all close to the railway station, which is itself close to the depot. Such a structure is typical for a situation which is ill-suited for sequential planning.
On weekdays, the RVV does 1,414 timetabled trips, consisting of 3,666 duty elements. The duty elements are connected by 233,842 potential connections, among them 57,646 potential deadhead trips. The duty scheduling rules include quotient as well as block breaks; in addition, constraints on average duty durations had to be taken into account. As far as we known, these RVV instances are the largest and most complex instances of integrated vehicle and duty scheduling problems that have been considered up to now.
In comparison to the reference solution provided by the RVV, our optimization tool IS-OPT could reduce the number of duties by 2-3%, the total working time by 5%, and the time spent by vehicles outside of the depot by 4%.
Our integrated vehicle and duty scheduling optimization module IS-OPT is integrated into the commercial planning system MICROBUS II of IVU Traffic Technologies AG and commercially marketed. Further development and support is done by the ZIB spin-off company Löbel, Borndörfer & Weider GbR.
