×

Solving the uncapacitated facility location problem using tabu search. (English) Zbl 1086.90038

Summary: A tabu search heuristic procedure is developed to solve the uncapacitated facility location problem. Tabu search is used to guide the solution process when evolving from one solution to another. A move is defined to be the opening or closing of a facility. The net cost change resulting from a candidate move is used to measure the attractiveness of the move. After a move is made, the net cost change of a candidate move is updated from its old value. Updating, rather than re-computing, the net cost changes substantially reduces computation time needed to solve a problem when the problem is not excessively large. Searching only a small subset of the feasible solutions that contains the optimal solution, the procedure is computationally very efficient. A computational experiment is conducted to test the performance of the procedure and computational results are reported. The procedure can easily find optimal or near optimal solutions for benchmark test problems from the literature. For randomly generated test problems, this tabu search procedure not only obtained solutions completely dominating those obtained with other heuristic methods recently published in the literature but also used substantially less computation time. Therefore, this tabu search procedure has advantage over other heuristic methods in both solution quality and computation speed.

MSC:

90B85 Continuous location
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Simchi-Levi, D.; Kaminsky, P.; Simchi-Levi, E., Designing and managing the supply chain, concepts, strategies and case studies, (2000), Irwin McGraw-Hill Boston, Massachusetts
[2] Chan, Y., Location theory and decision analysis, (2001), South-Western College Publishing Cincinnati, Ohio
[3] Daskin, M.S., Network and discrete location, models, algorithms, and applications, (1995), Wiley New York · Zbl 0870.90076
[4] Mirchandani PB, Francis RL, editors. Discrete location theory. New York: Wiley; 1990.
[5] Brandeau, M.L.; Chiu, S.L., Overview of representative problems in location research, Management science, 35, 6, 674-695, (1989) · Zbl 0669.90040
[6] Chhajed, D.; Francis, R.L.; Lowe, T.J., Contributions of operations research to location analysis, Location science, 1, 263-287, (1993) · Zbl 0926.90054
[7] Ghosh, A.; Harche, F., Location-allocation models in the private sector: progress, problems, and prospects, Location science, 1, 81-106, (1993) · Zbl 0923.90103
[8] Krarup, J.; Pruzan, P.M., The simple plant location problem: survey and synthesis, European journal of operational research, 12, 1, 36-81, (1983) · Zbl 0506.90018
[9] Krarup, J.; Pruzan, P.M., Ingredients of location analysis, (), 1-54
[10] Glover, F., Tabu search, part I, ORSA journal on computing, 1, 3, 190-206, (1989) · Zbl 0753.90054
[11] Glover, F., Tabu search, part II, ORSA journal on computing, 2, 1, 4-32, (1990) · Zbl 0771.90084
[12] Glover, F., Tabu search: a tutorial, Interfaces, 20, 4, 74-94, (1990)
[13] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publishers Hingham, MA · Zbl 0930.90083
[14] Glover, F.; Taillard, E.; deWerra, D., A User’s guide to tabu search, Annals of operations research, 41, 1-4, 3-28, (1993) · Zbl 0772.90063
[15] Cornuéjols, G.; Nemhauser, G.L.; Wolsey, L.A., The uncapacitated facility location problem, (), 119-171 · Zbl 0727.90043
[16] Gen, M.; Tsujimura, Y.; Ishizaki, S., Optimal design of a star-LAN using neural networks, Computers and industrial engineering, 31, 3/4, 855-859, (1996)
[17] Kuehn, A.A.; Hamburger, M.J., A heuristic program for locating warehouses, Management science, 9, 643-666, (1963)
[18] Cornuéjols, G.; Fisher, M.L.; Wolsey, L.A., Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms, Management science, 23, 789-810, (1977) · Zbl 0361.90034
[19] Nemhauser, G.L.; Wolsey, L.A.; Fisher, L.M., An analysis of approximations for maximizing submodular set functions, I, Mathematical programming, 14, 265-294, (1978) · Zbl 0374.90045
[20] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations research, 26, 992-1009, (1978) · Zbl 0422.90053
[21] Beasley, J.E., Lagrangean heuristics for location problems, European journal of operational research, 65, 383-399, (1993) · Zbl 0768.90045
[22] Vaithyanathan, S.; Burke, L.; Magent, M., Massively parallel analog tabu search using neural networks applied to simple plant location problems, European journal of operational research, 93, 317-330, (1996) · Zbl 0912.90196
[23] Al-Sultan, K.S.; Al-Fawzan, M.A., A tabu search approach to the uncapacitated facility location problem, Annals of operations research, 86, 91-103, (1999) · Zbl 0918.90093
[24] Grolimund, S.; Ganascia, J.-G., Driving tabu search with case-based reasoning, European journal of operational research, 103, 2, 326-338, (1997) · Zbl 0929.90046
[25] Ghosh, D., Neighborhood search heuristics for the uncapacitated facility location problem, European journal of operational research, 150, 150-162, (2003) · Zbl 1023.90524
[26] Michel, L.; Van Hentenryck, P., A simple tabu search for warehouse location, European journal of operational research, 157, 3, 576-591, (2004) · Zbl 1067.90054
[27] Resende MGC, Werneck RF. A hybrid multistart heuristic for the uncapacitated facility location problem. AT&T Labs Research Technical Report TD-SRELRR; 2003.
[28] Sun, M., A tabu search heuristic procedure for the uncapacitated facility location problem, (), 191-211 · Zbl 1072.90064
[29] Rolland, E.; Schilling, D.A.; Current, J.R., An efficient tabu search procedure for the p-Median problem, European journal of operational research, 96, 329-342, (1996) · Zbl 0924.90102
[30] Crainic, T.G.; Gendreau, M., Cooperative parallel tabu search for capacitated network design, Journal of heuristics, 8, 6, 601-627, (2002)
[31] Delmaire, H.; Díaz, J.A.; Fernández, E.; Ortega, M., Reactive GRASP and tabu search based heuristics for the single source capacitated plant location problem, Information systems and operations research, 37, 3, 194-225, (1999)
[32] Filho, V.J.M.F.; Galvão, R.D., A tabu search heuristic for the concentrator location problem, Location science, 6, 189-209, (1998)
[33] Tuzun, D.; Burke, L.I., A two-phase tabu search approach to the location routing problem, European journal of operational research, 116, 1, 87-99, (1999) · Zbl 1009.90056
[34] Körkel, M., On the exact solution of large-scale simple plant location problems, European journal of operational research, 39, 1, 157-173, (1989) · Zbl 0673.90032
[35] Beasley, J.E., OR-library: distributing test problems by electronic mail, Journal of the operational research society, 41, 11, 1069-1072, (1990)
[36] Hoefer M. UflLib at http://www.mpi-sb.mpg.de/units/ag1/projects/benchmarks/UflLib/; 2004.
[37] Sun, M., A tabu search heuristic procedure for solving the transportation problem with exclusionary side constraints, Journal of heuristics, 3, 4, 305-326, (1998) · Zbl 0903.90120
[38] Sun, M.; Aronson, J.E.; McKeown, P.G.; Drinka, D., A tabu search heuristic procedure for the fixed charge transportation problem, European journal of operational research, 106, 2-3, 441-456, (1998) · Zbl 0991.90010
[39] Sun, M.; McKeown, P.G., Tabu search applied to the general fixed charge problem, Annals of operations research, 41, 405-420, (1993) · Zbl 0775.90287
[40] Whitaker, R., A fast algorithm for the greedy interchange for large-scale clustering and Median location problems, Information systems and operations research, 21, 95-108, (1983) · Zbl 0527.90017
[41] Hoefer M. Performance of heuristic and approximation algorithms for the uncapacitated facility location problem. Research Report MPI-I-2002-1-005, Max-Planck-Institut für Informatik; 2002.
[42] Kochetov Y. Benchmarks Library at http://www.math.nsc.ru/LBRT/k5/Kochetov/bench.html; 2003.
[43] Kratica, J.; Tosic, D.; Filipovic, V.; Ljubic, I., Solving the simple plant location problem by genetic algorithm, RAIRO operations research, 35, 127-142, (2001) · Zbl 0995.90055
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.