关键词: 订单分批, 装箱, 改进的模拟退火算法, 货物冲突

Abstract: As a new e-commerce model, the online and offline (O2O) retail model is developing in full swing in China. One of the most representative models is the O2O large supermarket model. O2O large supermarketsprovide online shopping and offline delivery services, which have broken through the barriers between offline services and online transactions. In the O2O model, most of the goods ordered by customers are fresh products and daily necessities. In order to guarantee the safety of food, order fulfillment must consider the cargo conflict. For example, goods having different requirements for storage temperature should not be allowed to distribute in the same box. Normal goods and frozen goods may not be in the same box. Moreover, in the O2O model, orders show the characteristics of high frequency, small batch and urgent time window. Therefore, it is necessary to study the integrated scheduling of order batch picking and loading problems by considering cargo conflict.
The differences between this paper and the current research are as follows: (1)This study considers the two-dimensional loading problem with the cargo conflict constraint, while the current study does not consider the cargo conflict. (2)In this paper, the loading cost includes two parts: box cost and penalty cost. The higher the loading rate, the lower the penalty cost. The current study does not consider the penalty caused by the loading rate. (3)The current research divides the order picking and loading decisions. In this paper, we integrate the order picking and loading problems.
To improve the overall order delivery efficiency and ensure food safety and freshness in the O2O supermarket, this paper studies the integrated scheduling of order batching and loading problems with cargo conflict constraint. The mixed integer programming model is constructed. The objective function is to minimize the order picking cost and loading cost. The simulated annealing (SA) algorithm has been widely used in solving complex combinatorial optimization problems. The model considers the constraints of batch capacity and cargo conflict, which makes it difficult for the traditional SA algorithm to jump out of the local optimal solution, and the optimization performance limited. To increase the algorithm’s global search capability, the improved SA algorithm is designed. The improvement parts of SA include: the initial solution generation mechanism, the improved two-dimensional loading algorithm and the heating design. In order to verify the effectiveness of the model and algorithm, this paper implements a series of simulation experiments.
The experimental results show that: (1)Under different order types and parameter combinations, the improved SA algorithm can reduce the total cost more effectively than the other two algorithms. (2)The improved seed algorithm is better than the improved first-come-first-service (FCFS) to generate the initial solution. (3)The improved loading algorithm has lower cost and more operation friendliness than the traditional loading algorithm. (4)The improved SA with the heating design has better global search and optimization capability than the traditional SA. (5)The cargo conflict constraint can avoid the cargo conflict goods before the start of loading, avoid additional checking costs and selection costs, and reduce the total cost.
The limitation of this paper is that order picking and loading problems are often subject to multiple physical constraints in reality. Future work will aim to further study the joint scheduling problem of order picking and three-dimensional packing, which considers the constraints of products’ weight and fragility.

Key words: order batch, loading, improved simulated annealing algorithm, cargo conflict