Abordagem multiobjetivo para o PRV

ABORDAGEM MONO-OBJETIVO E MULTIOBJETIVO PARA O
PROBLEMA DE ROTEAMENTO DE VEÍCULOS
Lucas Carvalho Oliveira Matsueda
Departamento de Computação - Universidade Federal de Ouro Preto
Campus Universitário, Morro do Cruzeiro, CEP 35.400-000, Ouro Preto - MG, Brasil [e-mail] Flávio Vinícius Cruzeiro Martins
Instituto de Ciências Exatas e Aplicadas - Universidade Federal de Ouro Preto
Rua 36, n° 15, Loanda, João Monlevade – MG [e-mail] RESUMO
Este trabalho propõe duas ferramentas para resolver o Problema de Roteamento de
Veículos Capacitados (PRVC). A primeira implementa um Algoritmo Genético (AG) monoobjetivo, cujo objetivo é minimizar a distância total percorrido pelos veículos. A segunda implementa um AG multiobjetivo (NSGA-II), cujos objetivos são: minimizar o tempo de atendimento aos consumidores e o custo total de operação. Para avaliar a eficiência e robustez dos algoritmos desenvolvidos, foram utilizadas 4 instâncias que variam entre 22 e 101 consumidores. Os resultados de ambas as ferramentas foram comparados com o modelo exato, estes apresentaram, quando não iguais, resultados bem próximos, tendo como diferencial o tempo de execução.
PALAVRAS CHAVE. Problema de Roteamento de Veículos Capacitados. Algoritmo
Genético. Otimização Multiobjetivo.

ABSTRACT
This paper proposes two tools for solving the Vehicle Routing Problem Empowered.
The first tool implements a Genetic Algorithm (GA) mono-objective, whose goal is to minimize the total distance traveled by vehicles. The second tool implements a multiobjective version of the AG, the NSGA-II, whose goal is to minimize the time of service to consumers and the total cost of operation. To assess the efficiency and robustness of algorithms developed were used three instances of between 22 and 101 consumers. The results of both proposals are the tools showed good since they had, if not identical, results compared very close to the tools. Its diferencial runtime.
KEYWORDS. Vehicle Routing