A simple multi-wave algorithm for the uncapacitated facility location problem

Abstract

The multi-wave algorithm (Glover, 2016) integrates tabu search and strategic oscillation utilizing repeated waves (nested iterations) of constructive search or neighborhood search. We propose a simple multi-wave algorithm for solving the Uncapacitated Facility Location Problem (UFLP) to minimize the combined costs of selecting facilities to be opened and of assigning each customer to an opened facility in order to meet the customers’ demands. The objective is to minimize the overall cost including the costs of opening facilities and the costs of allocations. Our experimental tests on a standard set of benchmarks for this widely-studied class of problems show that our algorithm outperforms all previous methods.

Keywords

discrete optimization / UFLP / multi-wave optimization / strategic oscillation / tabu search

References

[1] Ahn S, Cooper C, Cornuéjols G, Frieze A (1988). Probabilistic analysis of a relaxation for the k-median problem. Mathematics of Operations Research, 13(1): 1–31

[2] Akbaripour H, Masehian E, Roostaei A (2017). Landscape analysis and scatter search metaheuristic for solving the uncapacitated single allocation hub location problem. International Journal of Industrial and Systems Engineering, 26(4): 425–459

[3] Al-Sultan K S, Al-Fawzan M A (1999). A tabu search approach to the uncapacitated facility location problem. Annals of Operations Research, 86: 91–103

[4] Albareda-Sambola M, Fernández E, Saldanha-da-Gama F (2017). Heuristic solutions to the facility location problem with general bernoulli demands. INFORMS Journal on Computing, 29(4): 737–753

[5] Amin S H, Zhang G (2013). A multi-objective facility location model for closed-loop supply chain network under uncertain demand and return. Applied Mathematical Modelling, 37(6): 4165–4176

[6] An H C, Svensson O (2017). Recent developments in approximation algorithms for facility location and clustering problems. In: Fukunaga T, Kawarabayashi K, eds. Combinatorial Optimization and Graph Algorithms, 1–19. Singapore: Springer

[7] Ardjmand E, Park N, Weckman G, Amin-Naseri M R (2014). The discrete unconscious search and its application to uncapacitated facility location problem. Computers & Industrial Engineering, 73: 32–40

[8] Arostegui M A Jr, Kadipasaoglu S N, Khumawala B M (2006). An empirical comparison of tabu search, simulated annealing, and genetic algorithms for facilities location problems. International Journal of Production Economics, 103(2): 742–754

[9] Atta S, Mahapatra P R S, Mukhopadhyay A (2018). Deterministic and randomized heuristic algorithms for uncapacitated facility location problem. Information and Decision Sciences, 205–216. Singapore: Springer

[10] Barahona F, Chudak F (1999). Near-optimal Solutions to Large Scale Facility Location Problems. Technical Report RC21606, IBM, USA

[11] Basu S, Sharma M, Ghosh P S (2015). Metaheuristic applications on discrete facility location problems: A survey. OPSEARCH, 52(3): 530–561

[12] Beasley J E (1990). OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11): 1069–1072

[13] Beasley J E (1993). Lagrangean heuristics for location problems. European Journal of Operational Research, 65(3): 383–399

[14] Beltran C, Tadonki C, Vial J Ph (2006). Solving the p-median problem with a semi-Lagrangian relaxation. Computational Optimization and Applications, 35(2): 239–260

[15] Beltran-Royo C, Vial J P, Alonso-Ayuso A (2012). Semi-lagrangian relaxation applied to the uncapacitated facility location problem. Computational Optimization and Applications, 51(1): 387–409

[16] Blum C, Roli A (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3): 268–308

[17] Cerrone C, Cerulli R, Golden B (2017). Carousel greedy: A generalized greedy algorithm with applications in optimization and statistics. Computers & Operations Research, 85: 97–112

[18] Chalupa D, Nielsen P (2018). Instance scale, numerical properties and design of metaheuristics: A study for the facility location problem. arXiv preprint arXiv:1801.03419

[19] Chen L, Olhager J, Tang O (2014). Manufacturing facility location and sustainability: A literature review and research agenda. International Journal of Production Economics, 149: 154–163

