Offline–Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests
Top Cited Papers
- 1 February 2019
- journal article
- research article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 53 (1) , 185-202
Abstract
Although increasing amounts of transaction data make it possible to characterize uncertainties surrounding customer service requests, few methods integrate predictive tools with prescriptive optimization procedures to meet growing demand for small-volume urban transport services. We incorporate temporal and spatial anticipation of service requests into approximate dynamic programming (ADP) procedures to yield dynamic routing policies for the single-vehicle routing problem with stochastic service requests, an important problem in city-based logistics. We contribute to the routing literature as well as to the field of ADP. We combine offline value function approximation (VFA) with online rollout algorithms resulting in a high-quality, computationally tractable policy. Our offline–online policy enhances the anticipation of the VFA policy, yielding spatial and temporal anticipation of requests and routing developments. Our combination of VFA with rollout algorithms demonstrates the potential benefit of using offline and online methods in tandem as a hybrid ADP procedure, making possible higher-quality policies with reduced computational requirements for real-time decision making. Finally, we identify a policy improvement guarantee applicable to VFA-based rollout algorithms, showing that base policies composed of deterministic decision rules lead to rollout policies with performance at least as strong as that of their base policy.Keywords
This publication has 33 references indexed in Scilit:
- A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goodsEuropean Journal of Operational Research, 2013
- A Comparison of Anticipatory Algorithms for the Dynamic and Stochastic Traveling Salesman ProblemTransportation Science, 2012
- Adaptive granular local search heuristic for a dynamic vehicle routing problemComputers & Operations Research, 2009
- The real-time time-dependent vehicle routing problemTransportation Research Part E: Logistics and Transportation Review, 2006
- Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveriesTransportation Research Part C: Emerging Technologies, 2006
- Waiting Strategies for Dynamic Vehicle RoutingTransportation Science, 2005
- Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic CustomersOperations Research, 2004
- Parallel Tabu Search for Real-Time Vehicle Routing and DispatchingTransportation Science, 1999
- Rollout Algorithms for Combinatorial OptimizationJournal of Heuristics, 1997
- A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean PlaneOperations Research, 1991