ABSTRACT

This paper aims to optimize the “Parts to Picker” picking system with order sorting and AGV path planning as its priorities according to AGV-based “Parts to Picker” sorting mode and the order picking procedures. And this paper builds an intelligent order batching model with the minimum number of AGV handling shelves as the objective function. In addition, this paper also introduces the concept of order proximity coefficient, realizes reasonable and effective batching of orders. Based on the results of the order batching, this paper presents a goods-picking list in the target shelves after collecting various order batches, and proposes a TSP-based and “S-type” shelves handling strategy. In addition, this paper builds a path planning model with the shortest AGV total handling distance. The path planning under multiple AGVs parallel situation is realized. Finally, this paper proves the efficiency of AGV path planning strategy based on the results of orders batching by listing practical examples from enterprise.

Keywords:

AGV, Picking Mode, Order Proximity, Path Planning

1. Introduction

The so-called “Parts-to-Picker” picking system is simply understood as the logistics distribution center in order picking operations, through the new type of automated logistics equipment to transport the target shelf to a fixed picking table, by the staff manually picking orders, that is, “moving parts, pickers do not move”. The “Parts-to-Picker” sorting mode mainly includes the “Parts-to-Picker” sorting system constructed by using AGV (Automated Guided Vehicle system) and the “Parts-to-Picker” sorting system constructed by using shuttle vehicles in three-dimensional automated warehouse. The object of this paper is the first kind of “Parts-to-Picker” sorting mode.

AGV (Automated Guided Vehicle) is an automatic tractor in Chinese. AGV is mainly powered by batteries. Usually, guided by one or several combinations of electromagnetic, optical and laser navigation technologies, it moves along the planned route. In practical application, AGV is mainly responsible for various handling functions. It is a new type of horizontal logistics handling facility. The physical diagram of AGV is shown in Figure 1.

Compared with the traditional sorting mode, the “Parts-to-Picker” sorting mode has the advantages of high picking efficiency, high storage density, reduced labor intensity, labor cost saving and logistics cost saving. The sorting mode is suitable for dealing with multiple varieties and less batches of e-commerce orders. The sorting mode is gradually applied to the logistics fields of e-commerce, medicine, cold chain, clothing, food and so on [1] .

However, due to the immature development of the “Parts-to-Picker” sorting mode in China, there is no unified industry standard and effective optimization measures in the process of order picking. In the picking process of the distribution center, there are some problems such as long picking path of AGV trolley and repeated picking paths [2] . In order to improve the operation efficiency of the “Parts-to-Picker” sorting mode, there are still many problems to be studied urgently, for example, research on order batching method of “Parts-to-Picker” sorting mode, AGV path planning, task allocation of AGV, storage space allocation of “Parts-to-Picker” warehouse, etc. Through the joint optimization of this series of links, the operation efficiency of the whole warehouse can be effectively improved and the order picking time can be shortened. However, the existing studies only focus on a certain link and do not consider the optimization of the mode of “Parts-to-Picker” sorting from a relatively holistic perspective. Therefore, in order to improve the operation efficiency of “Parts-to-Picker” sorting mode from multiple links, this paper focuses on the path planning of order batch based on “Parts-to-Picker” sorting mode. Through the reasonable batching of orders, and based on this, the path planning of AGV is carried out, in order to find an effective way to improve the efficiency of the “Parts-to-Picker” sorting mode.

2. Research Status

In recent years, with the increasing importance of sorting efficiency in distribution centers, people are paying more and more attention to the picking mode of “Parts-to-Picker”. Dallari F (2009) concluded that the sorting system can be divided into two types: the “Parts-to-Picker” and “Picker-to-Parts” by analyzing the operation process of the sorting system in several distribution centers. Faced with the characteristics of multi-item, large-scale orders and high requirement for the timeliness of order completion in current e-commerce enterprises, the “Parts-to-Picker” sorting operation mode can more effectively complete the task of order sorting [3] . L. Xu (2017) and others based on AGV of e-commerce logistics, studied the “Parts-to-Picker” sorting mode, established the storage allocation model based on the lowest picking cost, and realized the design of storage allocation algorithm based on similarity coefficient clustering analysis. The validity of the design of storage allocation algorithm is verified by an example [4] .

