  On-demand delivery has become increasingly popular around the world.
Motivated by a large grocery chain store who offers fast on-demand delivery
services, we model and solve a stochastic dynamic driver dispatching and
routing problem for last-mile delivery systems where on-time performance is the
main target. The system operator needs to dispatch a set of drivers and specify
their delivery routes facing random demand that arrives over a fixed number of
periods. The resulting stochastic dynamic program is challenging to solve due
to the curse of dimensionality. We propose a novel structured approximation
framework to approximate the value function via a parametrized dispatching and
routing policy. We analyze the structural properties of the approximation
framework and establish its performance guarantee under large-demand scenarios.
We then develop efficient exact algorithms for the approximation problem based
on Benders decomposition and column generation, which deliver verifiably
optimal solutions within minutes. The evaluation results on a real-world data
set show that our framework outperforms the current policy of the company by
36.53% on average in terms of delivery time. We also perform several policy
experiments to understand the value of dynamic dispatching and routing with
varying fleet sizes and dispatch frequencies.
