首页    期刊浏览 2025年02月03日 星期一
登录注册

文章基本信息

  • 标题:Algoritmos genéticos e computação paralela para problemas de roteirização de veículos com janelas de tempo e entregas fracionadas
  • 其他标题:Genetic algorithms and parallel computing for a vehicle routing problem with time windows and split deliveries
  • 本地全文:下载
  • 作者:Campos, Guilherme Guidolin de ; Yoshizaki, Hugo Tsugunobu Yoshida ; Belfiore, Patrícia Prado
  • 期刊名称:Gestão & Produção
  • 印刷版ISSN:0104-530X
  • 电子版ISSN:1806-9649
  • 出版年度:2006
  • 卷号:13
  • 期号:2
  • 页码:271-281
  • DOI:10.1590/S0104-530X2006000200009
  • 语种:Portuguese
  • 出版社:Universidade Federal de São Carlos
  • 摘要:

    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.

  • 其他摘要:

    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.

  • 关键词:problema de roteirização de veículos;janelas de tempo;entregas fracionadas;metaheurísticas
  • 其他关键词:vehicle routing problem;time windows;split deliveries;metaheuristics
国家哲学社会科学文献中心版权所有