GRASP with hybrid heuristic-subproblem optimization for the multi-level capacitated minimum spanning tree problem |
| |
Authors: | Alexandre X Martins Mauricio C de Souza Marcone J F Souza Túlio A M Toffolo |
| |
Institution: | (3) Institute Wirtschaftswissenschaften, Techn University Braunschweig, Braunschweig, Germany; |
| |
Abstract: | We propose a GRASP using an hybrid heuristic-subproblem optimization approach for the Multi-Level Capacitated Minimum Spanning
Tree (MLCMST) problem. The motivation behind such approach is that to evaluate moves rearranging the configuration of a subset
of nodes may require to solve a smaller-sized MLCMST instance. We thus use heuristic rules to define, in both the construction
and the local search phases, subproblems which are in turn solved exactly by employing an integer programming model. We report
numerical results obtained on benchmark instances from the literature, showing the approach to be competitive in terms of
solution quality. The proposed GRASP have in fact improved the best known upper bounds for almost all of the considered instances. |
| |
Keywords: | Multi-level capacitated minimum spanning tree problem Network design GRASP Subproblem optimization Local search |
本文献已被 SpringerLink 等数据库收录! |