A general VNS for the multi‐depot open vehicle routing problem with time windows.

Abstract

This paper presents an algorithm based on the variable neighborhood search (VNS) metaheuristic, called smart general VNS (SGVNS), to solve the multi-depot open vehicle routing problem with time windows (MDOVRPTW). For the problem, two single-objective approaches are proposed for cost assessment: one for reducing the total distance covered and the other for reducing the total number of vehicles used and, after, the total distance covered. SGVNS involves the perturbation and local search phases. In the perturbation phase, gradual changes are carried out in the neighborhoods to expand the diversifcation of solutions and escape from local optima. The random combination of specifc neighborhood structures is used in the local search to refne the solution generated in the previous phase. As no instances are known in the literature for MDOVRPTW, the computational tests are executed in two groups of classic MDVRPTW instances, involving up to 960 customers, 12 depots, and 120 vehicles. The present study made it possible to investigate cost improvements through the use of the MDOVRPTW model when compared to the

MDVRPTW. There was a reduction in the distance covered in all instances evalu- ated. The total distance covered decreased by 12.07% in one of the reference groups

and 10.43% in the other. For the frst group, the feet reduction occurred in 75% of

the instances. In the second group, there was a reduction in all instances. It corre- sponds to −10.42% and −24.13% of the total vehicles used in each group, respec- tively. The SGVNS algorithm proved efective for the two problems for which it was

applied, either in reducing the total traveled distance or in reducing the feet.