In the aspect of AGV scheduling, X. Shao (2016) and others proposed a multi-objective compound AGV scheduling system model based on driving distance, task waiting time and task priority. A* algorithm is used to design the shortest path search strategy to improve the efficiency of AGV task execution [5] . Suyun Zhang et al. (2017) set up an optimal control model considering AGV path capacity, safe distance, travel time and AGV speed, aiming at the possible path conflicts during transportation. The problem of AGV path conflict is effectively solved [6] . Zhiwei Wang (2014) [7] and Zheng Li (2014) [8] studied the “Parts-to-Picker” picking system based on AGV, and discussed the picking system of “Parts-to-Picker” from the overall layout of the system, warehouse storage allocation, order collection and processing system, control system and other aspects.

The order batch of “Parts-to-Picker” picking mode is very important for the whole picking process. MC Chen et al. (2005) designed a batch processing method for orders using data mining and integer programming. It is also found that the important links between orders are valuable [9] . CH Pan (2015) proposes a batch processing method based on group genetic algorithm. It has a certain optimization effect in balancing the workload of each sorting area and reducing the batch number in sorting system [10] . Yingying Wu (2016) and others put forward an order sequencing optimization model in order to reduce the frequency of container entry and exit. An improved K-Means clustering algorithm is proposed to distribute and sort orders for each picking station, which improves the picking efficiency [11] .

In the aspect of picking path optimization, Pratik J Parikh (2010) and others take the shortest picking path as the goal, and consider the operation time, study the multi-objective picking path optimization problem [12] . Fei Ma (2016) establishes a mathematical model with the objective of minimum the total picking path on the basis of the order batch problem, and designs an optimization method combining hybrid particle swarm optimization algorithm with heuristic strategy [13] . Li G. et al. (2017) proposed an improved artificial fish swarm algorithm based on differential evolution, which has good convergence speed, optimization accuracy and stability in solving global path planning problems [14] .

The existing AGV “Parts-to-Picker” sorting mode mainly studies storage allocation, AGV scheduling and related hardware equipment development. The optimization of picking path mainly focuses on the improvement of related algorithms, and does not consider the impact of order batch strategy on the results of path optimization, so the optimization results often cannot maximize the efficiency of the “Parts-to-Picker” picking mode. Therefore, it is of great practical significance and scientific research value to study the AGV path of order batch based on “Parts-to-Picker” mode for improving warehouse operation efficiency and reducing operation cost.

3. Study on Batch Order Scheme

The common order batching strategies in practical applications include aggregate metering batching, fixed order quantity batching, time window batching and intelligent batching. According to the different warehouse layout and order composition, the applicability of various batch methods is different.

In this paper, an intelligent batch method based on order proximity is used to batch orders according to order proximity, also known as order-related batching. This method of batching is mainly based on the relationship between orders. The more goods needed for two orders are located on the same shelf, the more shelf handling times saved by merging and sorting these orders. According to this rule, orders with high correlation are divided into batches. AGV trolley will complete the task of picking multiple similar orders at the same time with the least number of shelf handling times in the picking process, effectively reducing the repeated handling of the same shelf, thereby reducing the total handling distance of AGV, greatly improving the efficiency of warehouse sorting and saving a lot of resources.

3.1. Proximity Coefficient

In this paper, the measurement method of the correlation between orders is defined as the similarity coefficient between orders. Xiaojie Li summarized the commonly used methods for calculating similarity coefficient, such as Cosine Similarity, Pearson Correlation Coefficient and Jacquard Index [15] . Xingfu Wang and others have proved that cosine similarity can well reflect the internal changes of the set, and can be used to measure the similarity of samples [16] . Xiaolin Zhang introduced Jacquard similarity measure into the collaborative filtering system of goods, and established the corresponding evaluation and analysis method, which overcomes the drawback that cosine similarity only considers user ratings and ignores other information, and is especially suitable for the application of data with too high sparsity [17] .

