Çok amaçlı çok atamalı ana düğüm ağ tasarımı problemi için metasezgisel yaklaşımlar

Abstract

Bu tezde, çok amaçlı çok atamalı anadüğüm ağ tasarımı ve yönlendirme problemi için yenibir model sunuyoruz. Model, ağdaki ana düğümlerin atanmasını, ana düğümler arası ve anadüğüm ve düğümler arası ağın tasarımı, ve her bir kaynak-hedef düğüm ikilileri için ağiçerisindeki yönlendirmenin tasarlanmasını kapsar. Seçilen ana düğümlerin herbirinin kendiiçerisinde bağlı olma koşulu yoktur, ve ağdaki herbir ana düğüm ve düğümler arasıbağlantıların önceden belirlenmiş kapasite kriterleri vardır. Çok amaçlı problemin amaçları;toplam sabit masrafların ve yönlendirme masraflarının toplamının minimizasyonu veyönlendirmedeki maksimum ulaştırma süresinin minimizasyonudur. Bu tezde çok amaçlıproblem için matematiksel formül tasarlanmış ve bu alanda sıklıkla kullanılan çok amaçlıgenetik algoritma ve benzetimli tavlama tabanlı meta-sezgisel çözümler sunulmuştur.Tasarlanan matematiksel formülasyonu kullanarak, 5 düğümlü ve 7 düğümlü küçük ağlariçin optimum çözümü bulabiliyoruz. Geliştirdiğimiz sezgisel yaklaşımın performansınıgerçek verilerle ölçmek için, hesaplama deneyleri 20 düğüme indirgenmiş Avustralya postaveri seti ve Türk posta sistemi veri seti üzerinde yapılmıştır. Karşılaştırmalı kıyaslamalargeliştirilmiş tüm sezgisel operatörler için yapılmış, en iyi konfigürasyonların sonuçlarıtartışılmıştır. Sonuçlar, tasarladığımız sezgisel yaklaşımın makul süreler içerisinde;Avustralya posta sistemi için 15 saniyeden kısa bir sürede ve Türk posta sistemi için 10dakikadan kısa bir sürede olası çözümler bulabilmiştir.

In this thesis, we propose a new model for the multi-objective multiple allocation hubnetwork design and routing problem which contains determining the location of hubs, thedesign of hub network, and the routing of commodities between source-destination pairs inthe given network. The selected hubs are not assumed to be fully connected, and each nodeand arc in the network has capacity constraints. The multiple objectives of the problem arethe minimization of total fixed and transportation costs and the minimization of themaximum travel time required for routing. We propose a mathematical formulation for themulti-objective problem and present 2 meta-heuristic solutions, one based on a well-knownmulti-objective evolutionary algorithm and the other based on simulated annealingalgorithm. Using the proposed formulation, we are able to find optimal solution for smallnetworks of 5 nodes and 7 nodes. To evaluate the performance of our heuristic approach onreal data, the computational experiments are conducted on reduced AP data set with 20nodes and Turkish postal system data set. Comparative benchmarks are applied to a numberof heuristic operators and results of best configurations are discussed. The resultsdemonstrate that our heuristic approach can find feasible solutions to the problem inreasonable execution time, which is less than 15 seconds for AP data set and less than 10minutes for Turkish postal system data set.