×

Efficient primal-dual heuristic for a dynamic location problem. (English) Zbl 1159.90439

Summary: The dynamic location problem with opening, closure and reopening of facilities is formulated and an efficient primal-dual heuristic that computes both upper and lower limits to its optimal solution is described. The problem here studied considers the possibility of reconfiguring any location more than once over the planning horizon. This problem is NP-hard (the simple plant location problem is a special case of the problem studied). A primal-dual heuristic based on the work of D. Erlenkotter [Oper. Res. 26, 992–1009 (1978; Zbl 0422.90053)] and T. J. van Roy and D. Erlenkotter [Manage. Sci. 28, 1091–1105 (1982; Zbl 0495.90033)] was developed and tested over a set of randomly generated test problems. The results obtained are quite good, both in terms of the quality of lower and upper bounds calculated as in terms of the computational time spent by the heuristic. A branch-and-bound procedure that enables to optimize the problem is also described and tested over the same set of randomly generated problems.

MSC:

90B80 Discrete location and assignment
90C59 Approximation methods and heuristics in mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Beasley, J. E., Lagrangean heuristics for location problems, European Journal of Operational Research, 65, 383-399 (1993) · Zbl 0768.90045
[2] Cornuejols, G.; Nemhauser, G.; Wolsey, L., The uncapacitated facility location problem, (Mirchandani, P. B.; Francis, R. L., Discrete location theory (1990), Wiley Interscience: Wiley Interscience New York), 119-172 · Zbl 0727.90043
[3] Erlenkotter, D., A dual-based procedure for uncapacitated facility location, Operations Research, 26, 992-1009 (1978) · Zbl 0422.90053
[4] Krarup, J.; Pruzan, P., The simple plant location problem: survey and synthesis, European Journal of Operational Research, 12, 36-81 (1983) · Zbl 0506.90018
[5] Krarup, J.; Pruzan, P., Ingredients of locational analysis in discrete location, (Mirchandani, P. B.; Francis, R. L., Discrete location theory (1990), Wiley Interscience: Wiley Interscience New York), 1-54
[6] Morris, J. G., On the extent to which certain fixed-charged depot location problems can be solved by LP, Journal of the Operational Research Society, 29, 71-76 (1978)
[7] Ross, T.; Soland, R., Modelling facility location problems as generalized assignment problems, Management Science, 24, 345-357 (1977) · Zbl 0378.90066
[8] Swain, R., A parametric decomposition approach for the solution of uncapacitated location problems, Management Science, 21, 189-198 (1974) · Zbl 0331.90064
[9] Erlenkotter, D., A comparative study of approaches to dynamic location problems, European Journal of Operational Research, 6, 133-143 (1981) · Zbl 0451.90038
[10] Wesolowsky, G. O., Dynamic facility location, Management Science, 19, 1241-1248 (1973)
[11] Wesolowsky, G.; Truscott, W., The Multiperiod location-allocation problem with relocation of factilities, Management Science, 22, 57-65 (1975) · Zbl 0309.90066
[12] Fong, C. O.; Srinivasan, V., The multiregion dynamic capacity expansion problem—Part I, Operations Research, 29, 787-799 (1981) · Zbl 0463.90037
[13] Fong, C. O.; Srinivasan, V., The multiregion dynamic capacity expansion problem—Part II, Operations Research, 29, 800-816 (1981) · Zbl 0463.90038
[14] Van Roy, T.; Erlenkotter, D., A dual-based procedure for dynamic facility location, Management Science, 28, 1091-1105 (1982) · Zbl 0495.90033
[15] Laporte, G.; Dejax, P., Dynamic location-routing problems, Journal of the Operational Research Society, 40, 471-482 (1989) · Zbl 0665.90028
[16] Jacobsen, S., Multiperiod capacitated location models, (Mirchandani, P. B.; Francis, R. L., Discrete location theory (1990), Wiley Interscience: Wiley Interscience New York), 173-207 · Zbl 0731.90047
[17] Shulman, A., An algorithm for solving dynamic capacitated plant location problems with discrete expansion sizes, Operations Research, 39, 423-436 (1991) · Zbl 0742.90049
[18] Galvão, R. D.; Santibañez-Gonzalez, R., A Lagrangean heuristic for the \(P\)-median dynamic location problem, European Journal of Operational Research, 58, 250-262 (1992) · Zbl 0764.90057
[19] Melachrinoudis, E.; Min, H.; Wu, X., A multiobjective model for the dynamic location of landfills, Location Science, 3, 143-166 (1995) · Zbl 0916.90181
[20] Hinojosa, Y.; Puerto, J.; Fernández, F. R., A multiperiod two-echelon multicommodity capacitated plant location problem, European Journal of Operational Research, 123, 271-291 (2000) · Zbl 0967.90069
[21] Antunes, A.; Peeters, D., On solving complex multi-period location models using simulated annealing, European Journal of Operational Research, 130, 190-201 (2001) · Zbl 1068.90577
[22] Chardaire, P.; Sutter, A.; Costa, M.-C., Solving the dynamic facility location problem, Networks, 28, 117-124 (1996) · Zbl 0864.90073
[23] Canel, C.; Khumawala, B.; Law, J.; Loh, A., An algorithm for the capacitated, multi-commodity, multi-period facility location problem, Computers & Operations Research, 8, 411-427 (2001) · Zbl 1080.90535
[24] Saldanha da Gama F, Captivo ME. A note on a dual based procedure for dynamic facility location. Working Paper 11/96, Centro de InvestigaçÃo Operacional, Faculdade de Ciências da Universidade de Lisboa, 1996.; Saldanha da Gama F, Captivo ME. A note on a dual based procedure for dynamic facility location. Working Paper 11/96, Centro de InvestigaçÃo Operacional, Faculdade de Ciências da Universidade de Lisboa, 1996.
[25] Ahuja, R.; Magnanti, T.; Orlin, J., Network flows-theory, algorithms and applications (1993), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[26] Dias J, Captivo ME, Clímaco J. Capacitated dynamic location problems with opening, closure and reopening of facilities. Inescc Research Report 02/2004.; Dias J, Captivo ME, Clímaco J. Capacitated dynamic location problems with opening, closure and reopening of facilities. Inescc Research Report 02/2004. · Zbl 1126.90044
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.