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

We consider the multiple-depot multiple-vehicle-type scheduling problem (MDVSP) which arises in public transport bus companies and aims to assign buses to cover a given set of timetabled trips with consideration of practical requirements, such as multiple depots and vehicle types as well as depot capacities. An optimal schedule is characterized by minimal fleet size and minimal operational costs including costs for empty movements and waiting time. It is well-known that the MDVSP is NP-hard. Although progress has recently been made in solving large practical MDVSP to optimality with time-space network models, current optimization technology sets limits to the model size that can be solved. In order to approach very large practical instances we propose a two-phase method which produces close to optimal solutions. This modeling approach enables us to solve real-world problem instances with thousands of scheduled trips by direct application of standard optimization software. Furthermore, we introduce 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.