Multi-layer network design problems in telecommunication


Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Mühendislik Fakültesi, Endüstri Mühendisliği Bölümü, Türkiye

Tezin Onay Tarihi: 2013

Öğrenci: İNCİ YÜKSEL ERGÜN

Eş Danışman: ÖMER KIRCA, HALDUN SÜRAL

Özet:

The telecommunication network design problem is to configure a telecommunication network of major hardware and their links in order to satisfy traffic demands and flows subject to a set of constraints arising from topology, capacity, and technology. Telecommunication network design has been studied in several disciplines and its literature is intricate. In this study, we classify the telecommunication network design problems in the literature from the perspective of operations research and review the network optimization problems to match design problems with optimization problems. Our review examines mainly decision problems, mathematical formulations, and effective solution methods for the relevant network optimization problems. We address the multilayer telecommunication network design problem consisting of networks with several layers working interdependently and investigate its sub-problems and capabilities of existing formulations. We suggest a novel mathematical formulation that models all layers using a single-mega network and incorporates various practical decision problems. Our computational experiments show that the problem instances with more than two layers, which are not computationally tractable with the existing formulations, can be solved using the NFF by general-purpose integer programming solvers. We also develop tailored solution algorithms based on Benders decomposition to solve the large telecommunication network design problems that cannot be handled by general solvers. Consolidating the available test problem instances in the literature, we perform extensive computational experiments on these instances to assess the behavior of the algorithms and to present favorable results.