关键词: 即时配送, 订单取消, 车辆调度, 自适应大邻域搜索算法

Abstract: In instant delivery, the uncertain order cancellation behavior is a critical factor that disrupts vehicle scheduling. Different customers may have different order cancellation patterns, and delivery vehicles need to perform multiple trips to process batch orders, which can be formulated as a multi-trip vehicle routing problem. To address this issue, a mathematical programming model is developed with the objective of maximizing expected profit, utilizing probability distribution to measure different order cancellations. An adaptive large neighborhood search algorithm is designed based on problem characteristics to solve the model. Finally, algorithm performance testing and sensitivity analysis are conducted using adapted instances constructed from the Solomon benchmark case set and real-case data from a large chain restaurant in Dalian, China. The results indicate that profitability is higher when customer order cancellations follow a sinusoidal distribution compared to linear and discrete distributions.

Key words: instant delivery, order cancellation, vehicle scheduling, adaptive large neighborhood search