An Imitation Learning-Enhanced Iterated Matching Algorithm for On-Demand Food Delivery

As one representative of the emerging on-demand transport services, the on-demand food delivery (OFD) has penetrated into daily life. Due to its intrinsic complexities, the OFD has attracted the interest of a growing number of logistics researchers. This paper aims at optimizing the OFD process and addresses an OFD problem (OFDP). To overcome the dynamic and large-scale complexity, we abstract the OFDP into a static generalized assignment problem with a rolling horizon strategy. To meet the demand on high service quality and limited computation time, we propose an offline-optimization for online-operation framework based on imitation learning. Under this framework, an imitation learning-enhanced iterated matching algorithm (ILIMA) is proposed, which consists of three basic components: an iterated matching heuristic (IMH) to fast generate solutions, an expert to provide expertise, and a machine learning (ML) model to assist the decision-making process in IMH by mimicking the expert. In the offline-optimization phase, the ML model mines knowledge from the high-quality solutions optimized by the expert; in the online-operation phase, the IMH embedded with the well-trained ML model is deployed online to make decisions in a real OFD scenario. Offline simulation experiments are carried out on real historical data, which validate the superiority of ILIMA compared with existing methods. Moreover, rigorous online A/B tests are conducted on the scheduling system of Meituan, which demonstrates the practical value of ILIMA to improve customer satisfaction and delivery efficiency.