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

Emre Ekin

Makale detayları

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

Yazarlar:

Emre Ekin

Yayıncı:

Afyon Kocatepe University

Dergi:

Afyon Kocatepe Üniversitesi Sosyal Bilimler Dergisi Vol.26 Issue 2, pp.547-562

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001317882

pISSN:

1302-1265

Anahtar kelimeler:

Özet:

 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.

 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.

 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.

 Çalışmada Hakiminin 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 Excelde 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.

Makale detayları

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

Yazarlar:

Emre Ekin

Yayıncı:

Afyon Kocatepe University

Dergi:

Afyon Kocatepe Üniversitesi Sosyal Bilimler Dergisi Vol.26 Issue 2, pp.547-562

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001317882

pISSN:

1302-1265

Facility Location Problem

Integrated Programming

Genetic Algorithm

P-MedianTesis Yeri Seçimi

Tam Sayılı Programlama

Genetik Algoritma

P-Medyan

Sayı

Makale detayları

Yazarlar: Emre Ekin

Yayıncı: Afyon Kocatepe University

Dergi: Afyon Kocatepe Üniversitesi Sosyal Bilimler Dergisi Vol.26 Issue 2, pp.547-562

Belge Tipi: Makale

Yayın Tarihi: 6/2024

Belge Dili: İngilizce

Document ID (Org No.): 2001317882

pISSN: 1302-1265

Sayı

Yazarlar:

Emre Ekin

Yayıncı:

Afyon Kocatepe University

Dergi:

Afyon Kocatepe Üniversitesi Sosyal Bilimler Dergisi Vol.26 Issue 2, pp.547-562

Belge Tipi:

Makale

Yayın Tarihi:

6/2024

Belge Dili:

İngilizce

Document ID (Org No.):

2001317882

pISSN:

1302-1265