# Research on Hybrid Real-Time Picking Routing Optimization Based on Multiple Picking Stations

Authors: Deyao Wang; Jun Jiang; Ran Ma; Guicheng Shen
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In the order picking process of the warehouse center, considering the rapid increase in the volume of orders arriving at the picking center at the time of the promotional festival, a hybrid operation mode with multiple picking tables is used to meet the picking requirements of the huge number of real-time orders. Therefore, in this paper, a hybrid picking mode is proposed, taking into account both the idle degree of picking stations and their order item centers of gravity, and a new reinforcement learning algorithm embedding mechanism (PRL) with placeholder control is designed to solve the problem of a huge number of real-time item orders arriving at the picking center system on promotional holidays and in inconsistent quantities, and numerical simulations are performed for this algorithm. The experimental results show that the PRL algorithm in hybrid picking mode can handle a huge number of orders simultaneously and improve picking efficiency effectively.


---

## Body

## 1. Introduction

In recent years, with the booming development of e-commerce and the rapid popularity of mobile payment, online shopping has been developing at a high speed and the number of parcels has increased every year. Online shopping has grown at a quick pace in recent years, thanks to the blooming expansion of e-commerce and the rapid popularity of mobile payment. The number of deliveries has climbed every year. China’s e-commerce transactions were only 3.14 trillion yuan in 2008, but they have already risen to 31.63 billion yuan in 2018, a ten-year increase of tenfold, resulting in an explosive increase in the number of orders processed by e-commerce sorting centers per day [1]. However, as consumer demand continues to diversify and personalize, it is clear that the traditional picking center manual picking method is no longer able to control picking costs while responding quickly to customer order demands. Picking operations account for around 90% of the cost within the picking center, labor costs directly involved in picking operations account for approximately 0%, and picking time accounts for as much as 30% to 40% of the overall operating time. [2]. This shows that the real-time nature of picking operations is a key aspect of picking efficiency improvement and is crucial for e-commerce companies to enhance their core competitiveness. For example, Taobao’s “Double Eleven” and “Jingdong618’s” have raised the demand for real-time and efficient logistics sorting center solutions. Automated Guided Vehicles (AGVs) are increasingly being employed in logistics distribution centers as advanced automated logistics equipment in e-commerce, superstores, express delivery, and other industries. With the newest picking technology to manage finely orders and inventory items, a picking center can handle up to 2 million parcels in a single day and up to 4100 orders for custom clearance in one minute. The picking center’s real-time order picking efficiency places exceptionally high demands behind the massive order data.There are currently two main types of logistics picking operation modes, namely, multi-picker synchronous picking mode and multi-picker asynchronous picking mode. Multi-picker synchronous picking mode means that all picking stations must start at the same time for the same batch of tasks, and the next batch of tasks can only be performed when all picking stations have completed the current batch of tasks. Multi-picker asynchronous picking mode means that all logistics AGVs are grouped together, with each group serving one picker, and each picker can complete its work independently. It can be seen that the multi-picker synchronous picking mode has the problem of wasted picker resources waiting due to synchronous processing, while the multi-picker asynchronous picking mode has the problem of uneven task allocation of AGV resources due to the global grouping of AGVs.Therefore, this paper proposes a hybrid picking mode for the problem of uneven task allocation between synchronous picking waiting time consumption and asynchronous picking, i.e., a real-time picking operation mode according to the order reach time and the picking table idle rate, which solves the problem of time wastage caused by waiting in synchronous picking and the problem of uneven task allocation for nonglobal AGVs in asynchronous.


## 2. Literature Review

In essence, the picking path optimization problem with multiple picking stations studied in this paper belongs to the special vehicle path optimization problem (Vehicle Routing Problem, VRP). In 1959, the vehicle path problem (VRP) was proposed by Dantzig [3]. The traveling salesman problem (TSP) in vehicle routing Problem (VRP) was proved by Gaery [4] in his paper to be an NP-hard problem, so VRP problem is also an NP-hard problem. The NP-hard problem is not only of great significance in theoretical research but also of great significance in real life, as evidenced by the vehicle path optimization problem.In recent years, Praitk [5] has studied the effect of shelf quantity and shelf length on picking efficiency and proposed a picking equipment event model. Chan and Chan [6] investigated the effects of warehouse storage allocation strategy, picking path strategy, and picking density on picking efficiency. Lu et al. [7] focused on the implementation process of the order batch picking method (GASM) and the basic genetic algorithm picking method (GABM), and compared and analyzed the S-type picking path strategy and the midpoint slewing picking path strategy. Zhi and Ailan [8] suggested that the order picking strategy and path optimization were studied according to the distribution of goods in the order in the warehouse. And, Yi [9] proposed to establish an order management information system and strengthen the picking operation and the docking of the overbank distribution system and other strategies to optimize the picking operation with words. Caunhye et al. [10] studied the path optimization model in emergency logistics and analyzed the methods of path optimization in terms of the distribution situation of rescue supplies, the location of facilities, and casualty transportation, respectively.Some scholars have considered both order batching and picking path optimization together, in order to improve the efficiency of picking operations. Scholz et al. [11] proposed a variable neighborhood descent algorithm capable of handling large amounts of data by considering order binning, order assignment, batch sorting, and picking paths, and a new heuristic initial solution construction method was designed in order to speed up the solution over the vehicle. Chen et al. [12] combined the three problems of order batching, path optimization, and batch sorting to design a mixed integer programming model, and used a hybrid coded genetic algorithm and an ant colony optimization algorithm to solve the problem, and the experimental results proved that the solution speed and solution quality of the algorithm were due to the multi-objective genetic algorithm and the due date optimization algorithm. Matusiak et al. [13] received inspiration from a large shopping mall and used simulated annealing algorithm and A∗ algorithm to solve the order batching and path planning problems.In today’s era of rapid e-commerce development, how to respond quickly to customer needs is becoming a core issue for e-commerce and logistics companies. In order to improve the effectiveness of real-time picking, Amazon’s “KIVA” system and Jingdong’s “Tianwoldi Wolf System” have been born one after another. Various logistics companies in the industry have carried out innovation and exploration in picking system in picking route optimization. By combining the coordinate points of the storage area in the warehouse, the link path, using the ant colony algorithm and other intelligent algorithms to calculate the shortest picking path from the main channel to the picking table, improve the picking efficiency, and gradually improve the efficiency of real-time picking.Using neural network to solve the problem of path optimization can be traced back to 1985. Hopfield [14] used Hopfield networks for solving small CVRP instances. In 2015, Vinyals et al. [15] proposed a Pointer Network (PN) based on Recurrent Neural Network (RNN), which made a qualitative leap in the study of combinatorial optimization problems. Kool et al. [16] drew on the transformer model for a variety of path optimization and proposed a transformer model with rollout baseline to remove position embedding for multiple path optimization problems, which was applied to the VRP example. Ibrahim et al. [17] developed a reinforcement learning technique to find the optimal path from the parking lot to the customer base. Zhang and Yin [18] studied the optimization of supply paths in emergency situations and solved the supply routes based on a hybrid particle swarm algorithm under the premise of obtaining emergency orders. Sun et al. [19] established a mathematical model with capacity constraints and optimized the picking path based on genetic algorithm for a dual-zone distribution center.There are also some scholars to decompose the multi-pair multi-path optimization problem (MDVRP). David Pisinger and Ropke [20] proposed a heuristic algorithm for solving single-center VRP and applied it to solving MDVRP. Yu et al. [21] firstly simplified MDVRPTW into multiple VRPTW by clustering heuristic classification algorithm, and then used ant colony algorithm to solve each VRPTW. Jiali and Xiuping [22] designed a “two-stage adaptive genetic algorithm” based on multiple scanning operations and stage information feedback based on the idea of “segmented processing and overall optimization.”In summary, path planning is the focus of scholars’ research to improve the efficiency of picking operations and reduce the picking cost of sorting centers. In order to improve the picking efficiency of the picking center while responding quickly to the customer’s order demand, this paper proposes a hybrid real-time picking model of AGV based on the real-time operation of logistics AGVs, and designs an improved transformer algorithm to solve the task mobilization problem, and finally verifies the effectiveness of the algorithm through simulation experiments. The rest of this paper is organized as follows: Section3 describes the AGVs of picking center path optimization problem; Section 4 introduces the improved path optimization model based on deep reinforcement learning method; Section 5 performs the warehouse picking example validation; Section discusses the simulation experiment results; Section 6 and Section 7 give the conclusion and outlook of this paper.


## 3. A Mathematical Model of Mixed Real-Time Picking Mode with Multiple Picking Stations

### 3.1. Problem Description of the Hybrid Picking Model

