GRASP with Adaptive Memory Applied to the Maintenance Probe Routing and Scheduling Problem

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

Abstract

This paper presents some proposals to improve the performance of the GRASP metaheuristic applied to the Workover Rig Routing and Scheduling Problem (WRRSP). This problem consists on create schedules to workover rig set, responsable for doing mantenance on oil wells. This paper focuses on the analysis of GRASP algorithm added with Adaptive Memory Procedures (GRASP+MA). Computational results show that the GRASP+MA outperforms the standard GRASP, indicating that the icnlusion of a learning procdure can significantly improve the performance of this kind of metaheuristic.

References

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.