Skip to main content
SpringerLink
Log in

Applying Lagrangian relaxation to the resolution of two‐stage location problems

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

A family of two‐stage location problems is considered. These problems involve a systemproviding a choice of depots andyor plants, each with an associated location cost, and a setof demand points which must be supplied, in such a way that the total cost is minimized. Byusing Lagrangian relaxation, lower bounds and heuristic solutions are obtained for two kindsof formulation involving two or three indexes for each transportation variable. The goodnessof both formulations is compared by means of a computational study, and the results forseveral instances are presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Barceló, E. Fernández and K.O. Jörnsten, Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem, Eur. J. Oper. Res. 53(1991)38-45.

    Google Scholar 

  2. C. Barnhart, E.L. Johnson, G.L. Nemhauser, G. Sigismondi and P. Vance, Formulating a mixed integer programming problem to improve solvability, Oper. Res. 41(1993)1013-1019.

    Google Scholar 

  3. A.I. Barros, Discrete and fractional programming techniques for location models, Ph.D. Thesis, Erasmus University, Rotterdam, 1995.

    Google Scholar 

  4. A.I. Barros and M. Labbé, The multi-level uncapacitated facility location problem is not submodular, Eur. J. Oper. Res. 72(1994)607-609.

    Google Scholar 

  5. A.I. Barros and M. Labbé, A general model for the uncapacitated facility and depot location problem, Location Sci. 2(1994)173-191.

    Google Scholar 

  6. W.J. Baumol and P. Wolfe, A warehouse location problem, Oper. Res. 6(1958)252-263.

    Google Scholar 

  7. J.E. Beasley, An algorithm for solving large capacitated warehouse location problems, Eur. J. Oper. Res. 33(1988)314-325.

    Google Scholar 

  8. J.E. Beasley, Lagrangean heuristics for location problems, Eur. J. Oper. Res. 65(1993)383-399.

    Google Scholar 

  9. J.M. Bloemhof-Ruwaard, M. Salomon and L.N. Van Wassenhove, On the coordination of product and by-product flows in two level distribution networks: Model formulation and solution procedures, Eur. J. Oper. Res. 79(1994)325-339.

    Google Scholar 

  10. J.M. Bloemhof-Ruwaard, M. Salomon and L.N. Van Wassenhove, The capacitated distribution and waste disposal problem, Eur. J. Oper. Res. 88(1996)490-503.

    Google Scholar 

  11. N. Christofides and J.E. Beasley, Extensions to a Lagrangean relaxation approach for the capacitated warehouse location problem, Eur. J. Oper. Res. 12(1983)19-28.

    Google Scholar 

  12. G. Cornuéjols, R. Sridharan and J.M. Thizy, A comparison of heuristics and bounds for the Capacitated Plant Location Problem, Eur. J. Oper. Res. 50(1991)280-297.

    Google Scholar 

  13. T.G. Crainic and L. Delorme, Dual-ascent procedures for multicommodity location-allocation problems with balancing requirements, Transport. Sci. 27(1993)90-101.

    Google Scholar 

  14. T.G. Crainic, P. Dejax and L. Delorme, Models for multimode multicommodity location problems with interdepot balancing requirements, Ann. Oper. Res. 18(1989)279-302.

    Google Scholar 

  15. T.G. Crainic, L. Delorme and P. Dejax, A branch-and-bound method for multicommodity location with balancing requirements, Eur. J. Oper. Res. 65(1993)368-382.

    Google Scholar 

  16. L.B. Ellwein and P. Gray, Solving fixed charge location-allocation problems with capacity and configuration constraints, AIIE Trans. 3(1971)290-298.

    Google Scholar 

  17. D.G. Elson, Site location via mixed-integer programming, Oper. Res. Q. 23(1972)31-43.

    Google Scholar 

  18. M.L. Fisher, The Lagrangian relaxation method for solving integer programming problems, Manage. Sci. 27(1981)1-18.

    Google Scholar 

  19. L-L. Gao and E.P. Robinson, Jr., A dual-based optimization procedure for the two-echelon uncapacitated facility location problem, Nav. Res. Log. 39(1992)191-212.

    Google Scholar 

  20. B. Gendron and T.G. Crainic, A branch-and-bound algorithm for depot location and container fleet management, Location Sci. 3(1995)39-53.

    Google Scholar 

  21. A.M. Geoffrion, Lagrangean relaxation for integer programming, Math. Program. Study 2(1974) 82-114.

    Google Scholar 

  22. A.M. Geoffrion and G.W. Graves, Multicommodity distribution system design by Benders decomposition, Manage. Sci. 20(1974)822-844.

    Google Scholar 

  23. M. Guignard and S. Kim, Lagrangean decomposition for integer programming: Theory and applications, R.A.I.R.O. 21(1987)307-323.

    Google Scholar 

  24. M. Guignard and S. Kim, Lagrangean decomposition: A model yielding stronger Lagrangean bounds, Math. Program. 39(1987)215-228.

    Google Scholar 

  25. M. Guignard and K. Opaswongkarn, Lagrangean dual ascent algorithms for computing bounds in capacitated plant location problem, Eur. J. Oper. Res. 46(1990)73-83.

    Google Scholar 

  26. M. Guignard and M.B. Rosenwein, An application-oriented guide for designing Lagrangean dual ascent algorithms, Eur. J. Oper. Res. 43(1989)197-205.

    Google Scholar 

  27. P. Hanjoul and D. Peeters, A comparison of two dual-based procedures for solving the p-median problem, Eur. J. Oper. Res. 20(1985)387-396.

    Google Scholar 

  28. M. Held, P. Wolfe and H.P. Crowder, Validation of subgradient optimization, Math. Program. 6(1974)62-88.

    Google Scholar 

  29. L. Kaufman, M.V. Eede and P. Hansen, A plant and warehouse location problem, Oper. Res. Q. 28(1977)547-554.

    Google Scholar 

  30. A.A. Kuehn and M.J. Hamburger, A heuristic program for locating warehouses, Manage. Sci., 9 (1963) 643-666.

    Google Scholar 

  31. A. Marín and B. Pelegrín, A branch-and-bound algorithm for the transportation problem with location of p transshipment points, Computers & Oper. Res. 7(1997)659-678.

    Google Scholar 

  32. A. Marín and B. Pelegrín, The return plant location problem: Modelling and resolution, Eur. J. Oper. Res. 104(1998)375-392.

    Google Scholar 

  33. R.V. Nagelhout and G.L. Thompson, A cost operator approach to multistage location-allocation, Eur. J. Oper. Res. 6(1981)149-161.

    Google Scholar 

  34. H. Ro and D. Tcha, A branch and bound algorithm for the two-level uncapacitated facility location problem with some side constraints, Eur. J. Oper. Res. 18(1984)349-358.

    Google Scholar 

  35. M.M. Syslow, N. Deo and J.S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, Prentice-Hall, 1983.

  36. D. Tcha and B. Lee, A branch-and-bound algorithm for the multi-level uncapacitated facility location problem, Eur. J. Oper. Res. 18(1984)35-43.

    Google Scholar 

  37. J.M. Thizy, A facility location problem with aggregate capacity, INFOR 32(1994)1-18.

    Google Scholar 

Download references

Authors
  1. A. Marín
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Pelegrín
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Marín, A., Pelegrín, B. Applying Lagrangian relaxation to the resolution of two‐stage location problems. Annals of Operations Research 86, 179–198 (1999). https://doi.org/10.1023/A:1018998500803

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018998500803

Keywords

Search

Navigation