Through the collation of relevant literature, this paper uses Jacquard coefficient to measure the correlation between orders. Because of the high sparsity of e-commerce orders, Jacquard coefficient can effectively measure the similarity and difference between orders, which can truly reflect the similarity between two orders, and ignore the length of the order. The value range of Jacquard coefficient is between [0, 1]. Specifically, it can be expressed as: for two different orders A and B. Among them, order A contains m kinds of goods, order B contains n kinds of goods, U_A represents the set of target shelves of distribution of goods contained in order A, and U_B represents the set of target shelves of distribution of goods contained in order B. Then the proximity coefficient of the two orders can be expressed as follows:

$J\left(A,B\right)=\frac{\left|U_A\cap U_B\right|}{\left|U_A\cup U_B\right|}$ (3-1)

According to the definition of order proximity. If the target shelves of the distribution of goods required by Order A and Order B are not intersected, that is $U_A\cap U_B=0$ , then $J\left(A,B\right)=0$ . On the contrary, if the target shelf of the distribution of goods required by order A and order B is exactly the same, that is $U_A\cap U_B=U_A\cup U_B$ , then $J\left(A,B\right)=1$ . Therefore, when order A and order B only have the same target shelf distribution of some commodities, $0<J\left(A,B\right)<1$ .

3.2. Basic Hypothesis and Symbol Definition

In order to reduce the influence of some unimportant factors on the research, the following assumptions are made:

1) Each order contains at least one kind of goods;

2) Each order can only be sorted in one batch, and cannot be sorted by decomposition;

3) All kinds of goods in the same batch of orders can be picked through one-time shelf handling, without considering the shortage of goods;

4) Regardless of the order queue insertion problem, the picking desk will not start the next batch until it has completed all the picking tasks in the current batch;

5) The warehouse layout is known, the order information is known, and the storage space of the order items on the shelf is known;

6) Each commodity corresponds to a location in the warehouse.

Meanwhile, in order to describe the model clearly, the following parameters are defined.

Q represents the total number of orders to be picked out of the warehouse;

M represents the total number of items included in all orders to be selected;

N represents the total number of shelves distributed for items of the order to be picked;

T represents the total number of times the shelves are moved;

X_i represents the number of times shelf “I” has been moved;

c represents the number of turnover shelves per picking table;

k represents the number of storage places set for each turnover shelve;

p represents the number of batches to be allocated for the order to be picked;