An intelligent storage system is known to have multiple picking stations and a certain number of goods picking operations; each picking station can individually initiate picking tasks in real time, the system order portfolio arriving at the picking station is divided by order items, the AGV can visit multiple shelves of bays at a time to pick the goods required by the order according to the items and deliver these goods to the picking station. The shelves are stationary, and each shelf includes vertical levels. The AGVs are located in a uniform buffer zone when idle, have their own storage shelves and are capacity-constrained, so they can pick multiple items at once (e.g., the AGV TURO). When an order comes in, the AGV immediately picks the goods at the goods level according to the order requirements and sends them back to the picking table for sorting. The requirement is to design a reasonable picking path from the current scenario based on the order requirements and the location of the goods, and to efficiently complete the real-time picking task. A schematic of the picking path with capacity constraints in mixed picking mode is shown as Figure1.Figure 1
Schematic diagram of picking path with capacity constraints.The actual problem is abstracted and the following assumptions are made.(1)
When an order comes in, priority is given to the picking table with a high degree of availability and a short distance from the center of gravity of the order item for picking.(2)
All AGVs are in a unified buffer zone when they are idle; when an order comes, all AGVs will start from the same starting point and return to the starting point after completing the pickup task.(3)
AGVs depart from the picking table to each goods node for one-way pickup (one round), and an order can be completed by multiple rounds (AGVs) together.(4)
The AGV comes with its own shelf and has the capacity to be idle; when the pickup is carried out, the current pickup round ends immediately when the AGV’s shelf is full.(5)
The AGVs can go back and forth between the goods cargo and the picking table many times, and each round of the task accepts only one picking service from one AGV, and each time it departs to the goods node, it needs to meet the demand of the current goods picking at one time.(6)
Once an order arrives, the AGV is immediately assigned to pick up the goods.


### 3.2. Matching Method of Idle Picking Stations and Orders

#### 3.2.1. Calculating the Idle Degree of Picking Table

First, the idle degree of picking stations is calculated, and based on the idle degree of idle picking stations, picking orders are prioritized to the picking station with the highest idle degree. Idle degreet0mp The formula is shown in (1).(1)t0mp=t0mft,where t0mf denotes the idle time v0m of idle picking stations, t is the total working time, and M is the total number of picking stations in the idle state, where m∈1,2,…,M.


#### 3.2.2. Calculation of the Distance between the Center of Gravity of the Order Item and the Picking Table

Next, the distance between the center of the order item and the picking table is calculated with the following formula.(2)x¯n=∑i=1Lxn1L,y¯n=∑i=1Lyn1L,Lnm=x¯n−Vxm+x¯n−Vym.where xi,yi denote the x-axis coordinates and y-axis coordinates of the goods position where the i’th item order to be picked in the item order is located, and x¯n,y¯n is the center of the nth item order, L is the number of spaces used for the goods in the order, and Vxm,Vym are the horizontal and vertical coordinates of the free picking table.


### 3.3. CVRP Mathematical Model for Hybrid Real-Time Picking Mode

To facilitate model construction and subsequent calculations, the relevant variables are assumed as 3.3.1.


#### 3.3.1. Symbol Description

A=V,E: Picking network, where V=v0,v1,v2,……,vL represents the set of nodes and v0: represents the picking stationK: the number of AGVs required for the current picking order, where k∈1,2,…,KG: the total number of AGVsQ: maximum load capacity of the AGVqi: the loading capacity required by cargo jcij: the picking cost from slot i to slot jwijk: the AGV k remaining loading capacity from cargo i to cargo j(2) Decision-making variables.(3)xijk=1,thek′th AGV will travel form cargoito cargoj,0,otherwise,yik=1,cargoiwill be picked by thek′th AGV,0,otherwise.


#### 3.3.2. Objective Function

(4)minH=∑k=1K∑i=0L∑j=0Lxijkcij.


#### 3.3.3. Constraints

(5)K≤G,(6)∑i=1Lqiyik≤Q,∀k∈1,2,…,K,(7)∑k=1K∑i=1Lqiyik≤KQ,(8)∑k=1Kyik=1,∀i∈1,2,…,L,(9)∑j=1Lxijk=yik,∀i∈1,2,…,L,∀k∈1,2,…,K,(10)w0jk=x0jkQ,∀j∈1,2,…,L,∀k∈1,2,…,K,(11)∑k=1Kxijkwijk−qj≥0,∀i∈1,2,...,L,∀k∈1,2,...,K,(12)∑i,j⊂S×Sxijk≤S−1,S⊂1,……,LS≠∅∀k∈1,2,…,K.The objective function (4) indicates that the sum of the travel distances of all AGVs is the shortest; equation (5) indicates that the total number of AGVs required for order picking is less than the total number of AGVs; equation (6) indicates that the amount of goods picked by each AGV does not exceed its capacity limit; equation (7) indicates that the amount of goods required for this order picking does not exceed the sum of the capacity limits of all AGVs; equation (8) indicates that each goods position is guaranteed to be visited by only one AGV; equation (9) indicates that each cargo space is allowed to be visited only once in the same picking round; equation (10) indicates that each AGV is empty from the picking table; equation (11) indicates that the AGV has sufficient loading capacity for any cargo space before the AGV picks that space; equation (12) indicates the elimination of subloops.


## 3.1. Problem Description of the Hybrid Picking Model

An intelligent storage system is known to have multiple picking stations and a certain number of goods picking operations; each picking station can individually initiate picking tasks in real time, the system order portfolio arriving at the picking station is divided by order items, the AGV can visit multiple shelves of bays at a time to pick the goods required by the order according to the items and deliver these goods to the picking station. The shelves are stationary, and each shelf includes vertical levels. The AGVs are located in a uniform buffer zone when idle, have their own storage shelves and are capacity-constrained, so they can pick multiple items at once (e.g., the AGV TURO). When an order comes in, the AGV immediately picks the goods at the goods level according to the order requirements and sends them back to the picking table for sorting. The requirement is to design a reasonable picking path from the current scenario based on the order requirements and the location of the goods, and to efficiently complete the real-time picking task. A schematic of the picking path with capacity constraints in mixed picking mode is shown as Figure1.Figure 1
Schematic diagram of picking path with capacity constraints.The actual problem is abstracted and the following assumptions are made.(1)
When an order comes in, priority is given to the picking table with a high degree of availability and a short distance from the center of gravity of the order item for picking.(2)
All AGVs are in a unified buffer zone when they are idle; when an order comes, all AGVs will start from the same starting point and return to the starting point after completing the pickup task.(3)
AGVs depart from the picking table to each goods node for one-way pickup (one round), and an order can be completed by multiple rounds (AGVs) together.(4)
The AGV comes with its own shelf and has the capacity to be idle; when the pickup is carried out, the current pickup round ends immediately when the AGV’s shelf is full.(5)
The AGVs can go back and forth between the goods cargo and the picking table many times, and each round of the task accepts only one picking service from one AGV, and each time it departs to the goods node, it needs to meet the demand of the current goods picking at one time.(6)
Once an order arrives, the AGV is immediately assigned to pick up the goods.


## 3.2. Matching Method of Idle Picking Stations and Orders

### 3.2.1. Calculating the Idle Degree of Picking Table

First, the idle degree of picking stations is calculated, and based on the idle degree of idle picking stations, picking orders are prioritized to the picking station with the highest idle degree. Idle degreet0mp The formula is shown in (1).(1)t0mp=t0mft,where t0mf denotes the idle time v0m of idle picking stations, t is the total working time, and M is the total number of picking stations in the idle state, where m∈1,2,…,M.


### 3.2.2. Calculation of the Distance between the Center of Gravity of the Order Item and the Picking Table

Next, the distance between the center of the order item and the picking table is calculated with the following formula.(2)x¯n=∑i=1Lxn1L,y¯n=∑i=1Lyn1L,Lnm=x¯n−Vxm+x¯n−Vym.where xi,yi denote the x-axis coordinates and y-axis coordinates of the goods position where the i’th item order to be picked in the item order is located, and x¯n,y¯n is the center of the nth item order, L is the number of spaces used for the goods in the order, and Vxm,Vym are the horizontal and vertical coordinates of the free picking table.


## 3.2.1. Calculating the Idle Degree of Picking Table

First, the idle degree of picking stations is calculated, and based on the idle degree of idle picking stations, picking orders are prioritized to the picking station with the highest idle degree. Idle degreet0mp The formula is shown in (1).(1)t0mp=t0mft,where t0mf denotes the idle time v0m of idle picking stations, t is the total working time, and M is the total number of picking stations in the idle state, where m∈1,2,…,M.


## 3.2.2. Calculation of the Distance between the Center of Gravity of the Order Item and the Picking Table

Next, the distance between the center of the order item and the picking table is calculated with the following formula.(2)x¯n=∑i=1Lxn1L,y¯n=∑i=1Lyn1L,Lnm=x¯n−Vxm+x¯n−Vym.where xi,yi denote the x-axis coordinates and y-axis coordinates of the goods position where the i’th item order to be picked in the item order is located, and x¯n,y¯n is the center of the nth item order, L is the number of spaces used for the goods in the order, and Vxm,Vym are the horizontal and vertical coordinates of the free picking table.


## 3.3. CVRP Mathematical Model for Hybrid Real-Time Picking Mode

To facilitate model construction and subsequent calculations, the relevant variables are assumed as 3.3.1.


### 3.3.1. Symbol Description

A=V,E: Picking network, where V=v0,v1,v2,……,vL represents the set of nodes and v0: represents the picking stationK: the number of AGVs required for the current picking order, where k∈1,2,…,KG: the total number of AGVsQ: maximum load capacity of the AGVqi: the loading capacity required by cargo jcij: the picking cost from slot i to slot jwijk: the AGV k remaining loading capacity from cargo i to cargo j(2) Decision-making variables.(3)xijk=1,thek′th AGV will travel form cargoito cargoj,0,otherwise,yik=1,cargoiwill be picked by thek′th AGV,0,otherwise.


### 3.3.2. Objective Function

