  Dynamic vehicle routing problems (DVRPs) arise in several applications such
as technician routing, meal delivery, and parcel shipping. We consider the DVRP
with stochastic customer requests (DVRPSR), in which vehicles must be routed
dynamically with the goal of maximizing the number of served requests. We model
the DVRPSR as a multi-stage optimization problem, where the first-stage
decision defines route plans for serving scheduled requests. Our main
contributions are knapsack-based linear models to approximate accurately the
expected reward-to-go, measured as the number of accepted requests, at any
state of the stochastic system. These approximations are based on representing
each vehicle as a knapsack with a capacity given by the remaining service time
available along the vehicle's route. We combine these approximations with
optimal acceptance and assignment decision rules and derive efficient and
high-performing online scheduling policies. We further leverage good
predictions of the expected reward-to-go to design initial route plans that
facilitate serving dynamic requests. Computational experiments on very large
instances based on a real street network demonstrate the effectiveness of the
proposed methods in prescribing high-quality offline route plans and online
scheduling decisions.
