Big Bang-Big Crunch Optimization Algorithm for Solving the Uncapacitated Facility Location Problem

Abstract

The big bang–big crunch (BB–BC) algorithm has been proposed as a new optimization method based on the big bang and big crunch theory, one of the theories of the evolution of the universe. The BB-BC algorithm has been firstly presented to solve the optimization problems with continuous solutions space. If the solution space of the problem is binary-structural, the algorithm must be modified to solve this kind of the problems. Therefore, in this study, the BB-BC method, one of the population-based optimization algorithms, is modified to deal with binary optimization problems. The performance of the proposed methods is analyzed on uncapacitated facility location problems (UFLPs) which are one of the binary problems used in literature. The well-known small and medium twelve instances of UFLPs are used to analyze the performances and the effects of the control parameter of the BB-BC algorithm. The obtained results are comparatively presented. According to the experimental results, the binary version of the BB-BC method achieves successful results in solving UFLP in terms of solution quality.

Keywords

• Big Bang-Big Crunch Algorithm,Population-based optimization algorithms,Binary optimization,UFLP

References

1. [1] M. S. Kiran and M. Gunduz, "XOR-based artificial bee colony algorithm for binary optimization," Turkish Journal of Electrical Engineering and Computer Sciences, vol. 21, pp. 2307-2328, 2013.
2. [2] B. Alatas, "Uniform Big Bang-Chaotic Big Crunch optimization," Communications in Nonlinear Science and Numerical Simulation, vol. 16, pp. 3696-3703, Sep 2011.
3. [3] V. Korac, J. Kratica, and A. Savic, "An Improved Genetic Algorithm for the Multi Level Uncapacitated Facility Location Problem," International Journal of Computers Communications & Control, vol. 8, pp. 845-853, Dec 2013.
4. [4] H. Tohyama, K. Ida, and J. Matsueda, "A Genetic Algorithm for the Uncapacitated Facility Location Problem," Electronics and Communications in Japan, vol. 94, pp. 47-54, May 2011.
5. [5] M. Maric, "An Efficient Genetic Algorithm for Solving the Multi-Level Uncapacitated Facility Location Problem," Computing and Informatics, vol. 29, pp. 183-201, 2010.
6. [6] H. Topcuoglu, F. Corut, M. Ermis, and G. Yimaz, "Solving the uncapacitated hub location problem using genetic algorithms," Computers & Operations Research, vol. 32, pp. 967-984, Apr 2005.
7. [7] K. S. Al-Sultan and M. A. Al-Fawzan, "A tabu search approach to the uncapacitated facility location problem," Annals of Operations Research, vol. 86, pp. 91-103, 1999.
8. [8] M. H. Sun, "Solving the uncapacitated facility location problem using tabu search," Computers & Operations Research, vol. 33, pp. 2563-2589, Sep 2006.

9. [9] F. Altiparmak and E. Caliskan, "An Ant Colony Optimization Algorithm for the Uncapacitated Facility Location Problem," Proceedings of the 38th International Conference on Computers and Industrial Engineering, Vols 1-3, pp. 553-560, 2008.
10. [10] M. Sevkli and A. R. Guner, "A continuous particle swarm optimization algorithm for uncapacitated facility location problem," Ant Colony Optimization and Swarm Intelligence, Proceedings, vol. 4150, pp. 316-323, 2006.
11. [11] D. Z. Wang, C. H. Wu, A. Ip, D. W. Wang, and Y. Yan, "Parallel Multi-Population Particle Swarm Optimization Algorithm for the Uncapacitated Facility Location Problem using OpenMP," 2008 Ieee Congress on Evolutionary Computation, Vols 1-8, pp. 1214-1218, 2008.
12. [12] S. Saha, A. Kole, and K. Dey, "A Modified Continuous Particle Swarm Optimization Algorithm for Uncapacitated Facility Location Problem," Information Technology and Mobile Communication, vol. 147, pp. 305-311, 2011.
13. [13] Y. Watanabe, M. Takaya, and A. Yamamura, "Fitness Function in ABC Algorithm for Uncapacitated Facility Location Problem," Information and Communication Technology, vol. 9357, pp. 129-138, 2015.
14. [14] M. S. Kiran, "The continuous artificial bee colony algorithm for binary optimization," Applied Soft Computing, vol. 33, pp. 15-23, Aug 2015.
15. [15] M. H. Kashan, N. Nahavandi, and A. H. Kashan, "DisABC: A new artificial bee colony algorithm for binary optimization," Applied Soft Computing, vol. 12, pp. 342-352, Jan 2012.
16. [16] A. Kaveh and S. Talatahari, "Size optimization of space trusses using Big Bang-Big Crunch algorithm," Computers & Structures, vol. 87, pp. 1129-1140, Sep 2009.
17. [17] O. K. Erol and I. Eksin, "A new optimization method: Big Bang Big Crunch," Advances in Engineering Software, vol. 37, pp. 106-111, Feb 2006.
18. [18] A. Kaveh and S. Talatahari, "Optimal design of Schwedler and ribbed domes via hybrid Big Bang-Big Crunch algorithm," Journal of Constructional Steel Research, vol. 66, pp. 412-419, Mar 2010.
19. [19] C. V. Camp, "Design of space trusses using big bang-big crunch optimization," Journal of Structural Engineering-Asce, vol. 133, pp. 999-1008, Jul 2007.
20. [20] M. S. Daskin, L. V. Snyder, and R. T. Berger, "Facility location in supply chain design," Lehigh University, Working, pp. 03-010, 2003.
21. [21] G. Cornuejols, G. L. Nemhauser, and L. A. Wolsey, "The uncapacitated facility location problem," Lecture Notes in Artificial Intelligence, vol. 1865, pp. 171, 1990, 1990.
22. [22] K. Holmberg, "Exact solution methods for uncapacitated location problems with convex transportation costs," European Journal of Operational Research, vol. 114, pp. 127-140, Apr 1 1999.
23. [23] J. Barcelo, A. Hallefjord, E. Fernandez, and K. Jornsten, "Lagrangean Relaxation and Constraint Generation Procedures for Capacitated Plant Location-Problems with Single Sourcing," Or Spektrum, vol. 12, pp. 79-88, 1990.
24. [24] L. L. Gao and E. P. Robinson, "A Dual-Based Optimization Procedure for the 2-Echelon Uncapacitated Facility Location Problem," Naval Research Logistics, vol. 39, pp. 191-212, Mar 1992.
25. [25] J. E. Beasley, "Or-Library - Distributing Test Problems by Electronic Mail," Journal of the Operational Research Society, vol. 41, pp. 1069-1072, Nov 1990.