(4)minH=∑k=1K∑i=0L∑j=0Lxijkcij.


### 3.3.3. Constraints

(5)K≤G,(6)∑i=1Lqiyik≤Q,∀k∈1,2,…,K,(7)∑k=1K∑i=1Lqiyik≤KQ,(8)∑k=1Kyik=1,∀i∈1,2,…,L,(9)∑j=1Lxijk=yik,∀i∈1,2,…,L,∀k∈1,2,…,K,(10)w0jk=x0jkQ,∀j∈1,2,…,L,∀k∈1,2,…,K,(11)∑k=1Kxijkwijk−qj≥0,∀i∈1,2,...,L,∀k∈1,2,...,K,(12)∑i,j⊂S×Sxijk≤S−1,S⊂1,……,LS≠∅∀k∈1,2,…,K.The objective function (4) indicates that the sum of the travel distances of all AGVs is the shortest; equation (5) indicates that the total number of AGVs required for order picking is less than the total number of AGVs; equation (6) indicates that the amount of goods picked by each AGV does not exceed its capacity limit; equation (7) indicates that the amount of goods required for this order picking does not exceed the sum of the capacity limits of all AGVs; equation (8) indicates that each goods position is guaranteed to be visited by only one AGV; equation (9) indicates that each cargo space is allowed to be visited only once in the same picking round; equation (10) indicates that each AGV is empty from the picking table; equation (11) indicates that the AGV has sufficient loading capacity for any cargo space before the AGV picks that space; equation (12) indicates the elimination of subloops.


## 3.3.1. Symbol Description

A=V,E: Picking network, where V=v0,v1,v2,……,vL represents the set of nodes and v0: represents the picking stationK: the number of AGVs required for the current picking order, where k∈1,2,…,KG: the total number of AGVsQ: maximum load capacity of the AGVqi: the loading capacity required by cargo jcij: the picking cost from slot i to slot jwijk: the AGV k remaining loading capacity from cargo i to cargo j(2) Decision-making variables.(3)xijk=1,thek′th AGV will travel form cargoito cargoj,0,otherwise,yik=1,cargoiwill be picked by thek′th AGV,0,otherwise.


## 3.3.2. Objective Function

(4)minH=∑k=1K∑i=0L∑j=0Lxijkcij.


## 3.3.3. Constraints

(5)K≤G,(6)∑i=1Lqiyik≤Q,∀k∈1,2,…,K,(7)∑k=1K∑i=1Lqiyik≤KQ,(8)∑k=1Kyik=1,∀i∈1,2,…,L,(9)∑j=1Lxijk=yik,∀i∈1,2,…,L,∀k∈1,2,…,K,(10)w0jk=x0jkQ,∀j∈1,2,…,L,∀k∈1,2,…,K,(11)∑k=1Kxijkwijk−qj≥0,∀i∈1,2,...,L,∀k∈1,2,...,K,(12)∑i,j⊂S×Sxijk≤S−1,S⊂1,……,LS≠∅∀k∈1,2,…,K.The objective function (4) indicates that the sum of the travel distances of all AGVs is the shortest; equation (5) indicates that the total number of AGVs required for order picking is less than the total number of AGVs; equation (6) indicates that the amount of goods picked by each AGV does not exceed its capacity limit; equation (7) indicates that the amount of goods required for this order picking does not exceed the sum of the capacity limits of all AGVs; equation (8) indicates that each goods position is guaranteed to be visited by only one AGV; equation (9) indicates that each cargo space is allowed to be visited only once in the same picking round; equation (10) indicates that each AGV is empty from the picking table; equation (11) indicates that the AGV has sufficient loading capacity for any cargo space before the AGV picks that space; equation (12) indicates the elimination of subloops.


## 4. Algorithm Design for Hybrid Picking Mode

In previous reinforcement learning algorithms, it is more effective to solve purely theoretical routing problems. However, in this paper, starting from a realistic picking scenario, the shortest picking path solution is sought while considering the two prerequisites of “the idleness of the picking table” and “the distance between the center of gravity of the order item and the picking table.” The algorithm design of the hybrid picking mode in this paper refers to Wouter’s transformer model [16], and on this basis, the initial screening of the picking table and the order length alignment processing are added, which means that the limitation of the order volume at the moment of order arrival can be broken, so that the resources of the picking table can be more fully utilized and the picking efficiency of the intelligent AGV can be improved. The following is a detailed description of the algorithm.


### 4.1. Model Construction of Hybrid Picking Model

In order to solve the hybrid picking path optimization problem, this paper improves the transformer model. The specific idea is: using the method of placeholder expansion of picking nodes, a new placeholder encoding mechanism for aligning the order length of item order groups is proposed, so that it is transformed into an array of equal length, thus allowing the input data in the input batch to be solved for different numbers of picking positions; subsequently, in the encoding process, the input data are mapped into a high-dimensional space to obtain vector features. What’s more, in the encoding process, the input data are mapped into a high-dimensional space to obtain vector features, and then, in the decoding process, the solution model is constructed based on Markov Decision Process (MDP), and the algorithm model is shown in Figure2.Figure 2
Flow chart of coding and decoding.


#### 4.1.1. Coding Model for Hybrid Picking

(1) Target Picking Table Selection(A)
Calculate the picking table idle rateBased on the work duration of each picking table in the picking center during the day, the idle degree of each picking table in the idle state is calculated as shown in equation (1), and the idle rate is sorted from highest to lowest, and the picking table with the highest idle rate is selected for picking.(B)
Calculate the distance between the target picking table and the order center of gravity of the item to be pickedAccording to the warehouse management system and the warehouse control system, the order items are automatically divided according to the order commodity labels. In order to minimize the walking distance of the logistics AGV, the distance between the target picking table and the center of gravity of the order group to be picked for each item is calculated as shown in equation (2), and the picking table for entering the picking work is selected based on the principle of the shortest distance.(2) Item Order Processing. During e-commerce promotions (e.g., “Double 11” and“618 ”), the number of real-time orders arriving at the picking center management system increases sharply for a short period of time. To address the irregular nature of the real-time order quantity, this paper adds to the encoding structure of the transformer and proposes a new placeholder encoding mechanism for aligning the order lengths of item order groups into arrays of equal length to address the traditional reinforcement learning model in which the key to parallel computation is based on the input of the regularized batch tensor dimension. The principle is to determine the longest length of the required number of picks in the irregular batch order array, fill the placeholders for the blank, idle picking stations between the required picking orders and the longest length, and form structured data after tensor transformation, as shown in equation (13).(13)A=v00v01v02……v0n0vv……vv10v11v12……v1n1vv……vv20v21v22……v2n2vv……v……vM0vM1vM2……vMnM−3vMnM−2vMN……M×N,where M is the total number of batches, N is the length of the longest number of picks required in the batch order, vij is the demand for picking spaces in each order, ni is the length of the number of picks required for each order, and v is the placeholder.(3) Data Embedding Processing. First of all input the coordinates of the goods locations=x0,y0,x1,y1,…… and the demand for each good position in the order D=d1,d2,…… to the coding model. Then, the coordinates of the demand pointxi,yi and the demanddi are stitched together to obtain pi （ where P is a three-dimensional data (x, y, d)）and the high-dimensional linear projection of pi. The feature vector of picking points is obtained by embedding hi0. The feature vectors of the neural network at the i’th picking station are shown in Figure 3, where o represents the layer of the neural network and i indicates the picking points Briefly speaking, this vector represents the feature vector of the neural network of layer 0 in the ith picking table.Figure 3
Attention-based encoder.(4) Picking Network Feature Extraction(A)
Attention mechanismIn order to calculate the features of the network graph between picking points and picking points and between picking points and picking tables, the features,hi0. The picking network feature vector is calculated by performing multiple high-dimensional mappings, hgN.First, by using the model parametersWQ,WK,WV of the matrix operation, the feature information q,k,v of each picking node is calculated. Subsequently, the q with k correlation calculation is performed to obtain the weights. Similarly, we can calculate the picking node i with other picking nodes j correlation weights between uij.Next, the weights are normalized. We use thesoftmax function to normalize the correlation uij to normalize and calculate the attention weights aij∈0,1, which is the correlation coefficients received by the picked nodes.Finally, the normalized weights are used to sum up with the weight of V. Based on theaij and vj, calculate the current q. The attention value under the value hi′ represents the relevance degree information between the current picking node and other picking nodes.To facilitate the understanding of the attention mechanism, the detailed steps of the attention mechanism are shown in the Algorithm 1, where the model parameters are presented above.(B)
Multi-headed attention mechanismAlgorithm 1: Attention mechanism.
Inputs: each embedded node after embedding hill=0, picking nodes i,j∈1,2,…,LOutput: information about the correlation of each picking node with other picking nodes hi′(1)
Initializing the transformer network parametersWQ,WK,WV(2)
Fori = 1: L do:(3)
Calculate the values ofq, k, vqi=WQhil,hi′=∑jaijvj,vi=WVhil(4)
l=1+1(5)
Forj = 1: L does:(6)
Calculate the correlation between picking nodesi and other picking nodes juij=qiTkj/dkIfiandjarenotrelated−∞else(7)
Calculating attention weightsaij=euij/∑jeuij(8)
Calculating attentionhi′=∑jaijvj(9)
End for(10)
End forThe multi-headed attention mechanism is an algorithm for weighted messaging between cargo locations, and consists of multiple attention mechanisms that are stitched together to calculate the correlation information between picking points based on different dimensions to obtain the picking network feature vectorhgN.


