Efficient Adaptive Matching for Real-Time City Express Delivery
Yafei Li, Qingshun Wu, Xin Huang, Jianliang Xu, Wanru Gao, Mingliang Xu
Abstract
City express delivery services (a.k.a.~last-mile delivery) have become more prominent in recent years. Many logistics giants, such as Amazon, JD, and Cainiao, have deployed intelligent express delivery systems to deal with the growing demand for parcel delivery. Existing works adopt queuing or batch processing approaches to assign parcels to couriers. However, these approaches do not fully consider the distribution of parcels and couriers, leading to poor quality of task assignment. In this paper, we investigate a problem of delivery matching based on revenue maximization in real-time city express delivery services. Given a set of couriers and a stream of parcel collection tasks, our problem aims to assign each collection task to a suitable courier to maximize the overall revenue of the platform. The problem is shown to be NP-hard. To tackle the problem efficiently, we present a time-aware batch matching algorithm to offer high-quality courier-task matching in each sliding window. We further theoretically analyze the matching approximation bound. In addition, we propose an efficient deep reinforcement learning-based approach to adaptively determine the sliding window size for better matching results. Finally, extensive experiments demonstrate that our proposed algorithms can achieve desirable effectiveness and efficiency under a wide range of parameter settings.