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.