#### 4.1.2. Decoding Model for Hybrid Picking

(1) Picking Node Relevance Embedding. First, the picking point features are obtained by coding hiN=h0N,h1N,…… and picking network diagram features hgN, and the coordinates and demand of the goods and picking stations as input for decoding. The information of the picking table and the remaining loading capacity of the AGV are marked to make a start for solving the path solution.(2) Attention Mechanism. Like the attention mechanism for encoding, the attention mechanism in this stage calculates the direct correlation between the last picking node in the identified path order, i.e., the picking point about to depart, and the outstanding picking point to calculate the individual probabilities of the next picking node and determine the next picking point to go to.(3) Masking Mechanism. The masking mechanism is used to mask the next round of unsuitable cargo bits after the probability of the next visit to the node of interest is generated using the attention mechanism. And, the parameters of the masking process are set as shown in Table 1.Table 1
Mask parameter representation.
NumberParametersIndicatesExamples1VedVisited node vectorVed=0,0,0,02DNode demand vectorD=0.3,0.5,0.7,0.13UcapCar capacity already usedUcap=0.34BcapBroadcast valueBcap=BroadcastingVed,Ucap5AcapTruncated vectors (greater than the car capacity is truncated)Acap=1,0,0,06MMask vector (indicates nodes that cannot be accessed)M=1,0,0,0In the masking process,Ved uses 0 and 1 to represent accessible nodes, where the 1 represents two different meanings: (1) the nodes that have been accessed and (2) the nodes that are not suitable for access in this sub-loop, i.e., after accessing the point in the sub-loop, the cargo nodes will exceed the car capacity and do not meet the realistic constraints but have not yet been picked. The picking path can then be indexed by the sequence of the mask. The masking process is shown in Figure 4 and the whole decoding process is shown in Figure 5.Figure 4
Masking process.Figure 5
Attention-based decoder.


### 4.2. Training Optimization Components for Hybrid Picking Patterns

Here, we choose a reinforcement learning algorithm with a rollout baseline [22] as the evaluation parameter to train the model, which is a hybrid algorithm combining value-based and policy gradient-based algorithms with two neural network models built in, i.e., the transformer network model and the rollout network model.


#### 4.2.1. Reinforcement of the Learning Network Model

In a realistic picking center environment, it is generally a grid layout that presents a north-south or east-west orientation, thus using the Manhattan distance to design the objective function, see equation (14).(14)rπ|s=∑t=1nxπt−xπt−1+xπn−xπ1+∑t=1nyπt−yπt−1+yπn−yπ1.In this paper, the training network uses the above encoding and decoding model, i.e., the transformer model, with aθ-parameterized stochastic policy π, which generates the conditional probability distributions of the nodes according to the attention mechanism, and sequentially generates the solution sequence points, see equation (14). Based on the generated solution sequence points, the loss function is calculated, see the definition of equation (15), wherein LiBLX0n;σ is described in detail in the rollout, and is the time step of decoding.(15)∑T⋅Lt′=tπi−LiBLX0n:σ.Based on the loss function, the gradient optimization parameters of the objective function are calculated, which are defined as shown in equation (16).(16)∇θ←1N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n.Finally, the traditional stochastic gradient descent (SGD) process is replaced by the Adam first-order optimization algorithm, which backpropagates the gradients and updates the neural network weights iteratively using the training data, see the defined equation (17).(17)θ←Adamθ,∇θ.


#### 4.2.2. Reinforcing the Learning Baseline Model

Inputs: picking table and shelf locationssi=xi,yi,i=0,1,2,…,N, the number of picking orders demanded is di, the number of AGVs is k, the loading capacity of the AGV is D.Training: calculated according to the Adam optimization algorithmθ , update back propagation gradient, optimize transformer model parameters and update rollout, evaluate the network parameters, the detailed steps are shown in Algorithm 2.Algorithm 2: Reinforcement learning algorithms under mixed models.
Inputs: coordinates of picking table p, position s, and the demand for the picking table DOutput: The picked sequential cargo position is the solution π(1)
Initialize transformer and rollout evaluation network model parameters. Initialize optimizer parameters andinitialize learning rate(2)
Calculation of picking table idleness(3)
Calculation of the distance between the pintle order and the center of gravity of the picking table(4)
Fori = 1: E do-(5)
Initialization parameters.θ,θBL←θ(6)
si←random1234∀i∈1,…,Batch(7)
πi←rolloutsi,pθ∀i∈1,…,Batch(8)
πiBL←rolloutsi,pθ∀i∈1,…,Batch(9)
Forn=1,…,Ndo(10)
Initialization time step.t←0(11)
Repeat(12)
According to the probability distributionpyt+1n|Ytn,Xtn, select sequence points yt+1n(13)
Observing the new stateXt+1n(14)
t←t+1(15)
Until the termination conditions are met(16)
Calculate the objective function of the trainingLπi=LYn,X0n(17)
Calculate the evaluation value of the rollout baselineLπiBL(18)
To find the gradient for the transformer model network.∇θ←1/N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n(19)
Gradient updates to the transformer model network.θ←Adamθ,∇θ(20)
End for(21)
If one-sided pairedt-test test< α then(22)
θBL←θ(23)
End if(24)
End forStep (1) evaluate the network model parameters with 0 initializing transformer and rollout; step (2) with step (3) is to select the best picking station; step (4) iterative module; steps (5)–(7) randomly initialize the network strategy; step (9) perform batch training; step (10) start decoding; steps (11)–(15) generate decoding sequence, steps (16)–(29) calculate update gradient values and optimize the neural network parameters based on Adam’s algorithm. Steps (21)–(23) whether to update the evaluation function parameters.


## 4.1. Model Construction of Hybrid Picking Model

In order to solve the hybrid picking path optimization problem, this paper improves the transformer model. The specific idea is: using the method of placeholder expansion of picking nodes, a new placeholder encoding mechanism for aligning the order length of item order groups is proposed, so that it is transformed into an array of equal length, thus allowing the input data in the input batch to be solved for different numbers of picking positions; subsequently, in the encoding process, the input data are mapped into a high-dimensional space to obtain vector features. What’s more, in the encoding process, the input data are mapped into a high-dimensional space to obtain vector features, and then, in the decoding process, the solution model is constructed based on Markov Decision Process (MDP), and the algorithm model is shown in Figure2.Figure 2
Flow chart of coding and decoding.


### 4.1.1. Coding Model for Hybrid Picking

(1) Target Picking Table Selection(A)
Calculate the picking table idle rateBased on the work duration of each picking table in the picking center during the day, the idle degree of each picking table in the idle state is calculated as shown in equation (1), and the idle rate is sorted from highest to lowest, and the picking table with the highest idle rate is selected for picking.(B)
Calculate the distance between the target picking table and the order center of gravity of the item to be pickedAccording to the warehouse management system and the warehouse control system, the order items are automatically divided according to the order commodity labels. In order to minimize the walking distance of the logistics AGV, the distance between the target picking table and the center of gravity of the order group to be picked for each item is calculated as shown in equation (2), and the picking table for entering the picking work is selected based on the principle of the shortest distance.(2) Item Order Processing. During e-commerce promotions (e.g., “Double 11” and“618 ”), the number of real-time orders arriving at the picking center management system increases sharply for a short period of time. To address the irregular nature of the real-time order quantity, this paper adds to the encoding structure of the transformer and proposes a new placeholder encoding mechanism for aligning the order lengths of item order groups into arrays of equal length to address the traditional reinforcement learning model in which the key to parallel computation is based on the input of the regularized batch tensor dimension. The principle is to determine the longest length of the required number of picks in the irregular batch order array, fill the placeholders for the blank, idle picking stations between the required picking orders and the longest length, and form structured data after tensor transformation, as shown in equation (13).(13)A=v00v01v02……v0n0vv……vv10v11v12……v1n1vv……vv20v21v22……v2n2vv……v……vM0vM1vM2……vMnM−3vMnM−2vMN……M×N,where M is the total number of batches, N is the length of the longest number of picks required in the batch order, vij is the demand for picking spaces in each order, ni is the length of the number of picks required for each order, and v is the placeholder.(3) Data Embedding Processing. First of all input the coordinates of the goods locations=x0,y0,x1,y1,…… and the demand for each good position in the order D=d1,d2,…… to the coding model. Then, the coordinates of the demand pointxi,yi and the demanddi are stitched together to obtain pi （ where P is a three-dimensional data (x, y, d)）and the high-dimensional linear projection of pi. The feature vector of picking points is obtained by embedding hi0. The feature vectors of the neural network at the i’th picking station are shown in Figure 3, where o represents the layer of the neural network and i indicates the picking points Briefly speaking, this vector represents the feature vector of the neural network of layer 0 in the ith picking table.Figure 3
Attention-based encoder.(4) Picking Network Feature Extraction(A)
Attention mechanismIn order to calculate the features of the network graph between picking points and picking points and between picking points and picking tables, the features,hi0. The picking network feature vector is calculated by performing multiple high-dimensional mappings, hgN.First, by using the model parametersWQ,WK,WV of the matrix operation, the feature information q,k,v of each picking node is calculated. Subsequently, the q with k correlation calculation is performed to obtain the weights. Similarly, we can calculate the picking node i with other picking nodes j correlation weights between uij.Next, the weights are normalized. We use thesoftmax function to normalize the correlation uij to normalize and calculate the attention weights aij∈0,1, which is the correlation coefficients received by the picked nodes.Finally, the normalized weights are used to sum up with the weight of V. Based on theaij and vj, calculate the current q. The attention value under the value hi′ represents the relevance degree information between the current picking node and other picking nodes.To facilitate the understanding of the attention mechanism, the detailed steps of the attention mechanism are shown in the Algorithm 1, where the model parameters are presented above.(B)
Multi-headed attention mechanismAlgorithm 1: Attention mechanism.
Inputs: each embedded node after embedding hill=0, picking nodes i,j∈1,2,…,LOutput: information about the correlation of each picking node with other picking nodes hi′(1)
Initializing the transformer network parametersWQ,WK,WV(2)
Fori = 1: L do:(3)
Calculate the values ofq, k, vqi=WQhil,hi′=∑jaijvj,vi=WVhil(4)
l=1+1(5)
Forj = 1: L does:(6)
Calculate the correlation between picking nodesi and other picking nodes juij=qiTkj/dkIfiandjarenotrelated−∞else(7)
Calculating attention weightsaij=euij/∑jeuij(8)
Calculating attentionhi′=∑jaijvj(9)
End for(10)
End forThe multi-headed attention mechanism is an algorithm for weighted messaging between cargo locations, and consists of multiple attention mechanisms that are stitched together to calculate the correlation information between picking points based on different dimensions to obtain the picking network feature vectorhgN.


