×

Bandwidth packing: A tabu search approach. (English) Zbl 0774.90033

Summary: The bandwidth packing (BWP) problem is a combinatorially difficult problem arising in the area of telecommunications. The problem consists of assigning calls to paths in a capacitated graph, such that capacities are not violated and the total profit is maximized. In this paper we discuss the development of a tabu search (TS) method for the BWP problem. The method makes use of an efficient implementation of the \(k\)-shortest path algorithm, that allows the identification of a controlled set of feasible paths for each call. A tabu search is then performed to find the best path assignment for each call. The TS method developed here incorporates a number of features that have proved useful for obtaining optimal and near optimal solutions to difficult combinatorial problems. We establish the effectiveness of our approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem.

MSC:

90B18 Communication networks in operations research
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C09 Boolean programming
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization

Software:

Tabu search
PDF BibTeX XML Cite
Full Text: DOI