Solution Approach To P-Median Facility Location Problem With Integer Programming And Genetic Algorithm

Year 2024, Volume: 26 Issue: 2, 547 - 562, 28.06.2024

Emre Ekin

https://doi.org/10.32709/akusosbil.1125895

Abstract

In the study, the P-median problem that Hakimi brought to science was discussed. With this problem, in short, it is ensured that the locations for the supply of n demand points of p facilities with the lowest cost are determined and the demand points to be served are allocated to these locations. The solution of the p-median problem with the integer programming approach is in the NP (Non-Polynominal) difficult class, and the solution time increases exponentially as the size of the problem increases. For this, the use of heuristic approaches in the P-median problem significantly shortens the solution time of large-sized problems. The data used in the application were taken from the Operation Research-Library site. In practice, the P-median is considered as capacity-constrained and unconstrained. Euclidean distances were calculated in Excel. The solution of mixed integer programming is obtained by using the CPLEX program. In addition to mixed integer programming, genetic algorithm, which is a meta-heuristic method, is applied to the capacity-constrained P-median problem. Different solutions were obtained by changing the population size, maximum number of iterations, crossover and mutation probability values. It has been observed that there is more than one optimum solution in repeated studies. When working with larger data sets, this algorithm will be less likely to find the global optimum. However, when compared to mixed integer programming, the genetic algorithm gave results very close to the optimum result. The use of heuristic algorithms in real-world complex problems will both shorten the solution time considerably compared to the integer programming method and provide results that are very close to the optimum result.

Keywords

Facility Location Problem, Integrated Programming, Genetic Algorithm, P-Median

P-MEDYAN TESİS YERİ SEÇİM PROBLEMİNE TAM SAYILI PROGRAMLAMA VE GENETİK ALGORİTMASIYLA ÇÖZÜM YAKLAŞIMI

Abstract

Çalışmada Hakimi’nin bilime kazandırdığı P-medyan problemi konu alınmıştır. Bu problem ile kısaca p adet tesisin n adet talep noktasının gereksinimlerine en düşük maliyet ile temini hususunda lokasyonların belirlenmesi ve servis edilecek talep noktalarının bu lokasyonlara tahsis edilmesi sağlanmaktadır. P-medyan probleminin tam sayılı programlama yaklaşımı ile çözümü NP (Non-Polinominal) zor sınıfına girmekte ve problemin boyutu arttıkça çözüm süreside üssel olarak artmaktadır. Bunun için P-medyan probleminde sezgisel yaklaşımların kullanımı büyük boyutlu problemlerin çözüm süresini ciddi manada kısaltmaktadır. Uygulamada kullanılan veriler, Operatıon Research-Library sitesinden alınmıştır. Uygulamada P-medyan, kapasite kısıtlı ve kısıtsız olarak ele alınmıştır. Öklid mesafeleri Excel’de hesaplanmıştır. Karışık tam sayılı programlamanın çözümü CPLEX programı kullanılarak elde edilmiştir. Kapasite kısıtsız P-medyan problemine karışık tam sayılı programlamanın haricinde ilave olarak meta sezgisel bir metot olan genetik algoritması uygulanmıştır. Popülasyon büyüklüğü, maksimum iterasyon sayısı, çapraz geçiş ve mutasyon olasılık değerleri değiştirilerek farklı çözümler elde edilmiştir. Tekrarlı çalışmalarda birden fazla optimum çözüm olduğu görülmüştür. Daha büyük veri setleriyle çalışıldığında bu algoritmanın global optimum sonucu bulma olasılığı daha az olacaktır. Fakat yine de karışık tam sayılı programlama ile kıyaslandığında genetik algoritması, optimum sonuca çok yakın neticeler vermiştir. Gerçek dünyadaki karmaşık problemlerde sezgisel algoritmaların kullanılması, hem çözüm süresini tam sayılı programlama yöntemine göre fazlasıyla kısaltacak hem de optimum sonuca çok yakın sonuçların elde edilmesini sağlayacaktır.

Keywords

Tesis Yeri Seçimi, Tam Sayılı Programlama, Genetik Algoritma, P-Medyan

References

• Bastı, D. M. (2012). P-medyan Tesis Yeri Seçim Problemi ve Çözüm Yaklaşımları. AJIT-e Vol 3.
• Daskin, M. S. ( 2015). Location Science. Chapter 2.
• Gökay, E.G., & Taşkın, Ç.(2002). bibliography genetic algorithms and their application areas.Uludağ Uni İİBF Magazine Volume, 129-152.
• Mladenovic, N. (2007). The p-median problem: A survey of metaheuristic approaches. Elsevier.
• Öztürk, P. t. (tarih yok). Analysis of voltage stability in power systems with genetic algorithm. Sakarya uni sciences institute, 22.
• Reese, J. (2006). Methods for Solving the p-Median Problem: An Annotated Bibliography. Networks Vol 48.
• Vural, M. (2005). Mass Production Planning with Genetic Algorithm Method. ITU Institute of Sciences, s. 2-3.
• Worker, o., & korkoglu, s. (2003). genetic algorithm approach and an application in operations research. celal bayar iibf management and economics journal, 191-208.
• Yalçıner, A. Y., & Can, B. (2019). Shelf Space Optimization with Integer Programming and Simulation: Application in a Packaging Company. References; European Journal of Science and Technology, 375-388.