Stokastik talep altında telekomünikasyon ağlarındaki aracı firmalara yönelik kar en büyüklemesi problemi
Profit maximization problem for intermediaries in telecommunication networks under stochastic demand
Yazar: HASAN HÜSEYİN TURAN
Danışman: PROF. DR. MEHMET NAHİT SERARSLAN
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Endüstri Mühendisliği Ana Bilim Dalı / Endüstri Mühendisliği Bilim Dalı
Derece: Doktora, 2012
Konu: Endüstri ve Endüstri Mühendisliği = Industrial and Industrial Engineering
Dizin: Bulanık doğrusal programlama = Fuzzy linear programming ; Bulanık matematiksel programlama = Fuzzy mathematical programming ; Stokastik doğrusal programlama = Stochastic linear programming ; Stokastik programlama = Stochastic programming ; Telekomünikasyon = Telecommunication ; Telekomünikasyon ağı = Telecommunication network

Özet:
Son on yıl içerisinde telekomünikasyon piyasası birçok servisin, servis sağlayıcısının ve satıcının olduğu çok rekabetçi bir ortam halini almıştır. Günümüzde ister büyük ister küçük olsun bütün şirketler varlıklarını sürdürebilmek ve günlük işlerini ya da operasyonlarını tamamlayabilmek için telekomünikasyon ağlarını çeşitli şekillerde ve miktarlarda kullanırlar. Dolayısı ile şirketler, firma içerisinde ya da firmanın müşteri ve tedarikçileri ile ilişkilerinde ve operasyonlarında internet ağlarını kullanan birer varlık haline gelmiştir.Şirketler yani müşteriler işlerini ve operasyonlarını gerçekleştirebilmek için ihtiyaç duydukları ağ kaynaklarını aracı veya omurga telekomünikasyon firmalarından kiralayabilir veya satın alabilir ve ardından işleri tedarik edilen kaynaklara dağıtarak tamamlayabilirler. Ağ kaynakları kullanılarak gerçekleştirilen birkaç tipik ve önemli örnek: video konferans, VoIP (internet üzerinde telefon görüşmesi), gerçek zamanlı ses/video izleme, gerçek zamanlı işlemsel uygulamalar ve diğer toplu işlem uygulamalarıdır.Telekomünikasyonda karşılaşılan tasarım ve karar problemlerini en geniş kapsamla üç seviyeye ayırarak analiz etmek mümkündür. Bunlar mikro düzeyden makro düzeye sırasıyla; teknoloji, ağ ve kurumsal seviyede ortaya çıkan problemlerdir. Teknoloji düzeyinde yapılan çalışmalar telekomünikasyondaki router ve switch gibi çeşitli elemanların tasarımıyla ilgili problemleri ele almaktadır. Ağ seviyesindeki problemler ise büyüklük ve içerdikleri teknoloji bakımından farklı olabilecek ağların planlanması ve dizaynı ile alakalıdır. Bu seviyede alınan kararlar doğaları gereği dinamik niteliktedir ve birden çok zaman periyodunu içermektedir. Son olarak kurumsal seviye mümkün olan en yüksek seviye birleştirme olarak düşünülebilir. Bu düzeyden telekomünikasyon firmalarına daha geniş endüstriyel bir çevrenin veya piyasanın elemanı olarak bakılır. Bu piyasa çok sayıda ve yapıda diğer endüstriyel aktörleri ve çok çeşitli müşteri profillerini içermektedir. Bu düzeyde alınan kararlar: firmanın piyasaya süreceği hizmet çeşitliliğinin belirlenmesi, stratejik yatırım kararlarının belirlenmesi ve fiyatlandırma politikalarıdırBu çalışmada incelenen problemler kurumsal düzeydeki karar problemlerine örnek olabilecek niteliktedir. Kurumsal düzeyde üç önemli ve ana oyuncunun var olduğu kabulü yapılmıştır. Bu aktörler sırasıyla yukarıda tanımlanan ağ kaynaklarını işlerini tamamlamak için kullanan müşteriler, omurga ağ sağlayıcıları (BP) ve aracılar (IO) diğer adıyla bant genişliği brokerleridir. BP'lar kendi ağ alt yapısına sahipken, IO'lar kendilerine ait ağ kaynakları bulunmamaktadır. Bu nedenden ötürü, IO'lar servis sağlayabilmek için gerekli ağ kapasitesini BP'lardan ya da diğer aracılardan satın alırlar. Sonuç olarak, IO ne kadar kapasite satın alacağına karar verirken BP'de aracıya nasıl bir fiyatlandırma uygulayacağına karar vermektedir.Bu tezde, telekomünikasyon IO'sunun kapasite satın alırken karşılaştığı optimizasyon problemi; çok sayıda omurganın çeşitli şekillerde fiyatlandırma ve hizmet kalitesi sunduğu bir piyasada, stokastik son kullanıcı bant genişliği talebi altında modellemiş ve çözüm önerileri sunulmuştur. Problem IO'nun bakış acısıyla modellenmiş ve aracı rasyonel karar verici olarak kabul edilmiştir.Gerçek hayattaki birçok problemde olduğu gibi telekomünikasyon problemlerinde de belirsizlikler söz konusudur. Telekom ağlarındaki belirsizlikler, sistemin kendi içerisinden ve/veya sistemin çevresinden kaynaklanıyor olabilir. Nereden kaynaklanırsa kaynaklansın belirsizliklerin kesin olarak varsayılarak tanımlanması ve modellenmesi kurulan modellerin gerçekçi olmayan sonuçlar üretmesine neden olur.Bu çalışmada piyasa koşullarından dolayı oluşan belirsizliğin modellenmesinde stokastik programlama (SP) metodolojisi kullanılmıştır. SP'nın temelleri 1954 yılında yöneylem araştırması biliminin de kurucusu olan George B. Dantzig tarafından yayınlanan ?Belirsizlik altında Doğrusal Programlama? makalesi ile atılmış, özellikle günümüz bilgisayarlarının hesaplama gücündeki muazzam artış ile birlikte son 20 yıl içerisinde tedarik zinciri yönetiminden, sağlık alanına enerji kapasite planlamasından telekomünikasyona birçok uygulama alanı bulmuştur.Yürütülen kapsamlı literatür taraması sonucunda, telekomünikasyon ağlarında SP teknikleri çoğunlukla altyapı problemlerinin çözümüne yönelik olarak geliştirilmiş olduğu tespit edilmiş, yönetimsel düzeyde yani kurumsal ortamda aracıların problemini inceleyen bir çalışmaya rastlanmamış olması tezin özgün değerlerinden biridir. Bu bağlamda tezin ilk kısmında literatürde en çok kullanılan ve internet sağlayıcılarının da uyguladığı sırasıyla üç fiyatlandırma stratejisi: sabit fiyatlandırma, kademeli fiyatlandırma ve hacim fiyatlandırma; oluşturulan üç ayrı iki-evreli SP modeline entegre edilmiştir. Bu modeller sayesinde aracıların karar verici mercilerine: hangi omurgadan ne kadar bant genişliğini ne kadar süreyle satın alması; hangi seviyede hizmet kalitesi sunan servis sağlayıcılarının seçmesi; taleplerin realizasyonundan sonra karşılanmasına karar verilen kapasite isteklerinin hizmet kalitesi parametrelerini de göz önüne alarak nasıl satın alınan kapasitelere atanması gerektiği gibi stratejik planlama sorularının çözümleri sunulmaktadır.Tartışılan modellerde, ikinci evrede oluşabilecek bütün durumlar sonlu sayıdaki belli olasılık değerleri atanmış ayrık senaryolar ile ifade edilmiştir. Bunun neticesinde, küçük ölçekli problemler bile çok sayıdaki senaryodan ötürü, standart ticari doğrusal ve tamsayılı programlama yazılımlarının çözebileceği boyutların ötesine geçmektedir. İlk olarak büyük ölçekli karma tamsayılı programlama problemi olan sabit fiyatlandırma modeli Benders ayrıştırma algoritması ile makul süreler içinde çözülmüştür. Ardından, büyük ölçekli doğrusal programlama problemleri olan kademeli ve hacim fiyatlandırma modelleri yine Benders ayrıştırması ile çözülmeye çalışılmıştır. Modellerin özel yapısı olan, senaryoların bloklara ayrılmasından faydalanılarak geliştirilen L-Şekli algoritması ile alt problemler her bir senaryo için ayrı ayrı çözülmüştür. Böylelikle Benders ayrıştırmasının çözemediği test problemleri optimum olarak çözülmüş ve çözüm sürelerinde iyileşmeler sağlanmıştır.Çözüm algoritmalarının performansları ve SP metodolojisinin geçerliliğini sınamak amacıyla çok farklı sayıda ve büyüklükte rassal test verileri oluşturulmuş ve algoritmalar bu verilerle koşulmuştur. Testlerin sonuçlarının karşılaştırılması için Stokastik Çözümün Değeri (VSS) ve Mükemmel Bilginin Beklenen Değeri (EVPI) olmak üzere iki performans istatistiği tanımlanmıştır. Elde edilen istatistiklerin ışığında, telekomünikasyon piyasasındaki belirsizliklerin göz önüne alınarak oluşturulup çözülen stokastik modellerin, belirsizliğin hesaba katılmadığı beklenen değer modellerinin sonuçlarına göre her fiyatlandırma modelinde farklı oranda olsa da daha iyi sonuç verdiği yani aracıya daha yüksek bir kar sağladığı gözlenmiştir.Tezin ikici kısmının ilk yarısında ise, hacim bazlı fiyatlandırma politikası altındaki stokastik doğrusal programlama (SLP) modeline son kullanıcı bant genişliği taleplerinin belirsizliğine ek olarak; amaç fonksiyonundaki bütün maliyet ve kazanç parametreleri bulanıklaştırılmıştır. Oluşan bulanık amaç fonksiyonlu SLP modeli sayesinde telekomünikasyon ağlarında meydana gelebilecek bütün belirsizlikler düşünülerek çözüm aranmıştır. Çözüm yöntemi olarak literatürde bulunan iki algoritma problemin yapısına uygun olarak değiştirilerek, değişik veri kümelerinde koşulmuştur. Sonuçların tutarlılığı ve yöntemin uygulanabilirliği bulanık parametreler üzerinde yapılan duyarlılık analizleri ile test edilmiş. Ek olarak, VSS ve EVPI değerlerinin yanında beklenen talep karşılama oranı, atıl kapasite ve kapasite satın alınan omurga sayısı gibi ikincil istatistikler de hesaplanarak yöntemin tutarlılığı gösterilmiştir.Çalışmanın ikici kısmının son yarısında ise, hacim fiyatlandırma modeli çok amaçlı bulanık SLP yöntemi ile analiz edilmiştir. Amaç fonksiyonlarından birincisi aracının karını en büyüklemeye çalışırken; ikincisi ise omurgalardan satın alınan ya da kiralanan kapasitelerde, altyapı sorunlarından dolayı oluşan kayıpları en küçüklemeye çalışmaktadır. Böylelikle telekom IO'sunun kayıp kapasiteyi son kullanıcılara satabilme fırsatı bulması durumunda oluşabilecek çözümler incelenmiştir. Çözüm algoritmaları olarak sırasıyla maksimum-minimum, ağırlıklı eklenebilir maksimum-minimum ve ağırlık maksimum-minimum yöntemleri seçilerek; farklı amaç fonksiyonu ağırlıkları altında IO'nun nasıl bir şekilde bant genişliği satın alması gerektiği istatistiksel performans çıktıları ile birlikte hesaplanmış ve algoritmaların verimlilikleri analiz edilmiştir.

