IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i2p643-656.html
   My bibliography  Save this article

A Learning-Based Matheuristic for Stochastic Multicommodity Network Design

Author

Listed:
  • Fatemeh Sarayloo

    (Department of Computer Science and Operations Research, University of Montreal and the Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Quebec H3T 1J4, Canada)

  • Teodor Gabriel Crainic

    (Department of Analytics, Operations and Information Technologies, School of Management Sciences, University of Quebec at Montreal and CIRRELT, Montreal, Quebec H2X 3X2, Canada)

  • Walter Rei

    (Department of Analytics, Operations and Information Technologies, School of Management Sciences, University of Quebec at Montreal and CIRRELT, Montreal, Quebec H2X 3X2, Canada)

Abstract

This paper proposes a solution approach for the multicommodity capacitated fixed-charge network design problem with uncertain demand modeled as a two-stage stochastic program. The proposed learning-based matheuristic combines heuristic search techniques with mathematical programming. It provides a systematic approach to identifying structures of good-quality solutions by gradually considering scenarios and their influences on design decisions. Extensive computational experiments illustrate the efficiency of the proposed matheuristic in obtaining high-quality solutions with limited computational efforts.

Suggested Citation

  • Fatemeh Sarayloo & Teodor Gabriel Crainic & Walter Rei, 2021. "A Learning-Based Matheuristic for Stochastic Multicommodity Network Design," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 643-656, May.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:2:p:643-656
    DOI: 10.1287/ijoc.2020.0967
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.0967
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.0967?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. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    2. Francesca Maggioni & Stein Wallace, 2012. "Analyzing the quality of the expected value solution in stochastic programming," Annals of Operations Research, Springer, vol. 200(1), pages 37-54, November.
    3. Stein W. Wallace, 2000. "Decision Making Under Uncertainty: Is Sensitivity Analysis of Any Use?," Operations Research, INFORMS, vol. 48(1), pages 20-25, February.
    4. Julia L. Higle & Stein W. Wallace, 2003. "Sensitivity Analysis and Uncertainty in Linear Programming," Interfaces, INFORMS, vol. 33(4), pages 53-60, August.
    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. Haugen, Kjetil K. & Lokketangen, Arne & Woodruff, David L., 2001. "Progressive hedging as a meta-heuristic applied to stochastic lot-sizing," European Journal of Operational Research, Elsevier, vol. 132(1), pages 116-122, July.
    7. Schütz, Peter & Tomasgard, Asgeir & Ahmed, Shabbir, 2009. "Supply chain design under uncertainty using sample average approximation and dual decomposition," European Journal of Operational Research, Elsevier, vol. 199(2), pages 409-419, December.
    8. Azaron, A. & Brown, K.N. & Tarim, S.A. & Modarres, M., 2008. "A multi-objective stochastic programming approach for supply chain design considering risk," International Journal of Production Economics, Elsevier, vol. 116(1), pages 129-138, November.
    9. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.
    10. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    11. Natashia Boland & Matteo Fischetti & Michele Monaci & Martin Savelsbergh, 2016. "Proximity Benders: a decomposition heuristic for stochastic programs," Journal of Heuristics, Springer, vol. 22(2), pages 181-198, April.
    12. Jitka Dupačová & Giorgio Consigli & Stein Wallace, 2000. "Scenarios for Multistage Stochastic Programs," Annals of Operations Research, Springer, vol. 100(1), pages 25-53, December.
    13. Ilfat Ghamlouche & Teodor Gabriel Crainic & Michel Gendreau, 2003. "Cycle-Based Neighbourhoods for Fixed-Charge Capacitated Multicommodity Network Design," Operations Research, INFORMS, vol. 51(4), pages 655-667, 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. Liu, Chuanju & Lin, Shaochong & Shen, Zuo-Jun Max & Zhang, Junlong, 2023. "Stochastic service network design: The value of fixed routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 174(C).

    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. Fatemeh Sarayloo & Teodor Gabriel Crainic & Walter Rei, 2021. "A reduced cost-based restriction and refinement matheuristic for stochastic network design problem," Journal of Heuristics, Springer, vol. 27(3), pages 325-351, June.
    2. Xin Wang & Teodor Gabriel Crainic & Stein W. Wallace, 2019. "Stochastic Network Design for Planning Scheduled Transportation Services: The Value of Deterministic Solutions," INFORMS Journal on Computing, INFORMS, vol. 31(1), pages 153-170, February.
    3. Ahmad Baubaid & Natashia Boland & Martin Savelsbergh, 2021. "The Value of Limited Flexibility in Service Network Designs," Transportation Science, INFORMS, vol. 55(1), pages 52-74, 1-2.
    4. Arnt-Gunnar Lium & Teodor Gabriel Crainic & Stein W. Wallace, 2009. "A Study of Demand Stochasticity in Service Network Design," Transportation Science, INFORMS, vol. 43(2), pages 144-157, May.
    5. Lanza, Giacomo & Crainic, Teodor Gabriel & Rei, Walter & Ricciardi, Nicoletta, 2021. "Scheduled service network design with quality targets and stochastic travel times," European Journal of Operational Research, Elsevier, vol. 288(1), pages 30-46.
    6. Wang, Zujian & Qi, Mingyao, 2019. "Service network design considering multiple types of services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 1-14.
    7. Li, Xiangyong & Wei, Kai & Aneja, Y.P. & Tian, Peng, 2017. "Design-balanced capacitated multicommodity network design with heterogeneous assets," Omega, Elsevier, vol. 67(C), pages 145-159.
    8. Meng, Qiang & Hei, Xiuling & Wang, Shuaian & Mao, Haijun, 2015. "Carrying capacity procurement of rail and shipping services for automobile delivery with uncertain demand," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 82(C), pages 38-54.
    9. Thibault Delbart & Yves Molenbruch & Kris Braekers & An Caris, 2021. "Uncertainty in Intermodal and Synchromodal Transport: Review and Future Research Directions," Sustainability, MDPI, vol. 13(7), pages 1-25, April.
    10. 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.
    11. Tobias Harks & Felix G. König & Jannik Matuschke & Alexander T. Richter & Jens Schulz, 2016. "An Integrated Approach to Tactical Transportation Planning in Logistics Networks," Transportation Science, INFORMS, vol. 50(2), pages 439-460, May.
    12. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar & Mohammad Hassan Sharifitabar, 2015. "A Cutting-Plane Neighborhood Structure for Fixed-Charge Capacitated Multicommodity Network Design Problem," INFORMS Journal on Computing, INFORMS, vol. 27(1), pages 48-58, February.
    13. Endong Zhu & Teodor Gabriel Crainic & Michel Gendreau, 2014. "Scheduled Service Network Design for Freight Rail Transportation," Operations Research, INFORMS, vol. 62(2), pages 383-400, April.
    14. Crainic, Teodor Gabriel & Perboli, Guido & Rei, Walter & Rosano, Mariangela & Lerma, Veronica, 2024. "Capacity planning with uncertainty on contract fulfillment," European Journal of Operational Research, Elsevier, vol. 314(1), pages 152-175.
    15. Xin Wang & Stein W. Wallace, 2016. "Stochastic scheduled service network design in the presence of a spot market for excess capacity," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 5(4), pages 393-413, December.
    16. Bai, Ruibin & Wallace, Stein W. & Li, Jingpeng & Chong, Alain Yee-Loong, 2014. "Stochastic service network design with rerouting," Transportation Research Part B: Methodological, Elsevier, vol. 60(C), pages 50-65.
    17. Teodor Gabriel Crainic & Fausto Errico & Walter Rei & Nicoletta Ricciardi, 2016. "Modeling Demand Uncertainty in Two-Tier City Logistics Tactical Planning," Transportation Science, INFORMS, vol. 50(2), pages 559-578, May.
    18. Hui, Yer Van & Gao, Jia & Leung, Lawrence & Wallace, Stein, 2014. "Airfreight forwarder’s shipment planning under uncertainty: A two-stage stochastic programming approach," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 66(C), pages 83-102.
    19. Poudel, Sushil Raj & Marufuzzaman, Mohammad & Bian, Linkan, 2016. "A hybrid decomposition algorithm for designing a multi-modal transportation network under biomass supply uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 94(C), pages 1-25.
    20. Mervat Chouman & Teodor Gabriel Crainic, 2015. "Cutting-Plane Matheuristic for Service Network Design with Design-Balanced Requirements," Transportation Science, INFORMS, vol. 49(1), pages 99-113, February.

    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:inm:orijoc:v:33:y:2021:i:2:p:643-656. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.