Lagrangean heuristics for the capacitated multi-facility location allocation problem
Sığa kısıtlı yer seçimi-taşıma problemlerinin çözümü için lagrange gevşetmesi tabanlı sezgisel yöntemler
- Tez No: 200122
- Danışmanlar: PROF.DR. KUBAN ALTINEL
- Tez Türü: Yüksek Lisans
- Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2007
- Dil: İngilizce
- Üniversite: Boğaziçi Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 96
Özet
vüOZETğ şË ËSIGA KISITLI YER SECIMI - TASIMAşË Ë ş ü ü ü ËşËPROBLEMLERININ COZUMU ICIN LAGRANGEË Ë üGEVSETMESI TABANLI SEZGISEL YONTEMLERşBu şalışmada, sığa kısıtlı şok tesisli yer seşimi-taşıma problemi uzerinde şalışıl-cs g c c s ü csmıştır. Bu problem, sonlu sığaya sahip m adet tesisin, n adet müşterinin istemlerinis g uskarşılarken toplam taşıma giderlerini enküşukleyecek bişimde, düzlemde yerleştirilmesis s ucü c u sile ilgilenir. Bu bir dışbükey olmayan eniyileme problemidir ve eniyi şüzümünü hesapla-su co u u umak şok zor, bazı durumlarda ise olanaksızdır. Bu yüzden, bu şalışmada ilk olarakc u csübu problemin tesis yerlerinin iki boyutlu Oklid düzlemi yerine, verilmiş sonlu boyutluu sbir aday yer kümesinden seşildiği, kesikli uyarlaması güz ününe alınmakta ve karışıku cg o ou stam sayılı doğrusal bir programlama modeli geliştirilmektedir. Daha sonra bu modelg suzerine Lagrange gevşetmesi ve altgradyan algoritması temelli sezgisel yüntemler uygu-ü s olanmakta ve problemin sürekli bütünleşik sürümü işin bu sezgisellerden faydalanan yeniu uu s uu u cyüntemler ünerilmektedir. Yapılan bilgisayısal deneyler bu sezgisel yüntemlerin etkilio o oşalıştığını ve eniyi şüzümlere şok yakın sonuşlar bulduğunu güstermektedir.c sg co u c c g oBu şalışmada, sığa kısıtlı şok tesisli yer seşimi-taşıma problemi işin kesin şüzümcs g c c s c co uyüntemleri uzerinde de durulmuştur. Bu yüntemlerin geliştirilmesinde, problemin kısıt-o ü s o slarının üzel bir iki parşalı ağ yapısına sahip olması ve eniyi şüzümünün olurlu şüzümo c g co u u u co ukümesinin bir küşe noktasında gerşeklenmesinden yararlanma düşunülmüştür. Denedi-u os c usü u us uğimiz yaklaşımlar dal sınır yüntemlerinden aï¬n ülşekleme yüntemlerine, şüken şokyüz-g s o oc o co c ulüler yünteminden günder ve bül yüntemine kadar uzanan geniş yelpazeyi oluşturmak-u o o oo s stadır. Bu yüntemleri kullanarak, kesin şüzüm veren bir yüntem bulamasak da, problemo co u ohakkında daha fazla üngürü kazanmamız, ileride daha etkili sezgisel yüntemlerin gelişti-o ou o srilmesinde yararlı olacaktır.
Özet (Çeviri)
ivABSTRACTLAGRANGEAN HEURISTICS FOR THE CAPACITATEDMULTI-FACILITY LOCATION ALLOCATION PROBLEMIn this study, we consider the capacitated multi-facility location-allocation prob-lem, also called multi-facility Weber problem. It is concerned with the determinationof the location of m new facilities having known capacities, as well as the allocation oftheir supplies, to satisfy the demand of customers, such that the total transportationcost proportional to the distance between customers and facilities is minimized. Thedemand and location of each customer are given. This problem has a nonconvex ob-jective function and is very diï¬cult and sometimes even impossible to solve exactly.Therefore, using a discrete approximation becomes a promising strategy to obtain goodapproximate solutions. We ï¬rst present a mixed integer linear programming approxi-mation of the capacitated multi-facility Weber problem. We apply Lagrangean relax-ation and subgradient optimization-based heuristics on this approximation and thenpropose new heuristics for the continuous version of the problem which also make useof these Lagrangean heuristics. Computational results on the test instances indicatethat these heuristics are eï¬cient and accurate.We also study on exact solution procedures. We make use of the fact that the ca-pacitated multi-facility Weber problem has a special transportation network structureand the optimal solution occurs at an extreme point of the feasible region. The pro-cedures we work on range from branch-and-bound methods to aï¬ne scaling methods,to collapsing polytopes, and to send-and-split methods. Although we could not ï¬ndan exact solution methodology by using these procedures, we were able to gain moreinsight about the problem and this can help us in the development of other heuristicmethods in the future.
Benzer Tezler
- Location-allocation problems with multi-commodity flows: Exact and approximate solution methods
Çok mallı yerleşim-dağıtım problemleri: Kesin ve yaklaşık çözüm yöntemleri
MEHMET HAKAN AKYÜZ
Doktora
İngilizce
2011
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. TEMEL ÖNCAN
PROF. İ. KUBAN ALTINEL
- Solving the capacitated multifacility Weber problem approximately
Sınırlı sığalı çok tesisli Weber problemi için yaklaşık çözüm yöntemleri
BURAK BOYACI
Yüksek Lisans
İngilizce
2009
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Bölümü
PROF. İ. KUBAN ALTINEL
- Capacitated facility location problem with customer and facility differentiation
Müşteri sınıflarını göz önüne alarak en uygun tesisi açan tamsayı programlama modelinin yaklaşık çözümü
ÖZLEM ÇAVUŞ
Yüksek Lisans
İngilizce
2007
Endüstri ve Endüstri MühendisliğiBoğaziçi ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. KUBAN ALTINEL
- Multi-echelon dynamic capacitated facility location problem for the recovery of waste
Atıkların geri kazanımı için çok seviyeli ve dinamik kapasiteli tesis yer seçimi problemi
İSTENÇ TARHAN
Yüksek Lisans
İngilizce
2015
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. FATMA SEDEF MERAL
- Multi-item lot sizing problem with setup times
Kurma zamanlı çok ürünlü kafile büyüklüğü belirleme problemi
HALDUN SÜRAL
Doktora
İngilizce
1996
Endüstri ve Endüstri MühendisliğiOrta Doğu Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. ÖMER KIRCA