A tabu search algorithm for the capacitated shortest spanning tree problem

A tabu search algorithm for the capacitated shortest spanning tree problem

0.00 Avg rating0 Votes
Article ID: iaor2002395
Country: United States
Volume: 29
Issue: 3
Start Page Number: 161
End Page Number: 171
Publication Date: Apr 1997
Journal: Networks
Authors: , , ,
Keywords: tabu search
Abstract:

The Capacitated Shortest Scanning Tree Problem consists of determining a shortest spanning tree in a vertex weighted graph such that the weight of every subtree linked to the root by an edge does not exceed a prescribed capacity. We propose a tabu search heuristic for this problem, as well as dynamic data structures developed to speed up the algorithm. Computational results on new randomly generated instances and on instances taken from the literature indicate that the proposed approach produces high-quality solutions within reasonable computing times.

Reviews

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