IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v162y2022icp209-228.html
   My bibliography  Save this article

A stochastic optimization approach for the supply vessel planning problem under uncertain demand

Author

Listed:
  • Santos, A.M.P.
  • Fagerholt, Kjetil
  • Laporte, Gilbert
  • Guedes Soares, C.

Abstract

This paper presents a two-stage stochastic programming with recourse methodology to solve the Supply Vessel Planning Problem with Stochastic Demands (SVPPSD), a problem arising in offshore logistics and which generalizes the Periodic Vehicle Routing Problem with Stochastic Demands and Time Windows. In the SVPPSD, a fleet of vessels is used to deliver a regular supply of commodities to a set of offshore installations to ensure continuous production, with each installation requiring one or more visits per week and having stochastic demands. Both the onshore depot where the product to be distributed is kept and the offshore installations have time windows, and voyages are allowed to span more than one day. A solution to the SVPPSD consists in the identification of an optimal fleet of vessels and the corresponding weekly schedule. As a solution methodology, we embed a discrete-event simulation engine within a genetic search procedure to approximate the cost of recourse and arrive at the minimized expected cost solution. We make comparisons with two alternative approaches: an expected value problem with upscaled demand, and a chance-constrained algorithm. While alternative methodologies yield robust schedules, robustness is achieved mainly through an increase in fleet size. In contrast, a two-stage stochastic programming with recourse algorithm, by accounting for the cost of recourse in the search phase, and exploring a wider solution space, allows arriving at robust schedules with a smaller fleet size, thereby yielding significant cost savings. For the tested problem instances, the proposed algorithm leads to savings of approximately 10 to 15 million USD per year.

