| Revista: | Gestao & producao |
| Base de datos: | CLASE |
| Número de sistema: | 000282154 |
| ISSN: | 0104-530X |
| Autores: | Campos, Guilherme Guidolin de1 Yoshizaki, Hugo Tsugunobu Yoshida Belfiore, Patrícia Prado |
| Instituciones: | 1Universidade de Sao Paulo, Escola Politecnica, Sao Paulo. Brasil |
| Año: | 2006 |
| Periodo: | May-Ago |
| Volumen: | 13 |
| Número: | 2 |
| Paginación: | 271-281 |
| País: | Brasil |
| Idioma: | Portugués |
| Tipo de documento: | Artículo |
| Enfoque: | Analítico, teórico |
| Resumen en inglés | The present work considers the use of metaheuristics and parallel computing to solve a real problem of vehicle routing involving a heterogeneous fleet, time windows and split deliveries, in which customer demand can exceed vehicle capacity. The problem consists of determining a set of economical routes that meet each customer's needs while still being subject to all the constraints. The strategy adopted to solve the problem consists of an adaptation of the constructive heuristics proposed by Clarke & Wright (1964) as the initial solution. More sophisticated algorithms are then applied to achieve improvements, such as parallel genetic algorithms supported by a cluster of computers. The results indicate that the basic constructive heuristic provides satisfactory results for the problem, but that it can be improved through the use of more sophisticated techniques. The use of the parallel genetic algorithm with multiple populations and an initial solution, which presented the best results, reduced the total operational costs by about 10% compared with the constructive heuristic, and by 13% when compared with the company's original solutions |
| Resumen en portugués | 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 |
| Disciplinas: | Matemáticas |
| Palabras clave: | Matemáticas aplicadas, Brasil, Algoritmos genéticos, Heurística, Vehículos, Modelos matemáticos, Rutas, Satisfacción del cliente, Eficiencia económica |
| Texto completo: | Texto completo (Ver HTML) |
