Simple and efficient heuristic approach for the multiple-depot vehicle scheduling problem |
| |
Authors: | Pablo Cristini Guedes William Prigol Lopes Leonardo Rosa Rohde Denis Borenstein |
| |
Institution: | 1.Management School,Universidade Federal do Rio Grande do Sul,Porto Alegre,Brazil;2.Universidad de Cuenca,Cuenca,Ecuador;3.Industrial Engineering Department,Federal University of Pelotas,Pelotas,Brazil |
| |
Abstract: | 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). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|