Um GRASP eficiente para Problemas de Roteamento de uma Frota de Veículos
DOI:
https://doi.org/10.5540/tema.2006.07.01.0149Resumo
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
Como Citar
Edição
Seção
Licença
Política para Periódicos de Acesso Livre
Autores que publicam nesta revista concordam com os seguintes termos:
- Autores mantém os direitos autorais e concedem à revista o direito de primeira publicação, com o trabalho simultaneamente licenciado sob a Licença Creative Commons Attribution que permite o compartilhamento do trabalho com reconhecimento da autoria e publicação inicial nesta revista.
- Autores têm autorização para assumir contratos adicionais separadamente, para distribuição não-exclusiva da versão do trabalho publicada nesta revista (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento de autoria e publicação inicial nesta revista.
- Autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) a qualquer ponto antes ou durante o processo editorial, já que isso pode gerar alterações produtivas, bem como aumentar o impacto e a citação do trabalho publicado (Veja O Efeito do Acesso Livre).
- Esta é uma revista de acesso aberto, o que significa que todo o conteúdo é livremente disponível gratuitamente para o usuário ou sua instituição. Os usuários estão autorizados a ler, baixar, copiar, distribuir, imprimir, pesquisar ou vincular os textos completos dos artigos, ou usá-los para qualquer outro propósito legal, sem pedir permissão prévia do editor ou do autor. Isso está de acordo com a definição de acesso aberto do BOAI.
Todo o conteúdo do periódico está licenciado sob uma Licença Creative Commons do tipo atribuição BY.