Comparative analysis of genetic crossover operators for the p-median facility location problem

Nazife Nur Erdogmus, Bilal Ervural, Huseyin Hakli

Abstract


The p-median problem is a well-known combinatorial optimization problem with various formulations and many real-life applications. In this study, the performance of genetic algorithm (GA) with different crossover operators is studied. Well-known test problems in the literature are used to test the performance of crossover operators. The comparative experimental results show that the two-point crossover operator and the operator that randomly uses the one-point and two-point crossover operators can effectively solve problems represented by direct value coding, such as the p-median facility location problem.


Keywords


Crossover operators, Facility location, Genetic algorithm, P-median

Full Text:

PDF

References


Ç. Özgün-Kibiroğlu, M. N. Serarslan, and Y. İ. Topcu, ‘Particle Swarm Optimization for Uncapacitated Multiple Allocation Hub Location Problem under Congestion’, Expert Syst. Appl., vol. 119, pp. 1–19, Apr. 2019.

E. Aghezzaf, ‘Capacity planning and warehouse location in supply chains with uncertain demands’, J. Oper. Res. Soc., vol. 56, no. 4, pp. 453–462, Oct. 2005.

S. Salcedo-Sanz et al., ‘Optimal switch location in mobile communication networks using hybrid genetic algorithms’, Appl. Soft Comput. J., vol. 8, no. 4, pp. 1486–1497, Sep. 2008.

D. Pamučar, L. Vasin, P. Atanasković, and M. Miličić, ‘Planning the City Logistics Terminal Location by Applying the Green p -Median Model and Type-2 Neurofuzzy Network’, Comput. Intell. Neurosci., vol. 2016, 2016.

F. Silva and D. Serra, ‘Locating emergency services with different priorities: the priority queuing covering location problem’, J. Oper. Res. Soc., vol. 59, no. 9, pp. 1229–1238, Sep. 2008.

M. K. Oksuz and S. I. Satoglu, ‘A two-stage stochastic model for location planning of temporary medical centers for disaster response’, Int. J. Disaster Risk Reduct., vol. 44, p. 101426, Apr. 2020.

O. Kariv and S. L. Hakimi, ‘An Algorithmic Approach to Network Location Problems. II: The p -Medians’, SIAM J. Appl. Math., vol. 37, no. 3, pp. 539–560, Dec. 1979.

Z. Drezner, J. Brimberg, N. Mladenović, and S. Salhi, ‘New heuristic algorithms for solving the planar p-median problem’, Comput. Oper. Res., vol. 62, pp. 296–304, Jul. 2015.

O. Alp, E. Erkut, and Z. Drezner, ‘An Efficient Genetic Algorithm for the p-Median Problem’, in Annals of Operations Research, 2003, vol. 122, no. 1–4, pp. 21–42.

E. Rolland, D. A. Schilling, and J. R. Current, ‘An efficient tabu search procedure for the p-Median Problem’, Eur. J. Oper. Res., vol. 96, no. 2, pp. 329–342, Jan. 1997.

G. Erdoğan, N. Stylianou, and C. Vasilakis, ‘An open source decision support system for facility location analysis’, Decis. Support Syst., vol. 125, p. 113116, Oct. 2019.

M. B. Bernábe-Loranca, R. González-Velázquez, E. Granillo-Martinez, M. Romero-Montoya, and R. A. Barrera-Cámara, ‘P-median problem: A real case application’, in Advances in Intelligent Systems and Computing, 2021, vol. 1181 AISC, pp. 182–192.

J. Q. Hale, E. Zhou, and J. Peng, ‘A Lagrangian search method for the P-median problem’, J. Glob. Optim., vol. 69, no. 1, pp. 137–156, Sep. 2017.

J. M. Colmenar, P. Greistorfer, R. Martí, and A. Duarte, ‘Advanced Greedy Randomized Adaptive Search Procedure for the Obnoxious p-Median problem’, Eur. J. Oper. Res., vol. 252, no. 2, pp. 432–442, Jul. 2016.

