Paper Info
Title
The Multilevel Capacitated Minimum Spanning Tree Problem
Abstract
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.
Year
DOI
Venue
2006
10.1287/ijoc.1040.0123
INFORMS Journal on Computing
Keywords
Field
DocType
mlcmst problem,well-known capacitated minimum,multilevel capacitated minimum,savings-based heuristic,genetic algorithm,local search algorithm,multilevel capacitated minimum spanning,hybrid genetic algorithm,lower bound,tree problem,heuristic procedure,test problem,local search,genetic algorithms,heuristics,tree algorithms,networks
Capacitated minimum spanning tree,Mathematical optimization,Tree traversal,Distributed minimum spanning tree,Euclidean minimum spanning tree,Integer programming,Spanning tree,Local search (optimization),Mathematics,Minimum spanning tree
Journal
Volume
Issue
ISSN
18
3
1091-9856
Citations 
PageRank 
References 
6
0.54
16
Authors
3
Name
Order
Citations
PageRank
Ioannis Gamvros1202.03
Bruce Golden271.57
S. Raghavan321616.30