# Order Picking Optimization in Carousels Storage System

Authors: Xiong-zhi Wang; Guo-qing Wang; Xiao-chun Li
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

This paper addresses the order picking problem in a material handling system consisting of multiple carousels and one picker. Carousels are rotatable closed-loop storage systems for small items, where items are stored in bins along the loop. An order at carousels consists ofn different items stored there. The objective is to find an optimal picking sequence to minimizing the total order picking time. After proving the problem to be strongly NP-hard and deriving two characteristics, we develop a dynamic programming algorithm (DPA) for a special case (two-carousel storage system) and an improved nearest items heuristics (INIH) for the general problem. Experimental results verify that the solutions are quickly and steadily achieved and show their better performance.


---

## Body

## 1. Introduction

Carousels storage system is commonly referred to as an automated computer controlled system which is widely used to store and pick small, light, and highly demanded items, as an effective warehousing facility. It has been used in links of the supply chain: by manufacturers, distributors, and retailers. Standard carousel system consists of a carousel which may hold many different products stored in bins that rotate along a closed loop and a picker (either human or robotic) who occupies a fixed position at the front of the carousel (see Figure1). To retrieve a product, the carousel system automatically rotates (clockwise or counterclockwise) the bin with the requested product to the position of the picker. Accordingly, it is referred to as a product-to-picker system. The operator may effectively use the rotation time of the carousel for activities such as sorting, packaging, or labeling of the retrieved goods. To expand the merits and further reduce the waiting time for a picker, multiple carousels are integrated so that while a carousel is for picking, others can convey items simultaneously. Some of its advantages include increased efficiency derived from bringing parts to picker instead of sending picker to parts, high speed storage and retrieval, low installation and operating cost, and efficient space utilization.Figure 1
Standard carousel system.While companies are finding it important to optimize the operation of their carousel systems to gain a competitive edge in such environments, there are quite a few technical publications on the planning and control of carousels. Bartholdi III and Platzman [1] consider sequencing of picks in a single order. They assume that the time needed by a (robotic) picker to move between bins within the same carrier (or shelf) is negligible compared to the time to rotate the carousel to the next carrier (or shelf). This assumption reduces the problem to finding the shortest Hamiltonian path on a circle. They present a linear time algorithm that finds an optimum solution. Wen and Chang [2] also consider sequencing picks in a single order. They assume that the time to move between bins within the same carrier or shelf may not be neglected. They present three heuristics for this situation, based upon the algorithm in Bartholdi III and Platzman [1]. Several authors have considered the situation where the order-picker consecutively picks multiple orders thereby completing all picks in an order before commencing with the next order; that is, all picks in an order are performed consecutively. Ghosh and Wells [3] and van den Berg [4] present efficient dynamic programming algorithms that find an optimal pick sequence for picking multiple orders when the sequence of the orders is fixed (the sequence of the picks in the orders is free). Bartholdi III and Platzman [1] consider the problem when the order sequence is free, yet picks within the same order must be performed consecutively. They impose the extra constraint that each order is picked along its shortest spanning interval and present a heuristic for the problem with the extra constraint. Van den Berg [4] presents a polynomial time algorithm that solves the problem with the extra constraint to optimality. The author also shows that the solution of the algorithm for the problem with the extra constraint is at most 1.5 revolutions of the carousel above a lower bound for the problem without the extra constraint.In this paper, we focus on the deterministic single order picking problem in a multiple carousels system with a single order picker in which carousels are arrayed in the picking area, each with one picking station, and are independently controlled. We will present a formal problem description in Section2. In Section 3, the problem under study is proved to be strongly NP-hard. Some classical characteristics are put forward in Section 4 and an approximation algorithm is constructed for a special case (double carousel system) of the problem in Section 5. In Section 6, an improved nearest neighbor heuristics (INIH) is designed. We present our conclusions in the last section.


## 2. Problem Description

