A Markov decision process framework for order dispatching in on-demand delivery services

Abstract

This article investigates the order dispatching problem in on-demand delivery services, and provides an in-depth analysis of the problem, its associated challenges, and progress in literature and practice. We discuss both the static and dynamic problem settings. In the static context, all information is available from the start, allowing for the formulation of optimization problems that yield theoretical optimal solutions. However, these models fall short in addressing the inherent uncertainties and evolving nature of real-world operations. Dynamic models, in contrast, consider uncertainty over time and is promising for optimizing dispatch policies by considering long-term impacts. Then, a MDP model incorporating four source of uncertainties is illustrated with an example presented. Future research should focus on developing comprehensive frameworks that jointly optimize multiple decisions, such as dispatching, routing, pricing, and workforce planning, to achieve system-wide efficiency and resilience. Moreover, there is a need to better incorporate human behaviors, such as driver acceptance and customer cancellations, into dispatch algorithms to reduce deviations from optimal outcomes.