IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i13p1572-d588192.html
   My bibliography  Save this article

A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm

Author

Listed:
  • Wadi Khalid Anuar

    (Department of Logistics and Transportation, School of Technology Management and Logistics, Universiti Utara Malaysia, Sintok 06010, Kedah, Malaysia
    Laboratory of Computational Statistics and Operations Research, Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia)

  • Lai Soon Lee

    (Laboratory of Computational Statistics and Operations Research, Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia
    Department of Mathematics and Statistics, Faculty of Science, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia)

  • Hsin-Vonn Seow

    (Faculty of Arts and Social Sciences, Nottingham University Business School, University of Nottingham Malaysia Campus, Jalan Broga, Semenyih 43500, Selangor, Malaysia)

  • Stefan Pickl

    (Fakultät für Informatik, Universität der Bundeswehr München, 85577 Neubiberg, Germany)

Abstract

A matheuristic approach based on a reduced two-stage Stochastic Integer Linear Programming (SILP) model is presented. The proposed approach is suitable for obtaining a policy constructed dynamically on the go during the rollout algorithm. The rollout algorithm is part of the Approximate Dynamic Programming (ADP) lookahead solution approach for a Markov Decision Processes (MDP) framed Multi-Depot Dynamic Vehicle Routing Problem with Stochastic Road Capacity (MDDVRPSRC). First, a Deterministic Multi-Depot VRP with Road Capacity (D-MDVRPRC) is presented. Then an extension, MDVRPSRC-2S, is presented as an offline two-stage SILP model of the MDDVRPSRC. These models are validated using small simulated instances with CPLEX. Next, two reduced versions of the MDVRPSRC-2S model (MDVRPSRC-2S1 and MDVRPSRC-2S2) are derived. They have a specific task in routing: replenishment and delivering supplies. These reduced models are to be utilised interchangeably depending on the capacity of the vehicle, and repeatedly during the execution of rollout in reinforcement learning. As a result, it is shown that a base policy consisting of an exact optimal decision at each decision epoch can be obtained constructively through these reduced two-stage stochastic integer linear programming models. The results obtained from the resulting rollout policy with CPLEX execution during rollout are also presented to validate the reduced model and the matheuristic algorithm. This approach is proposed as a simple implementation when performing rollout for the lookahead approach in ADP.