In the multiple carousels system depicted in Figure2, there are multiple identical carousels, in which each one rotates individually either clockwise or counterclockwise. There is only one picker moving among the front of each carousel performing picking operations so as to collect all items from the picking points to the I/O (Input/Output) station. It is obvious to find that the picking time of the picker has to be considered explicitly, which is different from single carousel order picking problems. We are given an order with m items randomly placed in the system. The objective is to find a picking scheduling to minimize the total picking time. We assume the following.(1)
Each bin stores only one type of item without shortage during picking operation. There may be a few bins in each column, but the moving time among bin levels is negligible.(2)
Rotation speed of the carousels is constant. It means that there is no acceleration or retarding time considered.(3)
The capacity of the picker is large enough to contain the total number of items of any order.Figure 2
Multiple carousels system.The notation used throughout this paper is defined as follows:q: number of the carousels;a: the distance between any two adjacent carousels;n: number of columns in each carousel (assuming that the distance between any two  adjacent columns is 1);mi: number of items to be picked in carousel i in one order, i=1,2,…,q and m1+m2+⋯+mq=m; Ii={Ii1,Ii2,…,Ii,mi}: set of items in carousel i;lij: location of item Iij in carousel i;pij: picking time of item Iij;σ={[1],[2],…,[m]}: a feasible sequence of order picking, in which [i] is denoted as the ith item picked;[j*(k)]: the last item picked in the kth carousel before item [j] is picked;t[i][j]: the travel time from item [i] to item [j];T: the total picking time when all items required are picked;ν1: moving speed of the picker along the picking points (it is easy to know that the moving time τ is a/ν1  between two adjacent carousels);ν2: relative rotation speed of carousels, without loss of generality we normalize ν2 as 1.By using a mapping process, we can obtain an exact two-dimensional array(x,y) for all storage units in carousels where x indicates the carousel number and y represents which column the unit locates in that carousel, x=1,2,…,q; y=1,2,…,n. Therefore, item j location is denoted as (xj,yj)  in the system.As each carousel rotates individually either clockwise or counterclockwise, the travel time from itemi to item j in the same carousel (denoted as Hij) is
(1)Hij=min{|yj-yi|,n-|yj-yi|}.
And if item i and item j do not exist in the same carousel, the travel time from carousel where item i locates to another carousel where item j locates (denoted as Vij) is
(2)Vij=|xi-xj|*τ.
Note that the array (x,y) will change dynamically after an item is picked by rotating to the picking point. For example, if one item located at (x,y) is picked, another item location at (x,y′) in the same carousel will become (x,y′′), where y′′=y′+n-y (if y′<y) or y′′=y′-y (if y′>y).Assume there is a feasible sequenceσ={[1],[2],…,[l-1],[l],…,[m]}; the operation time of picking item [k] after [k-1] (denoted as t[l-1][l]) is
(3)t[l-1][l]=max{V[l-1][l],H[l*(k[l])][l]}=max{|y[l]-y[l*(k[l])]||x[l]-x[l-1]|*τ,min(|y[l]-y[l*(k[l])]|,n-|y[l]-y[l*(k[l])]|)}.
And the total operation time until all items are picked (denoted as T) is T=∑l=1mt[l-1][l], where item [0] means the start picking point. Hence, the problem studied in the paper is to minimize T by finding the best feasible sequence σ* of the order required. It can be simply modeled as follows:
(4)minT=∑l=1mt[zl-1][zl]s.t.t[zl-1][zl]=max{min(|y[zl]-y[zl*(k[zl])]|,n-|y[zl]-y[zl*(k[zl])]|)|x[zl]-x[zl-1]|*τ,=maxmin(|y[zl]-y[zl*(k[zl])]|,=maxn-|y[zl]-y[zl*(k[zl])]|)}[z0]=[0],zl∈{[1],[2],…,[m]},zr≠l≠zl,r,l=1,2,…,m;k=1,2,…,q.
When q=2, it is a special case of the problem. We denote the problem under study by P and the special case by SP.


## 3. NP-Hardness

In this section we first prove that the special caseSP is strongly NP-hard by a reduction from the 3-partition problem, which is known to be NP-complete in the strong sense. Then, it is easy to know that the general problem P is NP-hard because SP is a case of P.


### 3.1. 3-Partition

