Annals of Computer Science and Information Systems, Volume 18

DOI: http://dx.doi.org/10.15439/2019F158

Citation: Proceedings of the 2019 Federated Conference on Computer Science and Information Systems, M. Ganzha, L. Maciaszek, M. Paprzycki (eds). ACSIS, Vol. 18, pages 165–169 (2019)

Full text

Abstract. 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.

References

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.