Multi-layer network design problems in telecommunication

Abstract

Telekomünikasyon ağ tasarımı problemi, ağın trafik talebinin karşılanması için ana donanımlar ve bağlantılarından oluşan bir telekomünikasyon ağının, topoloji, kapasite ve teknoloji kısıtları altında konfigüre edilmesini içerir. Telekomünikasyon ağlarının planlaması farklı disiplinlerdeki araştırmacılar tarafından çok çalışılmıştır ve literatürü oldukça karmaşıktır. Bu çalışmada, literatürdeki telekomünikasyon ağ tasarımı problemleri yöneylem araştırması bakış açısı ile sınıflandırılmış ve tasarım problemlerini optimizasyon problemleri ile eşlemek amacı ile tasarım problemleri taranmıştır. Literatür taraması, temel olarak karar problemlerini, matematiksel formülasyonlar ve ilgili ağ optimizasyonu problemleri için etkin çözüm yöntemlerini irdelemektedir. Çalışmamızda birbirlerine bağımlı olarak çalışan birden fazla ağ katmanından oluşan telekomünikasyon ağlarının tasarımını içeren çok katmanlı telekomünikasyon tasarım problemi işlenmiştir. Ayrıca, problemin alt problemleri belirtilmiş ve mevcut model ve formülasyonların yeterlilikleri araştırılmıştır. Tüm katmanları tek bir büyük ağ üzerinde modelleyen ve çeşitli pratik karar problemlerini birleştiren yeni bir matematiksel formülasyon önerilmiştir. Mevcut formülasyonlar kullanılarak hesaplama yapılamayan ikiden fazla katmanlı test problemlerinin önerilen matematik formülasyon ile genel amaçlı tamsayılı program çözücüler kullanılarak çözülebildiği görülmüştür. Ayrıca, genel amaçlı çözücülerin çözemediği daha büyük telekomünikasyon ağ problemlerini çözebilmek için Benders ayrıştırma metoduna dayalı ve probleme özel olarak uyarlanmış çözüm algoritmaları geliştirilmiştir. Bu algoritmaların davranışlarını değerlendirmek amacı ile literatürde mevcut test problemleri birleştirilerek kapsamlı hesaplama deneyleri yapılmış ve başarılı sonuçlar sunulmuştur.

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.