Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers
In real-world urban logistics operations, changes to the routes and tasks occur in response to dynamic events. To ensure customers’ demands are met, planners need to make these changes quickly (sometimes instantaneously). This paper proposes the formulation of a dynamic vehicle routing problem with...
Saved in:
Main Authors: | , |
---|---|
Format: | text |
Language: | English |
Published: |
Institutional Knowledge at Singapore Management University
2020
|
Subjects: | |
Online Access: | https://ink.library.smu.edu.sg/sis_research/5568 https://ink.library.smu.edu.sg/context/sis_research/article/6571/viewcontent/Deep_Reinforcement_Learning_Approach_to_Solve.pdf |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Singapore Management University |
Language: | English |
id |
sg-smu-ink.sis_research-6571 |
---|---|
record_format |
dspace |
spelling |
sg-smu-ink.sis_research-65712021-05-18T04:18:20Z Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers JOE, Waldy LAU, Hoong Chuin In real-world urban logistics operations, changes to the routes and tasks occur in response to dynamic events. To ensure customers’ demands are met, planners need to make these changes quickly (sometimes instantaneously). This paper proposes the formulation of a dynamic vehicle routing problem with time windows and both known and stochastic customers as a route-based Markov Decision Process. We propose a solution approach that combines Deep Reinforcement Learning (specifically neural networks-based TemporalDifference learning with experience replay) to approximate the value function and a routing heuristic based on Simulated Annealing, called DRLSA. Our approach enables optimized re-routing decision to be generated almost instantaneously. Furthermore, to exploit the structure of this problem, we propose a state representation based on the total cost of the remaining routes of the vehicles. We show that the cost of the remaining routes of vehicles can serve as proxy to the sequence of the routes and time window requirements. DRLSA is evaluated against the commonly used Approximate Value Iteration (AVI) and Multiple Scenario Approach (MSA). Our experiment results show that DRLSA can achieve on average, 10% improvement over myopic, outperforming AVI and MSA even with small training episodes on problems with degree of dynamism above 0.5. 2020-10-01T07:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/5568 https://ink.library.smu.edu.sg/context/sis_research/article/6571/viewcontent/Deep_Reinforcement_Learning_Approach_to_Solve.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Vehicle routing Automatic vehicle Reinforcement learning Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Transportation |
institution |
Singapore Management University |
building |
SMU Libraries |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
SMU Libraries |
collection |
InK@SMU |
language |
English |
topic |
Vehicle routing Automatic vehicle Reinforcement learning Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Transportation |
spellingShingle |
Vehicle routing Automatic vehicle Reinforcement learning Numerical Analysis and Scientific Computing Operations Research, Systems Engineering and Industrial Engineering Transportation JOE, Waldy LAU, Hoong Chuin Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
description |
In real-world urban logistics operations, changes to the routes and tasks occur in response to dynamic events. To ensure customers’ demands are met, planners need to make these changes quickly (sometimes instantaneously). This paper proposes the formulation of a dynamic vehicle routing problem with time windows and both known and stochastic customers as a route-based Markov Decision Process. We propose a solution approach that combines Deep Reinforcement Learning (specifically neural networks-based TemporalDifference learning with experience replay) to approximate the value function and a routing heuristic based on Simulated Annealing, called DRLSA. Our approach enables optimized re-routing decision to be generated almost instantaneously. Furthermore, to exploit the structure of this problem, we propose a state representation based on the total cost of the remaining routes of the vehicles. We show that the cost of the remaining routes of vehicles can serve as proxy to the sequence of the routes and time window requirements. DRLSA is evaluated against the commonly used Approximate Value Iteration (AVI) and Multiple Scenario Approach (MSA). Our experiment results show that DRLSA can achieve on average, 10% improvement over myopic, outperforming AVI and MSA even with small training episodes on problems with degree of dynamism above 0.5. |
format |
text |
author |
JOE, Waldy LAU, Hoong Chuin |
author_facet |
JOE, Waldy LAU, Hoong Chuin |
author_sort |
JOE, Waldy |
title |
Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
title_short |
Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
title_full |
Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
title_fullStr |
Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
title_full_unstemmed |
Deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
title_sort |
deep reinforcement learning approach to solve dynamic vehicle routing problem with stochastic customers |
publisher |
Institutional Knowledge at Singapore Management University |
publishDate |
2020 |
url |
https://ink.library.smu.edu.sg/sis_research/5568 https://ink.library.smu.edu.sg/context/sis_research/article/6571/viewcontent/Deep_Reinforcement_Learning_Approach_to_Solve.pdf |
_version_ |
1770575512039587840 |