A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm
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 Prog...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Published: |
Multidisciplinary Digital Publishing Institute
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/95781/ |
| _version_ | 1848862220029526016 |
|---|---|
| author | Anuar, Wadi Khalid Lee, Lai Soon Seow, Hsin Vonn Pickl, Stefan |
| author_facet | Anuar, Wadi Khalid Lee, Lai Soon Seow, Hsin Vonn Pickl, Stefan |
| author_sort | Anuar, Wadi Khalid |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T13:13:33Z |
| format | Article |
| id | upm-95781 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T13:13:33Z |
| publishDate | 2021 |
| publisher | Multidisciplinary Digital Publishing Institute |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-957812023-04-05T03:21:43Z http://psasir.upm.edu.my/id/eprint/95781/ A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm Anuar, Wadi Khalid Lee, Lai Soon Seow, Hsin Vonn Pickl, Stefan 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. Multidisciplinary Digital Publishing Institute 2021 Article PeerReviewed Anuar, Wadi Khalid and Lee, Lai Soon and Seow, Hsin Vonn and Pickl, Stefan (2021) A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm. Mathematics, 9 (13). art. no. 1572. pp. 1-44. ISSN 2227-7390 https://www.mdpi.com/2227-7390/9/13/1572 10.3390/math9131572 |
| spellingShingle | Anuar, Wadi Khalid Lee, Lai Soon Seow, Hsin Vonn Pickl, Stefan A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title | A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title_full | A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title_fullStr | A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title_full_unstemmed | A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title_short | A multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| title_sort | multi-depot vehicle routing problem with stochastic road capacity and reduced two-stage stochastic integer linear programming models for rollout algorithm |
| url | http://psasir.upm.edu.my/id/eprint/95781/ http://psasir.upm.edu.my/id/eprint/95781/ http://psasir.upm.edu.my/id/eprint/95781/ |