Generating Order Bundle And Assignment Algorithm For Stochastic Last-Mile Delivery In Crowdshipping

Abstract

The Covid-19 pandemic and the digital era's rapid growth have shifted consumer behavior towards online shopping, increasing the demand for "same day delivery." Crowdshipping, involving collaboration between e-platform retailers and occasional drivers with diverse capacities, adds complexity to route planning, necessitating advanced last-mile delivery strategies integrating dedicated and occasional drivers (DDs and ODs). One approach to enhance the efficiency of crowdshipping is by consolidating orders into batches, enabling a single courier to handle multiple orders within the same pickup location and drop off route. However, this assignment-batching problem becomes computationally expensive in real-world scenarios with numerous customer orders and uncertain demand and supply. To address this, heuristic solution methods are employed. This study proposes an order clustering and assignment algorithm that combines Mixed Integer Programming (MIP) with basic game theory principles to iteratively improve solutions. Additionally, the Adaptive Large Neighborhood Search (ALNS) algorithm is applied in the routing stage. The approach leverages a graph-based method by decomposing the original problem into more manageable sub-problems through clustering. ALNS then refines the solution by disrupting the assigned sequences post-allocation, overcoming local minima from the initial clustering phase. The performance of the proposed solution is tested through experiments based on a real-world case study of GrubHub, as referenced in key literature. Results indicate that the algorithm effectively handles varying scales of instances, achieving relatively optimal solutions under different demand and supply conditions (e.g., density levels, courier availability) and problem sizes