A Golden Ball Algorithm for the Multi-Level Multi-Capacitated Facility Location Problem: A Comparative Study with Genetic Algorithm
Keywords:
Facility location, multi-capacity, multi-level, genetic algorithm, golden ball algorithmAbstract
This study addresses the Multi-Level Multi-Capacitated Facility Location Problem (ML-MCLP), which involves determining facility locations, capacity levels, and customer demands across a multi-level network while minimizing total assignment system costs. Given the NP-hard nature of the problem, we proposed a problem-specific “Golden Ball” (GBA) algorithm that incorporates a custom solution representation, feasibility checking mechanisms, and local improvement procedures. A comprehensive computational study is conducted on a diverse set of instances covering different problem sizes and capacity levels. Small and medium-sized instances are also solved using an exact mixed-integer programming solver to provide optimal or reference solutions. The proposed approach is compared to the genetic algorithm (GA) in terms of solution quality, computation time, robustness, and scalability. Several independent runs and statistical tests are used to evaluate the differences in performance. The results show that the proposed approach, based on the GBA algorithm, provides high-quality solutions and offers an optimal balance between solution quality and computational effort, particularly for large instances. These results demonstrate the potential of problem-specific GBA mechanisms to efficiently solve large-scale ML-MCLP instances.
References
K. Abbal, Y. Benadada, and M. El Amrani, “Bi-level multi-capacitated facility location problem,” in 2020 5th International Conference on Logistics Operations Management (GOL), Rabat, Morocco, 2020, pp. 1–5. doi: 10.1109/GOL49479.2020.9314710.
K. Abbal, M. El Amrani, and Y. Benadada, “Multi-level multi-capacitated facility location problem: Formulation and resolution,” in 2022 IEEE 6th International Conference on Logistics Operations Management (GOL), Strasbourg, France, 2022, pp. 1–6. doi: 10.1109/GOL53975.2022.9820242.
M. El Amrani, Y. Benadada, and B. Gendron, “Generalization of capacitated p-median location problem: Modeling and resolution,” in 2016 3rd International Conference on Logistics Operations Management (GOL), Fez, Morocco, 2016, pp. 1–6. doi: 10.1109/GOL.2016.7731674.
D. Tcha and B. Lee, “A branch-and-bound algorithm for the multi-level uncapacitated facility location problem,” European Journal of Operational Research, vol. 18, no. 1, pp. 35–43, 1984. doi: 10.1016/0377-2217(84)90258-3.
C. Ortiz-Astorquiza, I. Contreras, and G. Laporte, “An exact algorithm for multilevel uncapacitated facility location,” Transportation Science, vol. 53, no. 4, pp. 1085–1106, 2019. doi: 10.1287/trsc.2018.0868.
P. Chardaire, J.-L. Lutton, and A. Sutter, “Upper and lower bounds for the two-level simple plant location problem,” Annals of Operations Research, vol. 86, pp. 117–140, 1999. doi: 10.1023/A:1018942415824.
S. Tragantalerngsak, J. Holt, and M. Rönnqvist, “Lagrangian heuristics for the two-echelon, single-source, capacitated facility location problem,” European Journal of Operational Research, vol. 102, no. 3, pp. 611–625, 1997. doi: 10.1016/S0377-2217(96)00227-5.
Y. Hinojosa, J. Puerto, and F. R. Fernández, “A multiperiod two-echelon multicommodity capacitated plant location problem,” European Journal of Operational Research, vol. 123, no. 2, pp. 271–291, 2000. doi: 10.1016/S0377-2217(99)00256-8.
E. Osaba, F. Diaz, and E. Onieva, “Golden ball: A novel meta-heuristic to solve combinatorial optimization problems based on soccer concepts,” Applied Intelligence, vol. 41, no. 1, pp. 145–166, 2014. doi: 10.1007/s10489-013-0512-y.
E. Osaba, F. Diaz, R. Carballedo, E. Onieva, and A. Perallos, “Focusing on the Golden Ball metaheuristic: An extended study on a wider set of problems,” The Scientific World Journal, vol. 2014, Article ID 563259, 2014. doi: 10.1155/2014/563259.
K. Ruttanateerawichien, W. Kurutach, and T. Pichpibul, “An improved Golden Ball algorithm for the capacitated vehicle routing problem,” in Bio-Inspired Computing: Theories and Applications, Communications in Computer and Information Science, vol. 472, L. Pan, G. Păun, M. J. Pérez-Jiménez, and T. Song, Eds. Berlin, Germany: Springer, 2014, pp. 341–356. doi: 10.1007/978-3-662-45049-9_56.
A. Berahhou and Y. Benadada, “Dynamic vehicle routing problem with simultaneous delivery and pickup, overtime and inventory restriction: Golden Ball algorithm,” in 2022 IEEE 6th International Conference on Logistics Operations Management (GOL), Strasbourg, France, 2022, pp. 1–7. doi: 10.1109/GOL53975.2022.9820268.
J. H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, MI, USA: University of Michigan Press, 1975.
S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: Past, present, and future,” Multimedia Tools and Applications, vol. 80, no. 5, pp. 8091–8126, 2021. doi: 10.1007/s11042-020-10139-6.
Y.-Y. Leu, L. A. Matheson, and L. P. Rees, “Sequencing mixed-model assembly lines with genetic algorithms,” Computers & Industrial Engineering, vol. 30, no. 4, pp. 1027–1036, 1996. doi: 10.1016/0360-8352(96)00050-2.
M. Watanabe, K. Ida, and M. Gen, “A genetic algorithm with modified crossover operator and search area adaptation for the job-shop scheduling problem,” Computers & Industrial Engineering, vol. 48, no. 4, pp. 743–752, 2005. doi: 10.1016/j.cie.2004.12.008.
A. Berahhou, Y. Benadada, and K. Bouanane, “Memetic algorithm for the dynamic vehicle routing problem with simultaneous delivery and pickup,” International Journal of Industrial Engineering Computations, vol. 13, no. 4, pp. 587–600, 2022. doi: 10.5267/j.ijiec.2022.6.001.
D. R. M. Fernandes, C. Rocha, D. Aloise, G. M. Ribeiro, E. M. Santos, and A. Silva, “A simple and effective genetic algorithm for the two-stage capacitated facility location problem,” Computers & Industrial Engineering, vol. 75, pp. 200–208, 2014. doi: 10.1016/j.cie.2014.05.023.
J. Alcaraz, M. Landete, and J. F. Monge, “Design and analysis of hybrid metaheuristics for the reliability p-median problem,” European Journal of Operational Research, vol. 222, no. 1, pp. 54–64, 2012. doi: 10.1016/j.ejor.2012.04.016.
A. Rahmani and S. A. MirHassani, “A hybrid Firefly-Genetic algorithm for the capacitated facility location problem,” Information Sciences, vol. 283, pp. 70–78, 2014. doi: 10.1016/j.ins.2014.06.002.
M. Besbes, M. Zolghadri, R. Costa Affonso, F. Masmoudi, and M. Haddar, “A methodology for solving facility layout problem considering barriers: Genetic algorithm coupled with A* search,” Journal of Intelligent Manufacturing, vol. 31, no. 3, pp. 615–640, 2020. doi: 10.1007/s10845-019-01468-x.
M. M. Nasiri, V. Mahmoodian, A. Rahbari, and S. Farahmand, “A modified genetic algorithm for the capacitated competitive facility location problem with the partial demand satisfaction,” Computers & Industrial Engineering, vol. 124, pp. 435–448, 2018. doi: 10.1016/j.cie.2018.07.045.
J. H. Jaramillo, J. Bhadury, and R. Batta, “On the use of genetic algorithms to solve location problems,” Computers & Operations Research, vol. 29, no. 6, pp. 761–779, 2002. doi: 10.1016/S0305-0548(01)00021-1.
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. doi: 10.1016/j.ejor.2006.09.069.
G. Cornuéjols, R. Sridharan, and J. M. Thizy, “A comparison of heuristics and relaxations for the capacitated plant location problem,” European Journal of Operational Research, vol. 50, no. 3, pp. 280–297, 1991. doi: 10.1016/0377-2217(91)90261-S.
A. Klose, “An LP-based heuristic for two-stage capacitated facility location problems,” Journal of the Operational Research Society, vol. 50, no. 2, pp. 157–166, 1999. doi: 10.1057/palgrave.jors.2600675.
A. Azadeh, S. Elahi, M. H. Farahani, and B. Nasirian, “A genetic algorithm-Taguchi based approach to inventory routing problem of a single perishable product with transshipment,” Computers & Industrial Engineering, vol. 104, pp. 124–133, 2017. doi: 10.1016/j.cie.2016.12.019.
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Khalil Abbal (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
Copyright and Licensing
Authors publishing in the International Journal of Intelligent Optimization and Logistics (IJIOL) retain copyright of their work and grant the journal the right of first publication.
All articles are published under the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits unrestricted use, distribution, reproduction, and adaptation in any medium, including for commercial purposes, provided that appropriate credit is given to the original authors and the source of publication, a link to the license is provided, and any changes made are indicated.
Authors may enter into additional non-exclusive agreements for the distribution of the published version of their work, provided that its original publication in IJIOL is acknowledged.
