Stochastic Facility Location Problem with Distributed Demands along the Network Edges

Abstract

Since 1960s, facility location problem (FLP) has been studied by a myriad number of researchers. Nowadays, it is one of the most prominent branches of operations research which is applied in different fields such as determining the location of warehouses, hazardous materials sites, automated teller machines (ATMs), coastal search and rescue stations, etc. Also, the application of FLP in emergency logistics for choosing the best location of service centers has become rampant recently. On the premise that demands are uniformly distributed along the network edges, two network location problems are investigated in this study. For both problems, some of the candidate locations will be selected to establish the facilities. The first problem is a multiple-server congested facility location problem. It is assumed that demands are generated according to the Poisson process. Furthermore, the number of servers in each established facility is considered as a decision variable and the service time for each server follows an exponential distribution. Using queuing system analysis, a mathematical model is developed to minimize the customers’ aggregate expected traveling times and the aggregate expected waiting times. The second problem is a combined mobile and immobile pre-earthquake facility location problem. Each facility is used in the relief distribution operation. It’s incontrovertible that due to earthquakes, some network edges collapse and corresponding areas may lose their accessibility. Thus, it’s assumed that people on intact and accessible edges travel to the location of the distribution centers to receive the relief. For those who are located on collapsed or inaccessible network edges, the medium-scale Unmanned Aerial Vehicle (UAV) helicopters are utilized in the relief distribution operation. The mathematical model developed for this problem minimizes the aggregate traveling time for both people and UAVs over a set of feasible scenarios. In order to demonstrate the applicability of the model developed, a case study based on Tehran earthquake scenarios is presented. Since network location problems are NP-hard, three metaheuristic algorithms including genetic algorithm, memetic algorithm, and simulated annealing are investigated and developed to solve the proposed problems.

ÖZ: 1960'lardan itibaren tesis yer seçimi problemi çok sayıda araştırmacı tarafından incelenmiştir. Tesis yer seçimi günümüzde de yöneylem araştırmasının en önemli dallarından olup, farklı uygulamalarda örneğin, depo, tehlikeli madde sahaları, bankamatikler (ATM), kıyı arama ve kurtarma istasyonlarının yer seçimi gibi alanlarda kullanılır. Ayrıca, tesis yer seçimi uygulamalarından olan acil durum lojistiğinde en uygun servis merkezi yerinin belirlenmesi problemi de son zamanlarda çok yaygınlaşmıştır. Bu çalışmada taleplerin şebeke (ağ) boyunca birbiçimli (uniform) dağılımlı olduğu varsayımı ile iki şebeke yer seçimi problemi üzerinde çalışılmıştır. Her iki problemde de, birkaç aday yer arasından birkaç tesis seçilecektir. Birinci problem, çoklu sunucu tıkanık bir tesis konum sorunudur. Taleplerin Poisson sürecine göre oluşturulduğu varsayılmıştır. Ayrıca, kurulu tesislerin her birinde bulunan sunucu sayısı bir karar değişkeni olarak kabul edilmiş ve her sunucu için servis süresi üssel (exponential) bir dağılım izlemektedir. Kuyruk sistemi analizi kullanılarak, müşterilerin beklenen toplam seyahat süreleri ve beklenen toplam bekleme sürelerini en aza indirgemek için bir matematiksel model geliştirilmiştir. İkinci problem ise, hareketli ve sabit olmak üzere birleşik deprem öncesi tesis konum problemidir. Her tesis yardım dağıtım işleminde kullanılır. Açıktır ki depremlerden dolayı bazı şebeke arklarının (arc) çökmesi ve bundan dolayı bunlara karşılık gelen alanların erişilebilir olmaları sözkonusu olamaz. Böyle durumlarda, sağlam ve erişilebilir arklardaki insanların yardım alabilmek için dağıtım merkezlerine kendilerinin gittiği varsayılmıştır. Şebekenin çökmüş veya erişimin mümkün olmadığı durumlarda, orta ölçekli İnsansız Hava Aracı (İHA) helikopterleri yardım dağıtım operasyonunda kullanılacaktır. Bu problem için geliştirilen matematiksel model, bir dizi uygun senaryo çerçevesinde, hem insanların hem de İHA’larının toplam seyahat süresini en aza indirir. Geliştirilen modelin uygulanabilirliğini göstermek için Tahran'daki olası deprem senaryolarına dayanan bir vaka çalışması da sunulmuştur. Şebeke üzerinde tesis yer seçimi problemleri NP-zor olduğundan, önerilen problemleri çözecek genetik algoritma, memetik algoritma ve benzetimli tavlama gibi üç sezgi ötesi (metaheuristic) algoritma araştırılmış ve geliştirilmiştir.