Bingkun Dong| Xiaoning Zhu* | Rui Yan | Yao Wang
OPEN ACCESS
With the continuous development of the market economy, the tobacco industry is rapidly expanding in China. There are now numerous cigarette retailers across the country, which distribute multiple types of cigarettes to consumers in small batches and multiple times. Against this backdrop, the traditional warehouse storage and retrieval (S/R) approach, an integration of the radiofrequency identification (RFID) and manual sorting, no longer satisfies the market demand. Most cigarette distribution centres now use automated stereo warehouses, which face the com-plex and realistic problem of goods S/R with multiple stackers, multiple carriers and irregular goods locations. After analysing the features of the automated storage and retrieval system (AS/RS), this paper introduces the bacterial foraging optimization (BFO) algorithm to optimize the AS/RS in light of the actual work conditions. Firstly, a model framework was set up based on the production reality and algorithm constraints. Next, the model was solved by the bionic algorithm BFO. Finally, a numerical example was selected to verify the effectiveness of the algorithm. The results show that the BFO can effectively shorten the operation time and improve the S/R efficiency. The research findings provide a scientific and rational plan for automated ware-housing in complex environments.
automated storage and retrieval system (AS/RS), multiple carriers, goods location allocation, picking path, integrated optimization
With the continuous development of the market economy, the tobacco industry is rapidly expanding in China. There are now numerous cigarette retailers across the country, which distribute multiple types of cigarettes to consumers in small batches and multiple times. Against this backdrop, the traditional warehouse storage and retrieval (S/R) approach, an integration of the radiofrequency identification (RFID) and manual sorting, no longer satisfies the market demand. Fortunately, the automated storage and retrieval system (AS/RS) can achieve a good overall effect of warehouse S/R, thanks to its elimination of manual participation, and capability of automated, unmanned management [1]. The AS/RS optimization mainly focuses on two issues: goods location allocation and picking route optimization.
Because of the proliferation of the AS/RS, the goods location allocation has become much more complex than the simple combination of scheduling and travelling salesman problem [2]. Instead, this task now requires overall consideration of the ratio of storage space to turnover rate, that is, the cube-per-order (COI) [3]. A popular way of goods location allocation is to allocate the relevant goods close to each other and process the historical picking data [4-6]. One of the main strategies for picking route optimization lies in setting up a planning and optimization model for stacker picking routes that minimizes the outbound time [7-10]. The two methods are integrated in many studies.
The uncertain factors are often introduced to the AS/RS optimization, marking a cutting-edge research direction. For example, many scholars have explored the coordinated optimization of irregular goods locations with multiple carriers [11-14]. However, it is very difficult to find the optimal or suboptimal solution to the combinatorial optimization problem in a limited period of time, because the solution complexity increases exponentially with the growing scale of the problem.
Facing such an NP-hard problem, intelligent algorithms have obvious advantages over other methods. Some scholars [15-16] have adopted the simulated annealing (SA) algorithm to build an allocation model for goods locations using a dedicated storage strategy. Some scholars [17] have employed the genetic algorithm (GA) in computer simulation of the online scheduling system. Some scholars [18] have relied on hybrid heuristic algorithms to establish storage/retrieval mechanisms that select the optimal parking location of the stacker and reduce the picking time of fixed shelves. There are also scholars that applied tabu search [19] and ant colony algorithm (ACA) [20] in this field.
Considering the features of the AS/RS, this paper improves the bacterial foraging optimization (BFO) algorithm to optimize the warehousing and sorting of irregular goods locations with multiple carriers, and prepares an implementation plan for the automated stereo S/R of modern cigarette warehouses, aiming to shorten the computing time and enhance the S/R and picking efficiency.
The remainder of this paper is organized as follows: Section 2 establishes an abstract model for multi-carrier, irregular goods locations; Section 3 solves the model with the BFO algorithm and verifies the feasibility and optimization effect of the algorithm; Section 4 wraps up this paper with several conclusions.
2.1 Problem description
Our research focuses on an automated warehousing system produced by a tobacco machinery company. The system consists of an S/R module, a storage module, a transport module, and a control module. The S/R module has a stacker in each lane that stores and retrieves goods. The stackers can move both horizontally and vertically. The storage module contains 9,046 goods locations. A good can be placed on any of these locations. In the transport module, the goods are carried by forklifts and conveyor belts from the S/R module to long-distance transport devices.
Figure 1. Sketch map of the automated warehousing system
As shown in Figure 1, a stacker running on the route cannot interact with the shelves. Whereas the stackers operate in a discrete manner while the conveyor belt in a continuous manner, a temporary S/R area was set up between each stacker and the conveyor belt. The continuously inputted S/R orders form a storage queue and a retrieval queue, and can be divided into several order cycles. Considering the goods location allocation and the transport route are considered as a whole, this paper attempts to build an optimization model with two objectives, namely, minimizing the S/R time in a scheduling cycle and minimizing the waste of storage space.
2.2 Hypotheses
The following hypotheses were put forward for our automated warehousing system:
(1) In the automatic warehousing system, each good is treated as one S/R unit and each lane is composed of one stacker and one carrier; a carrier may contain multiple goods, and a good can either be stored or retrieved in each order cycle.
(2) There are multiple shelves in the warehouse. The goods locations are of the same height
in the same row and the same width in the same column. Each good can be placed at the most suitable location in any shelve.
(3) The goods of different specifications should be stored separately in carriers with suitable sizes.
(4) Between every two shelves, there are two stackers capable of moving at a uniform speed in both the horizontal and vertical directions. The moving speed is a known constant.
(5) Each stacker has p carriers, each of which can carry goods of all specifications. The carriers operate independent of each other.
(6) The following factors are not considered: the start-up time, braking time and single S/R time of any stacker, as well as the running and time of any materials on the conveyor belt.
(7) The load capacity of any goods location and any carrier exceeds the weight of any good. The total load capacity of a stacker is limited, while that of a shelf is not.
(8) The optimization aims to minimize the total S/R time and the space of the remaining goods locations in an order cycle.
2.3 Parameters and variables
The symbols used our model are listed in Table 1 below.
Table 1. Symbols and explanations
|
Symbol |
Explanation |
|
n |
The total number of goods to be stored |
|
m |
The total number of goods to be retrieved |
|
i |
The i-th good to be retrieved, i=1, 2, …, n |
|
j |
The j-th good to be stored, j=1, 2, …, m |
|
s |
The total number of shelves, i.e. that of stackers |
|
k |
The k-th shelf, k=1, 2, …, s |
|
Ik |
The total number of goods locations on the k-th shelf, k=1, 2, …, s, r, r'=1, 2, …, Ik |
|
vx |
The horizontal speed of each stacker |
|
vy |
The vertical speed of each stacker |
|
dxrr' |
The horizontal distance between goods locations r and r' |
|
dyrr' |
The vertical distance between goods locations r and r' |
|
crr' |
The time from goods locations r and r', r, r'=1, 2, …, Ik |
|
Q |
The maximum load capacity of each stacker |
|
qi |
The weight of the i-th good to be stored i=1, 2, …, n |
|
qj |
The weight of the j-th good to be retrieved, j=1, 2, …, m |
|
wr,hr |
The width and height of the r-th goods location, r =1, 2, …, Ik |
|
wi, hi |
The width and height of the i-th good to be stored, i=1, 2, …, n |
|
g |
The g-th stacker, g=1, 2, …, s |
|
P |
The number of carriers on each stacker, p=1, 2, …, P |
|
T |
The type of a good, t=1, 2, …, T |
The non-decision variable is defined as follows:
The indicator of whether a type t good is stored on the r-th location of the k-th shelf: $a_{rkt}∈\lbrace 0,1\rbrace r=1,2,…, I_k, , k=1,2,…,s, t=1,2,…,T$, where 1 means the good is stored on that location, while 0 means the otherwise. The variable $a_{rkt}$∈$\lbrace 0,1\rbrace$ is updated continuously during the S/R operations.
The decision variables are defined as follows:
The indicator of whether good i of type t to be stored is stored on the r-th location of the k-th shelf: xitrk $∈\lbrace 0,1\rbrace$, i=1, 2, …, n, r=1, 2, …, Ik,k=1, 2, …, s where 1 means the good is stored on that location, while 0 means the good is not stored on that location.
The indicator of whether good j of type t to be retrieved is retrieved from on the r-th location of the k-th shelf: $y_{jtrk}∈\lbrace 0,1\rbrace, j=1, 2, …, m, r=1, 2, …, I_k,k=1, 2, …, s$ where 1 means the good is retrieved from that location, while 0 means the good is not retrieved from that location.
The indicator of whether stacker g moves from the r-th location to the $r^{'}$ -location of the k-th shelf: $z_{gkrr^{'}}∈\lbrace 0,1\rbrace, g=1, 2, …, s, k=1, 2, …, s,k=1, 2, …, s, r,r^{'}=0, 1, 2, …, I_k$, where 1 means the stacker does move between the two locations and 0 means the stacker does not; if r or $r^{'}$ equals zero, then the stacker is in the temporary S/R area.
2.4 Mathematical model
The goods location allocation and picking route optimization involving multiple stackers, multiple carriers and irregular goods locations form a combinatorial optimization problem. The problem can be abstracted into a 0-1 integer programming model, which can be further transformed into a vehicle routing problem with pickups and deliveries (VRP-PD).
The objective functions can be expressed as:
Minimizing the total operation time:
$minZ=\sum_{g=1}^s\sum_{k=1}^s\sum_{r'=1}^{I_k}\sum_{r=1}^{I_k}c_{rr'}∙z_{gkrr'}$ (1)
Minimizing the space of the remaining goods locations:
$minZ'=\sum_{k=1}^s\sum_{r=1}^{I_k}\sum_{t=1}^T\sum_{i=1}^n x_{itrk} ∙(w_r-w_i)∙(h_r-h_i)$(2)
The model is subjected to the following constraints:
Only one storage operation is allowed at each location:
$\sum_{k=1}^s\sum_{r=1}^{I_k} x_{itrk} =1, i=1, 2, …, n$(3)
The storage operation cannot take place on non-empty locations:
$\sum_{k=1}^s\sum_{r=1}^{I_k}\sum_{t=1}^T x_{itrk}∙a_{rkt}=0, i=1, 2, …, n$(4)
Only one retrieval operation is allowed at each location:
$\sum_{k=1}^s\sum_{r=1}^{I_k} y_{jtrk} =1, j=1, 2, …, m $(5)
The retrieval operation cannot take place on non-empty locations:
$\sum_{k=1}^s\sum_{r=1}^{I_k}\sum_{t=1}^T y_{jtrk}∙a_{rkt}=1, j=1, 2, …, m $(6)
The goods are not super wide:
$0≤x_{itrk}∙(w_r-w_i)≤w_r, \\i=1,2,...,n, \\t=1,2,...,T, \\ r=1,2,...,I_k, \\ k=1,2,...,s$ (7)
The goods are not super high:
$0≤x_{itrk}∙(h_r-h_i)≤h_r\\i=1,2,...,n\\t=1,2,...,T\\r=1,2,...,I_k\\k=1,2,...,s$ (8)
The weight of each good should not exceed the load capacity of the stacker:
$\sum_{k=1}^s(\sum_{i=1}^n(\sum_{r'=1}^{I_k} z_{gkrr'} ∙x_{itrk}∙q_i+\sum_{j=1}^n (\sum_{r'=1}^{I_k} y_{jtrk} ∙y_{jtrk}∙q_j)≤Q\\j=1,2,...,m$(9)
If treated by accurate methods, our problem, a typical NP-hard problem, may consume lots of time and cost, and the search ability will decline drastically with the growth of problem scale. Thus, it is better to solve the problem by an approximation method.
3.1 Introduction to the BFO
The BFO is an excellent approximation method with excellent fine search and global optimization abilities in low-dimensional continuous problems. This algorithm achieves optimization through the co-competition between bacterial populations. As a swarm-based search technique, the BFO can optimize several swarms in parallel and jump out of the local minimum trap. In this paper, this algorithm is adopted to optimize the goods location allocation and path planning. The workflow of the BFO is illustrated in Figure 2.
3.2 BFO-based optimization design
Our model was optimized for objective (2) first before being optimized for objective (1). The original problem can be expressed as the following two planning problems:
$minZ'=\sum_{k=1}^s\sum_{r=1}^{I_k}\sum_{t=1}^T\sum_{i=1}^n x_{itrk} ∙(w_r-w_i)∙(h_r-h_i)$
S.t. (3)(4)(5)(6)(7)(8)
$minZ= \sum_{g=1}^s\sum_{k=1}^s\sum_{r'=1}^{I_k}\sum_{r=1}^{I_k} c_{rr'} ∙z_{gkrr'}$
S.t. (9)
Both problems can be solved by the BFO algorithm.
Coding:
The matrix coding (Table 2) was adopted for problem 1, with row mark being the number of good and column mark being the serial number of goods location.
Figure 2. The workflow of the BFO
Table 2. List of goods locations
|
|
|
Shelf 1 |
Shelf 2 |
… |
||||
|
|
|
Location 1 |
Location 2 |
… |
Location 1 |
Location 2 |
… |
… |
|
Type 1 |
Good 1 |
+1 |
0 |
0 |
0 |
0 |
-1 |
0 |
|
Good 2 |
0 |
0 |
+1 |
0 |
-1 |
0 |
0 |
|
|
… |
… |
|
|
|
|
|
|
|
In the matrix, +1 indicates whether good i of type t to be stored is stored on the r-th location of the k-th shelf, while -1 indicates whether good j of type t to be retrieved is retrieved from the r-th location of the k-th shelf.
Problem 2 was sequentially coded as a $s∙s∙I_k∙I_k$-digit integer, where the i-th digit means the ⌊⌊⌊ $i/I_k$ ⌋/ $I_k$ ⌋/ $s$ ⌋-th stacker moves from location⌊ $i/I_k$ ⌋ to location⌈$i/I_k$⌉ on the⌊⌊ $i/I_k$ ⌋/ $I_k$ ⌋-th shelf.
As mentioned before, the optimization was carried out by the BFO, which mimics the intelligent behaviors of bacteria like foraging, clustering, and replication.
(1) Trending
The flipping and swimming of bacteria into favorable areas is collectively known as trending. Specifically, flipping refers to the movement of bacteria in any direction by a unit step length, while swimming stands for that along the direction of the previous step by a unit step length. The position of the i-th bacterium during flipping can be updated by:
$P^i (j+1, k, l)=P^i (j,k, l)+C(i)φ(i) $ (9)
where $P^i (j,k, l)$ is the position of the i-th bacterium after the j-th trending, the k-th replication and the l-th migration; $C(i)$ is the unit step length of swimming along the selected direction; $φ(i)$ is a randomly generated direction vector.
If the fitness at $P^i (j+1, k, l)$ is better than that at $P^i (j,k, l)$, then the bacterium will swim along the same direction without changing the $φ$ until reaching the position with the optimal fitness or the pre-set number of trending. Otherwise, a new $φ$ will be generated for the next flipping.
(2) Replication
After reaching the pre-set number of trending, the bacteria self-replicate and produce new individuals. Before the replication, the fitness of the bacterial population was sorted in descending order. The top half of the population was retained, while the lower half was discarded. Then, the retained bacteria each split into two individuals. The replicated bacteria retained the original features of the parent bacteria.
(3) Migration
After completing the replication in the fixed cycles, the bacteria migrate at the probability Ped. Each bacterium satisfying the migration probability will die. Meanwhile, a new individual will generate at any position in the solution space, while the original individual migrates to a new position. The other bacteria will remain at the original positions, aiming to prevent the local optimum trap.
3.3 Example analysis
The stereo warehouse of a tobacco machinery company has an annual throughput of 1 million goods, equivalent to the daily mean throughput of 4,329 goods. Recently, the company increased the capacity of the stereo warehouse from 41,000 to 65,000, up by 58.53%. The distribution center operations include reception, storage, automatic replenishment, automatic sorting, and retrieval. It is necessary to further improve distribution efficiency and reduce the logistics cost.
In addition, each goods location is 1.5m long and 1m wide, and each stacker moves at 3m/s and 1m/s in the horizontal and vertical directions, respectively. For convenience, the speed variations in startup and braking were not taken into account. In our example, 20 types of gears need to be stored in or retrieved from 40 (5 rows * 8 columns), 80 (8 rows * 10 columns), 120 (10 rows * 12 columns) or 160 (10 rows * 16 columns) locations, and the distribution of the initial locations is generated randomly.
The BFO, the SA and the GA were used to solve the S/R problem respectively with the above location settings. The results in Table 3 show that the BFO consumed about 30% shorter time than the contrastive algorithms both on average and on the convergence to the optimal solution.
Table 3. Results of the numerical experiment
|
Number of locations |
The SA algorithm |
The GA |
The BFO |
|||
|
Converging time to optimal solution/s |
Computing time/s |
Converging time to optimal solution/s |
Computing time/s |
Converging time to optimal solution/s |
Computing time/s |
|
|
40 |
64.5 |
21.1 |
53.7 |
24.3 |
40.5 |
5.4 |
|
80 |
226.5 |
46.2 |
172.1 |
88.5 |
138.9 |
13.1 |
|
120 |
327.7 |
56.3 |
301.9 |
91.5 |
235.5 |
26.6 |
|
160 |
355.5 |
79.8 |
311.8 |
103.5 |
252.0 |
38.4 |
|
Mean |
243.5 |
50.8 |
209.8 |
76.9 |
166.7 |
20.8 |
In modern automated stereo cigarette warehouses, the AS/RS with multiple carriers and irregular goods locations may involve the S/R operations in multiple locations. The location allocation and picking route should be considered in a unified manner to improve equipment utilization, reduce redundant operation, shorten travel time and improve S/R efficiency.
In light of the above, this paper constructs two objective functions (the shortest time and the highest space utilization) and seven constraints, forming an automated and flexible S/R model with multiple carriers and irregular locations. Then, the BFO algorithm was selected to optimize this NP-hard problem. The experimental results show that the algorithm has significant advantages in improving the efficiency of S/R and picking, and outperformed other algorithms in working efficiency by about 25~30%.
This paper is made possible thanks to the generous support from National Natural Science Foundation of China (Grant No.: 71802021, 71602008 and 71801013), Beijing Natural Science Foundation (Grant No.: 9184023), and Beijing Social Science Fund Research Project (Grant No.: 16JDGLC032, 17JDGLB011 and 18GLB022).
[1] Lei NN. (2014). Research and application of automatic warehouse system. Mechanical Engineering & Automation (3): 163-165. https://doi.org/10.3969/j.issn.1672-6413.2014.03.068
[2] Deng AM, Cai J, Mao L. (2013). Research on slotting optimization in automated warehouse based on time. Chinese Journal of Management Science 21(6): 107-112. https://doi.org/10.3969/j.issn.1003-207X.2013.06.013
[3] White JA, Francis RL, Francis RL, McGinnis LF. (1974). Facility layout and location: an analytical approach. Prentice-Hall.
[4] Kallina C, Lynn J. (1976). Application of the cube-per-order index rule for stock location in a distribution warehouse. Interfaces 7(1): 37-46. https://doi.org/10.1287/inte.7.1.37
[5] Li QX, Ma FC, Zhang Q. (2015). Joint optimization for lead-time Supply-demand inventory in supply chain. Chinese Journal of Management Science 23(4): 117-122. https://doi.org/10.16381/j.cnki.issn1003-207x.2015.04.014
[6] Malmborg CJ, Krishnakumar B. (1989). Optimal storage assignment policies for multiaddress warehousing systems. IEEE Transactions on Systems, Man, and Cybernetics 19(2): 197-204. https://doi.org/10.1109/21.31026
[7] Caron F, Marchet G, Perego A. (1998). Routing policies and COI-based storage policies in picker-to-part systems. International Journal of Production Research 36(3): 713-732. https://doi.org/10.1080/002075498193651
[8] Brynzér H, Johansson MI. (1996). Storage location assignment: Using the product structure to reduce order picking times. International Journal of Production Economics 46): 595-603. https://doi.org/10.1016/0925-5273(94)00091-3
[9] Regattieri A, Santarelli G, Manzini R, Pareschi A. (2013). The impact of dwell point policy in an automated storage/retrieval system. International Journal of Production Research 51(14): 4336-4348. https://doi.org/10.1080/00207543.2013.776188
[10] Ma WJ, Wang XW, Wei ML. (2014). Optimal inventory policies for multiple products under capacity constraints. Journal of Wuhan University (Natural Science Edition 60(2): 135-138.
[11] Zeng Q, Zhang ZB, Yang LF. (2015). Optimization method for AR/RS stacker path planning with capacity limit. Machinery Design & Manufacture (1): 172-176. https://doi.org/10.3969/j.issn.1001-3997.2015.01.046
[12] Zhou BD, Lu XW. (2015). A review of solving algorithms for picking path optimization problem in distribution center. Modern Business (5): 26-27. https://doi.org/10.3969/j.issn.1673-5889.2015.05.009
[13] Zong XP, Qi XM, Wang PG. (2014) Study on optimization of sorting activities in automatic storage and retrieval systems. Logistics Technology (3): 403-405, 409. https://doi.org/10.3969/j.issn.1005-152X.2014.03.128
[14] Yang P, Miu LX, Qi MY. (2011). Integrated optimization of storage location assignment and route planning in a multi-shuttle automated storage and retrieval system. Journal of Tsinghua University (Science and Technology) 51(2): 261-266. https://doi.org/10.3724/SP.J.1146.2010.00204
[15] Atmaca E, Ozturk A. (2013). Defining order picking policy: A storage assignment model and a simulated annealing solution in AS/RS systems. Applied Mathematical Modelling 37(7): 5069-5079. https://doi.org/10.1016/j.apm.2012.09.057
[16] Zhao XF, Yun C, Hu J. (2012). Research on irregular storage location assignment optimization of AS/RS. Computer Engineering and Applications 48(24): 222-225, 230. https://doi.org/10.3778/j.issn.1002-8331.2012.24.049
[17] Song SL. (2018). Application of gray prediction and linear programming model in economic management. Mathematical Modelling of Engineering Problems 5(1): 46-50. https://doi.org/10.18280/mmep.050107
[18] Hu YH, Huang SY, Chen C, Hsu WJ, Toh AC, Loh CK, Song T. (2005). Travel time analysis of a new automated storage and retrieval system. Computers & Operations Research 32(6): 1515-1544. https://doi.org/10.1016/j.cor.2003.11.020
[19] Yang WQ, Deng L, Fei MR. (2013). Multi-objective automated warehousing scheduling based on improved tabu search. Computer Integrated Manufacturing Systems 19(8): 2097-2104.
[20] Li M, Chen X, Wang L. (2008). Research on order picking optimization problem for multiple aisles fixed storage racks. Control and Decision (23): 1338-1342. https://doi.org/10.3321/j.issn:1001-0920.2008.12.004
