The multilevel capacitated minimum spanning tree problem

The multilevel capacitated minimum spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor20071425
Country: United States
Volume: 18
Issue: 3
Start Page Number: 348
End Page Number: 365
Publication Date: Jun 2006
Journal: INFORMS Journal On Computing
Authors: , ,
Keywords: heuristics: genetic algorithms
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.

Reviews

Required fields are marked *. Your email address will not be published.