In this article, a hybrid algorithm is proposed to solve the Vehicle Scheduling Problem with Multiple Depots. The proposed methodology uses a genetic algorithm, initialized with three specialized constructive procedures. The solution generated by this first approach is then refined by means of a Set Partitioning (SP) model, whose variables (columns) correspond to the current itineraries of the final population. The SP approach possibly improves the incumbent solution which is then provided as an initial point to a well-known MDVSP model. Both the SP and MDVSP models are solved with the help of a mixed integer programming (MIP) solver. The algorithm is tested in benchmark instances consisting of 2, 3 and 5 depots, and a service load ranging from 100 to 500. The results obtained showed that the proposed algorithm was capable of finding the optimal solution in most cases when considering a time limit of 500 seconds. The methodology is also applied to solve a real-life instance that arises in the transportation system in Colombia (2 depots and 719 services), resulting in a decrease of the required fleet size and a balanced allocation of services, thus reducing deadhead trips.

This paper proposes a two-phase heuristic algorithm to solve the crew scheduling problem of the Megabus Bus Rapid Transit System. In the first stage, a division of the original schedules is performed using a recursive algorithm based on dynamic scheduling. In the second stage, work-shift construction based on graph theory is performed using a pairing algorithm (i.e., matching). The method is validated by applying it to the mass transit system of the Central Western Metropolitan Area (AMCO), operated by Integra SA, which serves 11 routes for a daily total of 2899 trips.