Uncapacitated multiple allocation hub location problem under congestion

Abstract

Ana dağıtım üsleri, ulaşım, lojistik ve telekomünikasyon sistemlerinde kullanılan özel tesislerdir. Ana dağıtım üsleri, havayolu endüstrisi, posta veya kargo hizmetleri, tedarik zinciri yönetimi, bilgisayar ağları, acil durum hizmetleri gibi birçok farklı alanda ortaya çıkmaktadır. Ana dağıtım üssü, toplama, değiştirme ve dağıtma merkezi olarak hizmet eder ve daha az dolaylı bağlantıya sahip tüm düğümler arasındaki doğrudan bağlantıların değiştirilmesine izin verir. Ana dağıtım üssü, akış konsolidasyonu ve yayılması yoluyla ölçek ekonomisinden yararlanmaktadır. Gidiş-geliş çiftlerinin her birini doğrudan haritalamak yerine, farklı düğümlerden gelen akışlar ana dağıtım üssünde toplanır ve aynı düğüme giden akışlar bu ana dağıtım üssünden dağıtılır. Ana dağıtım üssü yerleşim problemi, sosyal, politik ve ekonomik yönleriyle stratejik başarıya ulaşmada yardımcı olan belirleyici bir rol oynayabilir ve bu kararlar kolayca veya düzenli olarak değiştirilemez. Ana dağıtım üslerinin konumu, rotalama ve lojistik kararlar gibi ağ tasarımından kaynaklanan stratejik kararlar için özellikle önemlidir. Ana dağıtım üssü yerleşim problemi, merkezlerin konumu ve düğümlerin merkezlere atanması ile ilgilidir. Sorunun amacı, en uygun ana dağıtım üssü konumunu bulmak ve ana dağıtım üslerine karşılık gelen ana dağıtım üssü olmayan diğer düğümleri minimum maliyetle veya zamanla atamaktır. Bu iki karar birbirini karşılıklı olarak etkilediğinden, birlikte tartışılmalıdır. Bu nedenle, ana dağıtım üssü yerleşim problemi, ağ tasarım problemi olarak düşünülmelidir. Ana dağıtım üssü yerleşim problemi 20. yüzyılın son çeyreğinden bu yana önemli bir araştırma konusu olmuştur. Ana dağıtım üssü yerleşim problemlerine gösterilen büyük öneme rağmen, araştırmacıları mevcut literatürdeki boşluklar, nadiren araştırılan alanlar ve problemin gelecekteki motivasyonları hakkında aydınlatmaya ihtiyaç vardır. Dolayısıyla bu tez, temel problemden mevcut uzantılarına kadar bir sınıflandırma yapısı ile başlamaktadır. Seçilmiş 400 makalenin detaylıca değerlendirilmesi ile bir sınıflandırma yapısı önerilmektedir. Daha sonra ayrıntılı bir literatür taraması sunulmakta, her bir sınıfın önemli çalışmaları örneklenmekte ve son trendler konu başlıkları gruplanarak incelenmektedir. Hava taşımacılığında ve diğer ulaşım ağlarında, müşteri ihtiyaçlarını karşılamak ve rekabet avantajı sağlamak için ağı mümkün olduğu kadar genişletmek önemlidir. Ana dağıtım üssü yerleşim problemi, merkezler arası bağlantı maliyetinin düşürüldüğü ölçek ekonomilerinden faydalanırken; taşıma ve açılış maliyetlerini en aza indirgemeyi amaçlar. Problem minimum açılış ve ulaşım maliyetlerini belirlemeye odaklanırken, nispeten az sayıda ana dağıtım üssü seçilir. Bu seçilen ana dağıtım üsleri, üs olmayan düğümlere kıyasla aşırı yüklenmiş durumdadırlar. Ayrıca, ağa daha fazla düğüm eklenir, düğümler arasındaki akışları dengelemek için daha fazla kapasite kısıtlaması uygulanır. Temel olarak, son zamanlarda, hava taşımacılığı şirketleri, gecikmeler veya trafik sıkışıklığı gibi istenmeyen sonuçları çözmek ve merkez havaalanlarının trafik akışı yoğunluğunu optimize etmek istemektedir. Ana dağıtım üslerinin kapasiteleri zaman içindeki artan trafik akışlarına karşı hassas olma eğilimindedir. Bu nedenle, ana dağıtım üssü yerleşim problemleri kapasite özelliklerini düşünerek mevcut literatürde yer almak zorundadır. "Kapasite" terimi ana dağıtım üslerinde bir sınırlamaya işaret eder. Ancak, olası ana dağıtım üslerinin kapasite düzeyleriyle sınırlandırılması, soruna gerçekçi bir yaklaşım getiremez. Son yıllarda, ana dağıtım üslerinde yüklenilen kapasiteyi aşan ilave bir akış olarak yeni bir "sıkışıklık" terimi ortaya çıkmıştır. Bu tezde, sıkışıklık tabiri üslerdeki sıkışıklık etkisinin önlenmesi ve ağ tasarımının en iyilenmesi için ayrıntılı bir şekilde incelenmektedir. Sıkışıklığı içeren bir ana dağıtım üssü tasarımı, seçilen üslerin akış dağılımındaki dengesizliği ve üslerdeki aşırı yükleri önlemeyi amaçlar. Modele kapasite kısıtlamalarının dahil edilmesi ağ sıkışıklığı olmaksızın bir tasarıma olanak sağlayabilir, ancak bu tasarım zaman içinde gecikmelere veya kesintilere sonuç olacak talep artışlarını, olası kapasite değişikliklerini göz ardı ederek gerçekçi şekilde projelendirilemez. Bu nedenle, modelde sıkışıklığı bağımsız ancak kapasite, akış konsolidasyonu ve zaman parametreleri ile ilgili olarak tanımlamak önemlidir. Ana dağıtım üssü yerleşim probleminin pratik uygulamalarında, akış miktarı bakımından kapasitenin aşılması ve sıkışıklık meydana gelmesi kaçınılmazdır. Ayrıca, bir sıkışıklık meydana geldiğinde veya ana dağıtım üssünün kapasitesi yetersiz olduğunda, işlem süreleri, zamana bağlı servisler ve gecikmeler gibi ağ yetkinlikleri tetiklenir. Mevcut literatürden farklı olarak, sıkışıklık, akış miktarından ziyade kapasite düzeyi ile ilgilidir. Böylece sıkışıklık, maksimum kapasite seviyelerinde daha etkili hale gelir. Bir ana dağıtım üssü sıkışıklık durumuyla karşılaştığında, bağlantılı maliyetlerin de tahsis edilmesiyle tüm ağ tasarımı olumsuz yönde etkilenir. Ardından, akış miktarı arttıkça, tıkanıklık daha az ağ yeteneklerini etkiler. Genel olarak ana dağıtım üssü yerleşim problemleri, sıkışıklığı bir kapasite seviyesi veya önceden belirlenmiş bir kapasite oranı altında sınırlı olarak düşünür. Sıkışıklığın kaçınılmaz olması nedeniyle tersini tanımlamak çok önemlidir. Bu tezin ana katkısı, her bir ana dağıtım üssü üzerindeki fazla akışın ilgili ana üsteki toplam akışa oranı olarak yenilikçi bir sıkışıklık maliyet fonksiyonunu tanımlamaktır. Bu işlev, her bir ana dağıtım üssündeki kapasite sınırlandırmasının açık bir tespit yapılmadan sağlanmasına yardımcı olur. Ayrıca, hem gelen hem de giden akışlar, ana dağıtım üslerinden geçen toplam akışları belirlemek için toplanır, çünkü yolcu taşımacılığındaki havaalanları, hem gelen hem de giden uçuşların yoğunluğundan muzdarip olabilir. Sıkışıklığın ana dağıtım üssü yeri seçimi ve tahsis kararları üzerindeki etkisini gözlemlemek için, farklı sıkışıklık fonksiyonları karşılaştırmalı olarak sunulur. Başlangıç olarak, üslerin konumunu ve ağın tahsis yapısını belirleyen ve ağlardaki akış dağılımını dengelemek için merkezlerde oluşan sıkışıklığı kontrol eden yeni bir matematiksel model önermekteyiz. Ulaştırma, açılış ve sıkışıklık maliyetlerini en küçükleyen kapasite kısıtsız çok atamalı ana dağıtım üssü yerleşim problemi olarak karışık tam sayılı programlama modeli önerilmektedir. Bu tez boyunca, önerilen model kapasiteleri istenilen seviyeden daha yüksek olan ve ana dağıtım üsleri üzerindeki sıkışıklığın gene de amaç fonksiyonunda ceza maliyeti olarak dikkate alındığı ana dağıtım üssü yerlerini bulmayı amaçlamaktadır. Bu nedenle, ana dağıtım üsleri üzerlerindeki fazla akışlardan kaynaklanan ceza maliyetlerini en aza indirmek için, daha yüksek kapasiteye sahip olan düğümler arasından seçim yapılmaktadır. Optimizasyon problemlerinin modellenmesinde ana endişe, karar değişkenlerinin ve kısıtların sayısı anlamındaki problemin boyutudur. Karmaşıklık ve hesaplama süresi bakımından problemin boyutu çözüm sürecini zorlaştırır. Optimal çözüme ulaşmak için klasik çözüm teknikleri artan karar değişkeni ve kısıt sayısı karşısında yetersiz kalır. Bu zorlukların üstesinden gelmek için, Benders ayrıştırma tekniği gibi ayrıştırma teknikleri ve sezgisel algoritmalar uygulanabilir. Her ne kadar modelin matematiksel formülasyonları optimal çözümü başarabilse de, problemin boyutu ve hesaplama süresi çözümü daha karmaşık hale getirmektedir. Bu nedenle, önerilen doğrusal olmayan modelin nispeten daha çok çaba gerektiren bir çözüm prosedürüne ihtiyacı vardır. Bu tezin bir başka katkısı, karmaşık problemlerle başa çıkmak için etkili çözüm prosedürleri geliştirmektir. Sonuç olarak, önerilen modeli çözmek için kesin bir çözüm prosedürü olarak Benders ayrıştırma algoritması ve bir sezgisel algoritma olarak parçacık sürüsü optimizasyonu geliştirilmektedir. İlk olarak, Benders ayrıştırma algoritması probleme uygulanmaktadır. Benders algoritmasını uygulamak için karesel sıkışıklık maliyeti fonksiyonu doğrusallaştırılmaktadır. Ancak, algoritma beklenenden daha fazla zaman alıcı hale gelmiştir. İkinci olarak, büyük ölçekli problemler için en yakın optimal çözümleri bulmak için etkili bir parçacık sürüsü optimizasyon algoritması önerilmektedir. Tüm çözüm prosedürleri önerilen model yapısına uyarlanmıştır. Sayısal analizler AP veri setinde gerçekleştirilmiştir. Her iki çözüm prosedürü de karşılaştırmalı olarak incelenmiştir. Problemin çeşitli versiyonları (kapasite kısıtsız, kapasite kısıtlı ve sıkışık) ve üç ayrı sıkışıklık fonksiyonuyla modellenen problemler karşılaştırmalı olarak analiz edilmiştir. Sıkışıklık fonksiyonunun farklı tanımlanması ya da sıkışıklık faktörü, kapasite seviyesi, ölçek ekonomilerinin değişimi dahil olmak üzere farklı senaryolar altında deneyler yapılmıştır. Ayrıca, iterasyon sayısı, popülasyon büyüklüğü, öğrenme katsayıları gibi farklı parametreler altında sezgisel algoritmanın verimliliğini karşılaştırmak için duyarlılık analizleri incelenmiştir. Son olarak, önerilen tüm modellerin hesaba dayalı deneyleri ve tartışmaları sunulmuştur ve önerilen çözüm prosedürlerinin hesaplama performansları test edilmiştir

