Bandwidth Packing: A Tabu Search Approach

Manuel Laguna and Fred Glover
Additional contact information
Manuel Laguna: Graduate School of Business and Administration, Campus Box 419, University of Colorado at Boulder, Boulder, Colorado 80309-0419
Fred Glover: U.S. West Chair in Systems Science, Graduate School of Business and Administration, Campus Box 419, University of Colorado at Boulder, Boulder, Colorado 80309-0419

Management Science, 1993, vol. 39, issue 4, 492-500

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 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.

Keywords: tabu search; k-shortest paths; call routing (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (36)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.39.4.492 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:39:y:1993:i:4:p:492-500

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().