A variable neighborhood search-based algorithm with adaptive local search for the vehicle routing problem with time windows and multi-depots aiming for vehicle fleet reduction.
Nenhuma Miniatura disponível
Data
2023
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
This article addresses the Multi-Depot Vehicle Routing Problem with Time Windows with the minimization of
the number of used vehicles, denominated as MDVRPTW*. This problem is a variant of the classical MDVRPTW,
which only minimizes the total traveled distance. We developed an algorithm named Smart General Variable
Neighborhood Search with Adaptive Local Search (SGVNSALS) to solve this problem, and, for comparison
purposes, we also implemented a Smart General Variable Neighborhood Search (SGVNS) and a General Variable
Neighborhood Search (GVNS) algorithms. The SGVNSALS algorithm alternates the local search engine between
two different strategies. In the first strategy, the Randomized Variable Neighborhood Descent method (RVND)
performs the local search, and, when applying this strategy, most successful neighborhoods receive a higher
score. In the second strategy, the local search method is applied only in a single neighborhood, chosen by a
roulette method. Thus, the application of the first local search strategy serves as a learning method for applying
the second strategy. To test these algorithms, we use benchmark instances from MDVRPTW involving up to 960
customers, 12 depots, and 120 vehicles. The results show SGVNSALS performance surpassed both SGVNS and
GVNS concerning the number of used vehicles and covered distance. As there are no algorithms in the literature
dealing with MDVRPTW*, we compared the results from SGVNSALS with those of the best-known solutions
concerning these instances for MDVRPTW, where the objective is only to minimize the total distance covered.
The results showed that the proposed algorithm reduced the vehicle fleet by 91.18% of the evaluated instances,
and the fleet size achieved an average reduction of up to 23.32%. However, there was an average increase
of up to 31.48% in total distance traveled in these instances. Finally, the article evaluated the contribution of
each neighborhood to the local search and shaking operations of the algorithm, allowing the identification of
the neighborhoods that most contribute to a better exploration of the solution space of the problem.
Descrição
Palavras-chave
Citação
BEZERRA, S. N.; SOUZA, M. J. F.; SOUZA, S. R.de. A variable neighborhood search-based algorithm with adaptive local search for the vehicle routing problem with time windows and multi-depots aiming for vehicle fleet reduction. Computers & Operations Research, v. 149, artigo 106016, 2023. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0305054822002465>. Acesso em: 06 jul. 2023.