A Clustering-based Simulated Annealing Algorithm with Taguchi Method for the Discrete Ordered Median Problem

Abstract

Researchers have studied discrete location problems for a long time because of their importance in practice. The Discrete Ordered Median Problem (DOMP) generalizes discrete facility location problems. The DOMP generalizes the main facility location problems' objective functions such as the p-median, p-center and p-centdian location problems. As these problems, also known as the problems of location-allocation, have NP-hard structure, it is inevitable to use heuristic methods for solution. In this study, a metaheuristic algorithmic suggestion will be put forward by examining the DOMP to find optimal solutions. For that purpose, we proposed a Simulated Annealing (SA) metaheuristic with K-means Clustering Algorithm in initialization for the DOMP. Novel approaches for initial solution and K-exchange algorithm-based neighborhoods for local search were analysed. In addition, best level of selected parameters were determined by Taguchi method. Forty common p-median instances derived from OR-LIB were used to test the SA performance, and the results were compared with three state-of-art algorithms in the literature. According to the computational results, 21 best solutions were obtained on instances despite gap values and CPU times increasing proportionally to the scale of the instances. In a conclusion, the proposed clustering-based SA algorithm is competitive and can be a robust alternative for the DOMP.

Keywords

• Discrete ordered median problem
• Simulated annealing
• Taguchi
• K-means clustering.

References

1. [1] Z. Drezner and H. W. Hamacher, “Facility location: applications and theory,” Springer Science & Business, pp. 81-107, 2004.
2. [2] P. B. Mirchandani and R. L. Francis, “Discrete location theory,” Wiley Periodicals, 1990.
3. [3] S. L. Hakimi, “Optimum distribution of switching centers in a communication network and some related graph theoretic problems,” Operations Research, vol. 13, no. 3, pp. 462–475, 1965.
4. [4] J. Reese, “Solution methods for the p‐median problem: an annotated bibliography,” Networks: An International Journal, vol. 48, no. 3, pp. 125-142, 2006.
5. [5] S. Nickel, “Discrete ordered weber problems,” Operations Research Proceedings, Springer, pp. 71-76, 2001.
6. [6] N. Boland, P. Domínguez-Marín, S. Nickel, and J. Puerto, “Exact procedures for solving the discrete ordered median problem,” Computers Operations Research, vol. 33, no. 11, pp. 3270-3300, 2006.
7. [7] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 67, pp. 671-680, 1983.
8. [8] V. A. Cerny, “Thermodynamical approach to the traveling salesman problem: an efficient simulated algorithm,” Journal of Optimization Theory and Applications, vol. 45, no. 1, pp. 41-51, 1985.

