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

A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity

Author

Listed:
  • Majid Taghavi
  • Kai Huang

Abstract

In networks, there are often more than one sources of capacity. The capacities can be permanently or temporarily owned by the decision maker. Depending on the nature of sources, we identify the permanent capacity, spot market capacity, and contract capacity. We use a scenario tree to model the uncertainty, and build a multi‐stage stochastic integer program that can incorporate multiple sources and multiple types of capacities in a general network. We propose two solution methodologies for the problem. Firstly, we design an asymptotically convergent approximation algorithm. Secondly, we design a cutting plane algorithm based on Benders decomposition to find tight bounds for the problem. The numerical experiments show superb performance of the proposed algorithms compared with commercial software. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 600–614, 2017

Suggested Citation

  • Majid Taghavi & Kai Huang, 2016. "A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 600-614, December.
    • Handle: RePEc:wly:navres:v:63:y:2016:i:8:p:600-614
    DOI: 10.1002/nav.21726
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.21726
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.21726?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. D. R. Fulkerson, 1959. "Increasing the Capacity of a Network: The Parametric Budget Problem," Management Science, INFORMS, vol. 5(4), pages 472-483, July.
    2. Nikolaos E. Pratikakis & Matthew J. Realff & Jay H. Lee, 2010. "Strategic capacity decision‐making in a stochastic manufacturing environment using real‐time approximate dynamic programming," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(3), pages 211-224, April.
    3. Marí­n, íngel & Jaramillo, Patricia, 2008. "Urban rapid transit network capacity expansion," European Journal of Operational Research, Elsevier, vol. 191(1), pages 45-60, November.
    4. Ahuja, R. K. & Batra, J. L. & Gupta, S. K. & Punnen, A. P., 1996. "Optimal expansion of capacitated transshipment networks," European Journal of Operational Research, Elsevier, vol. 89(1), pages 176-184, February.
    5. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    6. Hong Zhang & Qingcheng Zeng, 2015. "A study of the relationships between the time charter and spot freight rates," Applied Economics, Taylor & Francis Journals, vol. 47(9), pages 955-965, February.
    7. Inderfurth, Karl & Kelle, Peter & Kleber, Rainer, 2013. "Dual sourcing using capacity reservation and spot market: Optimal procurement policy and heuristic parameter determination," European Journal of Operational Research, Elsevier, vol. 225(2), pages 298-309.
    8. P. J. Doulliez & M. R. Rao, 1975. "Optimal Network Capacity Planning: A Shortest-Path Scheme," Operations Research, INFORMS, vol. 23(4), pages 810-818, August.
    9. Pimentel, Bruno S. & Mateus, Geraldo R. & Almeida, Franklin A., 2013. "Stochastic capacity planning and dynamic network design," International Journal of Production Economics, Elsevier, vol. 145(1), pages 139-149.
    10. Alper Atamtürk & Dorit S. Hochbaum, 2001. "Capacity Acquisition, Subcontracting, and Lot Sizing," Management Science, INFORMS, vol. 47(8), pages 1081-1100, August.
    11. James C. Bean & Julia L. Higle & Robert L. Smith, 1992. "Capacity Expansion Under Stochastic Demands," Operations Research, INFORMS, vol. 40(3-supplem), pages 210-216, June.
    12. Ampol Karoonsoontawong & Steven Waller, 2010. "Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation," Networks and Spatial Economics, Springer, vol. 10(4), pages 525-550, December.
    13. Doulliez, Pj. & Rao, M.R., 1971. "Capacity of a network with increasing demands and arcs subject to failure," LIDAM Reprints CORE 97, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    14. Luss, Hanan, 1984. "Capacity expansion planning for a single facility product line," European Journal of Operational Research, Elsevier, vol. 18(1), pages 27-34, October.
    15. Tezuka, Koichiro & Ishii, Masahiro & Ishizaka, Motokazu, 2012. "An equilibrium price model of spot and forward shipping freight markets," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(4), pages 730-742.
    16. Daniel Bienstock & Oktay Günlük, 1996. "Capacitated Network Design---Polyhedral Structure and Computation," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 243-259, August.
    17. Shabbir Ahmed & Nikolaos V. Sahinidis, 2003. "An Approximation Scheme for Stochastic Integer Programs Arising in Capacity Expansion," Operations Research, INFORMS, vol. 51(3), pages 461-471, June.
    18. Jan A. Van Mieghem, 2003. "Commissioned Paper: Capacity Management, Investment, and Hedging: Review and Recent Developments," Manufacturing & Service Operations Management, INFORMS, vol. 5(4), pages 269-302, July.
    19. BIENSTOCK, Daniel & CHOPRA, Sunil & GÜNLÜK, Oktay & TSAI, Chih-Yang, 1998. "Minimum cost capacity installation for multicommodity network flows," LIDAM Reprints CORE 1391, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    20. Kai Huang & Shabbir Ahmed, 2009. "The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty," Operations Research, INFORMS, vol. 57(4), pages 893-904, August.
    21. P. J. Doulliez & M. R. Rao, 1971. "Capacity of a Network with Increasing Demands and Arcs Subject to Failure," Operations Research, INFORMS, vol. 19(4), pages 905-915, August.
    22. John R. Birge, 2000. "Option Methods for Incorporating Risk into Linear Capacity Planning Models," Manufacturing & Service Operations Management, INFORMS, vol. 2(1), pages 19-31, August.
    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. Majid Taghavi & Kai Huang, 2020. "A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints," Annals of Operations Research, Springer, vol. 284(2), pages 605-621, January.
    2. Sixiang Zhao, 2023. "Decision rule-based method in solving adjustable robust capacity expansion problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 97(2), pages 259-286, April.

    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. Majid Taghavi & Kai Huang, 2020. "A Lagrangian relaxation approach for stochastic network capacity expansion with budget constraints," Annals of Operations Research, Springer, vol. 284(2), pages 605-621, January.
    2. Torres-Rincón, Samuel & Sánchez-Silva, Mauricio & Bastidas-Arteaga, Emilio, 2021. "A multistage stochastic program for the design and management of flexible infrastructure networks," Reliability Engineering and System Safety, Elsevier, vol. 210(C).
    3. Martínez-Costa, Carme & Mas-Machuca, Marta & Benedito, Ernest & Corominas, Albert, 2014. "A review of mathematical programming models for strategic capacity planning in manufacturing," International Journal of Production Economics, Elsevier, vol. 153(C), pages 66-85.
    4. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    5. Qin, Ruwen & Nembhard, David A., 2012. "Demand modeling of stochastic product diffusion over the life cycle," International Journal of Production Economics, Elsevier, vol. 137(2), pages 201-210.
    6. Hongmin Li & Stephen C. Graves & Woonghee Tim Huh, 2014. "Optimal Capacity Conversion for Product Transitions Under High Service Requirements," Manufacturing & Service Operations Management, INFORMS, vol. 16(1), pages 46-60, February.
    7. Fragkos, Ioannis & Cordeau, Jean-François & Jans, Raf, 2021. "Decomposition methods for large-scale network expansion problems," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 60-80.
    8. Jan A. Van Mieghem, 2003. "Commissioned Paper: Capacity Management, Investment, and Hedging: Review and Recent Developments," Manufacturing & Service Operations Management, INFORMS, vol. 5(4), pages 269-302, July.
    9. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.
    10. Jikai Zou & Shabbir Ahmed & Xu Andy Sun, 2018. "Partially Adaptive Stochastic Optimization for Electric Power Generation Expansion Planning," INFORMS Journal on Computing, INFORMS, vol. 30(2), pages 388-401, May.
    11. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    12. Driouchi, Tarik & Bennett, David & Simpson, Gary, 2010. "A path-dependent contingent-claims approach to capacity investments," European Journal of Operational Research, Elsevier, vol. 201(1), pages 319-323, February.
    13. Alain Bensoussan & Benoit Chevalier-Roignant & Alejandro Rivera, 2022. "A model for wind farm management with option interactions," Post-Print hal-04325553, HAL.
    14. Yogesh Kumar Agarwal & Prahalad Venkateshan, 2019. "New Valid Inequalities for the Optimal Communication Spanning Tree Problem," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 268-284, April.
    15. Smirnov, Dina & van Jaarsveld, Willem & Atan, Zümbül & de Kok, Ton, 2021. "Long-term resource planning in the high-tech industry: Capacity or inventory?," European Journal of Operational Research, Elsevier, vol. 293(3), pages 926-940.
    16. John R. Birge, 2015. "OM Forum—Operations and Finance Interactions," Manufacturing & Service Operations Management, INFORMS, vol. 17(1), pages 4-15, February.
    17. Yongpei Guan, 2011. "Stochastic lot-sizing with backlogging: computational complexity analysis," Journal of Global Optimization, Springer, vol. 49(4), pages 651-678, April.
    18. Sergio Chayet & Wallace J. Hopp, 2008. "Risk‐sensitive sizing of responsive facilities," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(3), pages 218-233, April.
    19. Ni, Jian & Chu, Lap-Keung & Yen, Benjamin P.C., 2016. "Coordinating operational policy with financial hedging for risk-averse firms," Omega, Elsevier, vol. 59(PB), pages 279-289.
    20. Kai Huang & Shabbir Ahmed, 2009. "The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty," Operations Research, INFORMS, vol. 57(4), pages 893-904, August.

    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:63:y:2016:i:8:p:600-614. 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.