Suggested Citation

  • Santos, A.M.P. & Fagerholt, Kjetil & Laporte, Gilbert & Guedes Soares, C., 2022. "A stochastic optimization approach for the supply vessel planning problem under uncertain demand," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 209-228.
    • Handle: RePEc:eee:transb:v:162:y:2022:i:c:p:209-228
    DOI: 10.1016/j.trb.2022.05.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261522000923
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2022.05.015?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. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    2. Wang, K.-J. & Wang, S.-M. & Chen, J.-C., 2008. "A resource portfolio planning model using sampling-based stochastic programming and genetic algorithm," European Journal of Operational Research, Elsevier, vol. 184(1), pages 327-340, January.
    3. Moshe Dror & Gilbert Laporte & Pierre Trudeau, 1989. "Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks," Transportation Science, INFORMS, vol. 23(3), pages 166-176, August.
    4. Wu, Lingxiao & Pan, Kai & Wang, Shuaian & Yang, Dong, 2018. "Bulk ship scheduling in industrial shipping with stochastic backhaul canvassing demand," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 117-136.
    5. C. Hjorring & J. Holt, 1999. "New optimality cuts for a single‐vehicle stochastic routing problem," Annals of Operations Research, Springer, vol. 86(0), pages 569-584, January.
    6. Halvorsen-Weare, Elin E. & Fagerholt, Kjetil & Nonås, Lars Magne & Asbjørnslett, Bjørn Egil, 2012. "Optimal fleet composition and periodic routing of offshore supply vessels," European Journal of Operational Research, Elsevier, vol. 223(2), pages 508-517.
    7. 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.
    8. Bjørnar Aas & Øyvind Halskau Sr & Stein W Wallace, 2009. "The role of supply vessels in offshore logistics," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 11(3), pages 302-325, September.
    9. Powell, Warren B., 2019. "A unified framework for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 275(3), pages 795-821.
    10. Wu, Lingxiao & Wang, Shuaian & Laporte, Gilbert, 2021. "The Robust Bulk Ship Routing Problem with Batched Cargo Selection," Transportation Research Part B: Methodological, Elsevier, vol. 143(C), pages 124-159.
    11. Markov, Iliya & Bierlaire, Michel & Cordeau, Jean-François & Maknoon, Yousef & Varone, Sacha, 2018. "A unified framework for rich routing problems with stochastic demands," Transportation Research Part B: Methodological, Elsevier, vol. 114(C), pages 213-240.
    12. Gilbert Laporte & FranÇois V. Louveaux & Luc van Hamme, 2002. "An Integer L -Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 50(3), pages 415-423, June.
    13. Thomas Borthen & Henrik Loennechen & Xin Wang & Kjetil Fagerholt & Thibaut Vidal, 2018. "A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 121-150, June.
    Full references (including those not matched with items on IDEAS)

    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. Vieira, Bruno S. & Ribeiro, Glaydston M. & Bahiense, Laura & Cruz, Roberto & Mendes, André B. & Laporte, Gilbert, 2021. "Exact and heuristic algorithms for the fleet composition and periodic routing problem of offshore supply vessels with berth allocation decisions," European Journal of Operational Research, Elsevier, vol. 295(3), pages 908-923.
    2. 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.
    3. Salavati-Khoshghalb, Majid & Gendreau, Michel & Jabali, Ola & Rei, Walter, 2019. "An exact algorithm to solve the vehicle routing problem with stochastic demands under an optimal restocking policy," European Journal of Operational Research, Elsevier, vol. 273(1), pages 175-189.
    4. Thomas Borthen & Henrik Loennechen & Xin Wang & Kjetil Fagerholt & Thibaut Vidal, 2018. "A genetic search-based heuristic for a fleet size and periodic routing problem with application to offshore supply planning," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 7(2), pages 121-150, June.
    5. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 53(5), pages 1334-1353, September.
    6. Y. N. Hoogendoorn & R. Spliet, 2023. "An Improved Integer L -Shaped Method for the Vehicle Routing Problem with Stochastic Demands," INFORMS Journal on Computing, INFORMS, vol. 35(2), pages 423-439, March.
    7. Bertazzi, Luca & Secomandi, Nicola, 2018. "Faster rollout search for the vehicle routing problem with stochastic demands and restocking," European Journal of Operational Research, Elsevier, vol. 270(2), pages 487-497.
    8. Walter Rei & Michel Gendreau & Patrick Soriano, 2010. "A Hybrid Monte Carlo Local Branching Algorithm for the Single Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 136-146, February.
    9. Nicola Secomandi & François Margot, 2009. "Reoptimization Approaches for the Vehicle-Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 57(1), pages 214-230, February.
    10. De La Vega, Jonathan & Gendreau, Michel & Morabito, Reinaldo & Munari, Pedro & Ordóñez, Fernando, 2023. "An integer L-shaped algorithm for the vehicle routing problem with time windows and stochastic demands," European Journal of Operational Research, Elsevier, vol. 308(2), pages 676-695.
    11. Kangzhou Wang & Shulin Lan & Yingxue Zhao, 2017. "A genetic-algorithm-based approach to the two-echelon capacitated vehicle routing problem with stochastic demands in logistics service," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(11), pages 1409-1421, November.
    12. Kaiser, Mark J., 2015. "Offshore Service Vessel activity forecast and regulatory modeling in the U.S. Gulf of Mexico, 2012–2017," Marine Policy, Elsevier, vol. 57(C), pages 132-146.
    13. Goodson, Justin C. & Ohlmann, Jeffrey W. & Thomas, Barrett W., 2012. "Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand," European Journal of Operational Research, Elsevier, vol. 217(2), pages 312-323.
    14. 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.
    15. Novoa, Clara & Storer, Robert, 2009. "An approximate dynamic programming approach for the vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 196(2), pages 509-515, July.
    16. 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.
    17. 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.
    18. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A hybrid recourse policy for the vehicle routing problem with stochastic demands," EURO Journal on Transportation and Logistics, Springer;EURO - The Association of European Operational Research Societies, vol. 8(3), pages 269-298, September.
    19. Karels, Vincent C.G. & Rei, Walter & Veelenturf, Lucas P. & Van Woensel, Tom, 2024. "A vehicle routing problem with multiple service agreements," European Journal of Operational Research, Elsevier, vol. 313(1), pages 129-145.
    20. Remy Spliet & Adriana F. Gabor, 2015. "The Time Window Assignment Vehicle Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 721-731, November.

    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:transb:v:162:y:2022:i:c:p:209-228. 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/548/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.