×

A hybrid approach using an artificial bee algorithm with mixed integer programming applied to a large-scale capacitated facility location problem. (English) Zbl 1264.90102

Summary: We present a hybridization of two different approaches applied to the well-known Capacitated Facility Location Problem (CFLP). The Artificial Bee algorithm (BA) is used to select a promising subset of locations (warehouses) which are solely included in the Mixed Integer Programming (MIP) model. Next, the algorithm solves the subproblem by considering the entire set of customers. The hybrid implementation allows us to bypass certain inherited weaknesses of each algorithm, which means that we are able to find an optimal solution in an acceptable computational time. In this paper we demonstrate that BA can be significantly improved by use of the MIP algorithm. At the same time, our hybrid implementation allows the MIP algorithm to reach the optimal solution in a considerably shorter time than is needed to solve the model using the entire dataset directly within the model. Our hybrid approach outperforms the results obtained by each technique separately. It is able to find the optimal solution in a shorter time than each technique on its own, and the results are highly competitive with the state-of-the-art in large-scale optimization. Furthermore, according to our results, combining the BA with a mathematical programming approach appears to be an interesting research area in combinatorial optimization.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
90C11 Mixed integer programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] V. Maniezzo, T. Stützle, and S. Voß, Eds., Matheuristics: Hybridizing Metaheuristics and Mathematical Programming, vol. 10, Annals of Information Systems, 2009. · Zbl 1179.90007
[2] C. Blum, J. Puchinger, G. Raidl, and A. Roli, “Hybrid metaheuristics in combinatorial optimization: a survey,” Applied Soft Computing Journal, vol. 11, no. 6, pp. 4135-4151, 2011. · Zbl 1205.90298
[3] G. Cabrera, S. Roncagliolo, J. P. Riquelme, C. Cubillos, and R. Soto, “Hybrid particle swarm optimization-simulated annealing algorithm for the probabilistic traveling salesman problem,” Studies in Informatics and Control (SIC), vol. 21, no. 1, pp. 49-58, 2012.
[4] J. E. Beasley, “Lagrangean heuristics for location problems,” European Journal of Operational Research, vol. 65, pp. 383-399, 1993. · Zbl 0768.90045 · doi:10.1016/0377-2217(93)90118-7
[5] M. H. Kashan, N. Nahavandi, and A. H. Kashan, “DisABC: a new artificial bee colony algorithm for binary optimization,” Applied Soft Computing, vol. 12, no. 1, pp. 342-352, 2012.
[6] C. Canel and B. M. Khumawala, “A mixed-integer programming approach for the international facilities location problem,” International Journal of Operations & Production Management, vol. 16, no. 4, pp. 49-68, 1996. · Zbl 0880.90086
[7] D. T. Pham, A. Ghanbarzadeh, E. Ko\cc, S. Otri, S. Rahim, and M. Zaidi, “The Bees Algorithm-a novel tool for complex optimization problems,” in Proceedings of the 2nd International Virtual Conference on Intelligent Production Machines and Systems (IPROMS ’06), pp. 454-459, 2006.
[8] F. Barahona and F. A. Chudak, “Near-optimal solutions to large-scale facility location problems,” Discrete Optimization, vol. 2, no. 1, pp. 35-50, 2005. · Zbl 1140.90442 · doi:10.1016/j.disopt.2003.03.001
[9] M. Caserta and E. Quiñonez Rico, “A cross entrophy-based metaheuristic algorithm for large-scale capacitated facility location problem,” Journal of the Operational Research Society, vol. 60, pp. 1439-1448, 2009. · Zbl 1196.90021 · doi:10.1057/jors.2008.77
[10] 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. · Zbl 0918.90093 · doi:10.1023/A:1018956213524
[11] M. S. Daskin, Network and Discrete Location, John Wiley & Sons, New York, NY, USA, 1995. · Zbl 0870.90076 · doi:10.1002/9781118032343
[12] Z. Drezner and H. W. Hamacher, Facility Location: Applications and Theory, Springer, New York, NY, USA, 2004. · Zbl 0988.00044
[13] M. J. Cortinhal and M. E. Captivo, “Genetic algorithms for the single source capacitated location problem,” in Metaheuristics: Computer Decision-Making, M. G. Resende and J.P. de Sousa, Eds., pp. 187-216, Kluwer Academic Publisher, 2004.
[14] M. H. Sun, “A tabu search heuristic procedure for the capacitated facility location problem,” Journal of Heuristics, vol. 18, no. 1, pp. 91-118, 2012.
[15] M. A. J. Arostegui, S. N. Kadipasaoglu, and B. M. Khumawala, “An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems,” International Journal of Production Economics, vol. 103, pp. 742-754, 2006.
[16] G. Cornuejols, R. Sridharan, and J. M. A. Thizy, “comparison of heuristics and relaxation for the capacitated plant location problem,” European Jurnal of Operational Research, vol. 50, pp. 280-297, 1991. · Zbl 0734.90046 · doi:10.1016/0377-2217(91)90261-S
[17] A. Klose and A. Drexl, “Lower bounds for the capacitated facility location problem based on column generation,” Management Science, vol. 51, no. 11, pp. 1689-1705, 2005. · Zbl 1232.90255 · doi:10.1287/mnsc.1050.0410
[18] P. Sinha, “Observations on some heuristic methods for the capacitated facility location problem,” Opsearch, vol. 49, no. 1, pp. 86-93, 2012. · Zbl 1353.90183 · doi:10.1007/s12597-012-0064-7
[19] J. K. Sankaran, “On solving large instances of the capacitated facility location problem,” European Journal of Operational Research, vol. 178, no. 3, pp. 663-676, 2007. · Zbl 1163.90614 · doi:10.1016/j.ejor.2006.01.035
[20] M. J. Cortinhal and M. E. Captivo, “Upper and lower bounds for the single source capacitated location problem,” European Journal of Operational Research, vol. 151, no. 2, pp. 333-351, 2003. · Zbl 1053.90051 · doi:10.1016/S0377-2217(02)00829-9
[21] C. Chen and C. Ting, “Combining lagrangian heuristic and ant colony system to solve the single source capacitated facility location problem,” Transportation Research E, vol. 44, no. 6, pp. 1099-1122, 2008.
[22] R. C. Eberhart, Y. Shi, and J. Kennedy, Swarm Intelligence, Morgan Kaufman, 2001.
[23] J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Mich, USA, 1975. · Zbl 0317.68006
[24] D. Karaboga and B. Akay, “A comparative study of artificial Bee colony algorithm,” Applied Mathematics and Computation, vol. 214, no. 1, pp. 108-132, 2009. · Zbl 1169.65053 · doi:10.1016/j.amc.2009.03.090
[25] D. Karaboga and B. A. Akay, “survey: algorithms simulating bee swarm intelligence,” Artificial Intelligence Review, vol. 31, pp. 61-85, 2009. · Zbl 1169.65053
[26] L. Özbakir, A. Baykaso\uglu, and P. Tapkan, “Bees algorithm for generalized assignment problem,” Applied Mathematics and Computation, vol. 215, no. 11, pp. 3782-3795, 2010. · Zbl 1181.90167 · doi:10.1016/j.amc.2009.11.018
[27] P. Hansen, J. Brimberg, D. Uro, and N. Mladenović, “Primal-dual variable neighborhood search for the simple plant-location problem,” INFORMS Journal on Computing, vol. 19, no. 4, pp. 552-564, 2007. · Zbl 1241.90072 · doi:10.1287/ijoc.1060.0196
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.