Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem

Description: In this paper, a fast heuristic approach is proposed for solving the multiple depot vehicle scheduling problem (MDVSP), a well-known NP-hard problem. The heuristic is based on a two stage procedure. The first one applies two state space reduction procedures towards reducing the problem complexity. One procedure is based on the solutions of the single-depot vehicle scheduling for each depot, while the other uses the solution of a relaxed formulation of the MDVSP, in which a vehicle can finish its task sequence in a different depot from where it started. Next, the reduced problem is solved by employing a truncated column generation approach. The heuristic approach has been implemented in several variants, through different combinations of the reduction procedures, and tested on a series of benchmark problems provided by Pepin et al. (J Sched 12:17?30, 2009). The heuristic variants found solutions with very narrow gaps (below 0.7 %, on average) to best-known solutions (Pepin et al., J Sched 12:17?30, 2009), decreasing the required CPU time by an overall average factor of 17 in comparison with reported results in the literature (Otsuki and Aihara, J Heuristics 1?19, 2014).
Universidad de Cuenca
http://link.springer.com/article/10.1007%2Fs11590-015-0944-x

Get full text: http://repositorio.educacionsuperior.gob.ec/handle/28000/2979