Mixed integer programming formulations for multi-depot bus scheduling problem in Quito

In this work the multi-depot bus scheduling problem is considered. The problem consists in assigning a set of timetabled trips characterised by an origin depot with a departure time as well as a destination depot with an arrival time to feasible bus routes. Moreover, the selected bus routes must satisfy that each trip is covered exactly by one route, each bus has to return back to its original depot at the end of the working day, the available heterogeneous bus fleet is not exceeded and a certain cost function is minimised. Two different linear integer programming formulations are proposed. The first approach is closely related to arc-based models where all possible compatible trip connections are considered explicitly leading to a multi-commodity flow formulation, whereas the latter is defined on a time-space network based on aggregation of possible connection arcs allowing to route several trips on one single arc simultaneously, which avoids the explosive increase of the model size with a growing timetable. Some lower bounds are provided for both formulations and computational results based on simulated and real-world instances are reported.