9. [9] N. Metropolis, A. W. Rosenbluth, A. H. Teller, and E. Teller, “Equation of state calculation by fast computing methods,” Journal of Chemical Physics, vol. 21, no. 6, pp. 1087-1093, 1953.
10. [10] J. E. Beasley, “A note on solving large p-median problems,” In European Journal of Operational Research, vol. 21, no. 2, pp. 270-273, 1985.
11. [11] M. S. Daskin, “Network and discrete location: models, algorithms and applications,” John Wiley & Sons, 1995.
12. [12] J. Kalcsics, T. Melo, S. Nickel, and V. Schmid-Lutz, “Facility location decisions in supply chain management,” Operations Research Proceedings 1999, pp. 467-472, 1999.
13. [13] S. Nickel and J. Puerto, “A unified approach to network location problems,” Networks, vol. 34, pp. 283–290, 1999.
14. [14] J. Kalcsics, S. Nickel, and J. Puerto, “Multifacility ordered median problems on networks: a further analysis,” Networks, vol. 41, no. 1, pp. 1-12, 2003.
15. [15] J. Puerto and A. M. Rodríguez-Chía, “Ordered Median Location Problems,” Springer, pp. 249-288, 2015.
16. [16] P. L. Diego, “The Discrete Ordered Median Problem Revisited: New Formulations, Properties and Algorithms,” Doctoral Dissertation, Université Libre de Bruxelles, 2016.
17. [17] J. L. Redondo, A. Marín, and P. M. Ortigosa, “A parallelized lagrangean relaxation approach for the discrete ordered median problem,” Annals of Operations Research, vol. 246, no. 1, pp. 253-272, 2016.
18. [18] W. Ogryczak and P. Olender, “Ordered median problem with demand distribution weights,” Optimization Letters, vol. 10, no. 5, pp. 1071-1086, 2016.
19. [19] W. Ogryczak and T. Śliwiński, “On solving linear programs with the ordered weighted averaging objective,” European Journal of Operational Research, vol. 148, no. 1, pp. 80-91, 2003.
20. [20] P. Olender, “Hybrid models for the OWA optimization,” Journal of Telecommunications and Information Technology, vol. 4, pp. 22-30, 2016.
21. [21] M. Labbé, D. Ponce, and J. Puerto, “A comparative study of formulations and solution methods for the discrete ordered p-median problem,” In Computers & Operations Research, vol. 78, pp. 230-242, 2017.
22. [22] J. H. Holland, “Adaptation in Natural and Artificial Systems,” MIT Press, 1975.
23. [23] L. Davis, “Genetic Algorithms and Simulated Annealing,” Morgan Kaufmann Publishers, 1987.
24. [24] D. E. Goldberg and J. H. Holland, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison Wesley, 1989.
25. [25] N. Mladenovic, “A variable neighborhood algorithm - a new metaheuristic for combinatorial optimization,” Abstracts of papers presented at Optimization Days, pp. 234, 1995.
26. [26] P. Hansen and N. Mladenovic, “Variable neighborhood search for the p-median,” Location Science, vol. 5, no. 4, pp. 207-226, 1997.
27. [27] P. Dominguez-Marin, S. Nickel, P. Hansen, and N. Mladenović, “Heuristic procedures for solving the discrete ordered median problem,” Annals of Operations Research, vol. 136, no. 1, pp. 145-173, 2005.
28. [28] Z. Stanimirović, J. Kratica, and D. Dugošija, “Genetic algorithms for solving the discrete ordered median problem,” European Journal of Operational Research, vol. 182, no. 3, pp. 983-1001, 2007.
29. [29] J. Puerto, D. G. Pérez-Brito, and C. García-González, “A modified variable neighborhood search for the discrete ordered median problem,” In European Journal of Operational Research, vol. 234, no. 1, pp. 61-76, 2014.
30. [30] P. Olender and W. Ogryczak, “A revised variable neighborhood search for the discrete ordered median problem,” European Journal of Operational Research, vol. 274, no. 2, pp. 445-465, 2019.
31. [31] P. Domínguez-Marín, “The Discrete Ordered Median Problem: Models and Solution Methods: Models and Solution Methods,” Springer Science & Business Media, 2013.
32. [32] H. W. Hamacher and S. Nickel, “Combinatorial algorithms for some 1-facility median problems in the plane,” European Journal of Operational Research, vol. 79, pp. 340–351, 1994.
33. [33] H. I. Demir, R. K. Phanden, A. Kökçam, B. Erkayman and C. Erden, “Hybrid evolutionary strategy and simulated annealing algorithms for integrated process planning, scheduling and due-date assignment problem,” Academic Platform Journal of Engineering and Science, vol. 9, no. 1, pp. 86-91, 2021.
34. [34] E. Erdem, T. Aydın, and B. Erkayman, “Flight scheduling incorporating bad weather conditions through big data analytics: A comparison of metaheuristics,” Expert Systems, vol. 38, no. 8, pp. 1-19, 2021.
35. [35] K. Wagstaff, C. Cardie, S. Rogers, and S. Schrödl, “Constrained k-means clustering with background knowledge,” In LCML. vol. 1. pp. 577-584, 2001.
36. [36] L. Tan, Y. Tan, G. Yun, and Y. Wu, “Genetic Algorithms Based on Clustering for Traveling Salesman Problems,” 12th International Conference on Natural Computation, Fuzzy Systems and Knowledge Discovery, pp. 103-108, 2016.
37. [37] S. Z. Selim and K. Alsultan, “A simulated annealing algorithm for the clustering problem,” Pattern Recognition, vol. 24, no. 10, pp. 1003-1008, 1991.
38. [38] G. P. Babu and M. N. Murty, “Simulated annealing for selecting optimal initial seeds in the k-means algorithm,” Indian Journal of Pure and Applied Mathematics, vol. 25, no. 1-2, pp. 85-94, 1994.
39. [39] G. T. Perim, E. D. Wandekokem, and F. M. Varejão, “K-means initialization methods for improving clustering by simulated annealing,” In Ibero-American Conference on Artificial Intelligence, Springer, pp. 133-142, 2008.
40. [40] Z. H. Che, “A two-phase hybrid approach to supplier selection through cluster analysis with multiple dimensions,” International Journal of Innovative Computing Information and Control, vol. 6, no. 9, pp. 4093-4111, 2010.
41. [41] R. Kittaneh, S. Abdullah, and A. Abuhamdah, “Iterative simulated annealing for medical clustering problems,” Trends in Applied Sciences Research, vol. 7, no. 2, pp. 103-117, 2012.
42. [42] T. Lu, J. Fu, and X. Hu, “A Dynamic Path Planning Model Based on K-means Algorithm and Simulated Annealing Algorithm,” 2019 IEEE 3rd Information Technology, Networking, Electronic and Automation Control Conference, pp. 2390-2394, 2019.
43. [43] P. Rani, J. Shokeen, A. Agarwal, A. Bhatghare, A. Majithia, and J. Malhotra, “Credit Card Fraud Detection Using Blockchain and Simulated Annealing K-means Algorithm,” International Conference on Innovative Computing and Communications, pp. 51-59, 2022.
44. [44] G. T. Clausing and G. Taguchi, “Robust quality,” Harvard Business Review, vol. 13, pp. 27-42, 1990.
45. [45] D. C. Montgomery, “Design and Analysis of Experiments,” John Wiley & Sons, 2001.
46. [46] J. L. Liu, “Novel Taguchi-simulated annealing method applied to airfoil and wing planform optimization,” Journal of Aircraft, vol. 43, no. 1, pp. 102-109, 2006.
47. [47] S. A. Seyed-Alagheband, S. F. Ghomi, and M. Zandieh, “A simulated annealing algorithm for balancing the assembly line type II problem with sequence-dependent setup times between tasks,” International Journal of Production Research, vol. 49, no. 3, pp. 805-825, 2011.
48. [48] N. Zoraghi, A. A. Najafi, and N. S. T. Akhavan, “An integrated model of project scheduling and material ordering: a hybrid simulated annealing and genetic algorithm,” Journal of Optimization in Industrial Engineering, vol. 8, no. 1, pp. 19-27, 2012.
49. [49] S. Ghalme, A. Mankar, and Y. Bhalerao, “Integrated Taguchi-simulated annealing (SA) approach for analyzing wear behaviour of silicon nitride,” Journal of Applied Research and Technology, vol. 15, no. 6, pp. 624-632, 2017.
50. [50] I. Mahdavi, S. Firouzian, M. M. Paydar, and M. Saadat, “Simulated annealing and artificial immune system algorithms for cell formation with part family clustering,” Journal of Industrial Engineering and Management Studies, vol. 7, no. 1, pp. 191-219, 2020.