A. Antamoshkin and L. Kazakovtsev, ‘Random Search Algorithm for the p-Median Problem’, Informatica, no. 37, pp. 267–278, 2013.

A. Herrán, J. M. Colmenar, and A. Duarte, ‘A Variable Neighborhood Search approach for the Hamiltonian p-median problem’, Appl. Soft Comput. J., vol. 80, pp. 603–616, Jul. 2019.

S. Picek, M. Golub, and D. Jakobovic, ‘Evaluation of crossover operator performance in genetic algorithms with binary representation’, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2011, vol. 6840 LNBI, pp. 223–230.

H. Adeli and N. Cheng, ‘Concurrent Genetic Algorithms for Optimization of Large Structures’, J. Aerosp. Eng., vol. 7, no. 3, pp. 276–296, Jul. 1994.

K. A. De Jong and W. M. Spears, ‘An analysis of the interacting roles of population size and crossover in genetic algorithms’, in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1991, vol. 496 LNCS, pp. 38–47.

O. Hasançebi and F. Erbatur, ‘Evaluation of crossover techniques in genetic algorithm based optimum structural design’, Comput. Struct., vol. 78, no. 1, pp. 435–448, Nov. 2000.

M. Kaya, ‘The effects of two new crossover operators on genetic algorithm performance’, Appl. Soft Comput. J., vol. 11, no. 1, pp. 881–890, Jan. 2011.

J. H. Holland, ‘Adaptation in natural and artificial systems. an introductory analysis with applications to biology, control and artificial intelligence’, Ann Arbor Univ. Michigan Press. 1975, vol. 1, 1975.

E.-G. Talbi, M. Basseur, A. J. Nebro, and E. Alba, ‘Multi-objective optimization using metaheuristics: non-standard algorithms’, Int. Trans. Oper. Res., vol. 19, no. 1–2, pp. 283–305, Jan. 2012.

D. Dutta and R. C. Joshi, ‘A genetic: Algorithm approach to cost-based multi-QoS job scheduling in cloud computing environment’, Int. Conf. Work. Emerg. Trends Technol. 2011, ICWET 2011 - Conf. Proc., pp. 422–427, 2011.

S. S. Chaudhry, S. He, and P. E. Chaudhry, ‘Solving a class of facility location problems using genetic algorithms’, Expert Syst., vol. 20, no. 2, pp. 86–91, May 2003.

Z. Jinghui, H. Xiaomin, G. Min, and Z. Jun, ‘Comparison of performance between different selection strategies on simple genetic algorithms’, Proc. - Int. Conf. Comput. Intell. Model. Control Autom. CIMCA 2005 Int. Conf. Intell. Agents, Web Technol. Internet, vol. 2, pp. 1115–1120, 2005.

R. Abd Rahman, R. Ramli, Z. Jamari, and K. R. Ku-Mahamud, ‘Evolutionary algorithm with roulette-tournament selection for solving aquaculture diet formulation’, Math. Probl. Eng., vol. 2016, 2016.

B. Bozkaya, J. Z. Zhang, and E. Erkut., ‘A Genetic Algorithm for the p-Median Problem’, in Facility Location: Applications and Theory., Z. Drezner and H. Hamacher, Eds. Springer Berlin Heidelberg, 2002.

‘p-median - uncapacitated test problems’. [Online]. Available: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedinfo.html. [Accessed: 13-Oct-2021].

J. E. Beasley, ‘A note on solving large p-median problems’, Eur. J. Oper. Res., vol. 21, no. 2, pp. 270–273, Aug. 1985.


Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Selcuk University Journal of Engineering Sciences (SUJES) ISSN:2757-8828

Abstracting and indexing

Index Copernicus International

scholar_logo_64dp.png

Selcuk university journal of engineering sciences (Online)

ICI World of Journals

ResearchBib

Eurasian Scientific Journal Index