A mixed-integer programming model for identifying intuitive ambulance dispatching policies

Markov decision process models and algorithms can be used to identify optimal policies for dispatching ambulances to spatially distributed customers, where the optimal policies indicate the ambulance to dispatch to each customer type in each state. Since the optimal solutions are dependent on Markov state variables, they may not always correspond to a simple set of rules when implementing the policies in practice. Restricted policies that conform to a priority list for each type of customer may be desirable for use in practice, since such policies are transparent and easy to implement. A priority list policy is an ordered list of ambulances that indicates the preferred order to dispatch the ambulances to a customer type subject to ambulance availability. This paper proposes a constrained Markov decision process model for identifying optimal priority list policies that is formulated as a mixed integer programming model, does not extend the Markov state space, and can be solved using standard algorithms. A series of computational examples illustrate the approach. The optimal mixed integer programming solutions to the computational examples have objective function values that are close to those of the unrestricted model and are superior to those of heuristics.