BANDWIDTH PACKING - A TABU SEARCH APPROACH

The bandwidth packing (BWP) problem is a combinatorially difficult pro blem arising in the area of telecommunications. The problem consists o f assigning calls to paths in a capacitated graph, such that capacitie s 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 prob lem. The method makes use of an efficient implementation of the k-shor test path algorithm, that allows the identification of a controlled se t 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 h ere incorporates a number of features that have proved useful for obta ining optimal and near optimal solutions to difficult combinatorial pr oblems. We establish the effectiveness of our approach by comparing it s performance in speed and solution quality to other specialized heuri stics and to a standard optimization package applied to a 0-1 integer programming formulation of the problem.