Hubs are customized facilities whereby used in transportation, logistics and telecommunication systems. Hubs appear in many various fields such as airline industry, postal or cargo services, supply chain management, computer networks, emergency services. Hubs serve as consolidation, switching and sorting centers, and allow for the replacement of the direct connections between all nodes with fewer indirect connections. Hubs benefit from economies of scales by flow consolidation and dissemination. The flows originated from different nodes are accumulated in a hub and the flows designated to the same node are distributed from this hub rather than mapping directly each of the origin-destination pairs. Hub location problems could play a decisive role which helps to achieve strategic success with its social, political and economic aspects and these decisions couldn't modify easily or regularly. Location of hubs is significantly important for the strategical decisions arised from network design such as routing and logistic decisions. Hub location problem deal with the location of hubs and allocation of nodes to hubs. The purpose of the problem is to find the optimum hub location and assign non-hub nodes corresponding hubs at minimum cost or time. Since these two decisions have mutually influenced each other, they should be discussed together. Thus, hub location problem should be considered as a design problem of the networks. The hub location problem has been an important subject of research since the last quarter of 20th century. Despite of great attention on the hub location problem, there is needed to enlighten researchers about the gaps of existing literature, fields that are rarely investigated and the future directions of the problem. Therefore, this thesis starts with a classification structure covered from basic problem to its existing extensions. A classification structure is proposed by reviewing elaborately selected 400 papers. Then, a detailed literature review is presented, significant studies of each classes are exemplified, and recent trends are examined by grouping topics. In air transportation, as well as in other transportation networks, it is important to extend the network as large as possible to satisfy the customer needs and to obtain competitive advantage. The hub location problem aims to minimize the transportation and opening costs while taking the advantage of economies of scale where the cost of inter-hub connections is discounted. While the problem focuses on obtaining a minimum set of opening and transportation costs, a relatively small number of hubs are selected. These hubs are likely to be overloaded in comparison to non-hub nodes. Besides, the more nodes are inserted to the network, the more capacity restrictions are imposed to balance the flows between nodes. Essentially, in recent times, the air transportation companies seek to resolve these undesired consequences such as delays or congestion and optimize traffic flow density of their hub airports. Hubs' capacities tend to be sensitive against the increasing volume of traffic flows in time. Hence, considering capacity features of the hub location problem had to be included in the existing literature. The term "capacity" indicates a limitation on hubs. However, restricting possible hub nodes with capacity levels could not represent a realistic approach to the problem. In recent years, a new term "congestion" has been introduced as an additional flow in excess of the capacity which is imposed on hubs. In this thesis, the congestion term is investigated to optimize network design and to avoid congestion effect at hubs. A hub network design including congestion aims to prevent the imbalance of flow distribution of selected hubs and the overloads at hubs. Including capacity restrictions to model could design a network without congestion, however this design couldn't project realistically due to ignoring increases of demands in time, possible changes in capacity resulting from delays or disruptions. So, it is important to introducing congestion in the model independently, but related to capacity, flow consolidation and time parameters. For practical applications of hub location problem, exceeding capacity in terms of the amount of flow and occurring congestion is unavoidable. Also, once a congestion is occurred or capacity of hub become insufficient, network capabilities as processing time, time dependent services and delays is triggered. Unlike the existing literature, congestion is more involved in capacity level than the amount of flow. Thus, congestion becomes more effective around the maximum capacity level. When a hub faces with congestion situation, all network design is adversely influenced that the associated cost should be charged. Subsequently, more the amount of flow increase, less the congestion affects the network capabilities. In general hub location problems consider the congestion which is limited under a capacity level or a pre-determined proportion of the capacity. It is significantly crucial to identify reversely due to the fact that the congestion is inevitable. The main contribution of this thesis is to define an innovative congestion cost function which is the proportion of the excess flow on each hub to the total flow through respective hub. This function assists in ensuring the capacity limitation of each hub without an explicit determination. Moreover, both incoming and outgoing flows are summed up to determine total flows through hubs, because airports in passenger transportation may suffer from the intensity of both arriving and departing flights. . In order to observe the effect of the congestion on selection of hubs and allocation decisions, different congestion functions are presented comparatively. Initially, a mathematical model is proposed which determines the location of hubs and allocation structure of the network and controls the congestion at hubs to balance the flow distribution at network. A mixed integer programming model is formulated as an uncapacitated multiple allocation hub location problem that minimizes the transportation cost, opening cost and congestion cost. Throughout this thesis, proposed model aims to locate hubs whose capacities are larger than a desired level and still congestion on hubs is considered as a penalty cost in the objective function. Therefore, hubs are chosen between nodes which have higher capacities in order to minimize the penalty costs arising from surplus flows on hubs. While modeling the optimization problems, main concern is the size of the problem meaning the number of decision variables and constraints of the problem. The size of the problem makes the solution procedure more difficult in terms of the complexity and the computational time. Classical solution techniques to achieve the optimal solution remain incapable upon increasing number of decision variables and constraints. To overcome these difficulties, partitioning procedures such as Benders decomposition technique and heuristic algorithms may be applied. Although mathematical formulations of the model may achieve the optimality, the size of the problem and the computational time make the solution more complicated. Because of this, the proposed non-linear model needs a relatively more effortful solution procedures. Another contribution of this thesis is to develop efficient solution procedures for dealing with complex problems. Consequently, an exact solution procedure, Benders decomposition algorithm, and a heuristic algorithm, particle swarm optimization are developed to solve the proposed model. First, Benders decomposition algorithm is applied to the problem. To apply Benders algorithm, the quadratic congestion cost function is linearized. However, the algorithm become more time-consuming than expected. Secondly, to find near optimal solutions for large-scaled problems, an efficient particle swarm optimization algorithm is proposed. All solution procedures are adapted to proposed model structure. The numerical analyses are performed on Australian Post data set. Both solution procedures are examined comparatively. The various versions of the problem (uncapacitated, capacitated and congested) and problems modeled with three distinct congestion functions are comparatively analyzed. The experiments under different scenarios including the modification of congestion function or the variation in congestion factor, capacity level, economies of scale were made. Besides, the sensitivity analyses to compare the heuristic algorithm's efficiency under different parameters including number of iterations , population size, learning coefficients were examined. Lastly, computational experiments and discussions of all suggested models are presented, and the computational performance of suggested solution procedures are tested.