Um algoritmo multi-start iterated greedy para o problema de roteamento de veículos com drones

Abstract

The transportation of goods plays a crucial role in the global industry, driving the search for solutions that make logistics more efficient and sustainable. In this context, the Vehicle Routing Problem with Drones and Time Windows (VRP-DTW) emerges as a promising approach to optimizing deliveries by integrating trucks and drones to reduce operational costs, minimize pollutant emissions, and speed up the distribution of goods. In this type of problem, a set of trucks, all equipped with drones, must serve a defined number of customers along their routes. While trucks perform these deliveries, drones can assist by serving additional customers. The drone proves to be a cheaper alternative compared to the truck; however, due to its low autonomy, it must operate in coordination with land vehicles. In this work, a Multi-Start Iterated Greedy algorithm is proposed, which uses techniques for constructing the initial solution, followed by stages of destruction, reconstruction, and refinement, employing a set of moves that explore the solution’s neighborhoods to find better ones. Two methods were implemented: one method is based on reinforcement learning, Q-learning, to guide the order in which these moves are applied using a Q action-value function. The other method, Random Variable Neighborhood Descent (RVND), involves the random selection of the order of these moves. The algorithm’s performance was compared to other approaches from the literature addressing the VRP-DTW. Additionally, the performance of Q-learning was compared to the implemented RVND. Experiments were conducted considering instances with 25, 50, and 100 customers. The results show that the proposed approach proved competitive with those in the literature in terms of both solution quality and computational time. However, when comparing the use of RVND with Q-learning, the RVND approach demonstrated superior performance.