GRASP com Memória Adaptativa Aplicado ao Problema de Roteamento e Scheduling de Sondas de Manutenção

• Tiago Araújo Neves UFF
• Luiz Satoru Ochi UFF

Resumo

Este artigo apresenta algumas propostas para melhorar o desempenho da metaheurística GRASP applicado para o Problema de Roteamento Scheduling de Sondas de Manutenção (PRSSM). Este problema consiste em gerar roteiros para sondas de manutenção nos poços de petróleo. Este trabalho enfoca análises do algoritmo GRASP adicionando procedimentos de Memória Adaptativa (GRASP+MA). Resultados computacionais mostram que o GRASP+MA supera o desempenho do GRASP tradicional, indicando que o uso de fases de aprendizado pode melhorar significativamente o desempenho deste tipo de metaheurísticas.

Referências

Aloise, D., Noronha, T., Maia, R. S., Bittencourt, V., and Aloise, D. (2002). Heurística de colônia de formigas com path-relinking para o problema de otimização da alocação de sondas de produção terrestre. In Anais do XXXIV Simpósio Brasileiro de Pesquisa Operacional (SBPO).

de Noronha, T. F. and Aloise, D. J. (2001). Algoritmos e estratégias e solução para o problema do gerenciamento de sondas de produção terrestre na bacia petrolífera potiguar. Revista eletrônica de iniciação científica, 1(2):1–11.

Festa, P. and Resende, M. (2002). Essays and Surveys on Metaheuristics, chapter GRASP: An annotated bibliography, pages 325–367. Kluwer Academic Publishers.

Glover, F. and Laguna, M. (1997). Tabu Search. Kluwer Academic Publishers.

Glover, F., Laguna, M., and Martí, R. (2000). Fundamentals of scatter search and path relinking. Control and Cybernetics, 39:653–684.

Gonçalves, L. B., Martins, S. L., and Ochi, L. S. (2005). A grasp with adaptive memory for a period vehicle routing problem. In Proceedings of the International Conference on Computational Intelligence for Modelling Control and Automation, volume 1, pages 721–727, Vienna, Austria. IEEE.

Prais, M. and Ribeiro, C. C. (2000). Reactive grasp: an application to a matrix decomposition problem in tdma traffic assignment. INFORMS Journal on Computing, 12:64–176.

Resende, M. and Ribeiro, C. C. (2002). Handbook of Metaheuristics, chapter Greedy randomized adaptive search procedures (GRASP), pages 219–249. Kluwer Academic Publishers.

Silva, G. C., Andrade, M. R. Q., Ochi, L. S., Martins, S. L., and Plastino, A. (2007). New heuristics for the maximum diversity problem. To appear in Journal of Heuristics.

Taillard, E., Gambardella, L., Gendreau, M., and Potvin, J.-Y. (2001). Adaptive memory programming: A unified view of metaheuristics. European Journal of Operation Research, 135:1–16.

Talbi, E.-G. (2002). A taxinomy of hybrid metaheuristics. Journal of Heuristics, 8:541–564.

Trindade, V. (2005). Desenvolvimento e análise experimental da metaheurística grasp para um problema de planejamento de sondas de manutenção. Master’s thesis, Universidade Federal Fluminense UFF.