IDEAS home Printed from https://ideas.repec.org/a/sae/envirb/v47y2020i6p1014-1030.html
   My bibliography  Save this article

Generating optimal and near-optimal solutions to facility location problems

Author

Listed:
  • Richard L Church
  • Carlos A Baez

Abstract

There is a decided bent toward finding an optimal solution to a given facility location problem instance, even when there may be multiple optima or competitive near-optimal solutions. Identifying alternate solutions is often ignored in model application, even when such solutions may be preferred if they were known to exist. In this paper we discuss why generating close-to-optimal alternatives should be the preferred approach in solving spatial optimization problems, especially when it involves an application. There exists a classic approach for finding all alternate optima. This approach can be easily expanded to identify all near-optimal solutions to any discrete location model. We demonstrate the use of this technique for two classic problems: the p -median problem and the maximal covering location problem. Unfortunately, we have found that it can be mired in computational issues, even when problems are relatively small. We propose a new approach that overcomes some of these computational issues in finding alternate optima and near-optimal solutions.

Suggested Citation

  • Richard L Church & Carlos A Baez, 2020. "Generating optimal and near-optimal solutions to facility location problems," Environment and Planning B, , vol. 47(6), pages 1014-1030, July.
  • Handle: RePEc:sae:envirb:v:47:y:2020:i:6:p:1014-1030
    DOI: 10.1177/2399808320930241
    as

    Download full text from publisher

    File URL: https://journals.sagepub.com/doi/10.1177/2399808320930241
    Download Restriction: no

    File URL: https://libkey.io/10.1177/2399808320930241?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Maria Scaparra & Richard Church & F. Medrano, 2014. "Corridor location: the multi-gateway shortest path model," Journal of Geographical Systems, Springer, vol. 16(3), pages 287-309, July.
    2. Price, James & Keppo, Ilkka, 2017. "Modelling to generate alternatives: A technique to explore uncertainty in energy-environment-economy models," Applied Energy, Elsevier, vol. 195(C), pages 356-369.
    3. Andrew C. Trapp & Renata A. Konrad, 2015. "Finding diverse optima and near-optima to binary integer programs," IISE Transactions, Taylor & Francis Journals, vol. 47(11), pages 1300-1312, November.
    4. Richard L. Church & Alan Murray, 2018. "Location Covering Models," Advances in Spatial Science, Springer, number 978-3-319-99846-6.
    5. Richard Church & Charles R. Velle, 1974. "The Maximal Covering Location Problem," Papers in Regional Science, Wiley Blackwell, vol. 32(1), pages 101-118, January.
    6. Baum, Sanford & Carlson, Robert, 1979. "On solutions that are better than most," Omega, Elsevier, vol. 7(3), pages 249-255.
    7. S. L. Hakimi, 1965. "Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems," Operations Research, INFORMS, vol. 13(3), pages 462-475, June.
    8. DeCarolis, Joseph F., 2011. "Using modeling to generate alternatives (MGA) to expand our thinking on energy futures," Energy Economics, Elsevier, vol. 33(2), pages 145-152, March.
    9. E. Downey Brill, Jr., 1979. "The Use of Optimization Models in Public-Sector Planning," Management Science, INFORMS, vol. 25(5), pages 413-422, May.
    10. Mark S. Daskin, 2008. "What you should know about location modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 283-294, June.
    11. E. Downey Brill, Jr. & Shoou-Yuh Chang & Lewis D. Hopkins, 1982. "Modeling to Generate Alternatives: The HSJ Approach and an Illustration Using a Problem in Land Use Planning," Management Science, INFORMS, vol. 28(3), pages 221-235, March.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dubois, Antoine & Dumas, Jonathan & Thiran, Paolo & Limpens, Gauthier & Ernst, Damien, 2023. "Multi-objective near-optimal necessary conditions for multi-sectoral planning," Applied Energy, Elsevier, vol. 350(C).
    2. Blanco, Víctor & Gázquez, Ricardo & Saldanha-da-Gama, Francisco, 2023. "Multi-type maximal covering location problems: Hybridizing discrete and continuous problems," European Journal of Operational Research, Elsevier, vol. 307(3), pages 1040-1054.
    3. Jing, Rui & Kuriyan, Kamal & Kong, Qingyuan & Zhang, Zhihui & Shah, Nilay & Li, Ning & Zhao, Yingru, 2019. "Exploring the impact space of different technologies using a portfolio constraint based approach for multi-objective optimization of integrated urban energy systems," Renewable and Sustainable Energy Reviews, Elsevier, vol. 113(C), pages 1-1.
    4. Schwaeppe, Henrik & Thams, Marten Simon & Walter, Julian & Moser, Albert, 2024. "Finding better alternatives: Shadow prices of near-optimal solutions in energy system optimization modeling," Energy, Elsevier, vol. 292(C).
    5. Michael J. Brusco, 2022. "Solving Classic Discrete Facility Location Problems Using Excel Spreadsheets," INFORMS Transactions on Education, INFORMS, vol. 22(3), pages 160-171, May.
    6. Aditya Sinha & Aranya Venkatesh & Katherine Jordan & Cameron Wade & Hadi Eshraghi & Anderson R. Queiroz & Paulina Jaramillo & Jeremiah X. Johnson, 2024. "Diverse decarbonization pathways under near cost-optimal futures," Nature Communications, Nature, vol. 15(1), pages 1-15, December.
    7. Jiwon Baik & Alan T. Murray, 2022. "Locating a facility to simultaneously address access and coverage goals," Papers in Regional Science, Wiley Blackwell, vol. 101(5), pages 1199-1217, October.
    8. Chang, Miguel & Lund, Henrik & Thellufsen, Jakob Zinck & Østergaard, Poul Alberg, 2023. "Perspectives on purpose-driven coupling of energy system models," Energy, Elsevier, vol. 265(C).
    9. Murray, Alan T., 2021. "Contemporary optimization application through geographic information systems," Omega, Elsevier, vol. 99(C).
    10. Makowski, David & Hendrix, Eligius M. T. & van Ittersum, Martin K. & Rossing, Walter A. H., 2001. "Generation and presentation of nearly optimal solutions for mixed-integer linear programming, applied to a case in farming system design," European Journal of Operational Research, Elsevier, vol. 132(2), pages 425-438, July.
    11. David Guerrero & Jean Paul Hubert & Martin Koning & Nicolas Roelandt, 2022. "On the Spatial Scope of Warehouse Activity: An Exploratory Study in France," Post-Print hal-03551270, HAL.
    12. Berntsen, Philip B. & Trutnevyte, Evelina, 2017. "Ensuring diversity of national energy scenarios: Bottom-up energy system model with Modeling to Generate Alternatives," Energy, Elsevier, vol. 126(C), pages 886-898.
    13. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty," European Journal of Operational Research, Elsevier, vol. 306(1), pages 173-188.
    14. Mark S. Daskin, 2008. "What you should know about location modeling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(4), pages 283-294, June.
    15. Fodstad, Marte & Crespo del Granado, Pedro & Hellemo, Lars & Knudsen, Brage Rugstad & Pisciella, Paolo & Silvast, Antti & Bordin, Chiara & Schmidt, Sarah & Straus, Julian, 2022. "Next frontiers in energy system modelling: A review on challenges and the state of the art," Renewable and Sustainable Energy Reviews, Elsevier, vol. 160(C).
    16. Paolo Thiran & Hervé Jeanmart & Francesco Contino, 2023. "Validation of a Method to Select a Priori the Number of Typical Days for Energy System Optimisation Models," Energies, MDPI, vol. 16(6), pages 1-20, March.
    17. R A Gerrard & R L Church, 1995. "A General Construct for the Zonally Constrained p-Median Problem," Environment and Planning B, , vol. 22(2), pages 213-236, April.
    18. Jesús Sánchez-Oro & Ana D. López-Sánchez & Anna Martínez-Gavara & Alfredo G. Hernández-Díaz & Abraham Duarte, 2021. "A Hybrid Strategic Oscillation with Path Relinking Algorithm for the Multiobjective k -Balanced Center Location Problem," Mathematics, MDPI, vol. 9(8), pages 1-21, April.
    19. Yunjia Ma & Wei Xu & Lianjie Qin & Xiujuan Zhao, 2019. "Site Selection Models in Natural Disaster Shelters: A Review," Sustainability, MDPI, vol. 11(2), pages 1-24, January.
    20. A. D. López-Sánchez & J. Sánchez-Oro & M. Laguna, 2021. "A New Scatter Search Design for Multiobjective Combinatorial Optimization with an Application to Facility Location," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 629-642, May.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:sae:envirb:v:47:y:2020:i:6:p:1014-1030. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: SAGE Publications (email available below). General contact details of provider: .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.