Picking Path Optimization in Dual Zone Type Warehouse Based on Genetic Algorithms
Jie Zhu, Hong Zhang, Jian Guo, Li Zhou
School of Information, Beijing Wuzi University, Beijing, China
To cite this article:
Jie Zhu, Hong Zhang, Jian Guo, Li Zhou. Picking Path Optimization in Dual Zone Type Warehouse Based on Genetic Algorithms. International Journal of Economic Behavior and Organization. Vol. 3, No. 3, 2015, pp. 41-46. doi: 10.11648/j.ijebo.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. For picking route optimization problem, single or multiple picking equipment may be considered in the actual operation process in order to choose the shortest path as the objective function to establish the optimization model in this paper. And genetic algorithm is designed in detail to solve this model.
Keywords: Manual Order Picking System, Order Batching, Genetic Algorithm
Picking route optimization is an important problem in distribution center selection operation, and its cost of time and expense account for the high proportion of the whole order picking operation. Besides, it also forms the basis of order batch. In the order picking, customer orders are converted to the picking orders at first; and the transformation process of the picking orders includes order batch and order picking optimization operation.
This paper illustrates the study of picking route, and this problem is divided into two kinds of circumstances. The first one is single equipment picking, and the second is the multiple equipment picking. Before route optimization, those orders can either be with order batch or without it.
2. Background of the Research
2.1. Single Picking Equipment
The problem can be described as: in the process of picking orders of distribution center, one or more combined into a batch of orders need to be chosen by a selection equipment, and the total capacity and quality will not be over the ability of the equipment, trying to find the optimal picking route scheme to make the total picking path the shortest.
2.2. Multiple Picking Equipments
This problem can be described as: there is multiple picking equipment picking at the same time in the distribution center in order to save the time of a single order picking process (pre period short orders) or reduce the walking distance of all batch picking orders. In the premise of meeting the demand of picking equipment selection ability, finding the optimal route to make the general selection of road the shortest. In this problem, orders can be divided into different sorting equipment for picking, so you can reduce the front period of orders, and then ten orders can be merged into batch orders. The path optimization can reduce total walking distance. In the order picking, customer orders are first converted to the picking orders, and the transformation process of the picking orders includes order batch and order picking optimization operation.
3. Model Design of Order Picking Route Optimization
3.1. Single Picking Equipment Picking Route Optimization Model Assumptions
For the convenience of analysis and calculation, we make some basic assumptions before modeling.1-3
(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.
3.2. The Establishment of the Order Picking Model
is on behalf of total number of orders.
is on behalf of the cargo capacity ability of picking equipment m
is on behalf of the cargo quality ability of picking equipment m
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 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.
(1) is the objective function of the model. the purpose of model is to make the total path shortest. Formula (4) represents all the goods volume are not more than the maximum capacity of picking car. Formula (5) represents the quality of all of the goods does not exceed the maximum loading capacity of picking car. Decision variables (6) 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.
Analyses of single picking equipment’s situation: only a piece of selection equipment in distribution center, and the order with a batch or without a batch can use single picking device path optimization model. This model not only refers to only a piece of selection equipment of distribution center, but also refers to a batch of orders use a piece of selection equipment, for example in the distribution center applying this model, if there are some rush insertion orders during the process of orders picking, a separate order picking process will be needed.
3.3. Multiple Picking Equipments Picking Route Optimization Model Assumptions
When there are multiple picking equipments in the distribution center for the picking operation, the goods of orders need to be arranged in different picking route. This problem and vehicle routing problem (VRP) in operational research is similar, but also have different parts, and main difference lies in that the goods that are delivered by distribution vehicles are chosen by picking equipment, and there is a great difference in the capacity of the picking equipment and load. The differences of capacity lead to the two questions of optimization focus are different. In the distribution route optimization, the number of delivery vehicles is needed to be sure to make the total distribution route the shortest. During the process of picking, because the Capacity of picking equipment is small, all equipment can be used, and it also means that the number of path and picking equipment are the same.
In the previous study, the VRP model is applied to picking path optimization model directly, and these scholars iignored the existence of differences between two problems. This paper aims at the shortage of previous studies, combining with difference of picking route optimization problem, and then re models the path optimization problem of multi equipment selection.
For the need of research, in the premise of not affecting the nature of the picking path optimization problem, this paper makes the following assumptions:
1) The warehouse type in the research is double-area warehouse;
(2) The picking route ignores displacement in the vertical direction;
(3) Each order contains at least one item;
(4) The weight and quantity of the goods shall not be over any r picking equipment’s ability;
(5) The total weight and quantity of the goods shall not be over all r picking equipment’s ability;
(6)The goods item storage location should be known;
(7) The equipment starts picking at the entrance and exit, and goes back to its previous position after picking.
(8) A storage location of goods does not exceed the picking device’s ability, so it means that only a storage location is in a picking path, and do not need to repeat the selection.
3.4. The Establishment of the Order Picking Model
Based on the above assumptions, more equipment chosen path optimization problem can be described as: there are M pieces of picking equipment in the distribution center are parked in the entrance and exit of warehouse , and a batch of orders need to be picked. The total number of items is N, and the order’s demand of load and capacity does not exceed the limitation of picking device’s ability. We want to know how to arrange the order picking trucks and picking path so that the total picking distance is the shortest. Thus, the mathematical model of the order picking path problem can be expressed as follows9-10:
is on behalf of total number of picking equipment.
is on behalf of the number of goods to be selected.
is on behalf of the number of chosen paths.
is the need of the weight of goods
is the need of the volume of goods
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 any of the selected goods;
is the total distance between the chosen path and; .
means on the chosen path , the walking distance between the first picked item and entrance and exit.
means on the chosen path , the walking distance between the last picked item and entrance and exit.
is the decision variables to decide whether goods x is close to goods y.
The objective function (7) of the model means making the total path shortest after picking route optimization. Constraints (8) and (9) represent all the goods volume and the quality of all of the goods are not more than the maximum picking ability of picking car. Constraints (10) and (11) represent any of the goods are only on the one picking path and are only picked once. Constraints (12) represents the number of the picking path is less than or equal to the number of picking equipment. The decision variables (13) show that on the chosen path, if the goods y is picked immediately after the goods y is picked, the value is 1, otherwise the value is 0.
4. Design of the Genetic Algorithms
The design of order batching problem solving steps according to the genetic algorithm4-5 is as follows:
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 equipments, 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 coding6-8:
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.
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, 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.
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.
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:
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.11-15
In this chapter we make the modeling research of picking route optimization problem, and order picking route optimization problem can be divided into the traditional single picking equipment problem and multiple picking equipment problem. Considering the capacity of picking equipment, minimize picking route model is established. To solve the problems with the nature of NP, a fitness function, crossover operator, coding of genetic algorithm, and other parameters are used in genetic arithmetic method are designed in detail.
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)