Abstract
This contribution is focused on an acceleration of branch and bound algorithms for the uncapacitated facility location problem. Our approach is based on the well-known Erlenkotters’ procedures and Körkels’ multi-ascent and multi-adjustment algorithms, which have proved to be the efficient tools for solving the large-sized instances of the uncapacitated facility location problem. These two original approaches were examined and a thorough analysis of their performance revealed how each particular procedure contributes to the computational time of the whole algorithms. These analyses helped us to focus our effort on the most frequent procedures. The unique contribution of this paper is a new dual ascent procedure. This procedure leads to considerable acceleration of the lower bound computation process and reduces the resulting computational time. To demonstrate more efficient performance of amended algorithms we present the results of extensive numerical experiments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alves, M. L., & Almeida, M. T. (1992). Simulated annealing algorithm for simple plant location problem. Revista investigación, 12.
Balinski, M. (1965). Integer programming: methods, uses computation. Management Science, 12, 254–313.
Beasley, J. E. (1990). OR-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
Bilde, O., & Krarup, J. (1977). Sharp lower bounds and efficient algorithms for the simple plant location problem. Annals of Discrete Mathematics, 1, 77–97.
Brandeau, M. L., & Chiu, S. S. (1989). An overview of representative problems in location research. Management Science, 35(6), 645–674.
Conn, A. R., & Cornuéjols, G. (1990). A Projection method for the uncapacitated facility location problem. Mathematical Programming, 46, 273–298.
Cornuejols, G., Nemhauser, G. L., & Wolsey, L. A. (1990). The uncapacitated facility location problem. In P. B. Mirchandani, & R. L. Francis (Eds.), Discrete location theory (pp. 119–171). New York: Wiley.
Crainic, T. G. (2003). Long-haul freight transportation. In Handbook of transportation science. New York: Springer.
Erlenkotter, D. (1978). A dual-based procedure for uncapacitated facility location. Operations Research, 26(6), 992–1009.
Galvão, R. D. (2004). Uncapacitated facility location problems: contributions. Pesquisa Operacional, 24, 7–38.
Ghosh, D. (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research, 150, 150–162.
Goldengorin, B., Tijssen, G. A., Ghosh, D., & Sierksma, G. (2003). Solving the simple plant location problem using a data correcting approach. Journal of Global Optimization, 25(4), 377–406.
Goldengorin, B., Ghosh, D., & Sierksma, G. (2004). Branch and peg algorithms for the simple plant location problem. Computers & OR, 31(2), 241–255.
Hale, T. S., & Moberg, C. R. (2003). Location science research: a review. Annals of Operations Research, 123, 21–35.
Janáček, J. (2004). Service system design in the public and private sectors. In Proceedings of the International Conference: Mathematical Methods in Economics Virt (pp. 101–108).
Janáček, J., & Kovačiková, J. (1997). Exact solution techniques for large location problems. In Proceedings of the International Conference: Mathematical Methods in Economics (pp. 80–84). Ostrava.
Klose, A., & Drexl, A. (2005). Facility location models for distribution system design. European Journal of Operational Research, 162, 4–29.
Körkel, M. (1989). On then exact solution of large-scale simple plant location problem. European Journal of Operational Research, 39(2), 157–173.
Kratica, J., Tosic, D., Filipovic, V., & Ljubic, I. (2001). Solving the simple plant location problem by genetic algorithm. RAIRO Operations Research, 35, 127–142.
Labbé, M., & Louveaux, F. V. (1997). Location problem. In N. DellAmico, F. Maffioli, & S. Martello (Eds.), Annotated bibliographies in combinatorial optimization (pp. 264–271). New York: Wiley.
Michel, L., & Hentenryck, P. V. (2004). A simple tabu search for warehouse location. European Journal of Operational Research, 157(3), 576–591.
Mladenović, N., Brimberg, J., & Hansen, P. (2006). A note on duality gap in the simple plant location problem. European Journal of Operational Research, 174, 11–22.
Owen, H. O., & Daskin, M. S. (1998). Strategic facility location: a review. European journal of Operational Research, 111, 423–447.
Resende, M. G. C., & Werneck, R. F. (2006). A hybrid multistart heuristic for the uncapacitated facility location problem. European Journal of Operational Research, 174, 54–68.
Sultan, K. S., & Fawzan, M. A. (1999). A tabu search approach to the uncapacitated facility location problem. Annals of Operations Research, 86, 91–103.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Janáček, J., Buzna, Ľ. An acceleration of Erlenkotter-Körkel’s algorithms for the uncapacitated facility location problem. Ann Oper Res 164, 97–109 (2008). https://doi.org/10.1007/s10479-008-0343-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0343-0