Algoritmos genéticos e computação paralela para problemas de roteirização de veículos com janelas de tempo e entregas fracionadas
| Autor: | Patrícia Prado Belfiore, Guilherme Guidolin de Campos, Hugo Tsugunobu Yoshida Yoshizaki |
|---|---|
| Rok vydání: | 2006 |
| Předmět: | |
| Zdroj: | Gestão & Produção v.13 n.2 2006 Gestão & Produção Universidade Federal de São Carlos (UFSCAR) instacron:UFSCAR |
| ISSN: | 0104-530X |
| DOI: | 10.1590/s0104-530x2006000200009 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|