Given positive integersr,B and a set of integers A={b1,b2,…,b3r} with ∑k=13rbk=rB and B/3<bk<B/2 for k=1,2,…,3r. Does there exist a partition {A1,A2,…,Ar} such that |Al|=3, ∑bj∈Albj=B, and l=1,2,…,r?Theorem 1.
ProblemSP is strongly NP-hard.Proof.
For any given instance of 3-partition, construct an instance ofSP as follows:
(5)n=3r2B,m1=4r,m2=r,τ=0,ν=0,y=r(2rB+B+1),l1j=0,t1j=bj,j=1,2,…,3r,l1j=1,t1j=2rB,j=3r+1,…,4r,l2j=j(2rB+B+1),t2j=B,j=1,2,…,r.
Without loss of generality, assume that r≪min1≤j≤3r{bj}. Call items 11j(j=1,2,…,r) partition items and remaining items enforcing items. We now show that there exists a solution such that T(σ)≤y for this instance if and only if there exists a desired 3-partition.
If Part.Suppose that there exists a desired solution {A1,A2,…,Ar} for 3-partition. Let {Q1,Q2,…,Qr} be the corresponding partition item sets. Construct a picking sequence σ={Q1,I1,3r+1,I2,1,…,Qr,I1,4r,I2,r}. It is easy to see that T(σ)=y.
Only If Part.Let σ be a solution such that T(σ)≤y. Let R2 and T2 be the minimum total rotating time and total picking time of carousel 2, respectively. It is easy to see that R2+T2=y, which means that carousel 2 has no idle time in σ. Let Aj be the set of items picked on carousel 1 during time period while carousel 2 rotates from I2,j-1 to I2,j in σ. To keep carousel 2 from waiting for the picker, we know that ∑I1k∈Ajp1k≤rB+B+1.
LetT1 be the total picking time on carousel 1. Then it is clear that there are one enforcing item and at most 3 partition items in Aj, and the total picking time of the partition items Pj⩽B. On the other hand, if Pj<B, for any j=1,2,…,r, it means that at least one partition item is picked after picking the last item in carousel 2. Then T(σ)>y, a contradiction.Theorem 2.
ProblemP is strongly NP-hard.SP is a case of P, and SP is strongly NP-hard. It is easy to know that problem P is strongly NP-hard.


## 3.1. 3-Partition

Given positive integersr,B and a set of integers A={b1,b2,…,b3r} with ∑k=13rbk=rB and B/3<bk<B/2 for k=1,2,…,3r. Does there exist a partition {A1,A2,…,Ar} such that |Al|=3, ∑bj∈Albj=B, and l=1,2,…,r?Theorem 1.
ProblemSP is strongly NP-hard.Proof.
For any given instance of 3-partition, construct an instance ofSP as follows:
(5)n=3r2B,m1=4r,m2=r,τ=0,ν=0,y=r(2rB+B+1),l1j=0,t1j=bj,j=1,2,…,3r,l1j=1,t1j=2rB,j=3r+1,…,4r,l2j=j(2rB+B+1),t2j=B,j=1,2,…,r.
Without loss of generality, assume that r≪min1≤j≤3r{bj}. Call items 11j(j=1,2,…,r) partition items and remaining items enforcing items. We now show that there exists a solution such that T(σ)≤y for this instance if and only if there exists a desired 3-partition.
If Part.Suppose that there exists a desired solution {A1,A2,…,Ar} for 3-partition. Let {Q1,Q2,…,Qr} be the corresponding partition item sets. Construct a picking sequence σ={Q1,I1,3r+1,I2,1,…,Qr,I1,4r,I2,r}. It is easy to see that T(σ)=y.
Only If Part.Let σ be a solution such that T(σ)≤y. Let R2 and T2 be the minimum total rotating time and total picking time of carousel 2, respectively. It is easy to see that R2+T2=y, which means that carousel 2 has no idle time in σ. Let Aj be the set of items picked on carousel 1 during time period while carousel 2 rotates from I2,j-1 to I2,j in σ. To keep carousel 2 from waiting for the picker, we know that ∑I1k∈Ajp1k≤rB+B+1.
LetT1 be the total picking time on carousel 1. Then it is clear that there are one enforcing item and at most 3 partition items in Aj, and the total picking time of the partition items Pj⩽B. On the other hand, if Pj<B, for any j=1,2,…,r, it means that at least one partition item is picked after picking the last item in carousel 2. Then T(σ)>y, a contradiction.Theorem 2.
ProblemP is strongly NP-hard.SP is a case of P, and SP is strongly NP-hard. It is easy to know that problem P is strongly NP-hard.


