A bicriteria approach for the semi-desirable facility location problem

Year 2024, , 417 - 430, 21.08.2023

Fatma Ersoy Duran Diclehan Tezcaner Öztürk

https://doi.org/10.17341/gazimmfd.1164114

Abstract

Semi-desirable facilities have both desirable and undesirable effects on the demand points in their vicinity, which necessitates them to be located both close to and far away from those points. In this study, a bi-objective semi-desirable facility location problem with both desirable and undesirable effects is considered. The first objective minimizes the total transportation cost between the facility and the demand points and tends to locate the facility closer to these points. Assuming that the transportations are made on road maps, the rectilinear distance metric is used to compute the first criterion. The second objective function minimizes the maximum undesirable effect of the facility on the demand points, and it thus tends to locate the facility farther from the demand points. The undesirable effect of the facility on a demand point is represented with a function based on the distance between them. The undesirable effect stays constant within a close proximity of the facility, beyond this proximity it decreases linearly and becomes zero. Assuming that the undesirable effects spread radially from the facility, the Euclidean distance metric is used to compute the second criterion. We first develop a mixed integer nonlinear programming model for the problem. As a second approach, the Big Square Small Square (BSSS) algorithm that searches for a solution by dividing the solution area into sub-regions is adapted to the problem. A mathematical model with low computational requirements is developed to effectively evaluate whether there is an efficient solution in the sub-regions or not. The approach is demonstrated on two large problem instances, in which efficient solutions are obtained quickly by reducing the solution area.

Keywords

Facility location, semi-desirable, multiobjective optimization

Yarı-istenen tesis yer seçimi problemi için iki kriterli bir yaklaşım

Abstract

Yarı-istenen tesisler çevrelerindeki talep noktalarına hem yakın hem de uzak olmalarını gerektiren istenen ve istenmeyen etkilere sahiptir. Bu çalışmada istenen ve istenmeyen etkilere sahip iki amaçlı yarı-istenen tesis yerleşim problemi ele alınmaktadır. İlk amaç fonksiyonu, tesis ile talep noktaları arası toplam taşıma maliyetini minimize etmektedir ve tesisi talep noktalarına yakın yerleştirme eğilimindedir. Taşımaların doğrusal yollar üzerinden yapılacağı varsayılarak ilk kriter değeri hesaplanırken doğrusal mesafe metriği kullanılmıştır. İkinci amaç fonksiyonu ise tesisin talep noktalarında oluşturduğu istenmeyen etkinin maksimumunu minimize etmektedir, bu nedenle tesisi talep noktalarından uzaklaştırma eğilimindedir. Tesisin bir talep noktası üzerinde oluşturduğu istenmeyen etki, aralarındaki mesafeye bağlı bir fonksiyon ile temsil edilmiştir. Buna göre, tesisten belli bir mesafeye kadar istenmeyen etki sabit kalır, bu mesafeden sonra doğrusal olarak azalır ve sıfırlanır. İstenmeyen etkinin ise tesisten dairesel yayılacağı varsayılarak ikinci kriter değeri hesaplanırken Öklid mesafe metriği kullanılmıştır. Problemin çözümü için ilk olarak karma tamsayılı doğrusal olmayan programlama modeli geliştirilmiştir. İkinci bir yaklaşım olarak çözüm alanını alt bölgelere ayırarak çözüm arayan Büyük Kare Küçük Kare (BKKK) algoritması probleme uyarlanmıştır. Alt bölgelerde etkin çözüm bulunup bulunmamasını değerlendirmek için hesap yükü az olan bir matematiksel model geliştirilmiştir. Geliştirilen yaklaşım büyük boyutlu iki problem üzerinde test edilmiş ve çözüm alanı daraltılarak etkin çözümlere hızlıca ulaşılabilmiştir.

Keywords

Tesis yer seçimi, yarı-istenen, çok amaçlı optimizasyon

References

