GRASP Metaheuristic with Adaptive Memory for Solving the Generalized Minimum Spanning Tree Problem

• Cristiane Maria Santos Ferreira UFF
• Luiz Satoru Ochi UFF

Abstract

The Generalized Minimum Spanning Tree Problem consists of given a graph G whose vertices are divided into clusters, finding a tree spanning all clusters of G, in such a way that minimizes the total cost of the edges. Applications of this problem can be found in telecommunications networks, power distribution networks and in agricultural irrigation systems. This paper presents a GRASP metaheuristic with adaptive memory to solve this problem. Experimental results illustrate the effectiveness of the proposed method.

References

Dror, M., Haouari, M., and Chaouachi, J. S. (2000). Generalized spanning trees. European Journal of Operational Research, 120:583–592.

Feo, T., Resende, M., and Smith, S. (1994). A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878.

Feremans, C., Labbé, M., and Laporte, G. (2000). The generalized minimum spanning tree problem: Polyhedral analysis ans branch-and-cut algorithm. Technical report, Université Libre de Bruxelles, Bruxelas, Bélgica. Available at [link].

Fischetti, M., Salazar, J. J., and Toth, P. (1995). The symmetric generalized traveling salesman polytope. Networks, 26:113–123.

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

Golden, B., Raghavan, S., and Stanojević, D. (2005). Heuristic search for the generalized minimum spanning tree. INFORMS Journal on Computing, 17:290–304.

Goncalves, L. B., Ochi, L. S., and Martins, S. L. (2005). A grasp with adaptive memory for a period vehicle routing problem. In Mohammadian, M., editor, Proceedings of International Conference on Computational Intelligence for Modelling, Control & Automation (CIMCA 2005), volume 1, pages 721–727, Vienna, Austria. IEEE Computer Society.

Kansal, A. R. and Torquato, S. (2001). Globally and locally minimal weigth spanning tree networks. Physica A, 301:601–619.

Myung, Y. S., Lee, C. H., and Tcha, D. W. (1995). On the generalized minimum spanning tree problem. Networks, 26:231–241.

Prais, M. and Ribeiro, C. (2000). Reactive GRASP: An application to a matrix decomposition problem in TDMA traffic assignment. INFORMS Journal on Computing, 12:164–176.

Reinelt, G. (1991). TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3:376–384.

Resende, M. and Ribeiro, C. (2003). GRASP and path-relinking: Recent advances and applications. In Ibaraki, T. and Yoshitomi, Y., editors, Proceedings of the Fifth Metaheuristics International Conference (MIC2003), pages 1–6.

Shyu, S. J., Yin, P. Y., Lin, B. M. T., and Haouari, M. (2003). Ant-tree: An ant colony optimization approach to the generalized minimum spanning tree problem. Journal of Experimental and Theoretical Artificial Inteligence, 15:103–112.

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