### 4.1.2. Decoding Model for Hybrid Picking

(1) Picking Node Relevance Embedding. First, the picking point features are obtained by coding hiN=h0N,h1N,…… and picking network diagram features hgN, and the coordinates and demand of the goods and picking stations as input for decoding. The information of the picking table and the remaining loading capacity of the AGV are marked to make a start for solving the path solution.(2) Attention Mechanism. Like the attention mechanism for encoding, the attention mechanism in this stage calculates the direct correlation between the last picking node in the identified path order, i.e., the picking point about to depart, and the outstanding picking point to calculate the individual probabilities of the next picking node and determine the next picking point to go to.(3) Masking Mechanism. The masking mechanism is used to mask the next round of unsuitable cargo bits after the probability of the next visit to the node of interest is generated using the attention mechanism. And, the parameters of the masking process are set as shown in Table 1.Table 1
Mask parameter representation.
NumberParametersIndicatesExamples1VedVisited node vectorVed=0,0,0,02DNode demand vectorD=0.3,0.5,0.7,0.13UcapCar capacity already usedUcap=0.34BcapBroadcast valueBcap=BroadcastingVed,Ucap5AcapTruncated vectors (greater than the car capacity is truncated)Acap=1,0,0,06MMask vector (indicates nodes that cannot be accessed)M=1,0,0,0In the masking process,Ved uses 0 and 1 to represent accessible nodes, where the 1 represents two different meanings: (1) the nodes that have been accessed and (2) the nodes that are not suitable for access in this sub-loop, i.e., after accessing the point in the sub-loop, the cargo nodes will exceed the car capacity and do not meet the realistic constraints but have not yet been picked. The picking path can then be indexed by the sequence of the mask. The masking process is shown in Figure 4 and the whole decoding process is shown in Figure 5.Figure 4
Masking process.Figure 5
Attention-based decoder.


## 4.1.1. Coding Model for Hybrid Picking

(1) Target Picking Table Selection(A)
Calculate the picking table idle rateBased on the work duration of each picking table in the picking center during the day, the idle degree of each picking table in the idle state is calculated as shown in equation (1), and the idle rate is sorted from highest to lowest, and the picking table with the highest idle rate is selected for picking.(B)
Calculate the distance between the target picking table and the order center of gravity of the item to be pickedAccording to the warehouse management system and the warehouse control system, the order items are automatically divided according to the order commodity labels. In order to minimize the walking distance of the logistics AGV, the distance between the target picking table and the center of gravity of the order group to be picked for each item is calculated as shown in equation (2), and the picking table for entering the picking work is selected based on the principle of the shortest distance.(2) Item Order Processing. During e-commerce promotions (e.g., “Double 11” and“618 ”), the number of real-time orders arriving at the picking center management system increases sharply for a short period of time. To address the irregular nature of the real-time order quantity, this paper adds to the encoding structure of the transformer and proposes a new placeholder encoding mechanism for aligning the order lengths of item order groups into arrays of equal length to address the traditional reinforcement learning model in which the key to parallel computation is based on the input of the regularized batch tensor dimension. The principle is to determine the longest length of the required number of picks in the irregular batch order array, fill the placeholders for the blank, idle picking stations between the required picking orders and the longest length, and form structured data after tensor transformation, as shown in equation (13).(13)A=v00v01v02……v0n0vv……vv10v11v12……v1n1vv……vv20v21v22……v2n2vv……v……vM0vM1vM2……vMnM−3vMnM−2vMN……M×N,where M is the total number of batches, N is the length of the longest number of picks required in the batch order, vij is the demand for picking spaces in each order, ni is the length of the number of picks required for each order, and v is the placeholder.(3) Data Embedding Processing. First of all input the coordinates of the goods locations=x0,y0,x1,y1,…… and the demand for each good position in the order D=d1,d2,…… to the coding model. Then, the coordinates of the demand pointxi,yi and the demanddi are stitched together to obtain pi （ where P is a three-dimensional data (x, y, d)）and the high-dimensional linear projection of pi. The feature vector of picking points is obtained by embedding hi0. The feature vectors of the neural network at the i’th picking station are shown in Figure 3, where o represents the layer of the neural network and i indicates the picking points Briefly speaking, this vector represents the feature vector of the neural network of layer 0 in the ith picking table.Figure 3
Attention-based encoder.(4) Picking Network Feature Extraction(A)
Attention mechanismIn order to calculate the features of the network graph between picking points and picking points and between picking points and picking tables, the features,hi0. The picking network feature vector is calculated by performing multiple high-dimensional mappings, hgN.First, by using the model parametersWQ,WK,WV of the matrix operation, the feature information q,k,v of each picking node is calculated. Subsequently, the q with k correlation calculation is performed to obtain the weights. Similarly, we can calculate the picking node i with other picking nodes j correlation weights between uij.Next, the weights are normalized. We use thesoftmax function to normalize the correlation uij to normalize and calculate the attention weights aij∈0,1, which is the correlation coefficients received by the picked nodes.Finally, the normalized weights are used to sum up with the weight of V. Based on theaij and vj, calculate the current q. The attention value under the value hi′ represents the relevance degree information between the current picking node and other picking nodes.To facilitate the understanding of the attention mechanism, the detailed steps of the attention mechanism are shown in the Algorithm 1, where the model parameters are presented above.(B)
Multi-headed attention mechanismAlgorithm 1: Attention mechanism.
Inputs: each embedded node after embedding hill=0, picking nodes i,j∈1,2,…,LOutput: information about the correlation of each picking node with other picking nodes hi′(1)
Initializing the transformer network parametersWQ,WK,WV(2)
Fori = 1: L do:(3)
Calculate the values ofq, k, vqi=WQhil,hi′=∑jaijvj,vi=WVhil(4)
l=1+1(5)
Forj = 1: L does:(6)
Calculate the correlation between picking nodesi and other picking nodes juij=qiTkj/dkIfiandjarenotrelated−∞else(7)
Calculating attention weightsaij=euij/∑jeuij(8)
Calculating attentionhi′=∑jaijvj(9)
End for(10)
End forThe multi-headed attention mechanism is an algorithm for weighted messaging between cargo locations, and consists of multiple attention mechanisms that are stitched together to calculate the correlation information between picking points based on different dimensions to obtain the picking network feature vectorhgN.


## 4.1.2. Decoding Model for Hybrid Picking

(1) Picking Node Relevance Embedding. First, the picking point features are obtained by coding hiN=h0N,h1N,…… and picking network diagram features hgN, and the coordinates and demand of the goods and picking stations as input for decoding. The information of the picking table and the remaining loading capacity of the AGV are marked to make a start for solving the path solution.(2) Attention Mechanism. Like the attention mechanism for encoding, the attention mechanism in this stage calculates the direct correlation between the last picking node in the identified path order, i.e., the picking point about to depart, and the outstanding picking point to calculate the individual probabilities of the next picking node and determine the next picking point to go to.(3) Masking Mechanism. The masking mechanism is used to mask the next round of unsuitable cargo bits after the probability of the next visit to the node of interest is generated using the attention mechanism. And, the parameters of the masking process are set as shown in Table 1.Table 1
Mask parameter representation.
NumberParametersIndicatesExamples1VedVisited node vectorVed=0,0,0,02DNode demand vectorD=0.3,0.5,0.7,0.13UcapCar capacity already usedUcap=0.34BcapBroadcast valueBcap=BroadcastingVed,Ucap5AcapTruncated vectors (greater than the car capacity is truncated)Acap=1,0,0,06MMask vector (indicates nodes that cannot be accessed)M=1,0,0,0In the masking process,Ved uses 0 and 1 to represent accessible nodes, where the 1 represents two different meanings: (1) the nodes that have been accessed and (2) the nodes that are not suitable for access in this sub-loop, i.e., after accessing the point in the sub-loop, the cargo nodes will exceed the car capacity and do not meet the realistic constraints but have not yet been picked. The picking path can then be indexed by the sequence of the mask. The masking process is shown in Figure 4 and the whole decoding process is shown in Figure 5.Figure 4
Masking process.Figure 5
Attention-based decoder.


