A Markov decision model and decomposition heuristic for dynamic vehicle dispatching

The paper describes a dynamic and stochastic vehicle dispatching problem called the delivery dispatching problem. This problem is modeled as a Markov decision process. Because exact solution of this model is impractical, the paper adopts a heuristic approach for handling the problem. The heuristic is based in part on a decomposition of the problem by customer, where customer subproblems generate penalty functions that are applied in a master dispatching problem. The paper describes how to compute bounds on the algorithm’s performance, and apply it to several examples with good results.