Solution procedures for the rectilinear distance single source capacitated multi-facility Weber problem

Abstract

Tesis yerleştirme ve atama problemi, birçok alanda pratik uygulaması olan önemli bir konudur. Bu uygulamalar; ulaşım, dağıtım, üretim, tedarik zinciri yönetimi ve telekomünikasyon gibi alanlarda görülebilir. Bu nedenle, yazında tesis planlama problemleri için araştırmalar giderek artmaktadır. Bu çalışmada, birçok farklı tipteki tesis planlama problemleri arasından, tek kaynaktan tedarik edildiği varsayımı altında, yerleri bilinen istemciler için depo, işletme gibi birden fazla tesisin en iyi yerini bulmayı amaçlayan Tek Kaynaklı Sınırlı Sığalı Çok Tesisli Weber Problemi (TKSÇWP) ele alındı.Bu çalışmada, problemin çözümüne yönelik dört farklı ve özgün yöntem önerildi. Öncelikle, problemin en iyi sonucu veren Kesikli Yaklaşım Problemi (KYP) ele alındı. Geliştirilen ilk sezgisel yöntem ise, Cooper'ın (1972) çalışmasından yararlanarak önerilen Almaşık Yerleştirme?Atama (AYA) tipinde bir sezgisel dizgi işlemidir. Dik uzaklıklı TKSÇWP için önerilen diğer dizgi işlemlerle karşılaştırabilmek adına, bu basit yöntem ele alınan probleme uyarlandı. AYA dizgi işleminin atama aşamasında yer alan Tek Kaynaklı Taşıma Problemini (TKTP) ticari bir çözücü kullanarak en iyi sonuçla çözmede karşılaşılan zorluktan dolayı, Çok Büyük Ölçekli Komşuluk (ÇBÖK) arama dizgi işlemi ve Tabu Arama (TA) dizgi işlemi gibi sezgisel yöntemlere başvuruldu.OR-kütüphanesinden alınan deneme örneklerindeki sayısal deneylerde, gerek ÇBÖK arama, gerekse TA dizgi işlemlerinin AYA tipinde bir sezgisel dizgi işleminde olumlu sonuçlar verdiği ve iyileştirme sağladığı gözlemlendi. Özellikle ÇBÖK arama dizgi işleminin hissedilir oranda, kabul edilebilir bir sürede çok iyi sonuçlar verdiği söylenebilir.

The facility location-allocation problem is an important topic that arises in many practical settings. These applications arise in various areas such as transportation, distribution, production, supply chain decisions and telecommunication. As a result, the studies on the facility location problems are steadily increasing in the literature. In this work, the Single Source Capacitated Multi-Facility Weber Problem (SSCMWP) which aims to tackle the optimal location of a number of facilities such as plants, warehouses or concentrators that will serve a set of customers with known locations under single source assumption has been suggested.In this study, four different original algorithms have been proposed to tackle the SSCMWP. First of all, Discrete Approximation Problem (DAP) which can yield the optimal solution of the rectilinear distance SSCMWP has been presented. The first heuristic that is considered is an Alternate Location Allocation type (ALA) heuristic which is inspired from the seminal work of Cooper (1972). His approach has been adopted in order to compare it with other heuristic algorithms that are proposed for the rectilinear distance SSCMWP. To improve the allocation phase of the ALA type heuristic by heuristically solving the SSTP, a Very Large Scale Neighbourhood (VLSN) search algorithm and a Tabu Search (TS) algorithm are considered.By performing computational experiments on test instances obtained from the OR-library, it is observed that both VLSN search and TS algorithms yield substantial improvements over the ALA type heuristic. Especially it can be noted that the proposed VLSN search algorithm yields significantly better results especially in reasonable CPU times.