Algoritmos de otimização multi-objetivo para o problema de Roteamento de Veículos com janelas de tempo

Abstract

O Problema de Roteamento de Veículos com Janelas de Tempo (PRVJT) é uma variação do problema clássico de Roteamento de Veículos em que as demandas dos clientes devem ser atendidas dentro de uma janela de tempo estabelecida. Neste trabalho, aborda-se o PRVJT objetivando a otimização simultânea de múltiplos objetivos. Os objetivos a serem minimizados são: distância total de percurso dos veículos, desequilíbrio nas distâncias percorridas e desequilíbrio das cargas dos veículos. Já que o problema é NP-Difícil, para determinar uma aproximação das soluções Pareto-ótimas, propõe-se duas abordagens heurísticas. A primeira abordagem é baseada na meta-heurística Iterated Local Search, que utiliza uma etapa de intensificação a qual consiste na combinação de soluções dominantes. A segunda abordagem é um algoritmo genético com uma fase de intensificação baseada na heurística de busca local Iterated Greedy, que consiste em melhorar as soluções dominantes. Os desempenhos dos algoritmos heurísticos foram testados em um conjunto de instâncias disponíveis na literatura, denominado Solomon’s benchmarks, e os resultados foram comparados com os resultados de dois algoritmos multiobjetivos da literatura. Os resultados obtidos foram analisados estatisticamente e observou-se um desempenho superior dos algoritmos propostos.

The Vehicle Routing Problem with Time Windows (VRPTW) is a variant of the classical Vehicle Routing Problem in which the demands of each customer should be met within an established time window. In this paper we address the VRPTW with multi-objective optimization. The objectives are to minimize the total distance, the imbalance in the distances traveled and the imbalance in the loads of the vehicles. Since the problem is NP-Hard, in order to find near Paretooptimal solutions, two heuristic approaches were proposed. The first approach is based on the meta-heuristic Iterated Local Search that uses an intensification stage that consists in combination of non-dominated solutions. The second approach is a genetic algorithm with an intensification stage based on the local search heuristic Iterated Greedy that consists in improving the non-dominated solutions. The heuristic algorithms’ performance was tested with a set of problems available in the literature, known as Solomon’s benchmarks, and the results were compared with two multi-objective algorithms in the literature. The results were statistically analyzed and revealed superior performance of the proposed algorithms.