Os problemas de roteamento de veículos emergem em inúmeras situações práticas em logística de transporte. Dentre elas, pode-se destacar o dial-a-ride problem (DARP), que consiste em construir rotas de custo mínimo que atendam requisições de coleta e entrega, obedecendo as restrições de capacidade, janelas de tempo e tempo máximo de viagem. Este trabalho propõe um algoritmo híbrido para resolver uma variante do DARP com demanda e frota heterogêneas. O método combina a meta-heurística iterated local search (ILS) com um procedimento exato para resolver o problema de particionamento de conjuntos. Além disso, diversos procedimentos foram implementados para acelerar as buscas locais. Experimentos computacionais foram realizados em instâncias da literatura e os resultados obtidos sugerem que o algoritmo proposto é capaz de produzir soluções de alta qualidade, inclusive encontrando uma nova melhor solução, em tempos computacionais competitivos.

Vehicle routing problems arise in many practical situations regarding transportation logistics. Among them, one can highlight the dial-a-ride problem (DARP), which consists of designing least-cost routes to serve pickup-and-delivery requests, while meeting capacity, time windows and maximum ride time constraints. This work proposes a hybrid algorithm to solve a DARP variant where both the demands and vehicle fleet are heterogeneous. The method combines the iterated local search (ILS) metaheuristic with an exact procedure based on a set partitioning approach. In addition, several procedures were also implemented to speed-up the local search phase. Computational experiments were conducted on benchmark instances, and the results obtained suggest that the proposed algorithm is capable of producing highly quality solutions, even improving one best known solution, in a very competitive runtime.