## 4.2. Training Optimization Components for Hybrid Picking Patterns

Here, we choose a reinforcement learning algorithm with a rollout baseline [22] as the evaluation parameter to train the model, which is a hybrid algorithm combining value-based and policy gradient-based algorithms with two neural network models built in, i.e., the transformer network model and the rollout network model.


### 4.2.1. Reinforcement of the Learning Network Model

In a realistic picking center environment, it is generally a grid layout that presents a north-south or east-west orientation, thus using the Manhattan distance to design the objective function, see equation (14).(14)rπ|s=∑t=1nxπt−xπt−1+xπn−xπ1+∑t=1nyπt−yπt−1+yπn−yπ1.In this paper, the training network uses the above encoding and decoding model, i.e., the transformer model, with aθ-parameterized stochastic policy π, which generates the conditional probability distributions of the nodes according to the attention mechanism, and sequentially generates the solution sequence points, see equation (14). Based on the generated solution sequence points, the loss function is calculated, see the definition of equation (15), wherein LiBLX0n;σ is described in detail in the rollout, and is the time step of decoding.(15)∑T⋅Lt′=tπi−LiBLX0n:σ.Based on the loss function, the gradient optimization parameters of the objective function are calculated, which are defined as shown in equation (16).(16)∇θ←1N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n.Finally, the traditional stochastic gradient descent (SGD) process is replaced by the Adam first-order optimization algorithm, which backpropagates the gradients and updates the neural network weights iteratively using the training data, see the defined equation (17).(17)θ←Adamθ,∇θ.


### 4.2.2. Reinforcing the Learning Baseline Model

Inputs: picking table and shelf locationssi=xi,yi,i=0,1,2,…,N, the number of picking orders demanded is di, the number of AGVs is k, the loading capacity of the AGV is D.Training: calculated according to the Adam optimization algorithmθ , update back propagation gradient, optimize transformer model parameters and update rollout, evaluate the network parameters, the detailed steps are shown in Algorithm 2.Algorithm 2: Reinforcement learning algorithms under mixed models.
Inputs: coordinates of picking table p, position s, and the demand for the picking table DOutput: The picked sequential cargo position is the solution π(1)
Initialize transformer and rollout evaluation network model parameters. Initialize optimizer parameters andinitialize learning rate(2)
Calculation of picking table idleness(3)
Calculation of the distance between the pintle order and the center of gravity of the picking table(4)
Fori = 1: E do-(5)
Initialization parameters.θ,θBL←θ(6)
si←random1234∀i∈1,…,Batch(7)
πi←rolloutsi,pθ∀i∈1,…,Batch(8)
πiBL←rolloutsi,pθ∀i∈1,…,Batch(9)
Forn=1,…,Ndo(10)
Initialization time step.t←0(11)
Repeat(12)
According to the probability distributionpyt+1n|Ytn,Xtn, select sequence points yt+1n(13)
Observing the new stateXt+1n(14)
t←t+1(15)
Until the termination conditions are met(16)
Calculate the objective function of the trainingLπi=LYn,X0n(17)
Calculate the evaluation value of the rollout baselineLπiBL(18)
To find the gradient for the transformer model network.∇θ←1/N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n(19)
Gradient updates to the transformer model network.θ←Adamθ,∇θ(20)
End for(21)
If one-sided pairedt-test test< α then(22)
θBL←θ(23)
End if(24)
End forStep (1) evaluate the network model parameters with 0 initializing transformer and rollout; step (2) with step (3) is to select the best picking station; step (4) iterative module; steps (5)–(7) randomly initialize the network strategy; step (9) perform batch training; step (10) start decoding; steps (11)–(15) generate decoding sequence, steps (16)–(29) calculate update gradient values and optimize the neural network parameters based on Adam’s algorithm. Steps (21)–(23) whether to update the evaluation function parameters.


## 4.2.1. Reinforcement of the Learning Network Model

In a realistic picking center environment, it is generally a grid layout that presents a north-south or east-west orientation, thus using the Manhattan distance to design the objective function, see equation (14).(14)rπ|s=∑t=1nxπt−xπt−1+xπn−xπ1+∑t=1nyπt−yπt−1+yπn−yπ1.In this paper, the training network uses the above encoding and decoding model, i.e., the transformer model, with aθ-parameterized stochastic policy π, which generates the conditional probability distributions of the nodes according to the attention mechanism, and sequentially generates the solution sequence points, see equation (14). Based on the generated solution sequence points, the loss function is calculated, see the definition of equation (15), wherein LiBLX0n;σ is described in detail in the rollout, and is the time step of decoding.(15)∑T⋅Lt′=tπi−LiBLX0n:σ.Based on the loss function, the gradient optimization parameters of the objective function are calculated, which are defined as shown in equation (16).(16)∇θ←1N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n.Finally, the traditional stochastic gradient descent (SGD) process is replaced by the Adam first-order optimization algorithm, which backpropagates the gradients and updates the neural network weights iteratively using the training data, see the defined equation (17).(17)θ←Adamθ,∇θ.


## 4.2.2. Reinforcing the Learning Baseline Model

Inputs: picking table and shelf locationssi=xi,yi,i=0,1,2,…,N, the number of picking orders demanded is di, the number of AGVs is k, the loading capacity of the AGV is D.Training: calculated according to the Adam optimization algorithmθ , update back propagation gradient, optimize transformer model parameters and update rollout, evaluate the network parameters, the detailed steps are shown in Algorithm 2.Algorithm 2: Reinforcement learning algorithms under mixed models.
Inputs: coordinates of picking table p, position s, and the demand for the picking table DOutput: The picked sequential cargo position is the solution π(1)
Initialize transformer and rollout evaluation network model parameters. Initialize optimizer parameters andinitialize learning rate(2)
Calculation of picking table idleness(3)
Calculation of the distance between the pintle order and the center of gravity of the picking table(4)
Fori = 1: E do-(5)
Initialization parameters.θ,θBL←θ(6)
si←random1234∀i∈1,…,Batch(7)
πi←rolloutsi,pθ∀i∈1,…,Batch(8)
πiBL←rolloutsi,pθ∀i∈1,…,Batch(9)
Forn=1,…,Ndo(10)
Initialization time step.t←0(11)
Repeat(12)
According to the probability distributionpyt+1n|Ytn,Xtn, select sequence points yt+1n(13)
Observing the new stateXt+1n(14)
t←t+1(15)
Until the termination conditions are met(16)
Calculate the objective function of the trainingLπi=LYn,X0n(17)
Calculate the evaluation value of the rollout baselineLπiBL(18)
To find the gradient for the transformer model network.∇θ←1/N∑n=1N∑TnLt′=tπi−LiBLX0n;σ∇θlogPYn|X0n(19)
Gradient updates to the transformer model network.θ←Adamθ,∇θ(20)
End for(21)
If one-sided pairedt-test test< α then(22)
θBL←θ(23)
End if(24)
End forStep (1) evaluate the network model parameters with 0 initializing transformer and rollout; step (2) with step (3) is to select the best picking station; step (4) iterative module; steps (5)–(7) randomly initialize the network strategy; step (9) perform batch training; step (10) start decoding; steps (11)–(15) generate decoding sequence, steps (16)–(29) calculate update gradient values and optimize the neural network parameters based on Adam’s algorithm. Steps (21)–(23) whether to update the evaluation function parameters.


## 5. Example Simulation and Analysis

### 5.1. Example Simulation of Hybrid Real-Time Picking Mode

A picking center is arranged in a regional layout according to commodity items. There are multiple picking stations in the center. The AGVs are in a unified charging cache area, and they work together to complete picking. The intelligent warehouse is set to have 5 picking stations and 360 goods slots, and the demand for each task in each batch of order is less than 1. The quantity of AVG is not limited, which is enough to meet the assigned task of order picking.  In order to increase the complexity of the task and improve the universality of the algorithm, 13/14/15 picking order tasks are randomly generated according to the Poisson distribution adhered to at the time of order arrival. Since the distance between the CHARGING buffer of AGV and the picking point is too small compared with the total picking path of batch orders, the simulation experiment in this paper ignores the distance between the charging buffer of AGV and the first picking task point, and regards it as the AGV starting from the picking station and returning to the picking station when the loading capacity is insufficient. The relevant simulation data are shown in Table1. In order to display the distribution of data intuitively, it is drawn in the form of a scatter diagram, and the warehouse coordinate diagram is shown in Figure 6.Figure 6
Coordinate assignment chart.The calculation data of the picking station is shown in Table2and Table 3.The bold value in Table 2 indicates that under the conditions of comprehensively considering the idleness of the picking table and the distance from the center of gravity of the order to the picking table, we will select the optimal selection of the picking table entering the working state.Table 2
Picking table idleness and item order center of gravity distance.
Picking tableLocationVacancy rateDistance from the center of gravity of the first group of item ordersDistance to the center of gravity of the second group of item ordersDistance to the center of gravity of the third group of item ordersPicking table1(6, 17)0.69.7517.2231.77Picking table2(14, 17)0.313.3911.3524.42Picking table3(22, 17)0.5719.799.4617.65Picking table4(30, 17)0.427.0513.3412.44Picking table5(38, 17)0.534.6419.8611.22Table 3
Original data for picking nodes.
NumPicking stations 1Picking stations 3Picking stations 5CoordinatesDemandCoordinatesDemandCoordinatesDemand1(1, 9)0.13(27, 12)0.13(31, 6)0.032(4, 14)0.03(19, 13)0.10(37, 5)0.073(9, 11)0.17(22, 8)0.26(31, 9)0.074(3, 11)0.20(15, 12)0.2(39, 14)0.235(13, 8)0.10(25, 2)0.23(31, 14)0.206(9, 0)0.23(21, 0)0.40(31, 2)0.137(6, 11)0.13(27, 5)0.23(40, 6)0.078(3, 13)0.03(19, 6)0.33(43, 12)0.309(10, 11)0.27(16, 14)0.16(39, 1)0.2710(0, 8)0.27(27, 3)0.10(39, 3)0.2311(10, 13)0.40(21, 5)0.13(34, 5)0.3012(3, 5)0.02(24, 11)0.10(33, 6)0.1013(0, 6)0.03(25, 5)0.26(39, 2)0.0714——(19, 1)0.20(36, 6)0.0715————(34, 6)0.23Then the data are loaded into the model to solve the task assignment above. The picking road map obtained is shown in Figure7.Figure 7
Route assignment map.


