A Hybrid Differential Evolution Algorithm for the Online Meal Delivery Problem

In recent years, the online food ordering (OFO) platforms have arose fast and brought huge convenience to people in daily life. Under the scenario of a realistic OFO platform, this paper addresses an online meal delivery problem (OMDP). To reduce the search space, the OMDP is decomposed into two sub-problems, i.e., the pickup and delivery problem and the order dispatching problem. To solve each sub-problem effectively, a hybrid differential evolution algorithm is proposed, which is fused by the DE-based phase to plan routes and the heuristic-based phase to determine order dispatching schemes. In the DE-based routing phase, a heuristic considering the urgency of orders is designed to generate the initial population with certain quality. Besides, a mutation operator is developed to enhance the exploration and a crossover operator embedded with local search is designed to enhance the exploitation. In the heuristic-based dispatching phase, a regret heuristic is presented to produce good dispatching solutions by introducing the influences between delivery persons. Numerical tests have been carried out and computational results demonstrate the effectiveness of the proposed algorithm.