Location-allocation problems with multi-commodity flows: Exact and approximate solution methods

Abstract

Tesis yer seçimi, ya da kısaca yerleşim problemleri fabrika, depo, bakkal, alışveriş merkezi gibi tesisleri eniyi yerlere yerleştirmeyi amaçlar. Bir yandan eniyi yerleri bulmaya çalışırken diğer yandan da müşterilerden elde edilecek kazancı enbüyüklemek veya tesis açmaktan ve müşterilere hizmet etmekten kaynaklanan giderleri enküçüklemek gibi iki temel amacı gerçekleştirmeye çalışır. Dağıtım problemleri genel olarak, tesislerin yerleri yerine ürettikleri malların tüketicilere dağıtılmasıyla ilgilenirler. Amaçları alıcı istemlerini doyuran, tesis sığalarını aşmayan ve dağıtım ağından kaynaklı kısıtları sağlayan enküçük toplam giderli dağıtım planını belirlemektir. Bu ailenin bir bireyi olan taşıma probleminde tesisler ile tüketiciler, tesislerden tüketicilere doğru yönlenen oklarla bağlı yönlü çift kümeli ağlar üzerindedir ve tesislerde tek bir ürün türünün üretildiğini varsayarlar. Problemin çok mallı sürümü ise biraz daha geneldir ve bu varsayımı gevşetir: tesislerin üretimi değişik ürün türlerini içerir ve taşıma ağındaki akış çok mallıdır. Bu durum tek mallı problemin olağan kısıtlarına demetleme kısıtlarını ekleyerek matematiksel eniyileme gösterimine yansıtılır ve çok mallı taşıma problemi gösterimi elde edilir. Çalışmada asıl olarak bu iki problemi bütünleyen Sınırlı sığalı Çok mallı Çok tesisli Weber Problemi (SÇÇWP) ele alınmakta, yaklaşık ve kesin çözüm algoritmaları geliştirilmektedir. Yapılanları iki ana kümede özetlemek olanaklıdır. İlk küme SÇÇWP için yaklaşık çözüm yöntemleri içermektedir. Bu amaçla etkinlik ve doğruluk başarımları yüksek sezgiseller önerilmiştir. Ayrıca, Fisher-Tippet teoreminden yararlanılarak eniyi amaç değeri üzerinde güven aralıkları üretilmiştir. İkinci kümede hem Sınırlı Sığalı ÇWP (SÇWP), hem de SÇÇWP için kesin çözüm yöntemleri önerilmektedir. Özel olarak SÇWP ve SÇÇWP'yi kesin olarak çözen birisi taşıma diğeri tesis yeri değişkenleri uzayını parçalayan iki değişik dal-sınır (DS) dizgi işlemi geliştirilmektedir. Değişik dallanma kuralları denenmekte ve tesis yeri değişkenleri uzayını parçalayan DS dizgi işlemini kullanan bir ışın arama sezgiseli de önerilmektedir.

A multi-commodity and capacitated extension of the Multi-facility Location-Allocation Problem, namely the Multi-commodity Capacitated Multi-facilityWeber Problem (MCMWP) is considered, and exact and approximate solution methods are proposed. The MCMWP is new in the literature and aims to locate new facilities on the plane in order to meet the demand of customers for multiple types of products. The objective is to minimize total transportation costs, which are proportional to the distances measured with lr-norm for 1 < r ? ? between the facilities and customers, while satisfying the demand and capacity restrictions. The MCMWP has a non-convex objective function and it is difficult to solve. In the first part of this work, approximate solution methods are suggested. The first one of them is based on the Cooper's alternate location-allocation (ALA) heuristic and both continuous and discrete variants of the ALA heuristics are developed for the MCMWP. The second approximate solution method employs Discrete Approximation (DA) strategies. When the location of facilities are selected from a finite set of candidate sites it is possible to obtain approximate solutions of the MCMWP. The proposed DA strategies enable to obtain not only upper bounds but also lower bounds on the MCMWP. The third approximate solution method employs a Lagrangean Relaxation (LR) scheme. The MCMWP is relaxed such that the LR subproblems are variants of Multi-facility Weber Problems (MWP) with no capacity restrictions. The last approximate solution method produces confidence intervals for the optimal solution of the MCMWP using the Fisher-Tippett's theorem. In the second part of this work, exact solution methods are developed for both the Capacitated MWP (CMWP) and MCMWP. In particular, two different branch-and-bound (BB) algorithms, which partition allocation and location spaces, are suggested to exactly solve the CMWP and MCMWP. Lastly, a beam search heuristic using the location space based BB algorithm is implemented.