Uma combinação de VND e ACO para otimização em dois Níveis de localização de estações de recarga e roteamento de veículos

Abstract

Electric vehicles are becoming increasingly popular in transportation systems due to subsidies provided by governments that seek to increase their adoption by companies that, in turn, seek to lower the operating cost of their fleet. In this way, we have two agents involved in the process, with each one aiming to solve its own optimization problem, namely the Recharge Station Allocation Problem, which is the responsibility of the government, and the Vehicle Routing Problem, the responsibility of the company. company. A two-level optimization problem arises when the interests of both are addressed simultaneously. In addition, both electric and internal combustion vehicles can be used, increasing the complexity of the problem. This work proposes a solution strategy that combines the Variable Neighborhood Descent metaheuristic with Ant Colony Optimization with Local Search and a Route Selection Procedure for solving a two-level optimization problem involving the Allocation Problem of Stations at the upper level and the Vehicle Routing Problem at the lower level. Variable Neighborhood Descent is applied at the top level, while Ant Colony Optimization and other methods are used at the lower level. Computational experiments were carried out using two different sets of instances that cover different scenarios, which are constructed by varying some of their parameters, such as the energy and load capacity of vehicles and the geographic distribution of locations. The results obtained indicate that the proposed strategy achieved good results at both levels when compared to another approach in the literature, with lower structure construction and routing costs.