### 5.2. Algorithm Comparison

The experiments were implemented using Python 3.6, pycharm2019.1.3 of pytorch0.4.1, and the computer configuration used was: Intel(R) Core(TM) i5-6300U CPU@2.40 GHz, 2496Mhz, 22 cores, 41 logical processor, 4 GB of RAM, and a 64 bit of Windows 10. operating system.To analyze the effect of the proposed model, we choose three algorithms such as OR_ARC, OR_CHR, and PATH_CHEAPEST_ARC (PATH-ARC) from Google OR-Tools to perform the algorithm comparison analysis of length dimension and time dimension on the public dataset （Augerat standard dataset set A） . The datasets can be found at the URLhttps://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/download.Firstly, the advantages and disadvantages of the algorithm are evaluated from three aspects: the optimal distance dissociation of the example (best), the distance solution obtained by the algorithm model (min), and the error between the experimental solution and the optimal solution of the example (DEV%) (DEV = (min best)/best). The specific experimental results are shown in Table 4.Table 4
Comparison table of node algorithms.
InstanceBestPRLOR_CHRPATH-ARCOR_ARCMin (m)DEV (%)Min (m)DEV (%)Min (m)DEV (%)Min (m)DEV (%)1A-n32-k57847951.4088913.357870.378478.002A-n33-k56617046.5176115.076762.326924.653A-n33-k67427622.707430.207683.517916.624A-n34-k57998364.638405.178131.808789.905A-n37-k57307573.707908.2282212.657675.086A-n37-k68228634.9993113.258766.5992412.367A-n38-k58318633.858937.418573.0891910.568A-n39-k593710148.2210047.12104211.26105812.969A-n44-k7114611732.3612135.8111621.3812488.8910A-n45-k69149908.32103613.33104514.299837.5511A-n45-k7107311012.61125817.2411567.73122714.3112A-n46-k7101010998.81114713.55111910.7810362.6213A-n48-k7116711780.9412416.34129410.89133414.3414A-n53-k7140814563.41175724.81159613.35162315.2415A-n54-k7103511278.89115711.80124320.1110925.5416A-n55-k9129013746.51143411.16143110.9614149.6117A-n62-k8116812275.0512648.2412154.0111831.3018A-n63-k9176419168.62198712.6318957.4518565.2119A-n63-107847951.4088913.357870.378478.0020A-n64-k96617046.5176115.076762.326924.6521A-n65-k97427622.707430.207683.517916.6222A-n69-k97998364.638405.178131.808789.90Subsequently, in order to summarize the overall evaluation of each algorithm in the 22 group instances, four comparative analyses were performed in terms of the mean length of the algorithms, the total time, the mean DEV, and the standard deviation of the DEV, as shown in Table5.Table 5
Algorithm comparison table.
ProjectsDistance mean (m)Distance mean error rate (%)DEV mean valueDEV standard deviationTotal time (s)Best solution966.68000—PRL1015.095.014.852.600.7883OR_ARC1049.098.528.363.867.0147OR_CHR1071.7310.8710.395.695.8683PATH_ARC1038.237.406.845.466.8282As can be seen from Table5, compared with the three heuristics of ortools, PRL algorithm proposed in this paper is the closest to the exact solution from the perspective of distance and length. And, from the time dimension analysis, PRL algorithm has obvious advantages of parallel algorithm, shortens the time, and can be solved quickly.Then, this paper conducted significance tests for best solution and RL, OR_CHR, PATHARC, and OR_ARC, respectively, as shown in Table6.Table 6
Inter-subject effect test.
Dependent variable:BestSourceClass III sum of squaresDegree of freedomMean squareFSignificanceCorrection model1571745.414a4392936.3531772.1634.97709E-22Intercept distance534.7511534.7512.4120.138845022PRL14975.580114975.58067.5412.52493E-07OR_CHR4.48914.489.0200.888531759PATHARC305.1001305.1001.3760.256955406OR_ARC6074.52216074.52227.3966.7336E-05Error3769.35917221.727Total22133937.00022Total after correction1575514.77321a. R-squared = 0.998 (adjusted R-squared = .997).From Table6, it can be seen that the significance of the RL method and OR_ARC method is less than 0.05 and passes the level of the significance test, while the significance of the OR_CHR method and PATHARC method is bigger than 0.05 and does not pass the level of the significance test, given the significance of 5%. And, it can also be seen that there is a significant difference between the results obtained by the OR_CHR method and PATHARC method and Best solution, while there is no significant difference between the RL method and OR_ARC method and Best solution, and the difference between the RL method and Best solution is much smaller than the OR_AHC difference. It can be seen that the RL algorithm in this paper can solve the storage picking path problem well.Next, we analyzed the time and space complexity of the algorithm, and the results are shown in Table7.Table 7
Time complexity and space complexity.
AlgorithmTime complexitySpatial complexityOR_CHR—O1PATHARC—O1OR_ARC—O1PRLOn2dO1Table7 shows that the spatial complexity of both the heuristic algorithm and Transformer is O1, and the spatial complexity is the same. As for time complexity, Google’s ortools heuristic algorithm uses simulated annealing algorithm, which is based on probability and is a general optimization algorithm derived from the solid annealing principle. Theoretically, the algorithm has global optimization performance, so its complexity cannot be calculated. As a result, PRL’s time complexity is determined in comparison to heuristic algorithms, which use probabilistic algorithms and may keep iterating because the optimal solution is not found.As we all know, Google orTools is developed in C++, and its statements are executed much more efficiently than Python as a scripting language. However, according to the experimental data, the Google ortools heuristic algorithm developed by C++ has no advantage in computing time and optimal path length, and is obviously weaker than the PRL algorithm. Therefore, the PRL algorithm can be regarded as a good choice when solving the problem of warehouse routing.To sum up, although the average path length planned by the PRL method is slightly longer than the optimal solution accurately solved, it is closer to the optimal solution compared with the three heuristic algorithms of Google ortools. From the mean value of DEV, the error with the optimal solution is 5.1%. From the standard deviation of DEV, the error between the path length solved by the PRL method and the optimal solution is controlled within 7.45% with a probability of 0.8413, while the other three methods are 12.22%, 16.08%, and 12.3%, respectively. From the perspective of time dimension, PRL has strong parallel computing capability, and the solving time is 1/12 of Google OR_tools heuristic algorithm, or even shorter.


## 5.1. Example Simulation of Hybrid Real-Time Picking Mode

A picking center is arranged in a regional layout according to commodity items. There are multiple picking stations in the center. The AGVs are in a unified charging cache area, and they work together to complete picking. The intelligent warehouse is set to have 5 picking stations and 360 goods slots, and the demand for each task in each batch of order is less than 1. The quantity of AVG is not limited, which is enough to meet the assigned task of order picking.  In order to increase the complexity of the task and improve the universality of the algorithm, 13/14/15 picking order tasks are randomly generated according to the Poisson distribution adhered to at the time of order arrival. Since the distance between the CHARGING buffer of AGV and the picking point is too small compared with the total picking path of batch orders, the simulation experiment in this paper ignores the distance between the charging buffer of AGV and the first picking task point, and regards it as the AGV starting from the picking station and returning to the picking station when the loading capacity is insufficient. The relevant simulation data are shown in Table1. In order to display the distribution of data intuitively, it is drawn in the form of a scatter diagram, and the warehouse coordinate diagram is shown in Figure 6.Figure 6
Coordinate assignment chart.The calculation data of the picking station is shown in Table2and Table 3.The bold value in Table 2 indicates that under the conditions of comprehensively considering the idleness of the picking table and the distance from the center of gravity of the order to the picking table, we will select the optimal selection of the picking table entering the working state.Table 2
Picking table idleness and item order center of gravity distance.
Picking tableLocationVacancy rateDistance from the center of gravity of the first group of item ordersDistance to the center of gravity of the second group of item ordersDistance to the center of gravity of the third group of item ordersPicking table1(6, 17)0.69.7517.2231.77Picking table2(14, 17)0.313.3911.3524.42Picking table3(22, 17)0.5719.799.4617.65Picking table4(30, 17)0.427.0513.3412.44Picking table5(38, 17)0.534.6419.8611.22Table 3
Original data for picking nodes.
NumPicking stations 1Picking stations 3Picking stations 5CoordinatesDemandCoordinatesDemandCoordinatesDemand1(1, 9)0.13(27, 12)0.13(31, 6)0.032(4, 14)0.03(19, 13)0.10(37, 5)0.073(9, 11)0.17(22, 8)0.26(31, 9)0.074(3, 11)0.20(15, 12)0.2(39, 14)0.235(13, 8)0.10(25, 2)0.23(31, 14)0.206(9, 0)0.23(21, 0)0.40(31, 2)0.137(6, 11)0.13(27, 5)0.23(40, 6)0.078(3, 13)0.03(19, 6)0.33(43, 12)0.309(10, 11)0.27(16, 14)0.16(39, 1)0.2710(0, 8)0.27(27, 3)0.10(39, 3)0.2311(10, 13)0.40(21, 5)0.13(34, 5)0.3012(3, 5)0.02(24, 11)0.10(33, 6)0.1013(0, 6)0.03(25, 5)0.26(39, 2)0.0714——(19, 1)0.20(36, 6)0.0715————(34, 6)0.23Then the data are loaded into the model to solve the task assignment above. The picking road map obtained is shown in Figure7.Figure 7
Route assignment map.


