Improved vehicle scheduling in public transport through systematic changes in the time-table

Vehicle scheduling for a fixed time-table is easy to formulate and solve as a minimal-cost-flow problem. Normally, however, there is considerable flexibility in the time-table. We propose here a method for exploiting this flexibility in order to improve the vehicle scheduling.A given set of trips must be assigned to a fleet of identical vehicles, starting from a common garage. Each trip is characterized by initial stop, final stop, duration, earliest departure time, and latest departure time.The problem is to decide which vehicle should be assigned to each individual trip and when the trip should start, so that a generalized cost is minimized.The minimum-cost-flow problem is first solved for the ‘kernels’ of every trip in order to make clear when the critical time-periods occur and obtain a lower bound for the solution. The kernel is defined as a trip that starts at the latest possible departure time and finishes at the earliest possible arriving time.The departure time for each trip is then chosen, thereby increasing the chances of obtaining a good schedule. The minimum-cost-flow problem is then solved for this fixed time-table.Finally, the departure times for each vehicle are adjusted (blocked) so that each vehicle (and driver) is efficiently used. This method is used as an integral part of the Volvo Traffic Planning Package.