Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

10-2020

Abstract

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.

Keywords

Vehicle routing, Automatic vehicle, Reinforcement learning

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering | Transportation

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of the 30th International Conference on Automated Planning and Scheduling, Nancy, France, October 26-30

First Page

394

Last Page

402

Publisher

AAAI Press

City or Country

Menlo Park, CA

Copyright Owner and License

Publisher

Download

Share

COinS