A TABU SEARCH ALGORITHM FOR THE CAPACITATED SHORTEST SPANNING TREE PROBLEM

The Capacitated Shortest Spanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the wei ght of every subtree linked to the root by an edge does not exceed a p rescribed capacity. We propose a tabu search heuristic for this proble m, as well as dynamic data structures developed to speed up the algori thm. Computational results on new randomly generated instances and on instances taken from the literature indicate that the proposed approac h produces high-quality solutions within reasonable computing times. ( C) 1997 John Wiley & Sons, Inc.