Suggested Citation

  • Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2021. "A Multi-Depot Vehicle Routing Problem with Stochastic Road Capacity and Reduced Two-Stage Stochastic Integer Linear Programming Models for Rollout Algorithm," Mathematics, MDPI, vol. 9(13), pages 1-44, July.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:13:p:1572-:d:588192
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/13/1572/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/13/1572/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dror, Moshe, 1993. "Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution," European Journal of Operational Research, Elsevier, vol. 64(3), pages 432-441, February.
    2. 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.
    3. Justin C. Goodson & Jeffrey W. Ohlmann & Barrett W. Thomas, 2013. "Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits," Operations Research, INFORMS, vol. 61(1), pages 138-154, February.
    4. Richard Bellman, 1954. "Some Applications of the Theory of Dynamic Programming---A Review," Operations Research, INFORMS, vol. 2(3), pages 275-288, August.
    5. Davood Shiri & Vahid Akbari & F. Sibel Salman, 2020. "Online routing and scheduling of search-and-rescue teams," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 755-784, September.
    6. Zhen, Lu & Ma, Chengle & Wang, Kai & Xiao, Liyang & Zhang, Wei, 2020. "Multi-depot multi-trip vehicle routing problem with time windows and release dates," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 135(C).
    7. Shiripour, Saber & Mahdavi-Amiri, Nezam, 2019. "Optimal distribution of the injured in a multi-type transportation network with damage-dependent travel times: Two metaheuristic approaches," Socio-Economic Planning Sciences, Elsevier, vol. 68(C).
    8. Sha-lei Zhan & Liang Chen & Ping-Kuo Chen & Yong Ye, 2019. "A Vehicle Route Planning Method of Two-Phase Large-Scale Crowd Evacuation in Typhoon Relief Activities," Mathematical Problems in Engineering, Hindawi, vol. 2019, pages 1-9, August.
    9. Ferrer, José M. & Martín-Campo, F. Javier & Ortuño, M. Teresa & Pedraza-Martínez, Alfonso J. & Tirado, Gregorio & Vitoriano, Begoña, 2018. "Multi-criteria optimization for last mile distribution of disaster relief aid: Test cases and applications," European Journal of Operational Research, Elsevier, vol. 269(2), pages 501-515.
    10. Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.
    11. Richard Bellman, 1954. "On some applications of the theory of dynamic programming to logistics," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(2), pages 141-153, June.
    12. 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.
    13. B. Zhao, 2016. "April 2015 Nepal earthquake: observations and reflections," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 80(2), pages 1405-1410, January.
    14. Nicola Secomandi, 2001. "A Rollout Policy for the Vehicle Routing Problem with Stochastic Demands," Operations Research, INFORMS, vol. 49(5), pages 796-802, October.
    15. Yi, Wei & Ozdamar, Linet, 2007. "A dynamic logistics coordination model for evacuation and support in disaster response activities," European Journal of Operational Research, Elsevier, vol. 179(3), pages 1177-1193, June.
    16. 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.
    17. Claudia Archetti & Martin W. P. Savelsbergh & M. Grazia Speranza, 2006. "Worst-Case Analysis for Split Delivery Vehicle Routing Problems," Transportation Science, INFORMS, vol. 40(2), pages 226-234, May.
    18. Keyju Lee & Junjae Chae & Bomi Song & Donghyun Choi, 2020. "A Model for Sustainable Courier Services: Vehicle Routing with Exclusive Lanes," Sustainability, MDPI, vol. 12(3), pages 1-19, February.
    19. Haghani, Ali & Oh, Sei-Chang, 1996. "Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(3), pages 231-250, May.
    20. Marlin W. Ulmer & Justin C. Goodson & Dirk C. Mattfeld & Marco Hennig, 2019. "Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests," Service Science, INFORMS, vol. 53(1), pages 185-202, February.
    21. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    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. Maliheh Khorsi & Seyed Kamal Chaharsooghi & Ali Husseinzadeh Kashan & Ali Bozorgi-Amiri, 2022. "Solving the humanitarian multi-trip cumulative capacitated routing problem via a grouping metaheuristic algorithm," Annals of Operations Research, Springer, vol. 319(1), pages 173-210, December.

    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. Wadi Khalid Anuar & Lai Soon Lee & Hsin-Vonn Seow & Stefan Pickl, 2022. "A Multi-Depot Dynamic Vehicle Routing Problem with Stochastic Road Capacity: An MDP Model and Dynamic Policy for Post-Decision State Rollout Algorithm in Reinforcement Learning," Mathematics, MDPI, vol. 10(15), pages 1-70, July.
    2. Florio, Alexandre M. & Hartl, Richard F. & Minner, Stefan, 2020. "Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands," European Journal of Operational Research, Elsevier, vol. 285(1), pages 172-182.
    3. 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.
    4. 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.
    5. Soeffker, Ninja & Ulmer, Marlin W. & Mattfeld, Dirk C., 2022. "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review," European Journal of Operational Research, Elsevier, vol. 298(3), pages 801-820.
    6. Shu Zhang & Jeffrey W. Ohlmann & Barrett W. Thomas, 2018. "Dynamic Orienteering on a Network of Queues," Transportation Science, INFORMS, vol. 52(3), pages 691-706, June.
    7. Zhang, Jian & Woensel, Tom Van, 2023. "Dynamic vehicle routing with random requests: A literature review," International Journal of Production Economics, Elsevier, vol. 256(C).
    8. Basso, Rafael & Kulcsár, Balázs & Sanchez-Diaz, Ivan & Qu, Xiaobo, 2022. "Dynamic stochastic electric vehicle routing with safe reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    9. Sayarshad, Hamid R. & Gao, H. Oliver, 2018. "A non-myopic dynamic inventory routing and pricing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 109(C), pages 83-98.
    10. Sayarshad, Hamid R. & Chow, Joseph Y.J., 2015. "A scalable non-myopic dynamic dial-a-ride and pricing problem," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 539-554.
    11. F. Hooshmand Khaligh & S.A. MirHassani, 2016. "A mathematical model for vehicle routing problem under endogenous uncertainty," International Journal of Production Research, Taylor & Francis Journals, vol. 54(2), pages 579-590, January.
    12. Zhang, Junlong & Lam, William H.K. & Chen, Bi Yu, 2016. "On-time delivery probabilistic models for the vehicle routing problem with stochastic demands and time windows," European Journal of Operational Research, Elsevier, vol. 249(1), pages 144-154.
    13. 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.
    14. 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.
    15. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    16. Bosse, Alexander & Ulmer, Marlin W. & Manni, Emanuele & Mattfeld, Dirk C., 2023. "Dynamic priority rules for combining on-demand passenger transportation and transportation of goods," European Journal of Operational Research, Elsevier, vol. 309(1), pages 399-408.
    17. Huang, Michael & Smilowitz, Karen & Balcik, Burcu, 2012. "Models for relief routing: Equity, efficiency and efficacy," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 2-18.
    18. A. Mor & M. G. Speranza, 2022. "Vehicle routing problems over time: a survey," Annals of Operations Research, Springer, vol. 314(1), pages 255-275, July.
    19. Goodson, Justin C. & Thomas, Barrett W. & Ohlmann, Jeffrey W., 2017. "A rollout algorithm framework for heuristic solutions to finite-horizon stochastic dynamic programs," European Journal of Operational Research, Elsevier, vol. 258(1), pages 216-229.
    20. Alexandre M. Florio & Richard F. Hartl & Stefan Minner & Juan-José Salazar-González, 2021. "A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints," Transportation Science, INFORMS, vol. 55(1), pages 122-138, 1-2.

    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:gam:jmathe:v:9:y:2021:i:13:p:1572-:d:588192. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.