Um algoritmo híbrido para o problema de roteamento de veículos do tipo dial-a-ride com frota heterogênea e múltiplos depósitos

Abstract

Vehicle routing problems arise in many practical situations in the context of transportation logistics. Among them, we can highlight the problem of transporting customers from origin to destination locations, this problem is known as the dial-a-ride problem (DARP). The DARP consists of designing least-cost routes to serve pickup-and-delivery requests, while meeting capacity, time window, maximum route duration, and maximum ride time constraints. This work proposes a hybrid algorithm to solve DARP variants where both the demands and vehicle eet are heterogeneous, and the vehicles start their routes from multiple depots. The method combines the iterated local search metaheuristic with an exact procedure based on a set partitioning approach. In addition, several procedures were implemented to speedup the local search phase. Extensive computational experiments were conducted on benchmark instances in order to evaluate the impact of the diferent components of the algorithm, and to compare its performance with the best existing method. The results obtained suggest that the proposed algorithm outperforms the state-of-art method, producing high quality solutions, even improving seven best known results, in a very competitive runtime.