Article ID: | iaor20052191 |
Country: | United Kingdom |
Volume: | 32 |
Issue: | 1 |
Start Page Number: | 59 |
End Page Number: | 86 |
Publication Date: | Jan 2005 |
Journal: | Computers and Operations Research |
Authors: | Magyar Gbor, Gdor Istvn |
Keywords: | communication, heuristics |
This paper deals with the problem of cost-optimal hierarchical topology planning for telecommunications access networks. The generalized problem is computationally hard and only its substantially simplified variants have been studied before. We propose a heuristic algorithm relying on iterative problem decomposition, clustering methods and local optimization. The main idea of the approach is to combine clustering and local optimization operators and to apply the combined operators iteratively within the levels of the hierarchy. By an extensive empirical analysis it is shown that the presented method efficiently solves the underlying optimization problem for instances of practical size, furthermore, it is robust to handle flexibility in the problem statement and in the cost function.