Abstract
In this paper several dynamic multi-level location problems are formulated as mixed-integer linear programs. Both uncapacitated and capacitated versions of the problem are studied. The models presented are more complete than the ones known from the literature: they are dynamic and consider the possibility of a facility being opened, closed and reopened more than once during the planning horizon. They may include both upper and lower limits on the used capacity of each facility and may also consider the situation where there is no flow conservation in the intermediate facilities. Primal-dual heuristics were developed to solve the proposed models, having as main objective the capability of finding good primal solutions in reasonable computational times. Computational results are presented and discussed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
5. References
Aardal, K., Labbé, M., Leung, A., Queyranne, M. (1996). On the Two-Level Uncapacitated Facility Location Problem. INFORMS Journal on Computing 8, 289–301.
Bilde, O., Krarup, J. (1977) Sharp Lower Bounds and Efficient Algorithms for the Simple Plant Location Problem. Annals of Discrete Mathematics 1, 79–97.
Bloemhof-Ruwaard, J., Salomon, M., Van Wassenhove, L. N. (1996). The Capacitated Distribution and Waste Disposal Problem. European Journal of Operational Research 88, 490–503.
Canel, C., Khumawala, B., Law, J., Loh, A. (2001). An Algorithm for the Capacitated, Multi-Commodity, Multi-Period Facility Location Problem. Computers ⇐p; Operations Research 28, 411–427.
Chardaire, P. (1999). Hierarchical Two Level Location Problems. In Sansò and Soriano (editors) Telecommunications Network Planning, Kluwer Academics Publishers, 33–54.
Daskin, M. S. (1995). Network and Discrete Location Models, Algorithms and Applications, John Wiley ⇐p; Sons.
Dias, J., Captivo, M.E., ClÍmaco, J. (2006). Capacitated Dynamic Location Problems with Opening, Closure and Reopening of Facilities. In Salhi S., Drezner, Z. (editors) IMA J. Management Mathematics: Models and Applications in Location Analysis 17(4), 317–348
Eitan, Y., Narula, S. C., Tien, J. (1991). A Generalized Approach to Modelling the Hierarchical Location-Allocation Problem. IEEE Transactions on Systems Man and Cybernetics 21, 39–46.
Erlenkotter, D. (1978). A Dual-based Procedure for Uncapacitated Facility Location. Operations Research 26, 992–1009.
Espejo, L. G. A, Galvão, R. D., Boffey, B. (2003). Dual-based Heuristics for a Hierarchical Covering Location Problem. Computers ⇐p; Operations Research 30, 165–180.
Galvão, R. D., Espejo, L. G. A Boffey, B. (2002). A Hierarchical Model for the Location of Perinatal Facilities in the Municipality of Rio de Janeiro. European Journal of Operational Research 138, 495–517.
Gao, L.-L., Robinson E. P. Jr. (1992). A Dual-Based Optimization Procedure for the Two-Echelon Uncapacitated Facility Location Problem. Naval Research Logistics 39, 191–212.
Guignard, M., Spielberg, K. (1979). A Direct Dual Method for the Mixed Plant Location Problem with Some Side Constraints. Mathematical Programming 17, 198–228.
Hinojosa, Y., Puerto, J., Fernández, F.R. (2000). A Multiperiod two-echelon multicommodity capacitated plant location problem. European Journal of Operational Research 123, 271–291.
Jayaraman, V., Gupta, R., Pirkul, H. (2003). Selecting hierarchical facilities in a service-operations environment. European Journal of Operational Research 147, 613–628.
Klose, A. (2000). A Lagrangean Relax-and-Cut Approach for the Two-Stage Capacitated Facility Location Problem. European Journal of Operational Research 126, 408–421
Melachrinoudis, E., Min, H. (2000). The Dynamic Relocation and Phase-Out of a Hybrid, Two-Echelon Plant/Warehouse Facility: A Multiple Objective Approach. European Journal of Operational Research 123, 1–15.
Moore, G., ReVelle, C. (1982). The Hierarchical Service Location Problem. Management Science 28, 775–780
Narula, S. (1984). Hierarchical Location-Allocation Problems: A Classification Scheme. European Journal of Operational Research 15, 93–99.
Narula, S., Ogbu, U. (1985). Lagrangean Relaxation and Decomposition in an Uncapacitated 2-Hierarchical Location-Allocation Problem. Computers ⇐p; Operations Research 12, 169–180.
Pirkul, H., Jayaraman, V. (1998). A Multi-Commodity, Multi-Plant, Capacitated Facility Location Problem: Formulation and Efficient Heuristic Solution. Computers ⇐p; Operations Research 25, 869–878.
Ro, H.-B., Tcha, D.-W. (1984). A Branch and Bound Algorithm for the Two-Level Uncapacitated Facility Location Problem with Some Side Constraints. European Journal of Operational Research 18, 349–358
Saldanha da Gama, F., Captivo, M.E. (2002). A Branch-and-Bound Procedure for the Multi-Period Capacitated Location Problem. Working Paper 8/2002, Centro de Investigação Operacional — Faculdade de Ciências da Universidade de Lisboa.
Tcha, D.-W., Lee, B.-I. (1984). A Branch and Bound Algorithm for the Multilevel Uncapacitated Facility Location Problem. European Journal of Operational Research 18, 35–43.
Tien, J. M., El-Tell, K., Simons, G. R. (1983). Improved Formulations to the Hierarchical Health Facility Location-Allocation Problem. IEEE Transactions on Systems Man and Cybernetics 13, 1128–1132.
Tragantalerngsak, S., Holt, J., Rönnqvist, M. (2000). An Exact Method for the Two-Echelon, Single-Source, Capacitated Facility Location Problem. European Journal of Operational Research 123, 473–489.
Van Roy T., Erlenkotter, D. (1982). A Dual-Based Procedure for Dynamic Facility Location. Management Science 28, 1091–1105.
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by research project POSI/ISFL-13/308, POCTI/ISFL-1/152 and POCTI/MAT/139/2001.
Rights and permissions
About this article
Cite this article
Dias, J., Captivo, M.E. & Clíma, J. Dynamic multi-level capacitated and uncapacitated location problems: an approach using primal-dual heuristics. Oper Res Int J 7, 345–379 (2007). https://doi.org/10.1007/BF03024853
Issue Date:
DOI: https://doi.org/10.1007/BF03024853