## 5.2. Algorithm Comparison

The experiments were implemented using Python 3.6, pycharm2019.1.3 of pytorch0.4.1, and the computer configuration used was: Intel(R) Core(TM) i5-6300U CPU@2.40 GHz, 2496Mhz, 22 cores, 41 logical processor, 4 GB of RAM, and a 64 bit of Windows 10. operating system.To analyze the effect of the proposed model, we choose three algorithms such as OR_ARC, OR_CHR, and PATH_CHEAPEST_ARC (PATH-ARC) from Google OR-Tools to perform the algorithm comparison analysis of length dimension and time dimension on the public dataset （Augerat standard dataset set A） . The datasets can be found at the URLhttps://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/download.Firstly, the advantages and disadvantages of the algorithm are evaluated from three aspects: the optimal distance dissociation of the example (best), the distance solution obtained by the algorithm model (min), and the error between the experimental solution and the optimal solution of the example (DEV%) (DEV = (min best)/best). The specific experimental results are shown in Table 4.Table 4
Comparison table of node algorithms.
InstanceBestPRLOR_CHRPATH-ARCOR_ARCMin (m)DEV (%)Min (m)DEV (%)Min (m)DEV (%)Min (m)DEV (%)1A-n32-k57847951.4088913.357870.378478.002A-n33-k56617046.5176115.076762.326924.653A-n33-k67427622.707430.207683.517916.624A-n34-k57998364.638405.178131.808789.905A-n37-k57307573.707908.2282212.657675.086A-n37-k68228634.9993113.258766.5992412.367A-n38-k58318633.858937.418573.0891910.568A-n39-k593710148.2210047.12104211.26105812.969A-n44-k7114611732.3612135.8111621.3812488.8910A-n45-k69149908.32103613.33104514.299837.5511A-n45-k7107311012.61125817.2411567.73122714.3112A-n46-k7101010998.81114713.55111910.7810362.6213A-n48-k7116711780.9412416.34129410.89133414.3414A-n53-k7140814563.41175724.81159613.35162315.2415A-n54-k7103511278.89115711.80124320.1110925.5416A-n55-k9129013746.51143411.16143110.9614149.6117A-n62-k8116812275.0512648.2412154.0111831.3018A-n63-k9176419168.62198712.6318957.4518565.2119A-n63-107847951.4088913.357870.378478.0020A-n64-k96617046.5176115.076762.326924.6521A-n65-k97427622.707430.207683.517916.6222A-n69-k97998364.638405.178131.808789.90Subsequently, in order to summarize the overall evaluation of each algorithm in the 22 group instances, four comparative analyses were performed in terms of the mean length of the algorithms, the total time, the mean DEV, and the standard deviation of the DEV, as shown in Table5.Table 5
Algorithm comparison table.
ProjectsDistance mean (m)Distance mean error rate (%)DEV mean valueDEV standard deviationTotal time (s)Best solution966.68000—PRL1015.095.014.852.600.7883OR_ARC1049.098.528.363.867.0147OR_CHR1071.7310.8710.395.695.8683PATH_ARC1038.237.406.845.466.8282As can be seen from Table5, compared with the three heuristics of ortools, PRL algorithm proposed in this paper is the closest to the exact solution from the perspective of distance and length. And, from the time dimension analysis, PRL algorithm has obvious advantages of parallel algorithm, shortens the time, and can be solved quickly.Then, this paper conducted significance tests for best solution and RL, OR_CHR, PATHARC, and OR_ARC, respectively, as shown in Table6.Table 6
Inter-subject effect test.
Dependent variable:BestSourceClass III sum of squaresDegree of freedomMean squareFSignificanceCorrection model1571745.414a4392936.3531772.1634.97709E-22Intercept distance534.7511534.7512.4120.138845022PRL14975.580114975.58067.5412.52493E-07OR_CHR4.48914.489.0200.888531759PATHARC305.1001305.1001.3760.256955406OR_ARC6074.52216074.52227.3966.7336E-05Error3769.35917221.727Total22133937.00022Total after correction1575514.77321a. R-squared = 0.998 (adjusted R-squared = .997).From Table6, it can be seen that the significance of the RL method and OR_ARC method is less than 0.05 and passes the level of the significance test, while the significance of the OR_CHR method and PATHARC method is bigger than 0.05 and does not pass the level of the significance test, given the significance of 5%. And, it can also be seen that there is a significant difference between the results obtained by the OR_CHR method and PATHARC method and Best solution, while there is no significant difference between the RL method and OR_ARC method and Best solution, and the difference between the RL method and Best solution is much smaller than the OR_AHC difference. It can be seen that the RL algorithm in this paper can solve the storage picking path problem well.Next, we analyzed the time and space complexity of the algorithm, and the results are shown in Table7.Table 7
Time complexity and space complexity.
AlgorithmTime complexitySpatial complexityOR_CHR—O1PATHARC—O1OR_ARC—O1PRLOn2dO1Table7 shows that the spatial complexity of both the heuristic algorithm and Transformer is O1, and the spatial complexity is the same. As for time complexity, Google’s ortools heuristic algorithm uses simulated annealing algorithm, which is based on probability and is a general optimization algorithm derived from the solid annealing principle. Theoretically, the algorithm has global optimization performance, so its complexity cannot be calculated. As a result, PRL’s time complexity is determined in comparison to heuristic algorithms, which use probabilistic algorithms and may keep iterating because the optimal solution is not found.As we all know, Google orTools is developed in C++, and its statements are executed much more efficiently than Python as a scripting language. However, according to the experimental data, the Google ortools heuristic algorithm developed by C++ has no advantage in computing time and optimal path length, and is obviously weaker than the PRL algorithm. Therefore, the PRL algorithm can be regarded as a good choice when solving the problem of warehouse routing.To sum up, although the average path length planned by the PRL method is slightly longer than the optimal solution accurately solved, it is closer to the optimal solution compared with the three heuristic algorithms of Google ortools. From the mean value of DEV, the error with the optimal solution is 5.1%. From the standard deviation of DEV, the error between the path length solved by the PRL method and the optimal solution is controlled within 7.45% with a probability of 0.8413, while the other three methods are 12.22%, 16.08%, and 12.3%, respectively. From the perspective of time dimension, PRL has strong parallel computing capability, and the solving time is 1/12 of Google OR_tools heuristic algorithm, or even shorter.


## 6. Conclusion

With the rapid development of the Internet of Things technology, optimize the warehouse management system, establish and improve the intelligent picking system, for unmanned, intelligent transformation is the key direction of reform and development of e-commerce enterprises, courier enterprises.This thesis addresses the picking path planning problem of multiple picking stations in a warehouse in a zoned area, and designs a PRL algorithm using placeholder control to solve the path optimization problem in a shared mode where the number of picking orders is unequal and the picking stations do not need to work synchronously, taking into account two factors: the idleness of the picking stations and the distance of the center of gravity of the order items. The simulation results have shown that the PRL algorithm in this paper is very close to the optimal solution and far better than the three heuristic algorithms of Google’s ortools in terms of solving accuracy. In terms of solving speed, it has the advantage of fast solving and can almost realize real-time solving. In the dimension of structure, it has the advantage of variable input and avoiding retuning. Therefore, this method is very effective to solve the problem of multiple picking stations with different order numbers in intelligent warehouse. It can solve the picking path effectively and reduce the picking cost [23].


## 7. Outlook

This paper focuses on the picking center intelligent AGV picking path planning problem, cleverly converting the MDVRP problem into a CVRP problem by two-stage method, and designing an improved Transformer algorithm for path planning, thus realizing real-time picking in picking centers with improved picking efficiency compared to traditional methods. Meanwhile, this paper can be promoted for scenarios such as UAV take-out delivery, port container loading and unloading, and logistics distribution. Since this paper is carried out without considering the limitation of AVG number of picking centers, the following research direction is the optimal path planning of picking centers under the constraint of AVGs’ number.



---

*Source: 5510749-2022-04-06.xml*