Hybrid Genetic for the Single-Source Capacitated Multi-Facility Weber Problem
محورهای موضوعی : مجله بین المللی ریاضیات صنعتی
S Jahadi
1
(
Department of Industrial Engineering, Urmia University of Technology, Urmia, Iran.
)
M. Solimanpur
2
(
Department of Industrial Engineering, Urmia University, Urmia, Iran.
)
کلید واژه: Metaheuristic, Genetic algorithm, Location-allocation, Local search, Weber Problem,
چکیده مقاله :
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.
در این مقاله، ما مساله وبر چند تسهیلی با محدودیت ظرفیت تک منبعی را بررسی می کنیم. هدف استقرار چند تسهیل جدید در میان مشتریان موجود و به طور همزمان تخصیص مشتریان به تسهیلات می باشد، به طوری که محدودیت های ظرفیت تسهیلات برآورده شده و هر مشتری تمام تقاضایش را فقط از یک تسهیل فراهم نماید و در نتیجه هزینه کل حمل و نقل میان تسهیلات جدید و مشتریان موجود مینی مم شود. یک الگوریتم ژنتیک برای حل مساله ارائه میگردد که درون آن یک الگوریتم جستجوی محلی جاسازی شده است. الگوریتم ژنتیک پیشنهادی بر روی چند داده نمونه موجود در ادبیات آزمایش میگردد تا توانمندی آن در مقایسه با روش های موجود در ادبیات ارزیابی گردد.
[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.
