Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem

• This is the first time that column generation is directly applied to the MDVTSP.
• The development of algorithms to speedup the CG solution process.
• The design of a random instance generator for the MDVTSP.

The multiple-depot vehicle-type scheduling problem (MDVTSP) is an extension of the classic multiple-depot vehicle scheduling problem (MDVSP), where heterogeneous fleet is considered. Although several mathematical formulations and solution methods have been developed for the MDVSP, the MDVTSP is still relatively unexplored. Large instances of the MDVTSP (involving thousands of trips and several depots and vehicle types) are still difficult to solve in a reasonable time. We introduce a heuristic framework, combining time–space network, truncated column generation (TCG) and state space reduction, to solve large instances of the MDVTSP. Extensive testing was carried out using random generated instances, in which a peak demand distribution was defined based on real-world data from public transportation systems in Brazil. Furthermore, experiments were carried out with a real instance from a Brazilian city. The framework has been implemented in several algorithm variants, combining different developed preprocessing procedures, such as state space reduction and initial solutions for the TCG. Computational results show that all developed algorithms obtained very good performances both in quality and efficiency. The best solutions, considering simultaneously quality and efficiency, were obtained in the heuristics involving state space reduction.