Assigning Cells to Switches in Cellular Networks by Incorporating a Pricing Mechanism Into Simulated Annealing

Handoff and cabling costs play key roles in the design of cellular telecommunications networks. Efficient homing of cells to switches can have a significant impact on each of these costs. In the presence of capacity constraints at the switches, the problem of assigning cells to switches becomes a difficult one to solve, with all effective solution approaches being based on heuristic techniques. This paper presents a hybrid heuristic which integrates ideas from linear programming into a simulated annealing framework. Extensive computational results are presented comparing the performance of the heuristic with the lower bound obtained from the linear programming relaxation. These results indicate that this price influenced simulated annealing (PISA) procedure is extremely efficient, usually providing solutions with gaps around 1% in less than 1 s.