• Erkut E., & Neuman S., Analytical models for locating undesirable facilities, European Journal of Operational Research, 40 (3), 275–291, 1989.
• Teran-Somohano A., & Smith A. E., Locating multiple capacitated semi-obnoxious facilities using evolutionary strategies, Computers & Industrial Engineering, 133, 303-316, 2019.
• Alamatsaz, K., Fatemi Ghomi, S. M. T., & Iranpoor, M., Minimal covering unrestricted location of obnoxious facilities: bi-objective formulation and a case study, OPSEARCH, 58(2), 351-373, 2021.
• Lin, G., & Guan, J., A hybrid binary particle swarm optimization for the obnoxious p-median problem, Information Sciences, 425, 1-17, 2018.
• Berman, O., & Wang, Q., Locating semi-obnoxious facilities with expropriation: minisum criterion. Journal of the Operational Research Society, 58(3), 378-390, 2007.
• Ohsawa Y., & Tamura K., Efficient location for a semi-obnoxious facility, Annals of Operations Research, 123(1), 173-188, 2003.
• Karasakal E., & Nadirler D., An interactive solution approach for a bi-objective semi-desirable location problem, Journal of Global Optimization, 42(2), 177-199, 2008.
• Wagner A., Locating a semi-obnoxious facility in the special case of Manhattan distances, Mathematical Methods of Operations Research, 90(2), 255-270, 2019.
• Hansen P., Peeters D., Richard D., & Thisse, J. F., The minisum and minimax location problems revisited, Operations Research, 33(6), 1251-1265, 1985.
• Ohsawa Y., Bicriteria Euclidean location associated with maximin and minimax criteria, Naval Research Logistics (NRL), 47(7), 581-592, 2000.
• Plastria F., Gordillo J., & Carrizosa E., Locating a semi-obnoxious covering facility with repelling polygonal regions, Discrete Applied Mathematics, 161(16-17), 2604-2623, 2013.
• Yapicioglu H., Smith A. E., & Dozier G., Solving the semi-desirable facility location problem using bi-objective particle swarm, European Journal of Operational Research, 177(2), 733-749, 2007.
• Ortigosa P. M., Hendrix E. M., & Redondo J. L., On heuristic bi-criterion methods for semi-obnoxious facility location, Computational Optimization and Applications, 61(1), 205-217, 2015.
• Heydari R., & Melachrinoudis E., Location of a semi-obnoxious facility with elliptic maximin and network minisum objectives, European Journal of Operational Research, 223(2), 452-460, 2012.
• Golpayegani M., Fathali J., & Khosravian E., Median line location problem with positive and negative weights and Euclidean norm, Neural Computing and Applications, 24(3), 613-619, 2014.
• Golpayegani M., Fathali J., & Moradi H., A particle swarm optimization method for semi-obnoxious line location problem with rectilinear norm, Computers & Industrial Engineering, 109, 71-78, 2017.
• Skriver A. J., & Andersen K. A., The bicriterion semi-obnoxious location problem (BSLP) solved by an ε-Approximation, European Journal of Operational Research, 146(3), 517-528, 2000.
• Coutinho-Rodrigues J., Tralhão L., & Alçada-Almeida L., A bi-objective modeling approach applied to an urban semi-desirable facility location problem, European Journal of Operational Research, 223(1), 203-213, 2012.
• Ma, Y., Zhang, W., Feng, C., Lev, B., & Li, Z., A bi-level multi-objective location-routing model for municipal waste management with obnoxious effects, Waste Management, 135, 109-121, 2021.
• Gholami M., & Fathali J., The semi-obnoxious minisum circle location problem with Euclidean norm, International Journal of Nonlinear Analysis and Applications, 12(1), 669-678, 2021.
• Fernández J., Redondo J. L., Arrondo A. G., & Ortigosa P. M, A triobjective model for locating a public semiobnoxious facility in the plane, Mathematical Problems in Engineering, 2015.
• Hammad, A. W., Rey, D., & Akbarnezhad, A., A bi-level mixed integer programming model to solve the multi-servicing facility location problem, minimising negative impacts due to an existing semi-obnoxious facility, In Data and Decision Sciences in Action (pp. 381-395), 2018.
• Brimberg, J., & Juel, H., A minisum model with forbidden regions for locating a semi-desirable facility in the plane. Location Science, 6(1-4), 109-120, 1998.
• Sayin, S., A mixed integer programming formulation for the 1-maximin problem. Journal of the Operational Research Society, 51(3), 371-375, 2000.
• Vira, C., & Haimes, Y. Y., Multiobjective decision making: theory and methodology. Noth-Holland Series in System Science and Engineering, 62-109, 1983.
• Plastria, F., GBSSS: the generalized big square small square method for planar single-facility location, European Journal of Operational Research, 62(2), 163-174, 1992.