Um GRASP eficiente para Problemas de Roteamento de uma Frota de Veículos

Autores

  • A. Tortelly Jr.
  • L.S. Ochi

DOI:

https://doi.org/10.5540/tema.2006.07.01.0149

Resumo

Apresentamos neste artigo, uma nova metaheurística híbrida baseada em conceitos de Greedy Randomized Adaptive Search Procedure (GRASP) e Busca Tabu (BT) para a solução do Problema de Roteamento Periódico de Veículos (PRPV). A busca local do algoritmo GRASP é efetuada através de um procedimento BT incorporando estratégias de intensificação e diversificação. Resultados computacionais obtidos de conjuntos de instâncias da literatura mostram que o algoritmo proposto é altamente competitivo quando comparado com as heurísticas e metaheuristicas existentes para o PRPV.

Referências

[1] E. Beltrami, e L. Bodin,, Networks and vehicle routing for Municipal Waste Collection, Networks, 4 (1974), 65-94.

N. Christofides e J. Beasley, The PRP, Networks, 14 (1984), 237-256.

F. Cordeau, M. Gendreau e G. Laporte, A Tabu search heuristic for period reuting problems, Networks, 30 (1997), 105-119.

F. Glover e M. Laguna, “Busca Tabu”. Kluwer Academic Pub. 1998.

B.L. Golden, I.M. Chao e E.Wasil, An improved heuristic for the period vehicle routing problem. Networks, 25-44, (1995).

L.S. Ochi, L.M.A. Drummond, D.S. Vianna e A.O. Victor, A parallel evolutionary algorithm for the VRP, Future Generation Computer Systems Journal, Elsevier Science, 14, (1988), 285-292.

M. Resende, L.S. Pitsoulis, GRASP, in “Handobook of Applied Optimization”, Oxford Univ. Press, pp. 168-182, 2002.

R.A. Russell e D. Gribbin, A multi-phase approach to the period routing problem. Networks, 21 (1991), 747-765.

M. Silva, L. Drummond e L.S. Ochi, Metaheuristics based on GRASP and VNS for solving the Traveling Purchaser Problem, Proc. of the IV Metaheuristic International Conference, 12-17, Porto, Portugal, 2001.

C.C.R. Tan e J.E. Beasley, A heuristic algorithm for the period vehicle routing problem. Omega, 12, No. 5 (1984), 497-504.

Instâncias do PRPV: Disponível em http://mscmga.ms.ic.ac.uk/jeb/orlib/ .

Downloads

Publicado

2006-06-01

Como Citar

Tortelly Jr., A., & Ochi, L. (2006). Um GRASP eficiente para Problemas de Roteamento de uma Frota de Veículos. Trends in Computational and Applied Mathematics, 7(1), 149–158. https://doi.org/10.5540/tema.2006.07.01.0149

Edição

v. 7 n. 1 (2006)

Seção

Artigo Original

Licença

Direitos Autorais

Autores de artigos publicados no periódico Trends in Computational and Applied Mathematics mantêm os direitos autorais de seus trabalhos. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Os autores concedem ao periódico o direito de primeira publicação.

Propriedade Intelectual e Termos de uso

O conteúdo dos artigos é de responsabilidade exclusiva dos autores. O periódico utiliza a Atribuição Creative Commons (CC-BY) nos artigos publicados. Esta licença permite que os artigos publicados sejam reutilizados sem permissão para qualquer finalidade, desde que o trabalho original seja corretamente citado.

O periódico encoraja os Autores a autoarquivar seus manuscritos aceitos, publicando-os em blogs pessoais, repositórios institucionais e mídias sociais acadêmicas, bem como postando-os em suas mídias sociais pessoais, desde que seja incluída a citação completa à versão do website da revista.