An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones

摘要

As technology continues to improve people's quality of life, there is a large, unfulfilled market worldwide for on-demand meal delivery services. The competitive edge of the business is foremost sharpened by the agility of the transport system. While lightweight drones are being developed as the next-generation vehicular platform for meal delivery, an efficient fleet operation becomes especially critical. This paper presents a mixed integer programming (MIP) model that comprehensively characterizes all relevant aspects of the business scenario, and proposes an optimization-driven, progressive algorithm for online fleet dispatch operations. Different from typical graph-based formulations of vehicle routing problems, the proposed temporally discrete and spatially continuous MIP formulation endogenously accounts for geometry and mobility and therefore permits dynamic input of order information with arbitrary pickup and delivery locations. The model is augmented with special constraints and an artificial objective function which effectively relay the system states between successive time horizons. The algorithm is validated through simulation case studies and is shown to meet the design objectives. (C) 2019 Elsevier Ltd. All rights reserved.