Problem reduction algorithms for median type hub location problems - Öztürk, Cihat (My University, 2022)
Günümüzün küreselleşen dünyasında, lojistik ve iletişim alanlarındaki son gelişmeler modern vatandaşlar ve organizasyonlar için birçok fırsatı da beraberinde getirmektedir; ancak bu gelişmeler aynı zamanda, karar vericiler tarafından ele alınması gereken çok sayıda zorlu problemi de ortaya çıkarmaktadır. Bu zorlukların birçoğu, optimizasyon problemleri olarak temsil edilmeye uygundur. Ulaştırma ve iletişim ağ sistemlerinde düğüm tahsisi için ağ maliyeti minimizasyonu çerçevesi buna bir örnektir. Ulaştırma ve iletişim ağlarında, hizmet kalitesi ihtiyaçları ile ilgili belirli özellikleri karşılayan bir ağ topolojisi oluşturan konsept ve grup haberleşmede katman ağlar ise diğer örneklerdir. Bu tip problemlerden bir tanesi olan hub konum problemleri de genellikle stratejik seviyeli ağ optimizasyonu problemlerinden bir tanesidir ve ölçek ekonomisi tabanlı ağ yapısını dikkate alır. Bu tezde de konum problemlerinin varyantlarından biri olan hub konum problemleri ele alınır. Hub konum problemleri son yıllarda araştırmacıların en fazla ilgi gösterdikleri konuların başında gelmektedir. Ölçek ekonomisi konsepti ve maliyetleri düşürme stratejileri göz önünde bulundurulduğunda özellikle lojistik ve haberleşme alanlarında uygulanabilirliği yüksek bir problem tipidir. Hub konum problemleri temel olarak üç farklı kategoride değerlendirilebilir. Bunlar p-hub ortanca, p-hub merkez ve hub kapsama problemleridir. Bu tezde odaklanılan problem tipi p-hub ortanca problemleridir. Fakat p-hub ortanca problemlerinin varsayımlarından biri tüm hub konumlarının birbirine bağlı olmasıdır. Fakat gerçek hayat problemlerinde bu durum gerçekçi değildir. Bu yüzden, tamamlanmamış hub konum problemlerine de ayrıca odaklanılmaktadır. Tamamlanmamış hub konum problemlerinde hub ağındaki tüm merkez konumların birbirlerine bağlı olma varsayımı gevşetilmektedir. İlk olarak, küçük boyutlu CAB, TR ve AP veri setleri p-hub ortanca problemleri (hem tamamlanmış hem de tamamlanmamış ağlar için) çerçevesinde derinlemesine analiz edilir. Bu analizler neticesinde problem bazlı olarak optimal hub konumlarına dair özellikler çıkartılmıştır. Bu özellikler çerçevesinde CBCA, HCBCA, BCBCA ve HBCBCA olmak üzere dört farklı çözüm metodolojisi sunulmuştur. Bu metodolojiler temel olarak düğümler arası akış, merkezilik ve uzaklık metriklerini kullanan sezgisel metotlardır. Bu metotların verimliliğinin kanıtlanmasının ardından mevcut meta-sezgisel algoritmalar çerçevesinde çözüm metotları geliştirilir. İlk olarak tavlama benzetimi algoritması, genetik algoritma ve genelleştirilmiş değişken komşu arama algoritması dikkate alınan probleme entegre edilerek çözümler alınır. Daha sonra problem boyutu küçültme stratejisi ile azaltılmış ve genelleştirilmiş değişken komşu arama metodu geliştirilir. Bu metodun klasik meta sezgisel metotlara göre verimliliği küçük, orta ve büyük boyutlu problemler için karşılaştırılır. Elde edilen sonuçlar çerçevesinde R-GVNS algoritması özellikle büyük boyutlu problemlerin çözümü açısından etkili bir yaklaşım olarak görünmektedir. Sonuçların anlamlı olup olmadığı parametrik olmayan istatistiksel testlerden biri olan Wilcoxon İşaretli Sıralar Testi ile karşılaştırılır. Bu bağlamda R-GVNS algoritmasının birçok senaryoda klasik meta sezgisel metotlardan hem çözüm süresi hem de çözüm kalitesi açısından açık ara iyi sonuçlar verdiği saptanmıştır.

In today's globalized world, the recent developments in logistics and communication bring many opportunities for modern citizens and organizations.; however, these developments also raise a number of challenging problems that need to be addressed by decision makers. Several of these difficulties are amenable to representation as optimization methods. An example is the network cost minimization framework for node allocation in transport and communication network systems. In transport and communication networks, concept and overlay multi-cast networks are other examples, which create a network topology that meets certain characteristics related to service quality needs. Hub location problems, one of these types of problems, are generally strategic level network optimization problems and considered economies of scale-based network structure. In this thesis, hub location problems, one of the variants of location problems, are discussed. Hub location problems have been one of the topics that researchers have shown the most interest in recent years. Considering the economy of scale concept and cost reduction strategies, it is a highly applicable problem type, especially in the fields of logistics and telecommunication. Hub location problems can basically be evaluated in three different categories. These are p-hub median, p-hub center and hub covering problems. The problem type focused in this thesis is p-hub median problems. But one of the assumptions of p-hub median problems is that all hub locations are connected to each other. But in real life problems, this situation is not realistic. Thus, incomplete-hub location problems are also focused on. In incomplete hub location problems, the assumption that all locations in the hub network are interconnected is relaxed. First, small-sized CAB, TR and AP datasets are analyzed in depth within the framework of both complete and incomplete p-hub median problems. As a result of these analyzes, the characteristics of the optimal hub locations are extracted specifically for the problem. Based on these features, four different solution methodologies are presented, namely CBCA, HCBCA, BCBCA and HBCBCA. These methodologies are basically heuristic methods that use internode flow, centrality, and distance metrics. After proving the efficiency of these methods, solution methods are developed within the framework of existing meta-heuristic algorithms. First, simulated annealing, genetic algorithm and generalized variable neighborhood methods are integrated into the problem and solutions are obtained. Then, the reduced generalized variable neighborhood method is developed with the problem size reduction strategy. The efficiency of this method compared to classical meta-heuristic methods is compared for small, medium and large sized problems. Within the framework of the results obtained, the R-GVNS algorithm seems to be an effective approach, especially in terms of solving large-sized problems. Whether the results are significant or not is compared with the Wilcoxon Signed Rank Test, which is one of the non-parametric statistical tests. In this context, it has been determined that the R-GVNS algorithm gives better results than classical metaheuristic methods in terms of both solution time and solution quality in many scenarios.
Keywords: Endüstri mühendisliği; Heuristic Algorithms; Industrial engineering; Merkez Konum Problemleri; Meta-Heuristic Algorithms; Meta-Sezgisel Algoritmalar; Problem Azaltma Hub Location Problems; Problem Reduction; Sezgisel Algoritmalar