A Four-Stage Heuristic Algorithm for Solving On-demand Meal Delivery Routing Problem

Abstract

Meal delivery services provided by platforms with integrated delivery networks are becoming increasingly popular. This paper adopts a rolling horizon approach to solve the meal delivery routing problem (MDRP). To improve delivery efficiency in scenarios with high delivery demand, multiple orders are allowed to be combined into one bundle and up to two bundles from two different restaurants can be delivered on one route. Following this strategy, an optimization-based four-stage heuristic algorithm is developed to generate an optimal routing plan in each optimization period. The algorithm first generates bundles according to orders’ spatial and temporal distribution. Secondly, we find feasible bundle pairs. Then, routes for delivering any single bundle or a bundle pair are optimized, respectively. Finally, the routes are assigned to available vehicles. In computational experiments using instances from open datasets, the system’s performance is evaluated in respect of average click-to-door time and ready-to-pickup time. We demonstrate that this algorithm can effectively process real-time information and assign optimal routes to the vehicles. By comparing the proposed method with an existing algorithm and exact solutions generated for a similar scenario, the results indicate that our method can generate solutions with slightly higher service quality and closer to the exact solutions.

Lejun Zhou 周乐骏

PhD Transportation Engineering Student at UC Berkeley

My research intersets are optimization and machine learning in transportation engineering.