[20] Cheung B S, Langevin A, Villeneuve B (2001). High performing evolutionary techniques for solving complex location problems in industrial system design. Journal of Intelligent Manufacturing, 12(5): 455–466

[21] Cura T (2010). A parallel local search approach to solving the uncapacitated warehouse location problem. Computers & Industrial Engineering, 59(4): 1000–1009

[22] De Armas J, Juan A A, Marques J M, Pedroso J P (2017). Solving the deterministic and stochastic uncapacitated facility location problem: From a heuristic to a simheuristic. Journal of the Operational Research Society, 68(10): 1161–1176

[23] De Corte A, Sörensen K (2015). An iterated local search algorithm for water distribution network design optimization. Networks, 67(3): 187–198

[24] Erlenkotter D (1978). A dual-based procedure for uncapacitated facility location: General solution procedures and computational experience. Operations Research, 26(6): 992–1009

[25] Galli L, Letchford A N, Miller S J (2018). New valid inequalities and facets for the simple plant location problem. European Journal of Operational Research, 269(3): 824–833

[26] Galvão R D, Raggi L A (1989). A method for solving to optimality uncapacitated location problems. Annals of Operations Research, 18(1): 225–244

[27] Ghosh D (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research, 150(1): 150–162

[28] Glover F (1989). Tabu search—Part I. ORSA Journal on Computing, 1(3): 190–206

[29] Glover F (1995). Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA Journal on Computing, 7(4): 426–442

[30] Glover F (2000). Multi-start and strategic oscillation methods—principles to exploit adaptive memory. In: Laguna M, Gonzales-Velarde J L, eds. Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, 1–24. Berlin: Kluwer Academic Publishers

[31] Glover F (2016). The multi-wave algorithm for metaheuristic optimization. Journal of Heuristics, 22(3): 331–358

[32] Glover F, Laguna M (1997). Tabu Search. Boston: Kluwer Academic Publishers

[33] Goldengorin B, Ghosh D, Sierksma G (2003). Branch and peg algorithms for the simple plant location problem. Computers & Operations Research, 30(7): 967–981

[34] Grasas A, Juan A A, Faulin J, de Armas J, Ramalhinho H (2017). Biased randomization of heuristics using skewed probability distributions: A survey and some applications. Computers & Industrial Engineering, 110: 216–228

[35] Greistorfer P, Rego C (2006). A simple filter-and-fan approach to the facility location problem. Computers & Operations Research, 33(9): 2590–2601

[36] Hale T S, Moberg C R (2003). Location science research: A review. Annals of Operations Research, 123(1/4): 21–35

[37] Han L, Xu D, Du D, Zhang D (2018). A local search approximation algorithm for the uniform capacitated k-facility location problem. Journal of Combinatorial Optimization, 35(2): 409–423

[38] Homberger J, Gehring H (2008). A two-level parallel genetic algorithm for the uncapacitated warehouse location problem. In: Proceedings of Hawaii international conference on system sciences

[39] Jiang Y, Xu D, Du D, Wu C, Zhang D (2018). An approximation algorithm for soft capacitated k-facility location problem. Journal of Combinatorial Optimization, 35(2): 493–511

[40] Jörnsten K, Klose A (2016). An improved Lagrangian relaxation and dual ascent approach to facility location problems. Computational Management Science, 13(3): 317–348

[41] Khumawala B M (1972). An efficient branch and bound algorithm for the warehouse location problem. Management Science, 18(12): 718–731

[42] Klose A, Drexl A (2005). Facility location models for distribution system design. European Journal of Operational Research, 162(1): 4–29

[43] Körkel M (1989). On the exact solution of large-scale simple plant location problems. European Journal of Operational Research, 39(2): 157–173

[44] Kratica J, Tošic D, Filipović V, Ljubić I (2001). Solving the simple plant location problem by genetic algorithm. Operations Research, 35(1): 127–142

[45] Melo M T, Nickel S, Saldanha-Da-Gama F (2009). Facility location and supply chain management–A review. European Journal of Operational Research, 196(2): 401–412

[46] Michel L, Van Hentenryck P (2004). A simple tabu search for warehouse location. European Journal of Operational Research, 157(3): 576–591

[47] Ortiz-Astorquiza C, Contreras I, Laporte G (2017a). Formulations and approximation algorithms for multilevel uncapacitated facility location. INFORMS Journal on Computing, 29(4): 767–779

[48] Ortiz-Astorquiza C, Contrerasn I, Laporte G (2017b). Multi-level facility location problems. European Journal of Operational Research, 267(3): 791–805

[49] Pearce R H, Forbes M (2018). Disaggregated Benders decomposition and branch-and-cut for solving the budget-constrained dynamic uncapacitated facility location and network design problem. European Journal of Operational Research, 270(1): 78–88

[50] Posta M, Ferland J A, Michelon P (2014). An exact cooperative method for the uncapacitated facility location problem. Mathematical Programming Computation, 6(3): 199–231

[51] Resende M G, Werneck R F (2004). A hybrid heuristic for the p-median problem. Journal of Heuristics, 10(1): 59–88

[52] Resende M G C, Ribeiro C C (2003). Greedy randomized adaptive search procedures. In: Glover F, Kochenberger G, eds. Handbook of Metaheuristics, 219–249. Berlin: Kluwer Academic Publishers

[53] Resende M G C, Werneck R F (2006). A hybrid multistart heuristic for the uncapacitated facility location problem. European Journal of Operational Research, 174(1): 54–68

[54] Resende M G C, Werneck R F (2007). A fast swap-based local search procedure for location problems. Annals of Operations Research, 150(1): 205–230

[55] ReVelle C S, Eiselt H A, ReVelle C S (2005). Location analysis: A synthesis and survey. European Journal of Operational Research, 165(1): 1–19

[56] Sahman M A, Altun A A, Dündar A O (2017). The binary differential search algorithm approach for solving uncapacitated facility location problems. Journal of Computational and Theoretical Nanoscience, 14(1): 670–684

[57] Sun M (2005). A tabu search heuristic procedure for the uncapacitated facility location problem. In: Rego C, Alidaee B, eds. Metaheuristic Optimization via Memory and Evolution: Tabu Search and Scatter Search, 191–211. Boston: Kluwer Academic Publishers

[58] Sun M (2006). Solving the uncapacitated facility location problem using tabu search. Computers & Operations Research, 33(9): 2563–2589

[59] Todosijević R, Urošević D, Mladenović N, Hanafi S (2017). A general variable neighborhood search for solving the uncapacitated r-allocation p-hub median problem. Optimization Letters, 11(6): 1109–1121

[60] Tohyama H, Ida K, Matsueda J (2011). A genetic algorithm for the uncapacitated facility location problem. Electronics and Communications in Japan, 94(5): 47–54

[61] Tseng L Y, Wu C S (2009a). Multiple trajectory search for uncapacitated facility location problems. In: Proceedings of the Second International Joint Conference on Computational Sciences and Optimization, Sanya, China. 2: 965–968

[62] Tseng L Y, Wu C S (2009b). The multistart drop-add-swap heuristic for the uncapacitated facility location problem. In: Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics, Intelligent Control Systems and Optimization, Milan, Italy. 21–28

[63] Tsuya K, Takaya M, Yamamura A (2017). Application of the firefly algorithm to the uncapacitated facility location problem. Journal of Intelligent & Fuzzy Systems, 32(4): 3201–3208

[64] Wang D, Wu C H, Ip A, Wang D, Yan Y (2008). Parallel multipopulation particle swarm optimization algorithm for the uncapacitated facility location problem using OpenMP. In: Proceedings of 2008 IEEE Congress on Evolutionary Computation, IEEE World Congress on Computational Intelligence. 1214–1218

[65] Wang Y, Lu Z, Glover F, Hao J K (2013). Probabilistic GRASP-tabu search algorithms for the UBQP problem. Computers & Operations Research, 40(12): 3100–3107

[66] Xu J, Chiu S Y, Glover F (1997). Probabilistic tabu search for telecommunications network design. Combinatorial Optimization: Theory and Practice, 1(1): 69–94

[67] Yigit V, Aydin M E, Turkbey O (2006). Solving large-scale uncapacitated facility location problems with evolutionary simulated annealing. International Journal of Production Research, 44(22): 4773–4791

RIGHTS & PERMISSIONS

2018 The Author(s) 2018. Published by Higher Education Press. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0)