Bandwidth packing: A tabu search approach

Bandwidth packing: A tabu search approach

0.00 Avg rating0 Votes
Article ID: iaor1994307
Country: United States
Volume: 39
Start Page Number: 17
End Page Number: 29
Publication Date: Apr 1993
Journal: Management Science
Authors: ,
Keywords: communication, search, heuristics
Abstract:

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 the authors 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. The authors establish the effectiveness of the present approach by comparing its performance in speed and solution quality to other specialized heuristics and to a standard optimization package appled to a 0-1 integer programming formulation of the problem.

Reviews

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