IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v174y2023ics1366554523001060.html
   My bibliography  Save this article

Stochastic service network design: The value of fixed routes

Author

Listed:
  • Liu, Chuanju
  • Lin, Shaochong
  • Shen, Zuo-Jun Max
  • Zhang, Junlong

Abstract

This study introduces a challenging service network design problem with stochastic demands and fixed routes. In this problem, the routes of some service vehicles are fixed during the whole planning horizon, while the remaining vehicles are flexible in that their routes can adapt to different realizations of customer demands each day. The problem is to determine which vehicles should be set as fixed and how their fixed routes should be designed. To solve this problem, we formulate a two-stage stochastic mixed-integer linear program. The fixed routes are designed in the first stage before customer demands are realized, and the routes for flexible vehicles are designed in the second stage after customer demands are observed. A learning-based multiple scenario approach is developed as the solution method. Numerical experiments on real-world operational data from a logistics company show that fixing the routes of some service vehicles may reduce the operational cost by an average of approximately 6.37% compared with that in the case of no fixed routes.

Suggested Citation

  • 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).
    • Handle: RePEc:eee:transe:v:174:y:2023:i:c:s1366554523001060
    DOI: 10.1016/j.tre.2023.103118
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554523001060
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2023.103118?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. Yao, Yu & Van Woensel, Tom & Veelenturf, Lucas P. & Mo, Pengli, 2021. "The consistent vehicle routing problem considering path consistency in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 21-44.
    2. 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.
    3. Wang, Zujian & Qi, Mingyao & Cheng, Chun & Zhang, Canrong, 2019. "A hybrid algorithm for large-scale service network design considering a heterogeneous fleet," European Journal of Operational Research, Elsevier, vol. 276(2), pages 483-494.
    4. 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.
    5. Stacy A. Voccia & Ann Melissa Campbell & Barrett W. Thomas, 2019. "The Same-Day Delivery Problem for Online Purchases," Service Science, INFORMS, vol. 53(1), pages 167-184, February.
    6. Hewitt, Mike & Crainic, Teodor Gabriel & Nowak, Maciek & Rei, Walter, 2019. "Scheduled service network design with resource acquisition and management under uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 324-343.
    7. Natashia Boland & Mike Hewitt & Luke Marshall & Martin Savelsbergh, 2017. "The Continuous-Time Service Network Design Problem," Operations Research, INFORMS, vol. 65(5), pages 1303-1321, October.
    8. Teypaz, Nicolas & Schrenk, Susann & Cung, Van-Dat, 2010. "A decomposition scheme for large-scale Service Network Design with asset management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(1), pages 156-170, January.
    9. Yan Deng & Huiwen Jia & Shabbir Ahmed & Jon Lee & Siqian Shen, 2021. "Scenario Grouping and Decomposition Algorithms for Chance-Constrained Programs," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 757-773, May.
    10. 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.
    11. Michael Berliner Pedersen & Teodor Gabriel Crainic & Oli B. G. Madsen, 2009. "Models and Tabu Search Metaheuristics for Service Network Design with Asset-Balance Requirements," Transportation Science, INFORMS, vol. 43(2), pages 158-177, May.
    12. Jardar Andersen & Marielle Christiansen & Teodor Gabriel Crainic & Roar Grønhaug, 2011. "Branch and Price for Service Network Design with Asset Management Constraints," Transportation Science, INFORMS, vol. 45(1), pages 33-49, February.
    13. Ali Diabat & Claudia Archetti & Waleed Najy, 2021. "The Fixed-Partition Policy Inventory Routing Problem," Transportation Science, INFORMS, vol. 55(2), pages 353-370, March.
    14. 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.
    15. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    16. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    17. Chris Groër & Bruce Golden & Edward Wasil, 2009. "The Consistent Vehicle Routing Problem," Manufacturing & Service Operations Management, INFORMS, vol. 11(4), pages 630-643, February.
    18. 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.
    19. Teodor Gabriel Crainic & Mike Hewitt & Francesca Maggioni & Walter Rei, 2021. "Partial Benders Decomposition: General Methodology and Application to Stochastic Network Design," Transportation Science, INFORMS, vol. 55(2), pages 414-435, March.
    20. Teodor Gabriel Crainic & Mike Hewitt & Michel Toulouse & Duc Minh Vu, 2016. "Service Network Design with Resource Constraints," Transportation Science, INFORMS, vol. 50(4), pages 1380-1393, November.
    21. Karen Smilowitz & Maciek Nowak & Tingting Jiang, 2013. "Workforce Management in Periodic Delivery Operations," Transportation Science, INFORMS, vol. 47(2), pages 214-230, May.
    22. Schneider, M. & Stenger, A. & Schwahn, F. & Vigo, D., 2015. "Territory-Based Vehicle Routing in the Presence of Time Window Constraints," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62869, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    23. 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.
    24. Michael Schneider & Andreas Stenger & Fabian Schwahn & Daniele Vigo, 2015. "Territory-Based Vehicle Routing in the Presence of Time-Window Constraints," Transportation Science, INFORMS, vol. 49(4), pages 732-751, November.
    25. Lars M. Hvattum & Arne Løkketangen & Gilbert Laporte, 2006. "Solving a Dynamic and Stochastic Vehicle Routing Problem with a Sample Scenario Hedging Heuristic," Transportation Science, INFORMS, vol. 40(4), pages 421-438, November.
    26. Gianpaolo Ghiani & Emanuele Manni & Barrett W. Thomas, 2012. "A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman Problem," Transportation Science, INFORMS, vol. 46(3), pages 374-387, August.
    27. 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.
    28. Schneider, M., 2016. "The vehicle-routing problem with time windows and driver-specific times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65941, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    29. Müller, J. P. & Elbert, R. & Emde, Simon, 2021. "Intermodal service network design with stochastic demand and short-term schedule modifications," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 128307, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    30. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    31. F. Jordan Srour & Niels Agatz & Johan Oppen, 2018. "Strategies for Handling Temporal Uncertainty in Pickup and Delivery Problems with Time Windows," Transportation Science, INFORMS, vol. 52(1), pages 3-19, January.
    32. Huang, Nan & Li, Jiliu & Zhu, Wenbin & Qin, Hu, 2021. "The multi-trip vehicle routing problem with time windows and unloading queue at depot," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    33. 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.
    34. Demir, Emrah & Burgholzer, Wolfgang & Hrušovský, Martin & Arıkan, Emel & Jammernegg, Werner & Woensel, Tom Van, 2016. "A green intermodal service network design problem with travel time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 93(PB), pages 789-807.
    35. Müller, J. P. & Elbert, R. & Emde, Simon, 2021. "Integrating vehicle routing into intermodal service network design with stochastic transit times," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 127975, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    36. 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.
    37. 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.
    38. 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. Belieres, Simon & Hewitt, Mike, 2024. "Hedging against uncertainty in transportation network design through flexible scheduling," Omega, Elsevier, vol. 126(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. Liu, Chuanju & Zhang, Junlong & Lin, Shaochong & Shen, Zuo-Jun Max, 2023. "Service network design with consistent multiple trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    2. Belieres, Simon & Hewitt, Mike, 2024. "Hedging against uncertainty in transportation network design through flexible scheduling," Omega, Elsevier, vol. 126(C).
    3. Xudong Diao & Ai Gao & Xin Jin & Hui Chen, 2022. "A Layer-Based Relaxation Approach for Service Network Design," Sustainability, MDPI, vol. 14(20), pages 1-13, October.
    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. Zhang, X. & Liu, X., 2022. "A two-stage robust model for express service network design with surging demand," European Journal of Operational Research, Elsevier, vol. 299(1), pages 154-167.
    6. Naoto Katayama, 2020. "MIP neighborhood search heuristics for a service network design problem with design-balanced requirements," Journal of Heuristics, Springer, vol. 26(4), pages 475-502, August.
    7. Greening, Lacy M. & Dahan, Mathieu & Erera, Alan L., 2023. "Lead-Time-Constrained Middle-Mile Consolidation Network Design with Fixed Origins and Destinations," Transportation Research Part B: Methodological, Elsevier, vol. 174(C).
    8. Li, Xiangyong & Wei, Kai & Guo, Zhaoxia & Wang, Wei & Aneja, Y.P., 2021. "An exact approach for the service network design problem with heterogeneous resource constraints," Omega, Elsevier, vol. 102(C).
    9. Hewitt, Mike & Lehuédé, Fabien, 2023. "New formulations for the Scheduled Service Network Design Problem," Transportation Research Part B: Methodological, Elsevier, vol. 172(C), pages 117-133.
    10. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    11. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T. & Raoufi, R., 2014. "Multimodal freight transportation planning: A literature review," European Journal of Operational Research, Elsevier, vol. 233(1), pages 1-15.
    12. Pérez Rivera, Arturo E. & Mes, Martijn R.K., 2017. "Anticipatory freight selection in intermodal long-haul round-trips," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 176-194.
    13. Tawfik, Christine & Gendron, Bernard & Limbourg, Sabine, 2022. "An iterative two-stage heuristic algorithm for a bilevel service network design and pricing model," European Journal of Operational Research, Elsevier, vol. 300(2), pages 512-526.
    14. Wang, Zujian & Qi, Mingyao & Cheng, Chun & Zhang, Canrong, 2019. "A hybrid algorithm for large-scale service network design considering a heterogeneous fleet," European Journal of Operational Research, Elsevier, vol. 276(2), pages 483-494.
    15. Yao, Yu & Van Woensel, Tom & Veelenturf, Lucas P. & Mo, Pengli, 2021. "The consistent vehicle routing problem considering path consistency in a road network," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 21-44.
    16. 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.
    17. SteadieSeifi, M. & Dellaert, N.P. & Nuijten, W. & Van Woensel, T., 2017. "A metaheuristic for the multimodal network flow problem with product quality preservation and empty repositioning," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 321-344.
    18. 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.
    19. Bender, Matthias & Kalcsics, Jörg & Meyer, Anne, 2020. "Districting for parcel delivery services – A two-Stage solution approach and a real-World case study," Omega, Elsevier, vol. 96(C).
    20. Li, Xiangyong & Ding, Yi & Pan, Kai & Jiang, Dapei & Aneja, Y.P., 2020. "Single-path service network design problem with resource constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).

    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:eee:transe:v:174:y:2023:i:c:s1366554523001060. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/description#description .

    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.