关键词: 订单拆分, 订单配送, 联合优化, 自适应大规模邻域搜索, 聚类, 惩罚策略

Abstract: In recent years, e-commerce has given rise to new formats and patterns, which has fueled the vigorous growth of China’s online retail industry. Considering the order features of multi-item customer orders and the warehouse layout of multi-warehouse in one city that are frequently present in the actual operations of e-commerce enterprises, order splitting occurs easily. Unreasonable order splitting will inevitably lead to multiple dispersed delivery of orders as the e-commerce orders continue to shift to small batches, multiple varieties and high frequency. This not only raises the total cost, but also runs counter to the proposition of green logistics. Although academics both domestically and internationally have carried out a greater number of beneficial studies on order splitting and order delivery and written many valuable works, there are still shortcomings. For example, order splitting and order delivery as two key aspects of order fulfillment are an interrelated and organic unity. However, most existing research separates the order splitting from order delivery, and only optimizes a single problem in isolation, ignoring the correlation between the two. In view of the above, and for the pressing problem of order splitting and order delivery that e-commerce enterprises need to solve, it is of great theoretical and practical significance to investigate how to reasonably split and distribute orders to improve the overall efficiency of order fulfillment.
Driven by the aforementioned considerations, this paper focuses on order splitting and order delivery in a multi-item, multi-warehouse as a whole for joint optimization, and builds a mixed integer programming model with the objective of minimizing order fulfillment cost. Furthermore, this paper proposes an Improved Adaptive Large Neighborhood Search (IALNS) algorithm. The main contributions of this paper are the following aspects: (1)Breaking through the constraints of existing research, this paper views the order splitting and order delivery as a whole for joint optimization instead of treating them as two separate problems. (2)Based on the analysis of the problem characteristics and the idea of decreasing the solution space, this paper designs a 2-Hierarchically Separated Tree(2-HST) algorithm with tree metric advantage to cluster the customer orders initially by introducing the clustering analysis theory. (3)This paper proposes a tournament strategy that takes penalty into account. This strategy can effectively reduce the probability of operator selected repeatedly while maintaining the convergence performance of the algorithm.
The results illustrate that compared with the results of CPLEX and the four baseline algorithms: Ant Colony Optimization (ACO), Tabu Search (TS) algorithm, Adaptive Large Neighborhood Search (ALNS) algorithm and Product Link-based Hybrid Heuristic Large Neighborhood Search algorithm (PLBH-LNS) on order fulfillment cost and CPU running time, the proposed IALNS algorithm can obtain a higher quality local optimal solution within a reasonable time. Moreover, compared with the order splitting and delivery strategy actually adopted by e-commerce enterprise, the order splitting and delivery strategy obtained by the IALNS algorithm can decrease the order fulfillment cost by about 26% on average, which verifies the practicability of the algorithm.

Key words: order splitting, order delivery, joint optimization, adaptive large neighborhood search, clustering, penalty strategy