Hybrid Genetic for the Single-Source Capacitated Multi-Facility Weber Problem

Subject Areas : International Journal of Industrial Mathematics

سهید جهادی ¹ (Department of Industrial Engineering, Urmia University of Technology, Urmia, Iran.)
مقصود سلیمانپور ² (Department of Industrial Engineering, Urmia University, Urmia, Iran.)

Received: 2017-04-25 Accepted : 2021-06-07 Published : 2021-07-01

Keywords: Metaheuristic, Genetic algorithm, Location-allocation, Local search, Weber Problem,

Abstract :

In this paper, we investigate the Single-Source Capacitated Multi-Facility Weber Problem. The aim is to locate several new facilities among existing customers and simultaneously allocate customers to the facilities. A Genetic Algorithm is proposed for solving the problem, in which a local search method is embedded. The proposed Genetic Algorithm is tested on existing data sets to evaluate its robustness over available methods in the literature.

References:

[1] M. H. Aky, I. K. Altnel, T. ncan, Location and allocation based branch and bound algorithms for the capacitated multi-facility We ber problem, Annals of Operations Research 222 (2014) 45-71.
[2] M. H. Akyz, T. ncan, . K. Altnel, Branch and bound algorithms for solving the  multicommodity capacitated multi-facility Weber problem, Annals of Operations Research 279 (2019) 1-42.
[3] N. Aras, . K. Altnel, M. Orbay, New heuristic methods for the capacitated multifacility Weber problem, Naval Research Logistics (NRL) 54 (2007) 21-32.
[4] J. P. Arnaout, Ant colony optimization algorithm for the Euclidean location-allocation problem with unknown number of facilities, Journal of Intelligent Manufacturing 24 (2013) 45-54.
[5] I. Bongartz, P. H. Calamai, A. R. Conn, A projection method for lp norm locationallocation problems, Mathematical programming 66 (1994) 283-312.
[6] J. Brimberg, Z. Drezner, A new heuristic for solving the p-median problem in the plane, Computers & Operations Research 40 (2013) 427-437.
[7] J. Brimberg, Z. Drezner, N. Mladenovic, S. Salhi, Generating good starting solutions for the p-median problem in the plane, Electronic Notes in Discrete Mathematics 39 (2012) 225-232.
[8] J. Brimberg, P. Hansen, N. Mladenovi, E. D. Taillard, Improvements and comparison of heuristics for solving the uncapacitated multisource Weber problem, Operations research
48 (2000) 444-460.
[9] J. Brimberg, P. Hansen, N. Mladenovic, S. Salhi, A survey of solution methods for the continuous location-allocation problem, International Journal of Operations Research 5 (2008) 1-12.
[10] J. BRIMBERG, N. Mladenovic, Solving the continus location-allocation problem with tabu search, Studes in location annals 8 (1996) 23-32.
[11] J. Brimberg, A variable neighborhood algorithm for solving the continuous locationallocation problem, Studies in Locational Analysis 10 (1996) 1-12.
[12] L. Cooper, Location-allocation problems, Operations research 11 (1963) 331-343.
[13] L. Cooper, Heuristic methods for locationallocation problems, SIAM review 6 (1964) 37-53.
[14] L. Cooper, The transportation-location problem, Operations Research 20 (1972) 94-108.
[15] Z. Drezner, J. Brimberg, N. Mladenovi, S. Salhi, New heuristic algorithms for solving the planar p-median problem, Computers & Operations Research 62 (2015) 296-304.
[16] Z. Drezner, J. Brimberg, N. Mladenovi, S. Salhi, New local searches for solving the multi-source Weber problem, Annals of Operations Research 246 (2016) 181-203.
[17] S. Eilon, C. D. T. Watson-Gandy, N. Christofides, R. de Neufville, Distribution management-mathematical modelling and practical analysis, IEEE Transactions on Systems, Man, and Cybernetics 6 (1974) 589-589.
[18] M. D. H. Gamal, S. Salhi, A cellular heuristic for the multisource Weber problem, Computers & Operations Research 30 (2003) 1609-1624.
[19] M. D. H. Gamal, S. Salhi, Constructive heuristics for the uncapacitated continuous location-allocation problem, Journal of the Operational Research Society 52 (2001) 821-829.
[20] A. Ghaderi, M. S. Jabalameli, F. Barzinpour, R. Rahmaniani, An efficient hybrid particle swarm optimization algorithm for solving the uncapacitated continuous location-allocation problem, Networks and Spatial Economics 12 (2012) 421-439.
[21] D. Gong, M. Gen, G. Yamazaki, W. Xu, Hybrid evolutionary method for capacitated 298 location-allocation problem, Computers &industrial engineering 33 (1997) 577-580.
[22] P. Hansen, N. Mladenovi, E. Taillard, Heuristic solution of the multisource Weber problem as a p-median problem, Operations Research Letters 22 (1998) 55-62.
[23] S. J. Hosseininezhad, S. Salhi, M. S. Jabalameli, A cross entropy-based heuristic for the capacitated multi-source weber problem with facility fixed cost, Computers & Industrial Engineering 83 (2015) 151-158.
[24] C. A. Irawan, M. Luis, S. Salhi, A. Imran, The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem, Annals of Operations Research 275 (2019) 367-392.
[25] C. A. Irawan, S. Salhi, K. Soemadi, The continuous single-source capacitated multifacility Weber problem with setup costs: formulation and solution methods, Journal of Global Optimization 78 (2020) 271-294.
[26] M. S. Jabalameli, A. Ghaderi, Hybrid algorithms for the uncapacitated continuous location-allocation problem, The International Journal of Advanced Manufacturing Technology 37 (2008) 202-209.
[27] R. E. Kuenne, R. M. Soland, Exact and approximate solutions to the multisource Weber problem, Mathematical Programming 3 (1972) 193-209.
[28] C. L. Lara, F. Trespalacios, I. E. Grossmann, Global optimization algorithm for capacitated multi-facility continuous locationallocation problems, Journal of Global Optimization 71 (2018) 871-889.
[29] C. M. Liu, R. L. Kao, A. H. Wang, Solving location-allocation problems with rectilinear distances by simulated annealing, Journal of the Operational Research Society 45 (1994) 1304-1315.
[30] R. F. Love, H. Juel, Properties and solution methods for large locationallocation problems, Journal of the Operational Research Society 33 (1982) 443-452.
[31] R. F. Love, J. G. Morris, G. O. Wesolowsky, Facilities Location: Models & Methods, North-Holland 18 (1988) 51-60.
[32] M. Luis, M. F. Ramli, A. Lin, A greedy heuristic algorithm for solving the capacitated planar multi-facility locationallocation problem, AIP Conference Proceedings 1782 (2016) 040010.
[33] M. Luis, S. Salhi, G. Nagy, Region-rejection based heuristics for the capacitated multisource Weber problem, Computers & Operations Research 36 (2009) 2007-2017.
[34] M. Luis, S. Salhi, G. Nagy, A guided reactive GRASP for the capacitated multi-source Weber problem, Computers & Operations Research 38 (2011) 1014-1024.
[35] M. Luis, S. Salhi, G. Nagy, A constructive method and a guided hybrid grasp for the capacitated multi-source weber problem in the presence of fixed cost, Journal of Algorithms & Computational Technology 9 (2015) 215-232.
[36] H. Manzour, A. Torabi, M. S. Pishvaee, New heuristic methods for the single-source capacitated multi facility Weber problem, The International Journal of Advanced Manufacturing Technology 69 (2013) 1569-1579.
[37] S. M. H. Manzour-al-Ajdad, S. A. Torabi, K. Eshghi, Single-source capacitated multifacility weber problem an iterative two phase heuristic algorithm, Computers & Operations Research 39 (2012) 1465-1476.
[38] N. Mladenovi, J. Brimberg, P. Hansen, J. A. Moreno-Prez, The p-median problem: A survey of metaheuristic approaches, European Journal of Operational Research 179 (2007) 927-939.

