Real-time multi-depot vehicle type rescheduling problem

The multiple-depot vehicle type rescheduling problem (MDVTRSP) is a dynamic extension of the classic multiple-depot vehicle scheduling problem (MDVSP), where a heterogeneous fleet is considered. The MDVTRSP consists of finding a new schedule given that a severe disruption occurred in previously scheduled trips very quickly, simultaneously minimizing the transportation costs and the deviations from the original plan. Although several mathematical formulations and solution methods have been developed for the robust MDVTRSP, the real time MDVTRSP is still unexplored. In this paper, we introduce a formulation of the problem and develop a heuristic solution method, employing time-space network, truncated column generation, and preprocessing procedures. The solution method has been implemented in several algorithm variants, combining different developed preprocessing methods. Computational experiments on randomly generated instances were performed to evaluate the performance of the developed algorithms. The best solutions concerning efficiency and efficacy were obtained by the variants considering state space reductions to accelerate the convergence process of the column generation. Solutions were obtained very quickly (in less than 150 seconds for large instances, considering up to 2500 trips, eight depots, and one breakdown. The developed heuristics also presented a good behavior for several simultaneous disruptions, solving the problem with a little increase (less than 8.5%, on average) in the required CPU time. A case study using data from a real-life small instance in Brazil also demonstrated the efficiency and efficacy of the approach when compared with manual planning strategies.