Applying the Method for Solving Traveling Salesman Problem Based on Backtracking Algorithm to Order Picking ()
Received 4 May 2016; accepted 17 June 2016; published 21 June 2016
1. Introduction
With the development of electronic commerce and the emergence of the global economic integration, the scale of the orders has gradually evolved into a small amount and multi batch mode, which requires a higher efficiency in order picking operation. Picking operation of the distribution center is a work flow, which is according to customer’s orders picking out merchandise from the storage accurately and quickly as far as possible, and according to a certain way to classify, concentrate and wait for the distribution [1] . At present, the vast majority of the distribution center is still a labor-intensive industry. The process of order picking is the most demanding of all work in distribution center, its amount of labor accounts for 60% of all operations in distribution centers [2] , and picking operation time accounts for the proportion of the whole distribution center operating time is 30% - 40% [3] , thus reasonable picking method has a decisive influence on the efficiency of distribution center operation [4] .
A large warehouse has a large number of orders, so it commonly applies the automated warehouse, and adopts the batch picking operation mode. While in a small warehouse, still uses the single picking operation mode. But traditional order picking path without a scientific basis, picking personnel picks goods according to their experience, and their routes have great relationship with their picking experience and the familiar degree to warehouse layout [5] . Obviously, if this kind of operation mode needs to achieve high efficiency, it requires picking staff have higher skills, and it is easy to increase the cost of storage operations. This reference to the solution of traveling salesman problem, and apply it to traditional order picking operation, so that the traditional picking operations become more reasonable. In a certain extent, it improves the operational efficiency and reduces the time cost of the distribution center.
2. Model Design of Picking Area
2.1. Hypothesis of Operation Condition
Hypothesis 1: picking personnel in the channel can only continue to walk along a straight line.
Hypothesis 2: each row of shelves is filled with goods and not out of stock, and each channel is fully utilized.
Hypothesis 3: the capacity of the picking vehicle is 100 units, and the quantity of a single order is always smaller than the picking vehicle capacity.
Hypothesis 4: the picking speed of each picking personnel is the same.
Hypothesis 5: location of each kind of goods in the storage warehouse is known, and the walking distance of the order picking personnel picking any two kinds of goods is also known.
2.2. Setting Parameters for Warehouse Structure
Hypothesis 1: The warehouse is divided into A, B, C, D regions, and different kinds of goods are stored. Each region has 6 rows of shelves and three shelf channels.
Hypothesis 2: The warehouse likes a rectangle. Exit and entrance is located in a corner of the warehouse, which is in the first row of shelves at C area on the left. Shelf is the low layer and fixed shelves. There are 9 rows of storage locations along the direction of the roadway in each row of shelves. It is that each row of shelves have 9 cargos.
Hypothesis 3: The length of each cargo is 1 unit. The length of the picking channel is 2 units, and the length of the channel is 5 units. As to the area of A, B, C, D, their length is 12 units and width is 9 units.
Hypothesis 4: In the case that is to be verified in this paper, a single order includes 8 items. The storage situation is given in the warehouse model diagram of Figure 1.
3. Description and Model Establishment of Picking Path Problem
Traveling salesman problem (TSP) is a classical algorithm problem. It is described as follows: a salesman, in order to sell his goods out, needs to arrive to n cities in proper order to sell products, and the distance between each city is known. The salesman needs to find a way to travel each city, making the total length of the road is the shortest. Using a graph to describe the traveling salesman problem, set G = (V, E) is a weighted undirected graph. V represents each vertex (city) and E which is a positive represents distance between each vertex (city). A traversal path of a graph is a circuit including each vertex in V. The cost of traversing each vertex is the sum of the costs of all the edges on the route. For figure G, travel salesman problem is to find out the path which the cost is the smallest [6] .
Optimization of picking route is mainly about how to take out all items from the cargos in each area, making the whole picking path to reach the best. This kind of optimization problem is very similar to the common traveling salesman problem. This paper links the two problems, applying the method of solving the traveling salesman problem to the picking path optimization problem, and a mathematical model is proposed to solve the routing problem.
If there is N items in one order, the whole process is successively picking out n items from each cargo of
![]()
Figure 1. Order picking method of warehouse model.
warehouse, one picking order constituting one loop, determining the path selection and order in the loop, and makes the walking distance (D) of picking personnel have minimum value.
(1)
(2)
(3)
(4)
The Cij shows the shortest walking distance that the picking personnel from the number i items to the number j items. The value of Xij is only 1 or 0. When the Xij is 1, it indicates that the picking path includes the path from i to j. When the Xij is 0, it indicates that the picking path do not include the path from i to j. The formula (1) indicates the objective optimization function, which is the minimum order picking distance. The formula (2), (3), (4) are constraint conditions of the model. Formula (2), (3) can ensure each cargo waiting to be picked up only having one chance to be done. Formula (4) shows that the range of Xij’s value, and its value is 0 or 1.
4. Algorithm Description
The Solution space of the common traveling salesman problem is a permutation tree. Permutation tree’s backtracking search is similar with Perm’s recursive algorithm which generated all the arrangement of 1, 2 ∙∙∙ n. When it begin with x = [1, 2, ∙∙∙ , n], then the corresponding permutation tree is composed of all permutations of x [1: n].
In the recursive algorithm Travel Backtrack, when i = n, the current node is the parent node of permutation tree’s leaf node. In this case, whether the algorithm testing figure G exists a side from the vertex x [n − 1] to the vertex x [n] and another side from vertex x [n] to the vertex 1. If the two sides are existing, then a traveling salesman circuit has been found. At this time, the algorithm also need to determine whether the cost of this loop is better than bestw which is the cost of the founded current optimal loop. If so, you must update the current best value bestw and the current optimal solution bestx.
When i < n, the current expansion node is located in the i − 1 layer of permutation tree. When there is a side from the vertex x [i − 1] to the vertex x [i] in figure G, x [1: i] are constitute to a path of graph G, and when x [1: i] cost less than the current optimal value, the algorithm into the permutation tree’s i-layer, or it will cut down the respective sub-tree. Cw is used to record the cost of current path x [1: i] in the algorithm.
Based on backtracking algorithm to solve traveling salesman problem’s pseudo code is shown as below:
Algorithm beginning:
Int I;
City_Graph [l] [k]; / / Given the minimum distance between each two cities, l, k Î (1, 2, ∙∙∙ , n)
/ / test recursive method
for (I = 1; I < N; i++) {
x [i] = 0; / / The first step i haven’t solved.
bestx [i] = 0; / / It is still haven’t the optimal solution.
isIn [i] = 0; / /The city i haven’t added to the path.
}
X [1] = 1; / /The first step is go to city 1.
isIn [1] = 1; / / The first city is joined the path.
bestw = MAX_WEIGHT;
cw = 0;
/ / the recursive method
Travel Backtrack (t) {
If (t > N) {
through all the cities, and output of the current path
if (the cw < bestw) {
record the current optimal solution of the path
}
}
else {
for (j = 1; j < = N j++) {
find the city which the step t can arrive
}
};
Output value the optimal;
Output the optimal solution;
}
End of the algorithm
5. The Example Analysis
5.1. The Experimental Setup
For example as Figure 1, a distribution center’s order contains eight items, the storing case have been explicitly given in the drawing. According to the above assumptions, we can get the minimum distance between each two items, expresses by the 9 × 9 matrix is as follows, in which the first row indicates the distance from gateway to each product item; the second row denotes the distance from the first item to the gateway and to the another seven items, by parity of reasoning. Each items to themselves is not have path, so −1 means unreachable.
(5)
5.2. Experimental Environment
Hardware environment: Windows 7 PC with vc++6.0.
Software environment: C programming language.
5.3. The Result of the Experiment and Experimental Analysis (See Figure 2)
As it can be seen from the experimental results, the backtracking algorithm is starting from the position 1, then do full array formula traverse of other positions to find an optimum value. The optimal value is 101 in graphic, the optimal solution also is the optimal path, the optional path is 1 > 9 > 8 > 2 > 4 > 3 > 7 > 5 > 6. That is to say, in this instance, the picking workers are starting from the gateway, the plain sequence for successively picking items is 8, 7, 1, 3, 2, 6, 4, 5. The shortest walking distance is 15 + 10 + 10 + 16 + 11 + 10 + 12 + 17 = 101.
If in accordance with the traditional way of order picking, picking out the items of each order in turn, the items’ order is 1, 2, 3, 4, 5, 6, 7, 8, and then, the walking distance should be 32 + 22 + 11 + 19 + 17 + 20 + 27 + 10 = 158. The optimization length of picking path is 158 − 158 = 57. The results show that using the method of this paper, the path length of an order can be reduced 57 per unit length. When the quantity of order and the items in the orders are increased, the item distribution is more dispersed, the proposed method in this paper has more advantages, and it can save more path length.
6. Conclusion
The order picking method in this paper is assumed as a single select, without considering practices batch picking. The whole solution is putting the shortest walking distance of picking all the items in an order as the goal, and use of backtracking algorithm to solve the established distribution center’s single model. This paper uses the backtracking algorithm traversed the all possible paths, and chooses the best path of picking all items, so the total picking distance can get significantly optimized.
Acknowledgements
This paper is supported by the Funding Project for Technology Key Project of Municipal Education Commission of Beijing (ID: TSJHG201310037036); Funding Project for Beijing key laboratory of intelligent logistics system; Funding Project of Construction of Innovative Teams and Teacher Career Development for Universities and Colleges Under Beijing Municipality (ID: IDHT20130517), and Beijing Municipal Science and Technology Project (ID: Z131100005413004); Funding Project for Beijing philosophy and social science research base specially commissioned project planning (ID: 13JDJGD013); Funding Project for Beijing Intelligent Logistics System Collaborative Innovation Center.