[39] J. Moreno, C. Rodríguez, N. Jiménez, Heuristic cluster algorithm for multiple facility location-allocation problem, ‎RAIRO-Operations Research-Recherche Opérationnelle 25 (1991) 97-107.

[40] T. ncan, Heuristics for the single source capacitated multi-facility Weber problem, Computers & Industrial Engineering 64 (2013) 959-971.
[41] M. N. Neema, K. M. Maniruzzaman, A. Ohgai, New genetic algorithms based approaches to continuous p-median problem, Networks and Spatial Economics 11 (2011) 83-99.
[42] A. R. Dehkordi, The optimal solution set of the multi-source Weber problem, Bulletin of the Iranian Mathematical Society 45 (2019) 495-514.
[43] G. Reinelt, TSPLIB A traveling salesman problem library, ORSA journal on computing 3 (1991) 376-384.
[44] M. G. Resende, R. F. Werneck, A hybrid heuristic for the p-median problem, Journal of heuristics 10 (2004) 59-88.
[45] M. G. Resende, R. F. Werneck, A fast swapbased local search procedure for location problems, Annals of Operations Research 150 (2007) 205-230.
[46] S. Salhi, M. D. H. Gamal, A genetic algorithm based approach for the uncapacitated continuous location allocation problem, Annals of Operations Research 123 (2003) 203-222.
[47] M. B. Teitz, P. Bart, Heuristic methods for estimating the generalized vertex median of a weighted graph, Operations research 16 (1968) 955-961.
[48] E. Weiszfeld, Sur le point pour lequel lasomme des distances de n points donns est minimum, Tohoku Mathematical Journal, First Series 43 (1937) 355-386.
[49] Z. M. Zainuddin, S. Salhi, A perturbationbased heuristic for the capacitated multisource Weber problem,European Journal of Operational Research 179 (2007) 1194-1207.