## 4. Classical Characteristics

Lemma 3.
Considering the bidirectional single carousel, the optimal picking sequence switched direction at most once [1].Supposing there arek items to be picked in a certain carousel, three types of picking paths will exist as below (see Figure 3). It is obvious that the result of Lemma 3 can facilitate depriving the optimal sequence (linear time complexity method) for a single carousel system.(1)
Travel in clockwise or counter clockwise direction until allk items are picked (see Figures 3(a) and 3(b)).(2)
Travel from location 0 toi in a counterclockwise direction; then backward pass location from 0 to i+1 in a clockwise direction (see Figure 3(c)).(3)
Travel from location 0 toi+1 in a clockwise direction; then backward pass location from 0 to i in a counterclockwise direction (see Figure 3(d)).Picking routes of the multiple carousels system.
(a)
(b)
(c)
(d)Lemma 4.
If there is an optimal sequence in multiple carousels system, the subsequence of one certain carousel is also optimal.Proof.
Prove it by reduction to absurdity.  Let sequenceσ be a feasible solution of the problem in which any subsequence on the specified carousel is optimal with the total operation time Tσ in the problem. Consider
(6)σ={[1],[2],…,[lik-1],[lik],[lik+1],…,[li+1k-1],[li+1k],[li+1k+1],…,[m]}.
And the relevant total operation time Tσ  is
(7)Tσ=∑[j]=[1][m]t[j-1][j]=∑[j]=[1][lik-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[lik-1][lik]+t[lik][lik+1]+∑[j]=[lik+1][li+1k-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[li+1k-1][li+1k]+∑[j]=[li+1k][li+2-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[li+2k-1][li+2k]+∑[j]=[li+2k][m]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j]),
where the superscript k on letter l (the same below) indicates the carousel number.
The subsequenceσk on the kth carousel is
(8)σk={[l1k],[l2k],…,[lik],[li+1k],…,[lmkk]}.
Assume that there exist an optimal solution in which the subsequence on the specified carousel is not optimal, such as the subsequence on the kth carousel is (σk)′. Consider
(9)(σk)′={[l1k],[l2k],…,[li+1k],[lik],…,[lmkk]}.
And the overall optimal solution σ′ is
(10)σ′={[1],[2],…,[lik-1],[li+1k]′,[lik+1],…,[li+1k-1],[lik]′,[li+1k+1],…,[m]},
with the total operation time Tσ′(11)Tσ′=∑[j]=[1][m]t[j-1][j]=∑[j]=[1][lik-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[lik-1][li+1k]′+t[li+1k]′[lik+1]+∑[j]=[lik+1][li+1k-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[li+1k-1][lik]′+∑[j]=[lik]′[li+2k-1]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j])+t[li+2k-1][li+2k]+∑[j]=[li+2k][m]max(|x[j-1]-x[j]|*τ,H[j*(k[j])][j]).
There must be Tσ′≤Tσ.
Taking the position of[lik] and [li+1k] in the solution into account, three cases are discussed according to the relations between them and the adjacent positions.(1)
The position of item[lik] is adjacent to item [li+1k] in the global optimal sequence.
(i)
They are not in the carousel where items[lik-1] and [li+1k+1] locate.It is easy to know that the positions exchanging of[lik] and [li+1k] will result in the carousel rotating once more at least according to Lemma 3. And we can make it as follows:
(12)H[lik-1][lik]+H[lik][li+1k]+H[li+1k][li+2k]≤H[lik-1][li+1k]′+H[li+1k]′[lik]′+H[lik]′[li+2k].That is to say(13)t[lik-1][lik]+t[lik][li+1k]+t[li+2k-1][li+2k]=max(|x[lik]-x[lik-1]|*τ,H[li-1k][lik])+t[lik][li+1k]+H[li+1k][li+2k]≤t[li+1k-1]′[li+1k]′+t[li+1k]′[lik]′+t[li+2k-1][li+2k]=max(|x[lik]-x[lik-1]|*τ,H[li-1k][li+1k]′)+t[li+1k]′[lik]′+H[lik]′[li+2k],wheret[lik][li+1k]=t[li+1k]′[lik]′. Therefore, Tσ′≥Tσ from (7) and (11), assumption contradiction.(ii)
They are in the carousel where[lik-1] and [li+1k+1] locate.That is to say that[lik-1]=[li-1k] and [li+1k+1]=[li+2k]. The travel distance will be repeated, when the positions of items [lik] and [li+1k] in the optimal subsequence according to Lemma 3. Thus,
(14)t[lik-1][lik]+t[lik][li+1k]+t[li+1k][li+2k]≤t[lik-1][li+1k]′+t[li+1k]′[lik]′+t[lik]′[li+2k]′.Combined with (7) and (11), we can make Tσ′≥Tσ, assumption contradiction.(2)
The position of item[lik] is not adjacent to [li+1k] in the global optimal sequence. in other words, [lik] and [li+1k] are not in the carousel where [lik+1] locates.
(i)
Items[lik] and [lik-1] locate in the same carousel. Hence,
(15)t[lik-1][lik]+t[li+1k-1][li+1k]+t[li+2k-1][li+2k]=H[lik-1][lik]+H[lik][li+1k]+H[li+1k][li+2k]t[lik-1][li+1k]′+t[li+1k]′[lik]′+t[li+2k-1]′[li+2k]′=H[lik-1][li+1k]′+H[li+1k]′[lik]′+H[lik]′[li+2k].The rest of formulas (7) and (11) are equivalent.(ii)
Items[lik] and [lik-1] do not locate in the same carousel. So we have the following conclusions:
(16)t[lik-1][li+1k]′+t[li+1k]′[li+1k-1]+t[li+1k-1][lik]′+t[li+1k-1][li+2k]=max(|x[li+1k]′-x[lik-1]|*τ,H[li-1k][li+1k]′)+t[li+1k]′[li+1k-1]+H[li+1k]′[lik]′+H[lik]′[li+2k]≥max(|x[lik]-x[lik-1]|*τ,H[li-1k][lik])+t[lik][li+1k-1]+H[lik][li+1k]+H[li+1k][li+2k]=t[lik-1][lik]+t[lik][li+1k-1]+t[li+1k-1][li+1k]+t[li+2k-1][li+2k].As a result, we can derive thatTσ′≥Tσ from formulas (7), (11), (15), and (16), assumption contradiction
Through the above analysis of two cases, we can know that this conclusion of Lemma4 is established.In light of Lemma4, we notice that the amount of the feasible solutions will decrease sharply to be N!/∏i=1mki! given an order of sequencing N items, where m denotes amount of carousels in the system and ki represents the item quantity required in the ith carousel (i=1,2,…,m;∑ki=N). As a result, this conclusion can help us devise better or optimal solution by combining m optimal subsequences of each of the carousels which is easy to find.


## 5. Heuristics

### 5.1. A Dynamic Programming Algorithm for a Special Case (Double Carousel System)

In the double carousel system, there are two identical carousels. Each carousel rotates individually either clockwise or counterclockwise. There is only a single picker that performs the picking operations. In this section, we develop a dynamic programming algorithm (DPA) for fixed picking sequences on two carousels. Assume thatarc(i,i+1) (see Figure 4) is not visited by the optimal path. Then there are two possible forms of the optimal path.(1)
Travel from 0 toi in a counterclockwise direction; then backward pass from 0 to i+1 in a clockwise direction (see Figure 4(a)).(2)
Travel from 0 toi+1 in a clockwise direction; then backward pass from 0 to i in a counterclockwise direction (see Figure 4(b)).Two possible modes of the optimal path on any carousel.
(a)
(b)The optimal path on each carousel can be found by testing each ofm distinct arcs with the minimum distance, which is min{n-max{li+1-2li-li,2li+1-n-l0,i+1}}.For fixed picking paths on each carousel, an optimal picking path can be obtained with the following dynamic programming method;(1)
determine the optimal picking sequence for each carousel;(2)
find the dominant carousel with longer picking time, and fix the picking schedule for the carousel;(3)
schedule operations for another carousel as soon as possible with the constraint of the dominant schedule.


### 5.2. INIH for General Problem

Based on the previous analysis of two classical characteristics, we develop an improved nearest items heuristics (INIH) algorithm to solve the general problem in which all items required are stored randomly inq carousels.Let ordinal setSi(i=1,2,…,m) be the optimal sequence of the ith carousel, where |Si|=ki, Si={[i1],[i2],…,[iki]}, and the coordinate of element [il] is (x[il],y[il])(l=1,2,…,ki) (see Algorithm 1).Algorithm 1:Improved nearest items heuristics (INIH).
(1) Initialization: Get ordinal setSi(i=1,2,…,m); Define ordinal and general set S0 and S, respectively; set variable q
q←0,S0=⌀;
Fori=1 to m to
Get the first element[i1] of Si,S∪[i1];
End
(2) Computetq,k=max{|xq-xk|/v1,min{yk,n-yk}/v2}, k∈S;
Gettq,k*=mink∈S{tq,k},S0=S0∪k*;
q←k*;
(3) Find the ordinal setSj of the element k*;
IfSj=⌀, Return step (2);
OtherwiseSj=Sj∖k*,S=S∖k*;
Get the first element[jl] of Sj,S∪[jl];
(4) IfS=⌀, Output the ordinal set S0; Otherwise, Return step (2);The sequence of all elements of the ordinal setS0 is the order picking solution. It can improve the operation’s efficiency and search space of the general nearest items heuristics effectively so as to get better effect. It is easy to know that the complexity of INIH is linear of its scale according algorithm complexity theory [5]. And it is acceptable on computing time.


## 5.1. A Dynamic Programming Algorithm for a Special Case (Double Carousel System)

In the double carousel system, there are two identical carousels. Each carousel rotates individually either clockwise or counterclockwise. There is only a single picker that performs the picking operations. In this section, we develop a dynamic programming algorithm (DPA) for fixed picking sequences on two carousels. Assume thatarc(i,i+1) (see Figure 4) is not visited by the optimal path. Then there are two possible forms of the optimal path.(1)
Travel from 0 toi in a counterclockwise direction; then backward pass from 0 to i+1 in a clockwise direction (see Figure 4(a)).(2)
Travel from 0 toi+1 in a clockwise direction; then backward pass from 0 to i in a counterclockwise direction (see Figure 4(b)).Two possible modes of the optimal path on any carousel.
(a)
(b)The optimal path on each carousel can be found by testing each ofm distinct arcs with the minimum distance, which is min{n-max{li+1-2li-li,2li+1-n-l0,i+1}}.For fixed picking paths on each carousel, an optimal picking path can be obtained with the following dynamic programming method;(1)
determine the optimal picking sequence for each carousel;(2)
find the dominant carousel with longer picking time, and fix the picking schedule for the carousel;(3)
schedule operations for another carousel as soon as possible with the constraint of the dominant schedule.


## 5.2. INIH for General Problem

Based on the previous analysis of two classical characteristics, we develop an improved nearest items heuristics (INIH) algorithm to solve the general problem in which all items required are stored randomly inq carousels.Let ordinal setSi(i=1,2,…,m) be the optimal sequence of the ith carousel, where |Si|=ki, Si={[i1],[i2],…,[iki]}, and the coordinate of element [il] is (x[il],y[il])(l=1,2,…,ki) (see Algorithm 1).Algorithm 1:Improved nearest items heuristics (INIH).
(1) Initialization: Get ordinal setSi(i=1,2,…,m); Define ordinal and general set S0 and S, respectively; set variable q
q←0,S0=⌀;
Fori=1 to m to
Get the first element[i1] of Si,S∪[i1];
End
(2) Computetq,k=max{|xq-xk|/v1,min{yk,n-yk}/v2}, k∈S;
Gettq,k*=mink∈S{tq,k},S0=S0∪k*;
q←k*;
(3) Find the ordinal setSj of the element k*;
IfSj=⌀, Return step (2);
OtherwiseSj=Sj∖k*,S=S∖k*;
Get the first element[jl] of Sj,S∪[jl];
(4) IfS=⌀, Output the ordinal set S0; Otherwise, Return step (2);The sequence of all elements of the ordinal setS0 is the order picking solution. It can improve the operation’s efficiency and search space of the general nearest items heuristics effectively so as to get better effect. It is easy to know that the complexity of INIH is linear of its scale according algorithm complexity theory [5]. And it is acceptable on computing time.


## 6. Performance Study

To explore the computational performance of DPA and INIH algorithms comparing other methods such as conventional search (CS) and nearest item heuristics (NIH), we construct two groups of tests on personal computer PIII 1.5 G Hz by C language. Consider a practical multiple carousels system with the operational characteristics specified as follows:The two groups of items request: (10, 15, 20, 30, 50) and (100, 150, 200, 300, 500); items located on carousel:x-coordinate is from (2,4,…,30) randomly and y-coordinate is from function Rand(50); the distance of any two adjacent bins on carousel = 0.5 m; τ=3 m/s, ν=2 m/s, and a=2 m; Number of bins per carousel is 100, carousels quantity m=15 for INIH, and m=2 for DPA. R=Random(104), α,β, is from (0,1) randomly, and α+β=1.Three indexes are tested: average order picking time (Ot), standard difference (SD), and algorithm operating time (Ts). The testing results are specified as Tables1 and 2.Table 1
Testing performance of INIH.
N
10
15
20
30
50
100
150
200
300
500
CS
Ot
12.28
24.56
30.82
60.56
92.25
198.5
326.3
428.2
619.2
902.2
SD
10.2
12.26
16.64
20.2
26.62
32.36
40.24
50.25
56.2
68.0
Ts
0.024
0.032
0.081
0.168
0.298
1.212
2.324
4.486
8.02
10.96
NIH
Ot
11.3
12.21
25.86
48.24
80.56
160.2
281.4
362.4
520.8
783.4
SD
9.98
11.86
15.68
18.02
24.64
28.97
35.86
42.67
49.2
62.2
Ts
0.028
0.039
0.088
0.172
0.202
1.221
2.328
4.498
8.701
10.99
INIH
Ot
8.28
11.12
16.36
33.64
59.41
102.3
242.4
312.8
468.9
689.5
SD
9.1
10.04
14.98
15.54
19.52
23.24
29.12
36.64
41.1
59.2
Ts
0.021
0.038
0.079
0.156
0.209
1.208
2.23
4.308
8.021
9.02Table 2
Testing performance of DPA.
N
10
15
20
30
50
100
150
200
300
500
CS
Ot
2.26
4.16
5.52
10.28
15.14
30.48
45.32
66.46
101.1
168.2
SD
3.21
4.26
5.63
6.21
8.62
10.36
13.24
16.75
18.24
23.01
Ts
0.003
0.004
0.011
0.038
0.041
0.092
0.201
0.516
1.021
1.261
NIH
Ot
2.34
3.81
4.26
8.04
10.16
20.21
35.04
43.42
65.20
97.45
SD
3.18
4.06
5.18
6.02
7.64
9.87
12.26
15.24
16.21
20.21
Ts
0.003
0.004
0.010
0.032
0.040
0.086
0.197
0.498
0.901
1.209
DPA
Ot
2.18
3.22
4.06
7.64
9.01
15.32
29.41
33.84
42.89
68.54
SD
0
0
0
0
0
0
0
0
0
0
Ts
0.001
0.003
0.009
0.031
0.038
0.084
0.198
0.498
0.998
1.801Based on the previous analysis of testing data, we can obtain that DPA and INIH are better than CS and NIH for multiple carousels system. And the quality of INIH and DPA’s solution is well distinctive gradually without no more computing time and standard difference when the problem becomes of larger scale and more complicated. To be summarized, the computing efficiency and effectiveness of INIH and DPA are better accepted and will support strongly in practice.


## 7. Conclusions

Order picking has long been identified as the most labor-intensive and costly activity for almost every warehouse or distribution center. A bad order picking can lead to unsatisfactory service and high operational cost for the warehouse and consequently for the whole supply chain. In order to operate efficiently, the order picking process needs to be robustly designed and optimally controlled. In this paper we formulate the order picking optimization of multiple carousels system and give the mathematical model. According to the characteristics, an approximation algorithm (DPA) is presented for the special case of two carousels, and an improved nearest neighbor algorithm (INIH) is constructed for general problem. Finally, simulation tests are developed on the two heuristics. Experimental results verify that the optimum solutions are quickly and steadily achieved and show their better performance.As a generalization of our problem, there are a number of issues with different layout and rotating modes which are of interest for further research, for example, the multiple orders sequencing problem in the same environment. It is interesting to investigate that.



---

*Source: 692701-2013-10-31.xml*