Customized genetic algorithm for facility allocation using p-median

• Autorzy: Silva S. D. de S. , Costa M. G. F. , Costa Filho C. F. F.

Identyfikatory

DOI

10.15439/2019F158

• Konferencja: Federated Conference on Computer Science and Information Systems (14 ; 01-04.09.2019 ; Leipzig, Germany)
• Języki publikacji: EN

Abstrakty

EN

The p-median problem is classified as a NP-hard problem, which demands a long time for solution. To increase the use of the method in public management, commercial, military and industrial applications, several heuristic methods has been proposed in literature. In this work, we propose a customized Genetic Algorithm for solving the p-median problem, and we present its evaluation using benchmark problems of OR-library. The customized method combines parameters used in previous studies and introduces the evolution of solutions in stationary mode for solving PMP problems. The proposed Genetic Algorithm found the optimum solution in 37 of 40 instances of p-median problem. The mean deviation from the optimal solution was 0.002% and the mean processing time using CPU core i7 was 17.7s.

Słowa kluczowe

EN

computational complexity; genetic algorithms; microprocessor chips

PL

złożoność obliczeniowa; algorytmy genetyczne; mikroprocesor

• Wydawca: Polskie Towarzystwo Informatyczne
• Czasopismo: Annals of Computer Science and Information Systems
• Rocznik: 2019
• Tom: Vol. 18
• Strony: 165--169
• Opis fizyczny: Bibliogr. 19 poz., tab.

Twórcy

autor

Silva S. D. de S.

• Universidade Federal do Amazonas Manaus, Brasil

autor

Costa M. G. F.

• Universidade Federal do Amazonas Manaus, Brasil

autor

Costa Filho C. F. F.

• Universidade Federal do Amazonas Manaus, Brasil

Bibliografia

• 1. O. Kariv; S.L. Hakimi. The p-median problems. In: An Algorithmic Approach to Network Location Problems. SIAM Journal on Applied Mathematics, 1274, Real World Applications. Philadelphia, 37, 539-560, 1979
• 2. R.Whitaker. A fast algorithm for the greedy interchange for large-scale clustering and median location problems. INFOR 21, 95-108, 1983
• 3. C. Beltran, C. Tadonki, J. Vial. Solving the p-median problem with a semi-lagrangian relaxation, Logilab Report, HEC, University of Geneva, Switzerland, 2004
• 4. F. Chiyoshi, R.D. Galvão. A statistical analysis of simulated annealing applied to the p-median problem. Annals of Operational Research 96:61–74, 2000. http://dx.doi.org/10.1023/A:1018982914742
• 5. S. Salhi. Defining tabu list size and aspiration criterion within tabu search methods. Computers and Operations Research 29, 67–86, 2002. http://dx.doi.org/10.1016/S0305-0548(00)00062-9
• 6. O. Alp, E. Erkut, Z. Drezner. An efficient genetic algorithm for the p-median problem. Annals Operational Research 122:21–42, 2003. http://dx.doi.org/10.1023/A:1026130003508
• 7. S. Satoglu. M. Oksuz. G. Kayakutlu, K. Buyukozkan. A genetic algorithm for the p-Median facility location problem. GJCI2016 – Global Joint Conference on industrial engineering, Istanbul, 2016.
• 8. J. E. Beasley. OR-library: distributing test problems by electronic mail. Journal of Operations Research Society 41:1069–1072, 1990. http://dx.doi.org/10.2307/2582903
• 9. G. Reinelt. TSLIB – a traveling salesman library. ORSA Journal of Computing, 3, pp. 376-384, 1991. http://dx.doi.org/10.1287/ijoc.3.4.376
• 10. H. Chen, N.S. Flann, D.W. Watson. Parallel genetic simulated annealing: A massively parallel SIMD approach. IEEE Transactions of Parallel Distributed Computation, 9 (Feb. 1998), pp. 126-136, 1998. http://dx.doi.org/10.1109/71.663870
• 11. Z. Drezner, J. Brinberg, N. Mladenovic, S. Salhi. New heuristic algorithms for solving the planar p-median problem. Comp. Operations Research, 62, pp. 296-304, 2015. http://dx.doi.org/10.1016/j.cor.2014.05.010
• 12. D. F. Albdaiwi, H.h. AboelFotoh. A GPU-based genetic algorithm for the p-median problem, Journal of Supercomputing, 73, pp 4221-4244, 2010. http://dx.doi.org/10.1007/s11227-017-2006-x
• 13. J. A. Moreno-Perez, J. M. Moreno-Vega, N. Mladenovic, Tabu Search and Simulated Annealing in p-median Problems. Talk at the Canadian Operational Research Society Conference, Montreal, 1994.
• 14. J. E. Beasley, ‘OR-library’, 1985. [Online]. Available: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/pmedinfo.html. [Accessed: 04- Jul- 2019]
• 15. D. Corus and P. S. Oliveto. Standard steady state genetic algorithms can hillclimb faster than mutation-only evolutionary algorithms. IEEE Tran. on Evolut. Comp., 2017. http://dx.doi.org/10.1109/TEVC.2017.2745715
• 16. J. Holland. Adaption in natural and artificial systems. The University of Michigan Press, Ann Arbor, 1975.
• 17. M. Vavouras, K. Papadimitriou, I. Papaefstathiou,. High-speed FPGA- based implementations of a genetic algorithm, in: International Symposium on Systems, Architectures, Modeling, and Simulation, (IEEE2009), pp. 9–16, 2009.
• 18. K. Deliparaschos.; G. Doyamis, S. Tzafestas. A parameterised genetic algorithm IP core: FPGA design, implementation and performance evaluation Int. Journal of Electronics, 95, pp. 1149-1166, 2008.
• 19. R. P. Weicker, “Dhrystone: a synthetic systems programming benchmark,” Communications of the ACM, vol. 27, no. 10, pp. 1013–1030, Oct 1984. 41.

Uwagi

1. This research was financial supported by Samsung Electronica da Amazonia Ltda, under the terms of the Brazilian Federal Law number 8.387/91, through an agreement signed with Center for R&D in Electronic and Information Technology- CETELI/UFAM.

2. Track 1: Artificial Intelligence and Applications

3. Technical Session: 12th International Workshop on Computational Optimization

4. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).