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

doi:10.15302/J-FEM-2018038

Front. Eng

2018, Vol. 5

Issue (4) : 451-465 https://doi.org/10.15302/J-FEM-2018038

RESEARCH ARTICLE

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

Fred GLOVER¹(

), Saïd HANAFI², Oualid GUEMRI², Igor CREVITS²

¹. Leeds School of Business, University of Colorado, Boulder, CO 80309-0419, USA
². LAMIH, CNRS UMR 8201, Université de Valenciennes, France

Download: PDF(255 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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

Corresponding Author(s): Fred GLOVER

Just Accepted Date: 13 August 2018 Online First Date: 02 November 2018 Issue Date: 29 November 2018

Cite this article:

Fred GLOVER,Saïd HANAFI,Oualid GUEMRI, et al. A simple multi-wave algorithm for the uncapacitated facility location problem[J]. Front. Eng, 2018, 5(4): 451-465.

URL:

https://academic.hep.com.cn/fem/EN/10.15302/J-FEM-2018038
https://academic.hep.com.cn/fem/EN/Y2018/V5/I4/451

Fig.1 Vertical phase

r = | A M R | < v k

Fig.2 Horizontal phase

r = | A M R | < v k

Tab.1 MWA results versus multi-start results

Tab.2 MWA results versus literature results on GHOSH benchmark instances

Tab.3 MWA CPU-times versus literature CPU-times on GHOSH benchmark instances

Tab.4 MWA results versus literature results on MED test problems?

Tab.5 MWA best solutions versus ILS best solutions on MED test problems

?Instance	?TS		?LAG		?US		?HYB		?MWA
	?Cost	?CPU	?Cost	?CPU	?Cost	?CPU	?Cost	?CPU	?Cost	?CPU ?All	?Find
?MO1	?1305.95	?0.68	?1305.95	?0.69	?1305.95	?0.07	?1305.95	?0.988	?1305.95	?0.24	?0.08
?MO2	?1432.26	?0.76	?1445.70	?0.73	?1432.26	?0.07	?1432.26	?1.030	?1432.26	?0.27	?0.10
?MO3	?1516.77	?0.80	?1535.77	?0.79	?1516.77	?0.07	?1516.77	?0.960	?1516.77	?0.30	?0.12
?MO4	?1442.24	?0.77	?1442.24	?0.79	?1442.24	?0.06	?1442.24	?0.892	?1442.24	?0.27	?0.09
?MO5	?1408.77	?0.80	?1408.77	?0.78	?1408.77	?0.06	?1408.77	?0.815	?1408.77	?0.34	?0.09
?MP1	?2686.48	?4.97	?2722.66	?3.40	?2686.48	?0.24	?2686.48	?3.695	?2686.48	?0.72	?0.33
?MP2	?2904.86	?5.00	?2914.42	?2.81	?2904.86	?0.28	?2904.86	?4.125	?2904.86	?0.78	?0.47
?MP3	?2623.71	?4.95	?2623.71	?3.06	?2623.71	?0.30	?2623.71	?3.500	?2623.71	?0.61	?0.33
?MP4	?2938.75	?5.82	?2958.80	?3.23	?2938.75	?0.32	?2938.75	?3.887	?2938.75	?0.70	?0.34
?MP5	?2932.33	?5.49	?2946.03	?3.06	?2932.33	?0.25	?2932.33	?4.169	?2932.33	?0.75	?0.42
?MQ1	?4091.01	?20.84	?4091.01	?3.96	?4091.01	?0.84	?4091.01	?8.919	?4091.01	?1.64	?0.91
?MQ2	?4028.33	?17.82	?4096.13	?4.34	?4028.33	?0.79	?4028.33	?7.802	?4028.33	?1.65	?1.15
?MQ3	?4275.43	?15.46	?4373.08	?3.78	?4275.43	?0.84	?4275.43	?9.508	?4275.43	?1.63	?0.97
?MQ4	?4235.15	?16.24	?4274.68	?4.06	?4235.15	?0.74	?4235.15	?9.834	?4235.15	?1.84	?0.92
?MQ5	?4080.74	?17.66	?4138.50	?3.87	?4080.74	?0.90	?4080.74	?10.813	?4080.74	?1.87	?0.98
?MR1	?2608.15	?71.33	?2634.71	?11.67	?2608.15	?3.04	?2608.15	?27.221	?2608.15	?8.05	?4.03
?MR2	?2654.73	?74.02	?2704.66	?11.37	?2654.73	?2.98	?2654.73	?27.646	?2654.73	?6.02	?3.86
?MR3	?2788.25	?83.13	?2874.46	?11.62	?2788.25	?3.20	?2788.25	?26.417	?2788.25	?4.74	?4.10
?MR4	?2756.04	?72.84	?2774.38	?12.54	?2756.04	?2.91	?2756.04	?27.595	?2756.04	?7.70	?3.96
?MR5	?2505.05	?75.91	?2526.32	?11.57	?2505.05	?3.08	?2505.05	?26.989	?2505.05	?7.80	?4.54
?MS1	?5283.76	?629.31	?5434.11	?50.19	?5283.76	?10.56	?5283.76	?113.395	?5283.76	?31.34	?11.12
?MT1	?10069.80	?6173.04	?10172.55	?189.69	?10069.80	?120.58	?10069.80	?701.167	?10069.80	?180.33	?78.47
?#BKS	?22/22		?5/22		?22/22		?22/22		?22/22

Tab.6 MWA results versus literature results on M* test problems

Tab.7 MWA results versus literature results on ORLIB test problems

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 https://doi.org/10.1287/moor.13.1.1
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 https://doi.org/10.1504/IJISE.2017.085207
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 https://doi.org/10.1023/A:1018956213524
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 https://doi.org/10.1287/ijoc.2017.0755
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 https://doi.org/10.1016/j.apm.2012.09.039
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 https://doi.org/10.1016/j.cie.2014.04.010
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 https://doi.org/10.1016/j.ijpe.2005.08.010
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 https://doi.org/10.1007/s12597-014-0190-5
12	Beasley J E (1990). OR-Library: Distributing test problems by electronic mail. Journal of the Operational Research Society, 41(11): 1069–1072 https://doi.org/10.1057/jors.1990.166
13	Beasley J E (1993). Lagrangean heuristics for location problems. European Journal of Operational Research, 65(3): 383–399 https://doi.org/10.1016/0377-2217(93)90118-7
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 https://doi.org/10.1007/s10589-006-6513-6
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 https://doi.org/10.1007/s10589-010-9338-2
16	Blum C, Roli A (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3): 268–308 https://doi.org/10.1145/937503.937505
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 https://doi.org/10.1016/j.ijpe.2013.05.013
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 https://doi.org/10.1023/A:1012248319870
21	Cura T (2010). A parallel local search approach to solving the uncapacitated warehouse location problem. Computers & Industrial Engineering, 59(4): 1000–1009 https://doi.org/10.1016/j.cie.2010.09.012
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 https://doi.org/10.1057/s41274-016-0155-6
23	De Corte A, Sörensen K (2015). An iterated local search algorithm for water distribution network design optimization. Networks, 67(3): 187–198 https://doi.org/10.1002/net.21673
24	Erlenkotter D (1978). A dual-based procedure for uncapacitated facility location: General solution procedures and computational experience. Operations Research, 26(6): 992–1009 https://doi.org/10.1287/opre.26.6.992
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 https://doi.org/10.1016/j.ejor.2018.03.009
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 https://doi.org/10.1007/BF02097805
27	Ghosh D (2003). Neighborhood search heuristics for the uncapacitated facility location problem. European Journal of Operational Research, 150(1): 150–162 https://doi.org/10.1016/S0377-2217(02)00504-0
28	Glover F (1989). Tabu search—Part I. ORSA Journal on Computing, 1(3): 190–206 https://doi.org/10.1287/ijoc.1.3.190
29	Glover F (1995). Tabu thresholding: Improved search by nonmonotonic trajectories. ORSA Journal on Computing, 7(4): 426–442 https://doi.org/10.1287/ijoc.7.4.426
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 https://doi.org/10.1007/s10732-016-9312-y
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 https://doi.org/10.1016/S0305-0548(02)00049-7
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 https://doi.org/10.1016/j.cie.2017.06.019
35	Greistorfer P, Rego C (2006). A simple filter-and-fan approach to the facility location problem. Computers & Operations Research, 33(9): 2590–2601 https://doi.org/10.1016/j.cor.2005.07.006
36	Hale T S, Moberg C R (2003). Location science research: A review. Annals of Operations Research, 123(1/4): 21–35 https://doi.org/10.1023/A:1026110926707
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 https://doi.org/10.1007/s10878-017-0179-0
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 https://doi.org/10.1007/s10878-017-0192-3
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 https://doi.org/10.1007/s10287-015-0244-z
41	Khumawala B M (1972). An efficient branch and bound algorithm for the warehouse location problem. Management Science, 18(12): 718–731 https://doi.org/10.1287/mnsc.18.12.B718
42	Klose A, Drexl A (2005). Facility location models for distribution system design. European Journal of Operational Research, 162(1): 4–29 https://doi.org/10.1016/j.ejor.2003.10.031
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 https://doi.org/10.1016/0377-2217(89)90189-6
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 https://doi.org/10.1051/ro:2001107
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 https://doi.org/10.1016/j.ejor.2008.05.007
46	Michel L, Van Hentenryck P (2004). A simple tabu search for warehouse location. European Journal of Operational Research, 157(3): 576–591 https://doi.org/10.1016/S0377-2217(03)00247-9
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 https://doi.org/10.1287/ijoc.2017.0757
48	Ortiz-Astorquiza C, Contrerasn I, Laporte G (2017b). Multi-level facility location problems. European Journal of Operational Research, 267(3): 791–805 https://doi.org/10.1016/j.ejor.2017.10.019
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 https://doi.org/10.1016/j.ejor.2018.03.021
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 https://doi.org/10.1007/s12532-014-0065-z
51	Resende M G, Werneck R F (2004). A hybrid heuristic for the p-median problem. Journal of Heuristics, 10(1): 59–88 https://doi.org/10.1023/B:HEUR.0000019986.96257.50
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 https://doi.org/10.1016/j.ejor.2005.02.046
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 https://doi.org/10.1007/s10479-006-0154-0
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 https://doi.org/10.1016/j.ejor.2003.11.032
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 https://doi.org/10.1166/jctn.2017.6258
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 https://doi.org/10.1016/j.cor.2005.07.014
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 https://doi.org/10.1007/s11590-015-0867-6
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 https://doi.org/10.1002/ecj.10180
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 https://doi.org/10.3233/JIFS-169263
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 https://doi.org/10.1016/j.cor.2011.12.006
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 https://doi.org/10.1080/00207540600621003

Viewed

Full text

Abstract

Cited

Shared

Discussed