Study on Order Batching Model Design Based on Hopfield Neural Network
Hong Zhang, Jie Zhu, Li Zhou
School of Information, Beijing Wuzi University, Beijing, China
Email address
To cite this article:
Hong Zhang, Jie Zhu, Li Zhou. Study on Order Batching Model Design Based on Hopfield Neural Network. Science Journal of Business and Management. Vol. 3, No. 2, 2015, pp. 60-64. doi: 10.11648/j.sjbm.20150302.12
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 order batching problem, according to scholars in the study of this problem, including taking the picking equipment capacity and load restrictions into account rarely. In the paper, Hopfield Neural Network algorithm for sorting equipment were chosen to establish a capacity constraint order batching model which taking shortest path of all orders as the objective function and maximum equipment utilization order batching model.
Keywords: Manual Order Picking System, Order Batching, Stochastic Service System, Hopfield Neural Network
1. Introduction
In the order batching problem, aiming at the past research problems that exist in the scholars, including considerations of capacity and load limits of the picking equipment. The paper present two models using the Hopfield neural network algorithm: one is order batching model whose objective function is that all the orders total path is the shortest and the constraint conditions is the capacity of picking equipment. The other is order batching model whose objective function is that the utilization rate of picking equipment is maximum.
There are 3 Levels titles in an article to make ideas clear:
1) Introducing the basic assumptions of the order batching model.
2) Aimed at the total path shortest when the single order picking using Hopfield neural network path optimization model.
3) The Hopfield neural network application in order combination problem limited by the picking equipment.
2. Model Design
2.1. Model Assumptions and Definitions
For the convenience of analysis and calculation, we make some basic assumptions before modeling.^{1,2}
1) Warehouse layout as shown in Fig.1.
2) The storage location of all goods included in the each order is known.
3) The shelf height is negligible.
4) Each goods with only one storage point.
5) No out of stock situations.
6) A position of the goods can be completed at one time.
7) Each order contains at least one goods, and the size of each order goods is not greater than picking equipment capacity.
8) Picker's walking path is S-shaped route.
9) Only one picker.
2.2. The Definition of Order Batching Model
Orders batch size refers to the number of orders with a batch of orders.In order to facilitate the description of concepts related to the model, which will be used and the symbol is defined as follows.
1) refers to the total number of orders to be picked.
2) refers to the set of all orders.
3) refers to the set of all orders into batches.
4) refers to the total volume of all the goods in the order
5) refers to e total weight of all the goods in the order
6) refers to the maximum capacity of picking car.
7) refers to the maximum loading capacity of picking car.
8) refers to if the first i order divided into the first batches or not. If yes, ,if not,
9) refers to walking paths when picking the first batch order.
10) refers to walking paths when picking the first batch order according .
11) refers to the total walking paths when picked all goods.
3. Establishment and Solution of the Shortest Path of the Total Order Batch Model
3.1. Establishment of the Model
On the basis of the above assumptions and definitions. Order batching problem can be a simple expression that:Assume that in a period of time there are N order required picking.Each order contains several goods.And known the positions of the each items in the warehouse. (refers to channel coding of goods;). Under the condition of the orders without segmentation, according to the picking equipment volume and weight.the N orders is divided into several batches, according to the divided into batches, after the order picking, the purpose is to make the total path to the minimum.
Objective function
(1)
(2)
Constraint conditions:
(3)
(4)
(5)
In the above formula
(6)
(7)
Formula (1) represents the purpose of model is to make the total path shortest. Formula (2) represents each batch of distance. Formula (3) represents each order can only be divided in a batch. 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.
3.2. Model Solution
The thought of the total shortest path order batching model is to use the MAXSAV algorithm^{3-5}.
The following is the flow chart of the MAXSAV algorithm.
When the batch order, the calculation of the picker walking distance can be carried out in accordance with the steps below to solve:
(1) Calculating the distance between any two goods
is the distance between and .Assuming that the first picking location is mians distance from the beginning of warehouse to the first picking location. then
(1) when
(8)
(2)when ,
(9)
Assuming that the last picking location is mains the distance from the last picking location to beginning of warehouse.
1) when ,
(10)
2) when ,
(11)
The distance between any two goods
Assuming that any two picking points and. is the distance between and .then
If ,
(12)
3) If ,
a)If
i) when ,
(13)
ii) when ,
(14)
b) If
i) when ,
i-1) If
(15)
i-2) If
(16)
ii) when ,
(17)
(2) Calculating single order walking distance
Suppose there are N goods in a order,
Path length of picking all goods included the picking order is:
(3) Calculation of various orders combination of walking distance
Combination of orders can be regard as an order, all the goods in a picking path, calculating path distance.
(4) Calculating the sum of each batch order walking distance
3.3. Model Defects
Order portfolio restrictions is the picking capabilities of the picking equipment. If the order combination is meeting this constraint condition, unified computing the combination' picking path distance.
Consistent with the picking combination of equipment is more, so when the volume of orders is large, the computer will take a long time to complete the batch process. The wait time of the order may increase.
4. Picking Equipment Quantity Minimum Order Partial Model
Objective function
(18)
Constraint conditions:
(19)
(20)
(21)
This model is 0/1 planning, and the solution space is a matrix of N * N. Each element in the matrix represents the correlation of order and batch.
means the first order belong to the first batch. represent the weight coefficient of load rate and the rate of loading. And . Formula 19 represents the capacity constraints for each batch. Formula 20 represents the weight constraints for each batch. Formula 21 represents each order can only be divided in a batch.
Hopfield Network ^{6-8}design
Based on the above order batching problem represent and working principle of the HNN model,order batching problem Hopfield neural network is constructed. N * N neurons is contained in the network, the output function of each neuron is:
(22)
All neurons output can be arranged in a N order matrix. When the network is running at steady state, The 1 is the one on each line of output neurons of the matrix, the rest are 0, representing each order can only be divided in a batch. The sum of all the output values of the neurons is N, to ensure that the N orders are assigned to a batch, each column of the matrix can be arbitrary number of neurons in the output of 1, representing the various batches can load up the N orders.
By using the penalty function method to construct the energy function of order batching model are as follows:
(23)
The dynamic equation of the neural network model is:
(24)
In the formula 24, is a constant, selecting the appropriate parameters and initial values. The energy function in the model iterates until the energy function is stable according to the formula 24. We can get the order batching problem solution. In the use of CHNN process^{9,10}, V is changing in the range of [0,1].
5. Summary
This paper is mainly about the application of Hopfield neural network in the order batching problem, the shortest path model and minimum order batch picking equipment model are put forward. This paper first introduces the basic assumptions of the order batching model. Then aimed at the total path shortest when the single order picking using Hopfield neural network path optimization model. Finally the Hopfield neural network application in order comb ination problem limited by the picking equipment.
Acknowledgements
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).
References