Towards Workload-Constrained Efficient Order Assignment in Last-Mile Delivery

Efficient order assignment in last-mile delivery benefits customers, couriers, and the platform. State-of-the-practice order assignment is based on the static delivery area partition, which cannot adapt well to the dynamic order quantity and destination distributions on different days. State-of-the-art methods focus on balancing order amounts or the payoff among couriers dynamically, neglecting the courier's workload in delivering orders. This paper explores the courier's heterogeneous behaviors for delivering orders to different destinations to measure the courier's workload and then achieve more efficient order assignments under the fair workload constraint. We design a workload-constrained order assignment system, called <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">WORD</i>, to reduce the cost of the last-mile delivery, i.e., the couriers’ total travel distance and overdue order rate. Specifically, the heterogeneous behaviors for delivering orders are first utilized for workload calculation. Then a two-stage order assignment framework is designed, including a sort-based initialization algorithm for initializing the assignment under the fair workload constraint and a coalition-game-based improvement algorithm for improving the assignment. Extensive evaluation results with real-world logistics data from one of the largest logistics companies in China show that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">WORD</i> reduces the cost of the order assignment by up to 51.9% under the fair workload constraint compared to the state-of-the-art methods.