IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v27y2021i3d10.1007_s10732-020-09460-y.html
   My bibliography  Save this article

A reduced cost-based restriction and refinement matheuristic for stochastic network design problem

Author

Listed:
  • Fatemeh Sarayloo

    (Université de Montréal
    Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise la Logistique et le Transport (CIRRELT))

  • Teodor Gabriel Crainic

    (Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise la Logistique et le Transport (CIRRELT)
    Université du Québec à Montréal)

  • Walter Rei

    (Centre Interuniversitaire de Recherche sur les Réseaux d’Entreprise la Logistique et le Transport (CIRRELT)
    Université du Québec à Montréal)

Abstract

We propose a solution approach for stochastic network design problems with uncertain demands. We investigate how to efficiently use reduced cost information as a means of guiding variable fixing to define a restriction that reduces the complexity of solving the stochastic model without sacrificing the quality of the solution obtained. We then propose a matheuristic approach that iteratively defines and explores restricted regions of the global solution space that have a high potential of containing good solutions. Extensive computational experiments show the effectiveness of the proposed approach in obtaining high-quality solutions, while reducing the computational effort to obtain them.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09460-y
    DOI: 10.1007/s10732-020-09460-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-020-09460-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-020-09460-y?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    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. Julia L. Higle & Stein W. Wallace, 2003. "Sensitivity Analysis and Uncertainty in Linear Programming," Interfaces, INFORMS, vol. 33(4), pages 53-60, August.
    4. 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.
    5. Egon Balas & Eitan Zemel, 1980. "An Algorithm for Large Zero-One Knapsack Problems," Operations Research, INFORMS, vol. 28(5), pages 1130-1154, October.
    6. 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.
    7. 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.
    8. Crainic, Teodor Gabriel, 2000. "Service network design in freight transportation," European Journal of Operational Research, Elsevier, vol. 122(2), pages 272-288, April.
    9. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    10. 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).
    2. Filipe Rodrigues & Agostinho Agra & Lars Magnus Hvattum & Cristina Requejo, 2022. "Weighted iterated local branching for mathematical programming problems with binary variables," Journal of Heuristics, Springer, vol. 28(3), pages 329-350, June.

    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 Learning-Based Matheuristic for Stochastic Multicommodity Network Design," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 643-656, May.
    2. 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.
    3. 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.
    4. 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.
    5. 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).
    6. 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.
    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. 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.
    9. 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.
    10. Ahmad I. Jarrah & Ellis Johnson & Lucas C. Neubert, 2009. "Large-Scale, Less-than-Truckload Service Network Design," Operations Research, INFORMS, vol. 57(3), pages 609-625, June.
    11. 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.
    12. Teodor Gabriel Crainic & Nicoletta Ricciardi & Giovanni Storchi, 2009. "Models for Evaluating and Planning City Logistics Systems," Transportation Science, INFORMS, vol. 43(4), pages 432-454, November.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    17. 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.
    18. 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.
    19. Jiang, Xiaoping & Bai, Ruibin & Ren, Jianfeng & Li, Jiawei & Kendall, Graham, 2022. "Lagrange dual bound computation for stochastic service network design," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1097-1112.
    20. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2017. "Commodity Representations and Cut-Set-Based Inequalities for Multicommodity Capacitated Fixed-Charge Network Design," Transportation Science, INFORMS, vol. 51(2), pages 650-667, 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:spr:joheur:v:27:y:2021:i:3:d:10.1007_s10732-020-09460-y. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.