An iterated local search algorithm for latency vehicle routing problems with multiple depots

The Multi-depot Cumulative Capacitated Vehicle Routing Problem (MDCCVRP) extends the recently proposed Cumulative Capacitated Vehicle Routing Problem (CCVRP). The aim is to minimize the sum of the arrival times at the customers considering a fleet of Nv capacitated vehicles and a set of Nd uncapacitated depots. This paper proposes valid lower bounds and a novel metaheuristic algorithm for the solution of the MDCCVRP. The initial solution is obtained by combining different heuristic approaches, while the improving phase consists of an iterated local search algorithm (ILS). Computational experiments on 78 MDCCVRP benchmark instances show that the proposed algorithm is able to find, within reasonable computing times, solution values globally better than those obtained by the state-of-the-art heuristic algorithms. For challenging instances (having a large number of customers and a small fleet size), the algorithm can find, within short computing times, solutions globally better than those obtained by the published exact algorithms. The proposed algorithm has also been applied to the recently introduced Multi-depot k-traveling Repairman Problem (MDk-TRP) and the Latency Location Routing Problem (LLRP). The MDk-TRP is a particular case of the MDCCVRP arising when the vehicles are uncapacitated, while the LLRP is a generalization of the MDCCVRP in which, at most, p of the Nd available depots can be used. The computational experiments performed on 87 MDk-TRP benchmark instances and 76 LLRP benchmark instances show that the proposed algorithm globally outperforms the state-of-the-art metaheuristic algorithms for what concerns both the solution quality and the computing time. For large-size instances, the computing time required to provide a good quality solution is considerably smaller than that required by the previously published heuristic and exact algorithms. For all the problems, the proposed algorithm is able to find better solution values than those obtained by the respective state-of-the-art metaheuristic algorithms when it is executed for the same computing time as the respective competitor.