IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v57y2010i5p391-402.html
   My bibliography  Save this article

An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs

Author

Listed:
  • John Penuel
  • J. Cole Smith
  • Yang Yuan

Abstract

We study a stochastic scenario‐based facility location problem arising in situations when facilities must first be located, then activated in a particular scenario before they can be used to satisfy scenario demands. Unlike typical facility location problems, fixed charges arise in the initial location of the facilities, and then in the activation of located facilities. The first‐stage variables in our problem are the traditional binary facility‐location variables, whereas the second‐stage variables involve a mix of binary facility‐activation variables and continuous flow variables. Benders decomposition is not applicable for these problems due to the presence of the second‐stage integer activation variables. Instead, we derive cutting planes tailored to the problem under investigation from recourse solution data. These cutting planes are derived by solving a series of specialized shortest path problems based on a modified residual graph from the recourse solution, and are tighter than the general cuts established by Laporte and Louveaux for two‐stage binary programming problems. We demonstrate the computational efficacy of our approach on a variety of randomly generated test problems. © 2010 Wiley Periodicals, Inc. Naval Research Logistics, 2010

Suggested Citation

  • John Penuel & J. Cole Smith & Yang Yuan, 2010. "An integer decomposition algorithm for solving a two‐stage facility location problem with second‐stage activation costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(5), pages 391-402, August.
    • Handle: RePEc:wly:navres:v:57:y:2010:i:5:p:391-402
    DOI: 10.1002/nav.20401
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20401
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20401?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. Gilbert Laporte & François Louveaux & Hélène Mercure, 1992. "The Vehicle Routing Problem with Stochastic Travel Times," Transportation Science, INFORMS, vol. 26(3), pages 161-170, August.
    2. Gilbert Laporte & François V. Louveaux & Luc van Hamme, 1994. "Exact Solution to a Location Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 28(2), pages 95-103, May.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Tönissen, D.D. & Arts, J.J., 2020. "The stochastic maintenance location routing allocation problem for rolling stock," International Journal of Production Economics, Elsevier, vol. 230(C).
    2. Siqian Shen & J. Smith, 2013. "A decomposition approach for solving a broadcast domination network design problem," Annals of Operations Research, Springer, vol. 210(1), pages 333-360, November.

    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. Siqian Shen & J. Smith, 2013. "A decomposition approach for solving a broadcast domination network design problem," Annals of Operations Research, Springer, vol. 210(1), pages 333-360, November.
    2. Madadi, AliReza & Kurz, Mary E. & Mason, Scott J. & Taaffe, Kevin M., 2014. "Supply chain design under quality disruptions and tainted materials delivery," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 67(C), pages 105-123.
    3. Chiang, Wen-Chyuan & Russell, Robert & Xu, Xiaojing & Zepeda, David, 2009. "A simulation/metaheuristic approach to newspaper production and distribution supply chain problems," International Journal of Production Economics, Elsevier, vol. 121(2), pages 752-767, October.
    4. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    5. Correia, Isabel & Melo, Teresa, 2019. "Dynamic facility location problem with modular capacity adjustments under uncertainty," Technical Reports on Logistics of the Saarland Business School 17, Saarland University of Applied Sciences (htw saar), Saarland Business School.
    6. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.
    7. Jinil Han & Chungmok Lee & Sungsoo Park, 2014. "A Robust Scenario Approach for the Vehicle Routing Problem with Uncertain Travel Times," Transportation Science, INFORMS, vol. 48(3), pages 373-390, August.
    8. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    9. Hernan Caceres & Rajan Batta & Qing He, 2017. "School Bus Routing with Stochastic Demand and Duration Constraints," Transportation Science, INFORMS, vol. 51(4), pages 1349-1364, November.
    10. Gyana R. Parija & Shabbir Ahmed & Alan J. King, 2004. "On Bridging the Gap Between Stochastic Integer Programming and MIP Solver Technologies," INFORMS Journal on Computing, INFORMS, vol. 16(1), pages 73-83, February.
    11. Halit Üster & Sung Ook Hwang, 2017. "Closed-Loop Supply Chain Network Design Under Demand and Return Uncertainty," Transportation Science, INFORMS, vol. 51(4), pages 1063-1085, November.
    12. Bhoopalam, Anirudh Kishore & Agatz, Niels & Zuidwijk, Rob, 2018. "Planning of truck platoons: A literature review and directions for future research," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 212-228.
    13. Hongtao Lei & Gilbert Laporte & Bo Guo, 2012. "A generalized variable neighborhood search heuristic for the capacitated vehicle routing problem with stochastic service times," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 20(1), pages 99-118, April.
    14. Shubhechyya Ghosal & Wolfram Wiesemann, 2020. "The Distributionally Robust Chance-Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 68(3), pages 716-732, May.
    15. Amir Hossein Sadeghi & Ziyuan Sun & Amirreza Sahebi-Fakhrabad & Hamid Arzani & Robert Handfield, 2023. "A Mixed-Integer Linear Formulation for a Dynamic Modified Stochastic p-Median Problem in a Competitive Supply Chain Network Design," Logistics, MDPI, vol. 7(1), pages 1-24, March.
    16. Prasanna Balaprakash & Mauro Birattari & Thomas Stützle & Marco Dorigo, 2015. "Estimation-based metaheuristics for the single vehicle routing problem with stochastic demands and customers," Computational Optimization and Applications, Springer, vol. 61(2), pages 463-487, June.
    17. Peter Kall & János Mayer, 2006. "Some insights into the solution algorithms for SLP problems," Annals of Operations Research, Springer, vol. 142(1), pages 147-164, February.
    18. Chen, Lijian & Chiang, Wen-Chyuan & Russell, Robert & Chen, Jun & Sun, Dengfeng, 2018. "The probabilistic vehicle routing problem with service guarantees," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 111(C), pages 149-164.
    19. Hossein Hashemi Doulabi & Gilles Pesant & Louis-Martin Rousseau, 2020. "Vehicle Routing Problems with Synchronized Visits and Stochastic Travel and Service Times: Applications in Healthcare," Transportation Science, INFORMS, vol. 54(4), pages 1053-1072, July.
    20. Fu, Liping, 2002. "Scheduling dial-a-ride paratransit under time-varying, stochastic congestion," Transportation Research Part B: Methodological, Elsevier, vol. 36(6), pages 485-506, July.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:57:y:2010:i:5:p:391-402. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.