Solving large multiple-depot multiple-vehicle-type bus scheduling problems in practice

摘要

To study the problems associated with multiple-depot multiple-vehicle type scheduling problems (MDVSP). MDVSP arise in public transport bus companies. The present study aims at assigning buses to cover a given set of timetabled trips and to characterize an optimal schedule by minimum fleet size and minimum operational costs (a NP-hard problem). A two-phrase method producing close to optimal solutions is developed which enables one to solve real-world issues with thousands of scheduled trips by direct application of standard optimization software. The study also introduces the concept of depot groups for the case that a bus may return in the evening into another depot than where it started in the morning.