TESTING OF TREE-SEED ALGORITHM ON P-MEDIAN BENCHMARK PROBLEMS•

Year 2019, Volume: 37 Issue: 4, 1420 - 1434, 01.12.2019

İbrahim Miraç Eligüzel Eren Özceylan Cihan Çetinkaya

Abstract

This paper presents an application of tree-seed algorithm (TSA) -which is based on the relation between trees and their seeds- on the P-median benchmark problems. To the best knowledge of the authors, this is the first study which applies TSA to the P-median problem. In this paper, different P-median problem instances are generated to show the applicability of the TSA. The experimental results are compared with the optimal results obtained by GAMS-CPLEX. Also, TSA is applied on data sets from OR-Library, and then the obtained and known optimal results are compared. The comparisons demonstrate that the TSA can find optimal and near-optimal values for the small and medium-sized problems, respectively.

Keywords

Location and allocation, meta-heuristic, P-median problem, tree-seed algorithm.

References

• [1] L. A. N. Lorena and E. L. F. Senne, “A column generation approach to capacitated p-median problems,” Comput. Oper. Res., vol. 31, no. 6, pp. 863–876, 2004.
• [2] M. Herda, “Parallel Genetic Algorithm for Capacitated P-median Problem,” Procedia Eng., vol. 192, pp. 313–317, 2017.
• [3] F. Chiyoshi and R. D. Galvão, “A statistical analysis of simulated annealing applied to the p-median problem,” Ann. Oper. Res., vol. 1–4, no. X, pp. 61–74, 2000.
• [4] F. O. De França, F. J. Von Zuben, and L. N. De Castro, “MAX MIN Ant System and Capacitated p-Medians: Extensions and improved solutions,” Inform., vol. 29, no. 2, pp. 163–171, 2005.
• [5] 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, 1997.
• [6] B. Jayalakshmi and A. Singh, “A hybrid artificial bee colony algorithm for the p-median problem with positive/negative weights,” Opsearch, vol. 54, no. 1, pp. 67–93, 2017.
• [7] G. Lin and J. Guan, “A hybrid binary particle swarm optimization for the obnoxious p-median problem,” Inf. Sci. (Ny)., vol. 425, pp. 1–17, 2018.
• [8] O. Alp, E. Erkut, and Z. Drezner, “An Efficient Genetic Algorithm for the p-Median Problem,” Ann. Oper. Res., vol. 122, no. 1–4, pp. 21–42, 2003.
• [9] P. Avella, M. Boccia, S. Salerno, and I. Vasilyev, “An aggregation heuristic for large scale p-median problem,” Comput. Oper. Res., vol. 39, no. 7, pp. 1625–1632, 2012.
• [10] P. Prima and A. Aniati Murni, “Optimization of school location-allocation using genetic algorithm,” in Proceedings of 2018 the 8th International Workshop on Computer Science and Engineering, 2018, pp. 750–755.
• [11] B. Afify, S. Ray, A. Soeanu, A. Awasthi, M. Debbabi, and M. Allouche, “Evolutionary learning algorithm for reliable facility location under disruption,” Expert Syst. Appl., vol. 115, pp. 223–244, 2019.
• [12] M. Karatas and E. Yakıcı, “An analysis of p -median location problem : Effects of backup service level and demand assignment policy ✩,” Eur. J. Oper. Res., vol. 272, no. 1, pp. 207–218, 2019.
• [13] M. S. Kiran, “Expert Systems with Applications TSA : Tree-seed algorithm for continuous optimization,” Expert Syst. Appl., vol. 42, no. May, pp. 6686–6688, 2015.
• [14] Y. Zhao, J. Liu, Z. Lyu, and Z. Ding, “Structural damage identification based on residual vectors and tree-seed algorithm,” Zhongshan Daxue Xuebao, vol. 56, no. 4, pp. 46–50, 2017.
• [15] W. J. Chen, X. J. Tan, and M. Cai, “Parameter Identification of Equivalent Circuit Models for Li-ion Batteries Based on Tree Seeds Algorithm,” IOP Conf. Ser. Earth Environ. Sci., vol. 73, no. 1, 2017.
• [16] A. A. El-Fergany and H. M. Hasanien, “Tree-seed algorithm for solving optimal power flow problem in large-scale power systems incorporating validations and comparisons,” Appl. Soft Comput. J., vol. 64, pp. 307–316, 2018.
• [17] A. C. Cinar and M. S. Kiran, “Similarity and Logic Gate-Based Tree-Seed Algorithms for Binary Optimization,” Comput. Ind. Eng., vol. 115, no. December 2017, pp. 631–646, 2018.
• [18] R. D. Galvão, “Uncapacitated facility location problems: contributions,” Pesqui. Operacional, vol. 24, pp. 7–38, 2004.
• [19] F. Plastria, “Continuous Covering Location Problems,” in Facility Location:Applications and Theory, no. January, D. Zvi and H. Horst W., Eds. Springer, 2002.
• [20] J. Current, M. Daskin, and D. Schilling, Discrete Network Location Models, no. January 2016. 2002.
• [21] S. Mete, Z. A. Cil, and E. Özceylan, “Location and coverage analysis of bike-sharing stations in university campus,” Bus. Syst. Res., vol. 9, no. 2, pp. 80–95, 2018.
• [22] J. Reese, “Solution methods for the p-median problem: An annotated bibliography,” Networks, vol. 48, no. 3, pp. 125–142, 2006.
• [23] J. C. Teixeira and A. P. Antunes, “A hierarchical location model for public facility planning,” Eur. J. Oper. Res., vol. 185, no. 1, pp. 92–104, 2008.