Portal de Periódicos da CAPES

Artigo Acesso aberto Produção Nacional Revisado por pares

BIBTEX RIS

Algoritmos genéticos e computação paralela para problemas de roteirização de veículos com janelas de tempo e entregas fracionadas

2006; UNIVERSIDADE FEDERAL DE SÃO CARLOS; Volume: 13; Issue: 2 Linguagem: Português

10.1590/s0104-530x2006000200009

1806-9649

Guilherme Guidolin de Campos, Hugo Tsugunobu Yoshida Yoshizaki, Patrícia Belfiore,

Assembly Line Balancing Optimization

O presente trabalho propõe a utilização de metaheurísticas e computação paralela para a resolução de um problema real de roteirização de veículos com frota heterogênea, janelas de tempo e entregas fracionadas, no qual a demanda dos clientes pode ser maior que a capacidade dos veículos. O problema consiste na determinação de um conjunto de rotas econômicas que devem atender à necessidade de cada cliente respeitando todas as restrições. A estratégia adotada para a resolução do problema consiste na utilização de uma adaptação da heurística construtiva proposta por Clarke e Wright (1964) como solução inicial. Posteriormente, implementa-se um algoritmo genético paralelo que é resolvido com o auxílio de um cluster de computadores, com o objetivo de explorar novos espaços de soluções. Os resultados obtidos demonstram que a heurística construtiva básica apresenta resultados satisfatórios para o problema, mas pode ser melhorada substancialmente com o uso de técnicas mais sofisticadas. A aplicação do algoritmo genético paralelo de múltiplas populações com solução inicial, que apresentou os melhores resultados, proporciona redução no custo total da operação da ordem de 10%, em relação à heurística construtiva, e 13%, quando comparada às soluções utilizadas originalmente pela empresa.