$D_{ip}=\{\begin{array}{l}1,\text{shelf}i\text{was moved in batch}p\\ 0,\text{shelf}i\text{was not moved in batch}p\end{array}$

$G_{jp}=\{\begin{array}{l}1,\text{order}j\text{is assigned to batch}p\text{sorting}\\ 0,\text{order}j\text{is not assigned to batch}p\text{sorting}\end{array}$

3.3. Model Establishment

Objective function:

$\min T={\displaystyle \sum _{p=1}^P{\displaystyle \sum _{q=1}^Q{X}_i\ast D_{ip}}}$ (3-2)

Constraint condition:

${\displaystyle \sum _{p=1}^P{G}_{jp}}=1$ (3-3)

$X_i\ast D_{ip}\le 1$ (3-4)

${\displaystyle \sum _{j=1}^Q{G}_{ip}}\le c\ast k$ (3-5)

$i=1,2,\cdots ,N$ (3-6)

$j=1,2,\cdots ,Q$ (3-7)

$p=1,2,\cdots ,P$ (3-8)

Among them, formula (3-2) is the objective function, which means the minimum total number of times that AGV trolley carries out all sorting tasks, (3-3) means that each order can only be allocated to one order batch, that is, it is not allowed to split the order picking. Formula 3-4 indicates that the same batch can be transported to a certain shelf at most once, that is, the number of orders is not considered, and the secondary transportation caused by the shortage problem is not considered. Formula (3-5) indicates that the number of orders in each batch should not exceed the total storage number set by the picking desk after the order is divided into batches. (3-6), (3-7) and (3-8) represent the range of values of variables i, j and p, respectively.

4. Research on AGV Path Planning Based on Order Batching

4.1. Path Analysis of AGV in Picking Process

The path planning of AGV is one of the important links that affecting the efficiency of the whole “Parts-to-Picker” picking system. As the shuttle handling of AGV car in warehouse has replaced manual picking, the efficiency and time-consuming of AGV car in warehouse has become the focus of attention. The operation process in the warehouse can be described as: AGV trolley starts from the initial position, carries the target shelf to the picking table according to the tasks specified by the system, picks the required goods by the staff, and then AGV returns the shelf to the initial position of the shelf, and runs to the next target shelf allocated by the system to carry the task, repeating the process until all the picking tasks for the batch order are completed. The operation of AGV in the warehouse is shown in Figure 2. For the same batch of orders, there are usually two kinds of operations: one is picking by an AGV car, the other is picking by multiple AGV cars at the same time.

4.2. Shelf Handling Order Strategy

In this paper, the “Parts-to-Picker” system is responsible for the handling of shelves by multiple AGV cars, which belongs to a special multi-traveler problem MTSP (multiple travel salesman problem). The problem of MTSP is the process of starting from the same city by multiple travel agents, and they return to the starting city by visiting different cities [18] . Compared with the multiple travel salesman problem, AGV car not only moves between shelves, but also includes the roundtrip process from the target shelf to the picking table. However, in the case of specific warehouse layout and road network design, the distance between the target shelf and the picking table is a definite value. Therefore, in order to achieve the shortest goal of the total handling path, it is necessary to determine a reasonable shelf handling order. This paper mainly uses the following two kinds of handling strategies: shelf handling sequence based on TSP and “S” type shelf handling sequence.

In order to make the AGV run the shortest distance between the target shelves, we can learn from the solution of the TSP problem and determine an optimal shelf picking order from any target shelf, so that the AGV runs the shortest distance

between the shelves. The scheduling system assigns tasks to each AGV in turn to complete the sorting task, A schematic diagram of determining the shelf handling sequence based on the TSP concept is shown in Figure 3.

The “S” type of shelf handling strategy is a strategy for picking goods in the warehouse by the picker in the traditional “Arrival of man” picking mode. According to the distribution of the target shelves in the warehouse in the picking list, the target shelves are sequenced from one end of the shelf to the next row of shelves, and the order of the shelves is determined in turn. The order of the shelves is shown in Figure 4. Because the route of AGV car running between shelves is similar to “S” shape, it is defined as “S” type shelf handling strategy.

4.3. AGV Path Planning Model Based on Order Batch

1) Symbol Definition:

For the convenience of modeling and calculation, the following parameters are defined in the model:

D represents the total driving path length of all AGV cars;

N is the total number of shelves to be moved for each batch of orders, $N=1,2,\cdots ,n$ ;

M is the total number of picking stations, $M=1,2,\cdots ,m$ ;

C is the number of AGV cars, $C=1,2,\cdots ,c$ ;

T represents the total number of batches divided by order;

$x_{nc}=\{\begin{array}{l}1,\text{Shelf}n\text{is handled by trolley}c\\ 0,\text{ifnot}\end{array}$

$d_{\left(n,n+1\right)}$ represents the distance of the AGV car from shelf n to the next target shelf;

$d_{\left(0,n1\right)}$ represents the distance of the AGV from the initial position to the first target shelf;

$d_{\left(nN,0\right)}$ represents the distance from the last target shelf to the initial position of the AGV car;

$d_{\max }$ represents the longest distance of all AGV picking paths;

$d_{\min }$ represents the shortest distance of all AGV picking paths;

$d_{\left(n,m\right)}$ represents the distance from the target shelf n to the picking table m of the AGV trolley.

2) Establishment of AGV Path Planning Model:

Objective function:

$\min D={\displaystyle \sum _{t=1}^T\left({\displaystyle \sum _{c=1}^C\left(d_{\left(0,n1\right)}+d_{\left(nN,0\right)}\right)\ast x_{nc}}+{\displaystyle \sum _{c=1}^C{\displaystyle \sum _{n=1}^N{d}_{\left(n,n+1\right)}\ast x_{nc}}}+2\ast {\displaystyle \sum _{c=1}^C{\displaystyle \sum _{n=1}^N{d}_{\left(n,m\right)}\ast x_{nc}}}\right)}$ (4-1)

Constraint condition:

${\displaystyle \sum _{c=1}^C{\displaystyle \sum _{n=1}^N{x}_{nc}}}$ (4-2)

${\displaystyle \sum _{n=1}^N{x}_{nc}}\le \frac{N}{2}$ (4-3)

$d_{\max }-d_{\min }<L$ (4-4)

The formula (4-1) indicates that the total path of all the AGV trolleys from the starting position to the loading of the rack to the return of the rack back to the starting position is the shortest. Among them:

${\displaystyle \sum _{c=1}^C\left(d_{\left(0,n1\right)}+d_{\left(nN,0\right)}\right)}\ast x_{nc}$

represents the total driving distance of all AGV cars from the initial position to the first target shelf and from the last target shelf to the initial position; Form ${\displaystyle \sum _{c=1}^C{\displaystyle \sum _{n=1}^N{d}_{\left(n,n+1\right)}}}\ast x_{nc}$ denotes the driving distance of all AGV cars between shelves. Form $2\ast {\displaystyle \sum _{c=1}^C{\displaystyle \sum _{n=1}^{N_t}{d}_{\left(n,m\right)}}}\ast x_{nc}$ denotes the round trip distance of the AGV from the target shelf to the picking table. Formula 4-2 indicates that a batch order with the same shelf can only be moved once at most. Formula (4-3) means that in order to balance the task allocation of the car, the number of shelves carried by a single AGV car should not be greater than half of the total number of shelves. Formula (4-4) indicates that the difference between the longest distance $d_{\max }$ and the shortest distance $d_{\min }$ of the AGV carriage shelf in the same batch cannot be greater than a given value L.

5. Example Analysis

This paper takes the “Parts-to-Picker” warehouse of a regional distribution center of a domestic e-commerce enterprise as the research background. The main business of the warehouse is to store all kinds of goods in the region, and to select and distribute goods for customers in the region. The warehouse of the distribution center is 120 meters long, 50 meters wide and 24 meters high. It consists of two parts. The left side is the warehouse area. It is mainly used to store various items of goods, and to replenish goods for the v sorting area in time. On the right is the sorting area, which is mainly responsible for sorting, packaging and distribution of orders. In order to facilitate the study of the problem, the “Parts-to-Picker” sorting area was rasterized. As shown in Figure 5, the layout of the sorting area for the “Parts-to-Picker” warehouse is shown. There are several areas in the warehouse, such as goods storage area, storage area, outbound area, outbound buffer area and charging/storage area. The overall layout of the

warehouse is reasonable, each functional area is closely linked, and the warehouse area is reasonably utilized. In the warehouse, only the forklift is set up in the storage area, which is responsible for transporting the goods stored on the left side of the warehouse to the storage area of the sorting area for replenishment. The rest of the handling tasks are carried out by the AGV. There are 4 rows × 10 column × 6 shelves × 5 floors × 4 cargo Spaces = 4800 cargo Spaces in the sorting area. Each picking desk has 20 storage spaces on its turnover shelf, so the upper limit is 20 orders in batches.

5.1. Batch Processing of Orders

Because of the large number of orders that need to be processed in a cycle of the distribution center, 118 orders collected by the system in a certain period of time are randomly selected for case analysis. In this paper, the order batching strategy proposed in this paper is based on the shelves distributed by the order demand commodities. Therefore, the collected order data need to be preprocessed, and the items of each order need to be transformed into the corresponding shelves. The original order data and the processed data are shown in the appendix.

In order to verify the validity of the order proximity batching strategy proposed in this paper, the batch order is processed in batches using the order non-batch strategy and the fixed order quantity batching strategy. The order batch results are shown in Table 1.

Through the analysis of batch results, it can be concluded that the number of AGV shelves can be effectively reduced by batch processing of orders. Compared with the non-batch sorting, the fixed order batch strategy saves 24.9% of the average number of shelf handling, and the intelligent order batch strategy based on order proximity saves 43.6% of the average number of shelf handling compared with the non-batch sorting strategy. Compared with the non-batch order strategy, the two batch strategies can greatly save the number of shelves transported by AGV. However, the intelligent batch strategy based on order proximity considers the relationship between orders. Comparing the two batch strategies, it can be found that the batch strategy based on order proximity saves 24.9% of the shelf handling times compared with the fixed order batch strategy. Therefore, the validity of the proposed intelligent batch strategy based on order proximity is verified.

5.2. AGV Path Planning

Based on the results of different batch strategies, according to the two shelf handling strategies proposed in 4.1.2, the order of picking for each group of order target shelves is established, and the shelf list based on TSP and S-type shelf list are obtained respectively. Based on these two transport strategies, AGV picking path is planned and the total distance of AGV shelves under the two transport strategies is counted. The calculated results are shown in Table 2 as the results of AGV path planning with different order batching methods and different picking strategies.

The results show that the order allocation strategy based on order proximity and TSP shelf picking strategy can save 3888 grids and 23.7% compared with the traditional picking strategy; Compared with the traditional picking strategy, the order distribution strategy based on order proximity and the “S” type picking strategy saved 3877 grids, with a saving ratio of 24.7%. Under the same order batch strategy, “S” type shelf picking strategy is slightly better than TSP-based shelf picking strategy. Route savings rate is about 5.5%.

Through the analysis of the calculation results, batch processing based on order proximity can effectively reduce the number of AGV shelves. Based on the results of order batch, the path planning of AGV car shortens the total picking distance of AGV car, and greatly improves the efficiency of the whole picking system of “Parts-to-Picker”.

This paper takes the “Parts-to-Picker” warehouse of a regional distribution center of a domestic e-commerce enterprise as the research background. The problem of order batching and AGV path planning in the distribution center is studied. Selecting part of the order information of the distribution center, using the order batching method based on order similarity coefficient proposed in this paper, and based on the order batching results, two shelf picking strategies are adopted to plan the picking path of AGV. It is solved by the designed intelligent algorithm. By comparing with the results of traditional methods, it can be concluded that the optimization method proposed in this paper can significantly improve the efficiency of the AGV-based “Parts-to-Picker” picking system.

6. Conclusion

With the development of automation and informationization, the number of orders has increased dramatically, and the importance of order sorting has become increasingly prominent. The selection mode of “Parts-to-Picker” based on AGV has attracted more and more attention from various industries. In order to explore ways to improve the picking efficiency of the “Parts-to-Picker” picking mode, this paper focuses on order batching and AGV path planning under the “Parts-to-Picker” picking mode. Through the joint optimization of different order batching strategies and path planning methods, this paper deeply studies the impact of each link on the efficiency of the “Parts-to-Picker” sorting system, and provides a method to improve the efficiency of the “Parts-to-Picker” sorting system.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

Cite this paper

Liu, J.-E., Zhang, S.J. and Liu, H.L. (2019) Research on AGV Path Planning under “Parts-to-Picker” Mode. Open Journal of Social Sciences, 7, 1-14. https://doi.org/10.4236/jss.2019.76001

References