Offline-Online Approximate Dynamic Programming for Dynamic Vehicle Routing with Stochastic Requests

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 broader field of ADP. We identify the geographic spread of customer locations as a key predictor of the success of temporal versus spatial anticipation. We combine value function approximation (VFA) with rollout algorithms as a means of enhancing the anticipation of the VFA policy, resulting in spatial-temporal rollout policies. Our combination of VFAs and 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 the base policy.