Order Batching Optimization in Dual Zone Type Warehouse Based on Genetic Algorithms
Jie Zhu, Hong Zhang, Li Zhou, Jian Guo
School of Information, Beijing Wuzi University, Beijing, China
To cite this article:
Jie Zhu, Hong Zhang, Li Zhou, Jian Guo. Order Batching Optimization in Dual Zone Type Warehouse Based on Genetic Algorithms. Science Journal of Business and Management. Vol. 3, No. 3, 2015, pp. 77-81. doi: 10.11648/j.sjbm.20150303.13
Abstract: With the rapid development of e-commerce and the global economy, order picking mode of multiple batches and small quantities becoming more and more, which makes artificial picking system occupy a larger proportion in a variety of ways. The optimization study of the artificial person picking system has a crucial role to enhance the efficiency of batch picking, then increasing customer satisfaction. In this paper, according to the characteristics of the problem, Genetic algorithm was selected as the model's algorithm. The detailed design of coding, crossover method, genetic algorithm in solving process variation method, is used to realize the optimization of the model.
Keywords: Manual Order Picking System, Order Batching, Genetic Algorithm
The order batching problem expressed in mathematical language is the order needs to be chosen by the right way to carry on the batch, And through the calculate and determine the picking order so that to solve the objective function to achieve the optimal. Usually, the model has two objectives1-2: to reduce the walking distance in the selection process or walking time. The chosen time walking and walking distance is linear correlation relationship, Choose distance directly determines the walking time in the selection process. This chapter based on the shortest distance as the objective function of the order batching model. and Design genetic algorithm of order batching problem. The reason that the application of genetic algorithm is a batch order has been proved to be NP problem, through accurate calculation method is difficult to obtain the optimal solution of the problem, And the common optimization algorithm has limitations in the optimization of efficiency, it is difficult to be accepted within the scope of the time to find the optimal solutions to the problem, Therefore, it is necessary through an intelligent algorithm to solve the target3.
There are 3 Levels titles in an article to make ideas clear:
(1)Order picking model preparation
(2)Order picking model establishment
(3)Design of the Genetic Algorithms
2. Order Picking Model
2.1. Model Preparation
Distribution center is studied in this paper by artificial picking. Distribution center is labor-intensive. Each picker is picking by operating equipment. There are a number of turnover box on each picking equipment, and for each turnover box, there is only one order products. So you can avoid a second sorting process. Picker will directly put turnover box in the export warehouse after he has been completed pick.
For the convenience of analysis and calculation, we make some basic assumptions before modeling.1
(1) distribution center storage area is made up of parallel arrangement of shelves. warehouse-type is dual-zone warehouse, unlike the previous single-area warehouses for scholars. Dual-zone warehouses are more widely available in a large warehouse. The content of this research can be applied to multiple-zone warehouse. The layout structure is shown in Figure 1.
(2) number of picking person or picking device for at least one. In previous study, picking people or picking device is set on the amount of a single, in actual operation, there can be multiple selected devices in select situations at the same time, therefore, in this study, the selected devices are not doing quantity requirements, and that will be more in line with the actual circumstances.
(3) ignore the shelf height displacement. in the case of multiple shelves, Displacement in vertical direction are not included in the picking path. No matter what the picking strategy we take, the displacement is unable to reduce. It is a fixed value and therefore are not included in the calculation of the chosen path.
(4) each order contains at least one kind of product.
(5) the order is not allowed to split into different picking batches, but in the same picking batches, the same order of goods can be assigned to different person to pick.
(6) the picking orders of each batch are picked by N pickers or picking device at the same time, picking up a batch after batch of the next election.
(7) different selection devices with the same capacity limits and load limits.
(8) the total volume and the total weight of all the goods of each batch picking order cannot exceed the total volume and weight of all selected devices limit in the picking batch.
(9) the capacity and quality of individual items must not exceed the capacity and quality constraints of the individual picking device, that is to say, picking equipment can picking any goods in the warehouse.
(10) there is no out of stock and emergency insertion order status.
(11) the picking list goods storage position are known.
(12) the walking paths in the selection process is improved s-type strategies.
2.2. Model Establishment
is on behalf of total number of orders.
is on behalf of the number of picker or picking equipment.
is on behalf of orders.
is on behalf of the weight of goods in the order n of the batch k.
is on behalf of the volume of goods in the order n of the batch k.
is on behalf of the first k picking batch.
is the number of batches
is on behalf of the cargo capacity ability of picking equipment m
is on behalf of the cargo quality ability of picking equipment m
is the total number of paths
T is chosen paths j in choose batch k.
is the total distance walked according to the chosen path .
means in the k-th selected batch, walking distance between goods x and goods y.
is the decision variables to decided whether the goods y is immediately chose after sorting equipment finished goods x in the first k batch picking .
is the decision variables to decided whether the order list n in the picking batches k.
is the decision variables to decided whether the order list n in the picking path j.
is the number of goods a and goods b.
is the types of goods.
(1) is the objective function of the model. the purpose of model is to make the total path shortest. Formula (2) represents all the goods volume are not more than the maximum capacity of picking car. Formula (3) represents the quality of all of the goods does not exceed the maximum loading capacity of picking car. Constraints (2) and (3) is the corresponding model assumes that the eighth rules. Constraint (4) shows that in any one order, The number of picking path cannot exceed the number of picking equipment. Formula (5) represents each order can only be divided in a batch. Which is the corresponding model assumes that the fifth rules. Constraints (6) show that in an arbitrary picking batches, the number of chosen path is equal to the number of sorting equipment, The decision variables (7) showed that when order n is included in the batch k, the value is 1, otherwise the value is 0.The decision variables (8) showed that when order n is included in the path j, the value is 1, otherwise the value is 0.Decision variables (9) indicate whether the goods x and y are chosen in a row, if it is in the same batch in the same path next to the selection, the value is 1, otherwise the value is 0.
3. Design of the Genetic Algorithms
The design of order batching problem solving steps according to the genetic algorithm4-5 is as follows:
3.1. The Chromosome Coding Design
In the order batching problem, the order is called a gene, all orders are combined into one chromosome, and each chromosome represents the order batching problem a feasible solution.
Due to the large number of orders, in order to be able to express the solution of the problem by chromosome intuitively, the paper based on the floating-point encoding method. The encoding can be expressed as:
By encoding operating to all orders in the order collection, we regard the state of each order in each batch of each vehicle as a gene, and all order status collection form a chromosome. Since the design of the model involves multiple batches and multiple picking equipment, the designed gene should be able to represent order batch and order picking equipment information, or cannot be converted into the corresponding solution space of the chromosome. So for the selection of y value is the form of a-b, where a represents the order batches, and b represents the order picking equipment. For example, a chromosome coding:
The chromosome means: each number position in sequence represents the order number, such as 1-2 in the first place, it represents the order whose coding is 1 in its collection. 2-1 represents the order whose coding is 2.and so on a-b represents the coding order n. Which the number 1-2 represents order in this position is assigned to the first batch of the second picking device; and the number 2-1 represents order in this position is assigned to the second batch of the first picking device. And so on. The middle separator "-" is in order to facilitate the computer recognition of different batches and sorting equipment, through this code, there are multiple picking equipment order batching problem can be mapped to the GA for solving space.
In order batching process, always regard no more than picking equipment selection ability as constraints in batching, and the limit will join in the process of programming. We are not repeating them back.
3.2. The Population Size Design
In the design of the parameters chro, if the population is too small, the genetic algorithm is likely to converge to the local optimal solution, not to converge to the optimal solution. The main reason is that population size is too small, will lead to a decrease in the diversity of the population, leading to meaningful searches and the most advantage is lost. On the contrary, if the size of the population is set too large, the calculation needed in each iteration process will become very large, result in the slow, which will affect the practical application value of the algorithm. In this paper, we use the classic genetic algorithm to solve the problem. According to studies conducted by previous scholars, in this paper, chro=20-30, the size of the population to choose the interval values are acceptable.
3.3. The Design of Fitness Function
In the genetic algorithm, the fitness function is used to evaluate the pros and cons of chromosomes in the population, the fitness function and all selection, crossover operation in genetic algorithms have a close relationship and driving force of the GA process. Genetic algorithm carries on the comparison to the fitness of each chromosome in the population, and to determine selection probability based on the ranking, so fitness function f must be positive.
When solving the extreme value of the fitness function, the fitness function can be directly used to model the objective function f (x) to express, also known as the original fitness function. But when the objective function is the opposite, that is to solve the minimum value of the objective function, this method is no longer applicable, Because the optimal objective function value is smaller, when its genetic to the next generation of probability is smaller in accordance with the proportion of genetic. The fitness function need to be appropriately transformed, therefore, make it a standard measure. That is converted to the maximum of the objective function value is optimal. In the case of the objective function for minimization, standard fitness can be defined as:
Where is the original fitness function f (x) an upper bound, if belongs to an unknown quantity, can be through the current population of the maximum fitness value as the upper bound of chromosome.
3.4. Choose Strategy Design
In a population, Chromosome according to certain choice probability directly into the next iteration populations, the fitness value of the chromosome is the higher; the probability of being selected is greater. Poor fitness value of chromosome might not have the opportunity to be selected, In the process of selecting, the selection probability for each chromosome is:
The formula is selection probability operator. To calculate selection probability operator according to (3.11) for each chromosome, and then apply the selection operator to select the chromosomes for cross breeding.
3.5. Crossover Operator
Selecting operation does not produce new chromosomes, Just selecting excellent individuals from the parent generation chromosomes, In order to achieve optimum operation, chromosomal crossover operation must be carried out, Only in this way can produce new excellent individual to implement genetic algorithm optimization process. Through the selection and crossover operator, GA can result in higher average fitness of children group, which is in the optimal direction to evolve. Crossover is the main means of genetic algorithm for optimizing search, by crossover operation to produce the new individual, it greatly accelerate the speed of the search in the process of group evolution.
Selecting a certain number of chromosomes from the population according to a certain probability, and random group. After the completion of the group, exchange a certain genes of the chromosome from the selected location, the selected location can be one also can be more than one. The probability called the crossover probability. It gives the expected number of participating in the exchange of chromosome, i.e.:
Where N is the population size, In this paper, in the process of cross the crossover method used for single point crossover, the specific method is: for each chromosome, randomly generated a floating point number . If r<p then the chromosome is selected, repeated selection operation N times, and then all of the selected chromosomes were randomly paired. In chromosome randomly set a new crossing points to crossover after randomly paired, when it crosses, the two chromosomes before or after the point swap part structure. All the finished, forming new groups, such as:
3.6. Mutation Operators
The mutation operation of genetic algorithm is replacing some genes in the chromosome with the other allele of the gene to form a new individual. The important role of the mutation operator is to ensure the diversity of population. And it can make the genetic algorithm find the optimal solution near the current solution.
An important parameter of mutation operation is the mutation probability.
is the mutation probability
N is the population size
L is the chromosome length.
In the process of solving the order batching problem, if the mutation probability values of the larger, although able to generate more new chromosome, it may destroy a lot of good search pattern, it will make the genetic algorithm into the stochastic search algorithm; on the contrary if the mutation probability value is too small, then the mutation operation of executive ability is very weak, and the ability of generate new individuals and restrain premature convergence are weak. Combined with genetic algorithm design principles, the range of mutation probability is 0.0001-0.1.
In this chapter, The single order picking equipment limited factors is extended to multiple sorting equipment in distribution center selection process. And extend single zone simple type warehouse to double zone warehouse. Order batching picking route optimization model is established which is to choose walking distance as the optimization goal. The model reflects a more realistic batch picking in distribution center. For solving the model, this paper designed the genetic algorithm steps and parameters needed. Population size chro, fitness function f (x), crossover and mutation operators are described and designed.
This paper is funded by the project of National Natural Science Fund, Logistics distribution of artificial order picking random process model analysis and research(Project number: 71371033); and funded by intelligent logistics system Beijing Key Laboratory (No.BZ0211); and funded by scientific-research bases--- Science & Technology Innovation Platform---Modern logistics information and control technology research (Project number: PXM2015_014214_000001); and funded by 2014-2015 school year, Beijing Wuzi University, College students' scientific research and entrepreneurial action plan project (No.68); and funded by Beijing Wuzi University, Yunhe scholars program(00610303/007); and funded by Beijing Wuzi University, Management science and engineering Professional group of construction projects. (No. PXM2015_014214_000039). University Cultivation Fund Project of 2014-Research on Congestion Model and algorithm of picking system in distribution center (0541502703)