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. The authors 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. The authors contribute to the routing literature as well as to the field of ADP. They combine offline value function approximation (VFA) with online rollout algorithms resulting in a high-quality, computationally tractable policy. The authors' offline–online policy enhances the anticipation of the VFA policy, yielding spatial and temporal anticipation of requests and routing developments. Their 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, the authors 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.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01695266
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Feb 13 2019 10:44AM