Abstract:
During the last decade, telecommunications has become a very competitive environment with many vendors, carriers, and services. Nowadays every firm either big or small uses telecommunication networks at different amounts and ways in order to continue their existence and complete their daily tasks and operations. Hence, firms are becoming internet oriented entities that use telecommunications networks to support operations and relationships within the firm, and with their customers and suppliers.Firms, in other words customers, can lease or buy required amount of network resource from either telecommunication network backbones or telecommunication intermediaries to complete their operations, and afterwards each of these mentioned operations are assigned to one of the acquired resources. Some typical and important applications that are carried out by using network sources are: video conferencing, VoIP (phone call over the Internet), real time audio/video streaming, real time transactional applications and other batch transactional applications.It is possible to classify optimization problems that are encountered in telecommunication environment into three different levels such as technological, network and enterprise. The technological level deals with design of different elements of telecommunication networks. Network level problems concentrate on design and planning of different kinds of telecom networks which may differ by size and by technology involved. Decisions are often of dynamic nature and include several time periods. The enterprise level is the highest level of aggregation and looks at the telecommunication enterprise as a member of a larger industrial environment which includes other industrial actors and different consumer types. Decisions involve selection of the range of services which the enterprise will provide to the market, strategic investment decisions, pricing policy.The problem studied in this thesis falls into the enterprise level category. At this level, it is assumed that telecommunications market consists of three important main players, which are previously mentioned: customers who use network capacity to accomplish their tasks, backbone network providers (BP) and intermediaries (IO) or bandwidth brokers. Whereas BPs own the network infrastructure, IOs do not have their own network facilities and in order to provide the service IOs have to lease the necessary network capacity from BPs or other bandwidth brokers. Consequently, IOs have to decide how much capacity to acquire and the BPs decide the price to charge for the network capacity.In this thesis, an optimization problem that an IO faces when acquiring network capacity from a market in which there exist several BP network providers offering different pricing and quality of service schemes is modeled and solution approaches are proposed under stochastic bandwidth request of end-users. The problem is modeled from the IO?s point of view and assumes intermediary is rational decision maker.Telecommunication network problems are due to uncertainties like the other real life problems. The sources of the uncertainties in the telecommunications may be environmental or originated from the system itself. In all circumstances, neglected uncertainties in the models may result in inaccurate solutions.In this study, stochastic programming (SP) methodology is utilized to model the uncertainties arising due to the market conditions. The origin of SP frame work goes back to seminal paper of George B. Dantzing ?Linear Programming under Uncertainty? which was published in the year of 1954 by founder of operation research. Along with increasing computational power of computers in last 20 years, SP has been widely used in many diverse areas such as supply chain management, health care, energy capacity planning and telecommunications.The conducted extensive literature review reveled the fact that SP techniques used in telecommunication networks are developed mostly in order to solve infrastructure problems such as routing of demands in network links. To the best of our knowledge, there is no study related to application of SP at enterprise level which implies one of the uniqueness and contribution of this PhD thesis. In the first part of the thesis, the most commonly used pricing schemes by both internet providers and researchers namely flat rate pricing, tax-band pricing and pay-per-byte pricing are integrated into three separate two-stage SP model. The solutions of these models provide essential strategic planning information to the decision makers of intermediaries such as how much bandwidth for how long should be bought or leased from each backbone, which service providers should be chosen by considering quality of service levels, after realization of customers? demands which customer?s bandwidth request should be accepted and which of them should be rejected and finally how accepted bandwidth demands should be allocated into leased capacity by considering quality of service parameters such as delay and jitter.In the models discussed thus far, all of the possible states for second stage are modeled by a finite number of discrete scenarios with associated realization probability values. As a result, even small problem instances may become really huge due the large number of scenarios. Standard commercial linear and integer programming softwares are not capable of solving even middle size problems with well-known algorithms. Therefore, at first stage, flat rate pricing problem which is large scale mixed integer programming model is solved by using Benders? decomposition algorithm within reasonable time limits. Tax-band and pay-per-byte pricing strategies lead to large scale linear programming models that can be also solved to optimality by Benders? decomposition. In addition, solution times of these models are improved by solving each scenario separately at every iteration for all sub-problems by taking account block separable structure.In the first half of the second part of the thesis, in addition to the randomness of end customers? bandwidth demand at pay-per-byte pricing scheme, unit costs and unit revenues are also assumed as unknown or vague parameters in the market. By introducing mentioned assumption, stochastic linear programming (SLP) model for pay-per-byte policy turned into fuzzy-SLP model with fuzzy objective function coefficients. As solution methods, existing two algorithms in literature are modified to cope with the structure of model and problem. Afterwards, several problem sets are ran by using modified algorithms. Consistency of results and applicability of methods are tested by sensitivity analysis on fuzzy parameters. Besides, secondary performance statistics such as expected demand fulfillment ratio, expected unused capacity and number of selected backbones are calculated in addition to the primary performance measures VSS and EVPI.In the last half of the second part of the thesis, pay-per-byte pricing scheme is analyzed via fuzzy multi-objective SP method. The first objective function of the model tries to maximize the expected profit of intermediary. On the other hand, second objective function aims to minimize capacity loss occurred during capacity acquisition from backbones. This modeling approach enables selling the lost capacity to end users. The max-min, weighted additive max-min and weighted max-min methods are chosen as solution algorithms. The effectiveness and efficiency of algorithms are investigated by changing weights of each objective and then final performance statistics are reported in order to help IO to solve complex capacity purchasing and demand allocation problem.