×

Upper and lower bounds for the single source capacitated location problem. (English) Zbl 1053.90051

Summary: The single source capacitated location problem is considered. Given a set of potential locations and the plant capacities, it must be decided where and how many plants must be open and which clients must be assigned to each open plant. A Lagrangean relaxation is used to obtain lower bounds for this problem. Upper bounds are given by Lagrangean heuristics followed by search methods and by one tabu search metaheuristic. Computational experiments on different sets of problems are presented.

MSC:

90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agar, M. C.; Salhi, S., Lagrangean heuristics applied to a variety of large scale capacitated plant location problems, Journal of the Operational Research Society, 49, 1072-1084 (1998) · Zbl 1140.90419
[2] Barceló, J.; Casanovas, J., A heuristic Lagrangean algorithm for the capacitated plant location problem, European Journal of Operational Research, 15, 212-226 (1984) · Zbl 0544.90025
[3] Barceló, J.; Fernandez, E.; Jornsten, K., Computational results from a new relaxation algorithm for the capacitated plant location problem, European Journal of Operational Research, 53, 38-45 (1991) · Zbl 0734.90044
[4] Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of the Operational Society, 41, 1069-1072 (1990)
[5] Beasley, J. E., Lagrangean heuristics for location problems, European Journal of Operational Research, 65, 383-399 (1993) · Zbl 0768.90045
[6] Christofides, N.; Mingozzi, A.; Toth, P., Combinatorial Optimization (1979), Wiley: Wiley Chichester
[8] Darby-Dowman, K.; Lewis, H. S., Lagrangean relaxation and the single source capacitated facility location problem, Journal of the Operational Research Society, 39, 11, 1035-1040 (1988) · Zbl 0662.90025
[10] DeMaio, O.; Roveda, C. A., An all zero-one algorithm for a certain class of transportation problems, Operations Research, 19, 1406-1418 (1971) · Zbl 0276.90037
[12] Erlenkotter, D., A dual-based procedure for the uncapacitated facility location, Operations Research, 26, 992-1009 (1978) · Zbl 0422.90053
[13] Fiho, V. J.M. F.; Galvão, R. D., A tabu search heuristic for the concentrator location problem, Location Science, 6, 189-209 (1998)
[14] Floyd, R. W.; Algorithm 97: Shortest Path, Communications of the ACM, 5, 6, 345 (1962)
[15] Glover, F., Future path for integer programming and links to artificial intelligence, Computers and Operations Research, 1, 533-549 (1986) · Zbl 0615.90083
[16] Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0930.90083
[18] Held, M.; Karp, R. M., The travelling salesman problem and minimum spanning trees, Operations Research, 18, 1138-1162 (1970) · Zbl 0226.90047
[19] Held, M.; Karp, R. M., The travelling salesman problem and minimum spanning trees: Part II, Mathematical Programming, 1, 6-25 (1970) · Zbl 0232.90038
[20] Hindi, K. S.; Pienkosz, K., Efficient solution of large scale, single source, capacitated plant location problem, Journal of the Operational Research Society, 50, 268-274 (1999) · Zbl 1054.90588
[21] Holmberg, K.; Ronnqvist, M.; Yuan, D., An exact algorithm for the capacitated facility location problems with single sourcing, European Journal of Operational Research, 113, 544-559 (1999) · Zbl 0947.90059
[22] Klincewicz, J. G.; Luss, H., A Lagrangean relaxation heuristic for the capacitated facility location with single-source constraints, Journal of the Operational Research Society, 37/5, 495-500 (1986) · Zbl 0588.90025
[23] Kuehn, A.; Hamburger, M. J., A heuristic program for locating warehouses, Management Science, 9, 643-666 (1963)
[25] Neebe, A. E.; Rao, M. R., An algorithm for the fixed-charge assigning users to sources problem, Journal of the Operational Research Society, 34, 11, 1107-1113 (1983) · Zbl 0521.90075
[26] Nauss, R. M., An improved algorithm for the capacitated facility location problem, Journal of the Operational Research Society, 29, 1195-1201 (1978) · Zbl 0402.90063
[27] Pirkul, H., Efficient algorithms for the capacitated concentrator problem, Computers and Operations Research, 14, 197-208 (1987) · Zbl 0617.90019
[28] Sridharan, R., A Lagrangean heuristic for the capacitated plant problem with single source constraints, European Journal of Operational Research, 66, 305-312 (1993) · Zbl 0771.90062
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.