Meta-Heurísticas em Pesquisa Operacional – Capítulo 11

  • Título: Um Algoritmo Heurístico Baseado em Iterated Local Search para Problemas de Roteamento de Veículos
  • Autores: Anand Subramanian, Puca Huachi Vaz Penna, Luiz Satoru Ochi e Marcone Jamilson Freitas Souza
  • DOI:10.7436/2013.mhpo.11
  • Resumo: Este capítulo apresenta um algoritmo heurístico, baseado na meta-heurística Iterated Local Search, para resolver diversas variantes do Problema de Roteamento de Veículos. São descritos os procedimentos de construção das soluções iniciais, as estruturas de vizinhança para explorar o espaço de soluções, o esquema de busca local, assim como os mecanismos de perturbação. Foram realizados experimentos computacionais em conjuntos consagrados de problemas-teste da literatura referente às variantes consideradas. Os resultados mostraram que o algoritmo desenvolvido produz soluções finais de alta qualidade e baixa variabilidade. Além disto, considerando o conjunto de problemas-teste usados, ele detém mais de 80% dos melhores resultados da literatura.
  • Palavras-chave: Problemas de Roteamento de Veículos, Iterated Local Search, Meta-heurística.
  • Abstract: This work presents a heuristic algorithm, based on the Iterated Local Search (ILS) metaheuristic, for solving different variants of the Vehicle Routing Problem. The construction procedures, the neighborhood structures to explore the solution space, the local search scheme and the perturbation mechanisms are described. Computational experiments were carried out in well-known benchmark instances of the variants considered. The results showed that the developed algorithm produces high quality solutions with small variability. In addition, when considering the set of test-problems used, the proposed algorithm holds more than 80% of the best known results of the literature..
  • Keywords: Vehicle Routing Problem, Iterated Local Search, Metaheuristic.
PDF do capítulo (0,697 MB):
BIBTEX do capítulo:

 

Os comentários estão encerrados.