A tabu-search heuristic for solving the multi-depot vehicle scheduling problem

Abstract

Currently the logistical problems are relying quite significantly on Operational Research in order to achieve greater efficiency in their operations. Among the problems related to the vehicles scheduling in a logistics system, the Multiple Depot Vehicle Scheduling Problem (MDVSP) has been addressed in several studies. The MDVSP presupposes the existence of depots that affect the planning of sequences to which travel must be performed. Often, exact methods cannot solve large instances encountered in practice and in order to take them into account, several heuristic approaches are being developed. The aim of this study was thus to solve the MDVSP using a meta-heuristic based on tabu-search method. The main motivation for this work came from the indication that only recently the use of meta-heuristics is being applied to MDVSP context (Pepin et al. 2008) and, also, the limitations listed by Rohde (2008) in his study, which used the branch-and-bound in one of the steps of the heuristic presented to solve the problem, which has increased the time resolution. The research method for solving this problem was based on adaptations of traditional techniques of Operational Research, and provided resolutions presenting very competitive results for the MDVSP such as the cost of the objective function, number of vehicles used and computational time.