A hybrid Granular Tabu Search algorithm for the Multi-Depot Vehicle Routing Problem

In this paper, we propose a hybrid Granular Tabu Search algorithm to solve the Multi-Depot Vehicle Routing Problem (MDVRP). We are given on input a set of identical vehicles (each having a capacity and a maximum duration), a set of depots, and a set of customers with deterministic demands and service times. The problem consists of determining the routes to be performed to fulfill the demand of the customers by satisfying, for each route, the associated capacity and maximum duration constraints. The objective is to minimize the sum of the traveling costs related to the performed routes. The proposed algorithm is based on a heuristic framework previously introduced by the authors for the solution of the Capacitated Location Routing Problem (CLRP). The algorithm applies a hybrid Granular Tabu Search procedure, which considers different neighborhoods and diversification strategies, to improve the initial solution obtained by a hybrid procedure. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several best solutions obtained by the previously published methods and new best solutions.