A Markov Decision Model and Decomposition Heuristic for Dynamic Vehicle Dispatching

Operations Research · 1993 · Volume 41 · Issue 1

Abstract

We describe 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, we adopt 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. We describe how to compute bounds on the algorithm's performance, and apply it to several examples with good results.

Keywords

dynamic programming, Markov, finite state: Markov decision model for vehicle dispatching, transportation, route selection: route selection for inventory replenishment

Enable JavaScript for citation tools and additional paper interactions.