| Popis: |
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. 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. 96 |
