Navegando por Autor "Bezerra, Sinaide Nunes"

Agora exibindo 1 - 3 de 3

A general VNS for the multi‐depot open vehicle routing problem with time windows.
(2023) Bezerra, Sinaide Nunes; Souza, Sergio Ricardo de; Souza, Marcone Jamilson Freitas
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.
A GVNS algorithm for solving the multi-depot vehicle routing problem.
(2018) Bezerra, Sinaide Nunes; Souza, Sérgio Ricardo de; Souza, Marcone Jamilson Freitas
This paper presents an algorithm based on the General Variable Neighborhood Search (GVNS) metaheuristic for solving the Multi-Depot Vehicle Routing Problem (MDVRP). The MDVRP consists in designing a set of vehicle routes serving all customers, such that the maximum number of vehicle per depot and vehicle-capacity are respected, and the total cost of transportation is minimized. The proposed algorithm uses Randomized Variable Neighborhood Descent (RVND) as local search method and it is tested in classical instances of the problem. The obtained results are presented and discussed in this paper.
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.
(2023) Bezerra, Sinaide Nunes; Souza, Marcone Jamilson Freitas; Souza, Sérgio Ricardo de
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.