On modeling stochastic dynamic vehicle routing problems

Operations research requires models that unambiguously define problems and support the generation and presentation of solution methodology. In the field of dynamic routing, capturing the joint evolution of complex sequential routing decisions and stochastic information is challenging, leading to a situation where rigorous methods have outpaced rigorous models and thus making it difficult for researchers to engage in rigorous science. We provide a modeling framework that strongly connects application with method and that leverages the rich body of route-based planning and optimization. As a generalization of conventional Markov decision processes (MDPs), route-based MDPs augment the state space, action space, and reward structure to include routing information. Accordingly, route-based MDPs make it conceptually easier to connect dynamic routing problems with the route-based methods typically used to solve them – construct and revise routes as new information is learned. We anticipate route-based MDPs will facilitate more scientific rigor in dynamic routing studies, provide researchers with a common modeling language, allow for better inquiry, and improve classification and description of solution methods.