Description
Public transportation services usually operate on previously determined bus – or other vehicle – lines, which connect a certain number of stations. The lines and their daily services are fixed in a timetable which provides the departure and arrival time of the trips for each line. In practice the timetable – based on travel demands and logistic decisions – is given in advance.
A central problem of public transportation companies is to optimize their operational process. Since the minimization of the overall operational cost is a very complex task, the arising subproblems are considered as separeted optimization problems. The vehicle scheduling problem in public tranportation consists of scheduling a fleet of vehicles to cover the timetabled trips with a minimum cost. Apart from the general cost determined by the scheduled vehicles, the transporation costs of the timetabled trips and that of the so-called deadhead trips (trips without passangers between two geolocations) contribute to the definition of an appropriate objective function.
There are several mathematical formulations that can be used to model the vehicle scheduling problem. Most of these formulations are based on network-flow approaches and quasi-assignment models. In real-world applications, however, numerous additional constraints are considered which are not covered by the above models. In daily operation the vehicle schedules need to satisfy vehicle-specific requirements such as fueling and maintenance constraints or different parking rules. In operational management it is also a frequent situation that some unexpected events (the most common of which are vehicle breakdown and lateness) render the pre-planned schedule infeasible, which requires a rescheduling process. Vehicle assignment with respect to the daily schedules in a long-term fashion (several weeks or months) is also a crucial question in order to plan those duties of the vehicles that are not related to the timetable. Finally, since driver scheduling is also an important part of operational transport management, the constructed vehicle schedules need to consider some soft constraints induced by the driver rules.
In this talk we present efficient models and solutions methods for the above mentioned real-world vehicle scheduling problems. The solutions were developed by an implementation-oriented approach, which will be demonstrated by real-world test cases. The results were achieved in a group work at the Discrete Optimization and Data Mining Laboratory in cooperation with a regional bus transportation company.
Primary author
Dr
Miklos Kresz
(University of Szeged)
