Exact solution methodologies for the p-center problem under single and multiple allocation strategies
Tekli ve çoklu atama stratejileri altında p-merkez problemi için kesin çözüm yöntemleri
- Tez No: 452739
- Danışmanlar: DOÇ. DR. OYA KARAŞAN
- Tez Türü: Doktora
- Konular: Mühendislik Bilimleri, Engineering Sciences
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2013
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 112
Özet
Literatürde yaygın olarak bilinen p-merkez problemi, verilen bir serim üzerine p adet merkez yerleştirilmesini, serimdeki talep noktalarının bu merkezlerden hizmet alacak şekilde atamalarının yapılmasını ve bu atama mesafelerinin en büyüğünün en küçüklenmesini amaçlar. Problem düzlemsel serimlerde dahi NP-Zor sınıfında bir problemdir. Ancak ağaç serimlerde polinom zamanlı algoritmalar mevcuttur. Problemin temel uygulama alanlarından bazıları ambulans, itfaiye gibi acil servis ünitelerinin yerleştirilmesi ve doğal afet sonrası arama kurtarma ekiplerinin afet bölgelerine atanmasıdır. Problem aday merkezlerin kümesine göre ikiye ayrılır. Serim üzerindeki her noktanın bir aday merkez olduğu problem mutlak p-merkez problemi, sadece düğümlerin aday merkez olabildiği problem ise düğüm kısıtlı p-merkez problemi olarak adlandırılır. Merkezlerin hizmet kapasitesinin sınırlı olduğu problemlere kapasite kısıtlı p-merkez problemi adı verilir. Kapasite kısıtlı p-merkez probleminde talep noktalarının merkezlere atanmasında tekli ya da çoklu atama stratejileri güdülebilir. Çoklu atama stratejisinin güdüldüğü kapasite kısıtlı p-merkez problemi üzerine ilk kez bu tezde odaklanılmış ve bu problemin çözümüne yönelik yeni algoritmalar geliştirilmiştir. Bu tezde mutlak ve düğüm kısıtlı p-merkez problemi ile tekli ve çoklu atama stratejileri altındaki kapasite kısıtlı p-merkez problemlerinin çözümüne yönelik modelleme ve algoritma tabanlı yöntemler geliştirilmesi amaçlanmıştır. Bu doğrultuda öncelikle bu problemler üzerine literatürde yapılan çalışmaların geniş çaplı taraması yapılmıştır. Bu problemler için öncelikli olarak çeşitli matematiksel modeller oluşturulmuş, bu modellerin yapısal özellikleri kullanılarak optimal çözüm veren algoritmalar geliştirilmiştir. Bu tezde geliştirilen algoritmaları ve matematiksel modelleri daha hızlı çözebilmek amacıyla, yeni alt ve üst sınırlar elde edilmesini sağlayan yöntemler sunulmuş, bu alt ve üst sınılar kullanılarak geniş ölçekli problemler üzerinde testler gerçekleştirilmiş ve daha önce çöülemeyen büyüklükteki problemler çözülmüştür.
Özet (Çeviri)
The p-center problem is a relatively well known facility location problem that involves locating p identical facilities on a network to minimize the maximum distance between demand nodes and their closest facilities. The focus of the problem is on the minimization of the worst case service time. This sort of objective is more meaningful than total cost objectives for problems with a time sensitive service structure. A majority of applications arises in emergency service locations such as determining optimal locations of ambulances, fire stations and police stations where the human life is at stake. There is also an increased interest in p-center location and related location covering problems in the contexts of terror fighting, natural disasters and human-caused disasters. The p-center problem is NP-hard even if the network is planar with unit vertex weights, unit edge lengths and with the maximum vertex degree of 3. If the locations of the facilities are restricted to the vertices of the network, the problem is called the vertex restricted p-center problem; if the facilities can be placed anywhere on the network, it is called the absolute p-center problem. The p-center problem with capacity restrictions on the facilities is referred to as the capacitated p-center problem and in this problem, the demand nodes can be assigned to facilities with single or multiple allocation strategies. In this thesis, the capacitated p-center problem under the multiple allocation strategy is studied for the first time in the literature. The main focus of this thesis is a modelling and algorithmic perspective in the exact solution of absolute, vertex restricted and capacitated p-center problems. The existing literature is enhanced by the development of mathematical formulations that can solve typical dimensions through the use of off the-shelf commercial solvers. By using the structural properties of the proposed formulations, exact algorithms are developed. In order to increase the efficiency of the proposed formulations and algorithms in solving higher dimensional problems, new lower and upper bounds are provided and these bounds are utilized during the experimental studies. The dimensions of problems solved in this thesis are the highest reported in the literature.
Benzer Tezler
- Statistical design and yield enhancement of low voltage cmos VLSI circuits
Düşük gerilimli analog VLSI devrelerin istatistiksel tasarımı
TUNA B. TARIM
Doktora
İngilizce
1999
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. H. HAKAN KUNTMAN
- Examination timetabling problem
Sınav zaman çizelgeleme problemi
BERK ŞAHİN
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. OYA KARAŞAN
- Kanat profili üzerinde oluşan buzun iki boyutta matematiksel modellenmesi ve sayısal çözümü
Two dimensional mathematical modelling and numerical solution of accumulated ice on wing profiles
RAMAZAN DÖKME
Yüksek Lisans
Türkçe
2019
Uçak Mühendisliğiİstanbul Teknik ÜniversitesiUçak ve Uzay Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET CİHAT BAYTAŞ
- Hub and regenerator location and survivable network design
Erişim cihazı-güçlendirici yer seçimi ve kalımlı ağ tasarımı
ONUR ÖZKÖK
Doktora
İngilizce
2011
Endüstri ve Endüstri Mühendisliğiİhsan Doğramacı Bilkent ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. HANDE YAMAN PATERNOTTE
DOÇ. DR. OYA EKİN KARAŞAN