This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Gamvros, I. Articles by Raghavan, S. Search for Related Content

The Multilevel Capacitated Minimum Spanning Tree Problem

The Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742-1815, USA
The Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742-1815, USA
The Robert H. Smith School of Business, University of Maryland, College Park, Maryland 20742-1815, USA
igamvros{at}rhsmith.umd.edu
bgolden{at}rhsmith.umd.edu
raghavan{at}umd.edu

In this paper, we consider the multilevel capacitated minimum spanning tree (MLCMST) problem, a generalization of the well-known capacitated minimum spanning tree (CMST) problem, that allows for multiple facility types in the design of the network. We develop two flow-based mixed integer programming formulations that can be used to find tight lower bounds for MLCMST problems with up to 150 nodes. We also develop several heuristic procedures for the MLCMST problem. First, we present a savings-based heuristic. Next, we develop local search algorithms that use exponential size, node-based, cyclic and path exchange neighborhoods. Finally, we develop a hybrid genetic algorithm for the MLCMST. Extensive computational results on a large set of test problems indicate that the genetic algorithm is robust and, among the heuristics, generates the best solutions. They are typically 6.09% from the lower bound and 0.25% from the optimal solution value.

Key words: networks; tree algorithms; heuristics; local search; multiexchange neighborhood; genetic algorithms
History: received June 2003; revised October 2004; accepted November 2004.