The min–max order picking problem in synchronised dynamic zone-picking systems

ABSTRACT

In both manual and automated warehouses, a combination of efficient zoning and picker routing plays an important role in improving travel time, congestion, and system throughput. This paper considers the order picker routing problem in a dynamic and synchronised zoning environment, where the items corresponding to each customer order are picked simultaneously in multiple zones, and zones may change between different orders. The objective is to minimise the maximum time of completing the picking activities in any zone. Using a min–max type of objective not only minimises the makespan of an order picking wave, but it also helps balance the workload of the order pickers more effectively. We present a mathematical model for the optimal solution of this problem, as well as a dynamic programming approach to find the optimal solution for the case where a zone is a set of adjacent aisles. Computational experiments on randomly generated instances show that the dynamic programming approach is able to find optimal solutions in negligible computational times.

KEYWORDS:

• Warehouse management
• order picking
• zone picking
• workload balancing
• dynamic programming
• heuristics

1. Introduction

In order picking operations, items must be collected from the warehouse to satisfy the customer demand while aiming to optimise a cost or/and service-related objective (e.g. De Koster, Le-Duc, and Roodbergen 2007; Scholz et al. 2016; Van Gils et al. 2018; Çelik and Süral 2019; Masae, Glock, and Grosse 2020). In the last decades, a growing competition with limited time windows has put extra pressure on order picking operations. Furthermore, the increasing demands from online retailing have resulted in many relatively small-size orders with promised time windows, which make effective order picking and workload balancing necessary (Ardjmand et al. 2018; Vanheusden et al. 2020). Consequently, warehouse managers are under increased pressure to make use of their order picking resources in an efficient manner.

One way of ensuring a more efficient order picking process in terms of response time is the use of zone-picking. Zone-picking is a method of order picking where the picking area is divided into a number of zones so that the picking activity is being conducted at each zone by a different picker, sequentially or synchronously. Zone-picking also has other advantages including reduction of the travel time, achieving better workload balance, avoiding congestion within aisles, and ensuring familiarity of pick locations.

Although zone-picking and batch-picking are the two main factors influencing the performance of order picking processes at tactical and operational levels, zone-picking has received less attention in the literature among all order picking operations (Yu and de Koster 2009). Synchronised zone-picking refers to the zone-picking process where all pickers work on the same order simultaneously, thus creating a picking wave, whereas dynamic zone-picking refers to the zone-picking decisions made at the operational level, since it is possible to arrange the zone sizes and re-assign the pickers to zones at each picking wave. A dynamic zoning environment is especially important when synchronised zone-picking is considered, as fixed zones would lead to significant idle times where the pickers wait until all the pickers complete the picking activity. Hence, as opposed to static zoning, dynamic zoning is considered as an operational level decision problem and can be simultaneously addressed with other operational level problems, including picker routing and workload balancing.

In most picker routing problems, the main objective is to minimise the total travel time of the order pickers, as it constitutes more than half of the order picking time (Bartholdi and Hackman 2019). Since travel time is a function of distance, keeping the walking speed fixed and minimising the walking distance is proposed by many authors as the main factor to optimise the total picking time (e.g. Hall 1993; Vaughan and Petersen 1999; Roodbergen and de Koster 2001a; De Santis et al. 2018; Çelik and Süral 2019). On the other hand, in synchronised zone-picking, the lead time of an order picking is determined by the longest time taken by any of the order pickers in each zone. For this end, in this paper, we make use of a min–max objective for the order picking problem (OPP) in a parallel-aisle warehouse with a synchronised dynamic zone-picking system. Such zone-picking systems with a makespan minimisation objective dynamically balance the workload among pickers without the need of additional operational control. To the best of our knowledge, this is the first study that defines the OPP in a synchronised zone-picking system with a min–max objective, while also simultaneously considering the picker routing, zone assignment, and workload balancing decisions. The findings of this research should be helpful in warehouses where multiple pickers are employed, and lead time requirements are stringent.

Throughout this paper, we first present the min–max OPP without zoning and give the VRP min–max formulation. Afterwards, we discuss the OPP with dynamic zoning under the assumption that each zone of adjacent aisles is assigned to a single picker. For the min–max VRP without zoning, we propose a heuristic approach for the two-picker case based on the exact picker routing algorithm and the knapsack problem. This approach also constitutes a baseline for our exact approach for the min–max VRP with zoning, which runs in polynomial time. Finally, we work on randomly generated order picking instances where the pick locations in a picking list are independently and uniformly distributed over the order picking area to illustrate the algorithms and compare the performance of the solution methodologies in various computational experiments.

The remainder of this paper is organised as follows. Section 2 describes the warehouse corresponding to the OPP and provides a summary of the literature on picker routing, zone-picking, and integrated warehouse operations. In Section 3, we develop the min–max VRP formulations for multi-picker OPP without and with zoning constraints. In Section 4, we present the heuristic approach for the two-picker OPP without zoning. In Section 5, we develop an exact approach for the min–max OPP under synchronised dynamic zone-picking. Computational experiments are presented in Section 6, and the paper is concluded in Section 7.

2. Problem description and related literature

The parallel aisle warehouse considered in this paper is given in Figure 1. It contains cross-aisles at front and back of the picking-aisles as in Figure 1(a) and may contain middle cross-aisles, which perpendicularly divide the warehouse into blocks, and thereby divide the aisles into sub-aisles, as shown on Figure 1(b).

Figure 1. Two OPP instances. (a) A single-block warehouse with 6 aisles each with 16 time-unit length and 11 picking locations. (b) A three-block warehouse with 8 aisles each with 16 time-unit length and 25 picking locations (Çelik and Süral 2019).

Figure 2 shows the graph representations of the warehouses in Figure 1 where each pick location is represented by node $v_p$ while $v_0$ represents the depot, and the edge $\left(p,q\right)$ represents the path providing direct access between node $v_p$ and $v_q$. The nodes $a_i$ and $b_i$ represent the back and front intersection points of picking-aisle $i$, respectively. Nodes $m_{ij}$ represent the intersection point of picking-aisles $i$ and middle cross-aisle $j$. A back cross-aisle of a block is the front cross-aisle of the next block. A picker starts a feasible picking route from the depot, collects all the items in the picking list and returns to the depot. The OPP is to find such a feasible route that can be completed in the minimum time.

Figure 2. The graph representations of Figure 1(a) and (b) (Çelik and Süral 2019).

There exists an extensive literature on warehouse management problems. Reviews classifying warehouse problems include Rouwenhorst et al. (2000), De Koster, Le-Duc, and Roodbergen (2007), Gu, Goetschalckx, and McGinnis (2007), Van Gils et al. (2018), and Masae, Glock, and Grosse (2020). Particularly, Gu, Goetschalckx, and McGinnis (2007) conclude that zoning accounts for less than 6% in the surveyed literature. Van Gils et al. (2018) note that zoning and workforce-related problems are the ones that have drawn the least attention.

Due to the importance of order picking on the overall warehouse performance, the OPP is widely studied. Exact approaches for various versions of the problem include Ratliff and Rosenthal (1983), Roodbergen and de Koster (2001b), Scholz et al. (2016) and Pansart, Catusse, and Cambazard (2018), whereas heuristics are proposed by, among others, Hall (1993), Vaughan and Petersen (1999), Roodbergen and de Koster (2001a), Theys et al. (2010), De Santis et al. (2018), and Çelik and Süral (2019).

The zone-picking literature can be classified as (i) sequential zone-picking, where the pickers pick the items in a zone and pass to the picker in the next zone, and (ii) synchronised zone-picking, where the pickers pick the items simultaneously in different zones.

The literature regarding sequential zone-picking systems mostly consists of queuing network studies. De Koster (1994) analyses such a system as a Jackson queuing network where the order inter-arrival times and the zone service times are exponentially distributed. Yu and de Koster (2008) generalise the distribution of order inter-arrival and zone service times, and Yu and de Koster (2009) consider the general queuing network to analyse the impact of batching and zone-picking on throughput times. Melacini, Perotti, and Tumino (2011) extend the above-mentioned queuing literature by considering the number of zones and the number of pickers for each zone as variables. Van der Gaast et al. (2020) estimate the performance of such systems by also including the buffers capacities at each zone.

In the literature regarding synchronised zone-picking systems, Jane and Laih (2005) present a heuristic algorithm balancing the workloads of pickers at different zones to increase the utilisation of a picking wave. De Koster, Le-Duc, and Zaerpour (2012) focus on determining the optimal zone size at the tactical level while also considering sorting/consolidation time. Roy et al. (2012) develop a queuing network model and investigate the impact of the number of zones on response time and total travel time. Roy et al. (2019) model a queuing network of movable storage systems and investigate the performance zone-picker assignment strategies.

The main difference of our work from the above-mentioned zoning studies is that while these consider a static zoning environment, our paper focuses on dynamic zoning systems. To the best of our knowledge, there are very few studies considering dynamic zoning strategy. Bartholdi and Eisenstein (1996) and Bartholdi, Eisenstein, and Foley (2001) introduce the ‘bucket brigades’ concept where they model a sequential zone-picking process in a dynamic way where there are no fixed zones. Similarly, Ho and Liao (2009) propose a dynamic zoning strategy where an initial zone partition is designed by distance and flow relationships, then a metaheuristic is developed to help achieving better workload balance and finally a dynamic zone control method is applied for observation. Azadeh, Roy, and de Koster (2020) study an order picking process where robots are used instead of conveyor-like fixed systems to reduce pickers’ non-value-added travel times. The picker focuses only on picking process while accompanying robot travels between the picker and the depot. Azadeh, Roy, and de Koster (2020) also conclude that it would be significant to examine the optimal dynamic zone sizes to increase the system throughput which is another contribution of our study.

Van Gils et al. (2018) review and classify the most recent literature regarding the integration and interaction of the tactical and operational warehouse problems. Integrated OPP refers to jointly formulate and solve more than one operational warehouse problem (Van Gils et al. 2018; Scholz, Schubert, and Wäscher 2017). To the best of our knowledge, zone-picking operations have received no attention in integrated order picking literature.

The main contributions of this paper are two-fold. First, we define and solve an integrated zone-picking, picker routing and workload balancing problem by minimising the lead time of the picking wave and applying the policy of synchronised dynamic zone-picking where each picker is assigned to a zone of aisles at each picking wave. For this end, we present an exact polynomial-time DP algorithm, which may be implemented in many real-world warehousing environments and significantly improve performance. Second, for the first time in the literature, the zone-picking approach is studied at the operational level under a synchronised dynamic zone-picking policy. This paper is also one of the few studies which investigate the multi-picker multi-block OPP.

3. Min–max OPP with dynamic and synchronised zone-picking

In this section, we propose a min–max VRP formulation to minimise the lead time of the multi-picker wave-picking process, after which we introduce zoning constraints into the formulation. The following assumptions are made to model the problem:

• A zone is a set of contiguous identical aisles. An aisle cannot belong to more than one zone. The aisles are narrow enough so that order picking can be performed simultaneously from both sides of an aisle in negligible time.

• The warehouse performs wave-picking with a min–max type objective, and we focus on one wave at a time by applying synchronised dynamic zone-picking policy to operationally control the zone sizes and therefore picker workloads.

• Each order picking tour starts and ends at the same point (the depot), and all the items in the wave are picked in one picking tour (of each picker).

3.1. VRP formulation for the min–max OPP

Minimum total time travelled in a multi-picker OPP can be obtained by applying a two-index VRP variant of commodity flow formulation by Gavish and Graves (1978) (VRP-MINSUM). To consider balancing, we require a three-index formulation, where the additional index k is introduced for pickers to clarify which picker traverses edge (p, q): $x_{pqk}=\{\begin{array}{ll}1,& \text{if}{k}^{\text{th}}\text{ picker traverses edge}\left(p,q\right)\\ 0,& \text{otherwise}.\end{array}$

Let us define by $N$ as the set of all pick locations including the depot $\left(v_0\right)$ and $K$ as the set of all pickers. Also let $c_{pq}$ be the distance of edge $\left(p,q\right)$ and $g_{pqk}$ be the number of units of the commodity passed onto pick location $p\in N$ directly from pick location $q\in N$ by picker $k\in K$. The following commodity flow formulation aims to minimise the maximum distance travelled by any one of the pickers (VRP-MINMAX). $minL$ $\text{subject to}$ (1) $\begin{array}{rl}& \sum _{\begin{array}{c}p\in N\\ p\ne q\end{array}}\sum _{k\in K}{x}_{pqk}=1\text{for}q\in N\mathrm{\setminus }\left\{0\right\}\end{array}$(1) (2) $\begin{array}{rl}& \sum _{\begin{array}{c}q\in N\\ q\ne p\end{array}}\sum _{k\in K}{x}_{pqk}=1\text{for}p\in N\mathrm{\setminus }\left\{0\right\}\end{array}$(2) (3) $\begin{array}{rl}& \sum _{q\in N\mathrm{\setminus }\left\{0\right\}}{x}_{0qk}=1\text{for}k\in K\end{array}$(3) (4) $\begin{array}{rl}& \sum _{p\in N\mathrm{\setminus }\left\{0\right\}}{x}_{p0k}=1\text{for}k\in K\end{array}$(4) (5) $\begin{array}{rl}& \sum _{\begin{array}{c}p\in N\\ p\ne q\end{array}}{x}_{pqk}=\sum _{\begin{array}{c}p\in N\\ p\ne q\end{array}}{x}_{qpk}\text{for}q\in N\mathrm{\setminus }\left\{0\right\};k\in K\end{array}$(5) (6) $\begin{array}{rl}& \sum _{\begin{array}{c}p\in N\\ p\ne q\end{array}}\sum _{k\in K}{g}_{pqk}-\sum _{\begin{array}{c}p\in N\mathrm{\setminus }\left\{0\right\}\\ q\ne p\end{array}}\sum _{k\in K}{g}_{qpk}=1\text{for}q\in N\mathrm{\setminus }\left\{0\right\}\end{array}$(6) (7) $\begin{array}{rl}& g_{pqk}\le \left(\left|N\right|-\left|K\right|\right)x_{pqk}\text{for}p\in N;q\in N\mathrm{\setminus }\left\{0\right\};\\ & p\ne q;k\in K\end{array}$(7) (8) $\begin{array}{rl}& \sum _{p\in N}\sum _{q\in N}{c}_{pq}{x}_{pqk}\le L\text{for}k\in K\end{array}$(8) (9) $\begin{array}{rl}& x_{pqk}\in \left\{0,1\right\}\text{for}p\in N;q\in N;p\ne q;k\in K\end{array}$(9) (10) $\begin{array}{rl}& g_{pqk}\ge 0\text{for}p\in N;q\in N;p\ne q;k\in K\end{array}$(10)

In this formulation, the objective is to minimise the distance travelled by the latest picker. Constraints (1) and (2) state that each pick location should be visited exactly once by a picker. Constraints (3) and (4) state that exactly $\left|K\right|$ pickers should leave and return to the depot. Constraint (5) guarantees a tour for each picker. Constraint (6) ensures that exactly one unit of commodity is left to each pick location and constraint (7) states that no commodity is passed through the arcs that are not included in the picker tour. The main constraint leading to weakness of the formulation is the big-M constraint (7). $\left(\left|N\right|-\left|K\right|\right)$ is used as the big-M, since there are $\left|N\right|$ pick locations including the depot, and there are $\left|K\right|$ pickers, each of whom requires visiting at least one pick location. So, each picker can deliver at most $\left(\left|N\right|-\left|K\right|\right)$ units of the commodity. Constraint (8) ensures that the time travelled by each picker cannot be more than the longest tour, L, which is to be minimised in the objective function.

3.2. VRP-MINMAX formulation with zone-picking constraints

To incorporate zone-picking constraints into the formulation in the preceding section, we assume the warehouse follows a synchronised zone-picking policy where all pickers start simultaneously to better control throughput times. When pickers complete the picking tour, they wait for the completion of the overall picking wave at the depot. A zone is defined as a set of adjacent aisles and zones do not necessarily have the same number of aisles. A picker can be assigned at most one zone and an aisle cannot belong to more than one zone. We focus on minimising the lead time of a picking wave; hence, workload balancing is also achieved.

Let $M$ be the set of all aisles and parameter $e_p$ be the aisle on which the item $p\in N$ is located. Then define: $y_{ik}=\{\begin{array}{ll}1,& \text{if}{k}^{\text{th}}\text{ picker is assigned to aisle}i;i\in M,\\ 0,& \text{otherwise}\end{array}$

The following formulation (called VRP-Z) aims to minimise the maximum travel time subject to zoning constraints. $minL$ $\text{subject to}$ $\left(1\right)-\left(10\right)$ (11) $\begin{array}{rl}& y_{11}+y_{\left|M\right|,\left|K\right|}=2\end{array}$(11) (12) $\begin{array}{rl}& \sum _{k\in K}{y}_{ik}=1\text{for}i\in M\end{array}$(12) (13) $\begin{array}{rl}& \sum _{i\in M}{y}_{ik}\ge 1\text{for}k\in K\end{array}$(13) (14) $\begin{array}{rl}& 2x_{pqk}\le y_{\left(e_p\right)\left(k\right)}+y_{\left(e_q\right)\left(k\right)}\text{for}p\in N\mathrm{\setminus }\left\{0\right\};\\ & \text{for}q\in N\mathrm{\setminus }\left\{0\right\};p\ne q;k\in K\end{array}$(14) (15) $\begin{array}{rl}& y_{ik}\le y_{\left(i+1\right)k}+y_{\left(i+1\right)\left(k+1\right)}\text{for}i\in M\mathrm{\setminus }\left|M\right|;k\in K\mathrm{\setminus }\left|K\right|\end{array}$(15) (16) $\begin{array}{rl}& y_{ik}+y_{\left(i+1\right)\left(k-1\right)}\le 1\text{for}i\in M\mathrm{\setminus }\left|M\right|;k\in K\mathrm{\setminus }\left\{1\right\}\end{array}$(16) (17) $\begin{array}{rl}& y_{ik}\in \left\{0,1\right\}\text{for}i\in M;k\in K\end{array}$(17)

Constraint (11) guarantees that the first picker is assigned to the first aisle and the last picker is assigned to the last aisle. Constraint (12) ensures that each aisle is assigned to exactly one picker. Constraint (13) guarantees that each picker is assigned to at least one aisle. Constraint (14) is the linking constraint and guarantees that if $k^{th}$ picker is traversing the edge $\left(p,q\right)$, then the aisles, in which items $p$ and $q$ are located, are assigned to picker $k$. Constraints (15) and (16) ensure that a zone is a set of adjacent identical aisles such that if picker $k$ is assigned to aisle $i$, then the next aisle is assigned either to picker $k$ or picker $k+1$ and no further aisle can be assigned to the previous pickers.

4. A dynamic programming-based heuristic for the min–max OPP with two pickers

The integer programming formulations in Section 3.1 are computationally challenging to solve for larger instances, as will become apparent in Section 6. We first consider the case with two pickers and propose a heuristic approach for VRP-MINMAX, which also serves as the baseline for the exact approach for VRP-Z with a general number of pickers. The heuristic introduces a simple but effective DP algorithm by assigning pickers to aisles, which may be considered as constituting temporary zones. This is followed by an improvement scheme (the travel time balancing algorithm) derived from the knapsack problem, to reduce the optimality gap at the expense of aisle-zone integrity.

For the single-picker OPP, Ratliff and Rosenthal (1983) provide an exact algorithm consisting of $\left|M\right|$ stages where $\left|M\right|$ is the number of aisles. In their algorithm, there are two sub-stages for each aisle. Each stage has a number of states called equivalence classes represented by: (i) degree parity at the back of an aisle, (ii) degree parity at the front of an aisle, and (iii) number of connected components. Degree parities can be zero (0), even (E) or odd (U), while connectivity can be 0C, 1C or 2C. A partial tour can be represented by one of the six equivalence classes. These states are updated along the stages using two classes of connection types: intra-aisle and inter-aisle, as shown in Figure 3. At each stage, minimum tour lengths for each state are found by adding the related possible connection types to the minimum tour lengths of the previous sub-stage. At the last aisle, the partial tour with the minimum length sum is determined, which yields the optimal solution for the single-picker OPP.

Figure 3. (a) Possible intra-aisle connection types, (b) Possible inter-aisle connection types.

Before developing the proposed algorithms at this and following sections, we primarily summarise the notation.

Table

$M$	Set of all aisles; $M=\left\{1,2,\dots ,\left|M\right|\right\}$.
$RR\left(i,j\right)$	Minimum tour length solution of the R&R algorithm starting from depot, entering the zone starting with aisle $i$ and exiting to return to the depot from aisle $j$.
$min{L_i}^1$	Minimum tour length for picker 1 when aisle $i$ is set as the stopping aisle i.e. when first $i$ aisle is assigned to picker 1.
$min{L_i}^2$	Minimum tour length for picker 2 when aisle $i$ is set as the stopping aisle i.e. when last $\left|M\right|-i$ aisle is assigned to picker 2.
$F\left(i,k\right)$	Cost-to-go function, in Section 5, which is the travel time of the latest picker, for optimally assigning $k$ pickers to $i$ aisles; $i\in M$, $k\in M$, $i\ge k$.

4.1. Construction of temporary zones

In the first stage of the heuristic, we apply $RR\left(i,j\right)$ repeatedly for each picker after assigning their starting and ending aisles. Initially, the first aisle is assigned to picker 1 and the last $\left|M\right|-1$ aisles are assigned to picker 2, thus aisle $1$ is set as the stopping aisle. Then, minimum tour lengths are calculated for $RR\left(1,1\right)$ and $RR\left(2,\left|M\right|\right)$, and called $min{L_1}^1$ and $min{L_1}^2$. Subsequently, aisle $2$ is set as the stopping aisle and minimum tour lengths are calculated again $\left(min{L_2}^1,min{L_2}^2\right)$. The stopping aisle $i$ is increased in this manner until the minimum tour length for picker 1 exceeds the one for picker 2, i.e. $min{L_i}^1\ge min{L_i}^2$. At this final stage, the first $i$ aisles are assigned to picker 1 and the remaining $\left|M\right|-i$ aisles are assigned to picker 2 where picker 1 travels at least as many time units as picker 2. Note that, at $\left(i-1\right)$th stopping aisle stage,$min{L_{i-1}}^1\le min{L_{i-1}}^2$. At this previous stage, the first $i-1$ aisles are assigned to picker 1 and the remaining $\left|M\right|-i+1$ aisles are assigned to picker 2 where picker 1 travels at most as many time units as picker 2.

The aim of the proposed algorithm is to return a smaller wave time, i.e. smaller maximum time travelled, at the final and the previous stages. In the next section, we present an improvement algorithm that further reduces the wave time by minimising the absolute travel time difference between the two pickers.

4.2. Travel time balancing algorithm

In the first phase of the heuristic, one picker will travel more than the other. Reassignment of moves from one picker to the other is likely to improve the workload balance at the expense of zone integrity. For this end, we develop a DP algorithm called travel time balancing algorithm.

The problem stated here can be described as a variant of the knapsack problem to minimise the travel time difference between two pickers. Suppose we solve a $0-1$ knapsack problem having capacity $W$ with $i$ items each with weight $w_j$ and value $v_j$ with the following notation:

Table

$W$	$2\times \left(min{L_i}^1-min{L_i}^2\right)$.
$w_j=v_j$	Connection type 3 movement length for aisle $j$; $j\in \left\{1,2,\dots ,i\right\}$.
$w$	Travel time difference between the two pickers; $w\in \left\{1,2,\dots ,W\right\}$.
$K_1\left(j,w\right)$	The maximal movement obtainable when filling a knapsack of capacity $w$ time units using movements among aisles $1$ through $j$.
$K_2\left(j,w\right)$	The minimum difference between pickers obtainable when filling a knapsack of capacity $w$ time units using movements among aisles $1$ through $j$.

The objective for the $0-1$ knapsack problem is to select a subset of items to maximise the total value while satisfying the capacity constraint.$K_1$ value function stated as the following recursive formula refers to the knapsack DP algorithm: $K_1\left(j,w\right)=\{\begin{array}{ll}{K}_1\left(j-1,w\right),& w_{j-1}>w\\ \begin{array}{l}max\left(K_1\right(j-1,w),\\ K_1\left(j-1,w-2w_{j-1}\right)\\ +w_{j-1}),\end{array}& \text{otherwise}\end{array}$ where the base cases are $K_1\left(0,w\right)=0$ for $w\in \{1,2,\dots ,W\}$ and $K_1\left(j,0\right)=0$ for $j\in \left\{1,2,\dots ,i\right\}$. Since we would like to reach as close as possible to half of the knapsack capacity,$\left(min{L_i}^1-min{L_i}^2\right)$, we aim to choose a subset of connection type 3 intra-aisle movements from first $i$ aisles, take it from picker 1 and give it to picker 2 to minimise the difference between two pickers. To solve this problem, we use another value function storing the actual difference. Such values can be stored at $K_2$ value function as: $K_2\left(j,w\right)=\left|min{L_i}^1-min{L_i}^2-2\times K_1\left(j,w\right)\right|$

The optimal subset of movements,$K_1\left(j,w\right)$, is the one which minimises the difference $K_2\left(j,w\right).$ A pseudocode of the algorithm is depicted in Algorithm 1.

Finally, the maximum time travelled at the final stage and the previous stage are compared and the smaller of these two maximums is found. $\begin{array}{rl}minma{x}_h& =min\left(max(min{L_i}^1,min{L_i}^2\right),\\ & max(min{L_{i-1}}^1,min{L_{i-1}}^2))\end{array}$

This heuristic returns the best split between two pickers that has the smallest wave time. Here, we find a near optimal min–max solution for the two-picker min–max OPP while balancing the workload of the pickers and forcing them to use the minimum-time routes. The pseudocode of the two-picker min–max OPP algorithm is depicted in Algorithm 2.

4.3. Numerical example

For the example given in Figure 1(a), we demonstrate the solutions of MINSUM, initial phase of the heuristic, and MINMAX in Figure 4(a–c), respectively.

Figure 4. The minimum time solutions for the example in Figure 1(a). (a) VRP-MINSUM, (b) VRP-MINMAX and two-picker OPP algorithm, (c) initial phase of the two-picker dynamic zone-picking heuristic.

Table

Algorithm 1 Travel time balancing algorithm

for aisle $j=1toi$ do

for difference $w=0toW$ do

if aisle $j=1$ or difference $w=0$

$K_1\left(j,w\right)=0$

else if $\left(2\times w_{j-1}\le w\right)$

$K_1\left(j,w\right)=\text{max}\left(K_1\left(j-1,w\right),K_1\left(j-1,w-2\times w_{j-1}\right)+w_{j-1}\right)$

else

$K_1\left(j,w\right)=K_1\left(j-1,w\right)$

$K_2\left(j,w\right)=\left|min{L_i}^1-min{L_i}^2-2\times K_1\left(j,w\right)\right|$

end if

end for

end for

for aisle $j=1toi$ do

for difference $w=0toW$ do

if $temp>K_2\left(j,w\right)$

$temp=K_2\left(j,w\right)$

${\mathrm{\Delta }}_i=K_1\left(j,w\right)$

end if

end for

end for

$min{L_i}^1=min{L_i}^1-{\mathrm{\Delta }}_i$

$min{L_i}^2=min{L_i}^2+{\mathrm{\Delta }}_i$

Table

Algorithm 2 Two-picker min–max OPP algorithm

for aisle $i=1to\left|M\right|$ do

let $RR\left(1,i\right)=\mathit{m}\mathit{i}\mathit{n}{{\mathit{L}}_{\mathit{i}}}^1$

let $RR\left(i+1,\left|M\right|\right)=\mathit{m}\mathit{i}\mathit{n}{{\mathit{L}}_{\mathit{i}}}^2$

if $\mathit{m}\mathit{i}\mathit{n}{{\mathit{L}}_{\mathit{i}}}^1\ge \mathit{m}\mathit{i}\mathit{n}{{\mathit{L}}_{\mathit{i}}}^2$

Improve results for the final stage by applying travel time balancing algorithm

Improve results for the previous stage

Break

return $minma{x}_h=min\left(max(min{L_i}^1,min{L_i}^2\right),max(min{L_{i-1}}^1,min{L_{i-1}}^2))$

else

continue

end if

end for

The VRP-MINSUM model minimises the total time travelled at 112 time units, with a maximum travel time of 92 units. The VRP-MINMAX model minimises the maximum time travelled at 58 units. Moreover, the difference between pickers is only 2 units. The first phase of the proposed heuristic yields an approximate solution for the VRP-MINMAX problem with 62 units. The difference between the travel times of the pickers is 10 units. Finally, this difference is further reduced by the balancing heuristic at the expense of aisle-zone integrity using the travel time balancing algorithm, which yields the same solution of the VRP-MINMAX formulation.

In the following section, we extend the temporary zoning idea in this section to develop an exact approach for the min–max OPP under dynamic zoning and a general number of pickers.

5. An exact algorithm for the min–max OPP under synchronised dynamic zone-picking

Contrary to tactical level zone-picking policy, there are no dedicated zones assigned to pickers at the operational level. Zones are assigned to pickers at each picking wave. Thus, the zone-picking problem is reduced to an operational level decision integrated with routing and workload balancing problems. In this way, we solve an integrated zone-picking, picker routing and workload balancing problem where each zone consists of a certain number of aisles.

In this proposed algorithm, we first determine all minimum tour lengths for each possible zone configuration. Based on this information, we recursively look at the optimal combination of zone assignments that minimises the longest-time tour length for a given number of pickers.

Proposition 1 states the required number of minimum tour length information prior to zone assignment. Proofs of the propositions can be found in the Appendix.

Proposition 5.1:

R&R algorithm can be calculated for $\frac{\left(\left|M\right|\right)\left(\left|M\right|+1\right)}{2}$ different zone configurations for an $\left|M\right|$-aisle picking area in polynomial time.

Proposition 2 states the number of possible zones for picker $k$ and implies that zone-assignment problem can be studied using combinational calculations.

Proposition 5.2:

There are $\left(\begin{array}{c}\left|M\right|-1\\ k-1\end{array}\right)$ different zone configurations to assign k pickers to $\left|M\right|$ aisles in an $\left|M\right|$-aisle picking area.

As an example, a visual representation on which k pickers are assigned to 6 aisles where $k\in \left\{1,2,\dots ,6\right\}$ is shown in Figure 5.

Figure 5. Visual representation of 6-aisle picking area zone-assignment.

Next, we present two corollaries to better define the later DP recursion.

Corollary 5.1:

The $\left(\begin{array}{c}\left|M\right|-1\\ k-1\end{array}\right)$ possible zone configurations can be represented in a Binomial Expansion where each row represents the number of aisles and each ‘top-right to bottom-left diagonal line’ represents the number of pickers as shown in Figure 6. This can be coded down where each row represents the number of aisles and each column represents the number of pickers.

Figure 6. Binomial expansion of 6-aisle picking area zone-assignment.

The coefficients in the Binomial Expansion also correspond to the entries of Pascal’s Triangle such that the $\left(\begin{array}{c}i\\ k\end{array}\right)$th coefficient in the Binomial expansion is equal to the entry at aisle $i$, picker $k$ in the Pascal’s Triangle.

Corollary 5.2:

We can track the pathways of $\left(\begin{array}{c}\left|M\right|-1\\ k-1\end{array}\right)$ possible zone configurations to assign $k$ pickers to $\left|M\right|$ aisles using Pascal’s Triangle graph representation.

For example, there are $\left(\begin{array}{c}5\\ 2\end{array}\right)$ different pathways to go to the entry at aisle $6$, picker $3$ in the Pascal’s Triangle as shown in Figure 7.

Figure 7. The pathways of 10 possible zone configurations for 6 aisles and 3 pickers.

We can now state the main theorem of this study and Algorithm 3. With this algorithm, we can track the optimal combination of zone assignments that minimises the longest-time tour length for a given number of pickers.

Theorem 5.1:

The min–max OPP in synchronised dynamic zone-picking systems can be solved in polynomial time using DP.

Proof:

$F\left(i,k\right)$ is the cost-to-go function which is equal to the lead time of the picking wave that optimally assigns $k$ pickers to $i$ aisles, where $i\ge k$; $i\in M$. As the initial step, for the single picker case where $k=1,$ it is clear that $F\left(i,1\right)=RR\left(1,i\right)$. Moreover, when the number of pickers equals to the number of aisles where $k=i,$ the cost-to-go function returns $F\left(i,i\right)=\underset{j=\mathrm{1..}i}{max}\left\{RR\left(j,j\right)\right\}$. Then, the general DP recursion can be formalised as follows: $F\left(i,k\right)=\underset{j=k-1,\dots ,i-1}{min}\left\{max\left[F\left(j,k-1\right);RR\left(j+1,i\right)\right]\right\}$ Here, the problem of finding the optimal combination of zone assignment for $\left|M\right|$ aisles and $k$ pickers is broken down into the subproblem of introducing the $k^{th}$ picker and combining it with memorised optimal zone assignment subproblem solutions for $k-1$ pickers. In total, we have $\left(k-1\right)\times \left(\left|M\right|-\left(k-1\right)\right)$ subproblems to assign k pickers to |M| aisles where each of them has a constant running time thanks to the memorisation. This implies that the recursion has an overall computational complexity of $O\left(k\left|M\right|\right).$

As an example, Figure 8 depicts a visual representation of Algorithm 3 to find the minimum lead time of a picking wave among $\left(\begin{array}{c}5\\ 2\end{array}\right)$ possible zone configurations with 3 pickers and 6 aisles, i.e. $F\left(6,3\right)$.

Figure 8. Visual representation of Algorithm 3.

A pseudocode of the algorithm is given in Algorithm 3.

Table

Algorithm 3 Dynamic zone-picking algorithm for multiple order pickers

for aisle $i=1to\left|M\right|$ do

for aisle $j=ito\left|M\right|$ do

return $RR\left(i,j\right)$

end for

end for

for aisle $i=1to\left|M\right|$ do

$F\left(i,1\right)=RR\left(1,i\right)$

end for

for aisle $i=2to\left|M\right|$ do

if $\left(F\left(i-1,i-1\right)>R\left(i,i\right)\right)$

$F\left(i,i\right)=F\left(i-1,i-1\right)$

else

$F\left(i,i\right)=R\left(i,i\right)$

end if

end for

for aisle $i=3to\left|M\right|$ do

for picker $k=2to\left(i-1\right)$ do

for $j=\left(k-1\right)to\left(i-1\right)$ do

if $temp>\text{max}\left(F\right(j,k-1),RR(j+1,i)$

$temp=\text{max}\left(F\right(j,k-1),RR(j+1,i)$

end if

end for

$F\left(i,k\right)=temp$

end for

end for

By this method, we not only minimise the lead time of the picking wave for each number of pickers, but we also balance the pickers’ travel times.

Proposition 1 allows us to calculate the minimum tour length for each possible zone configuration. Given that there are multiple blocks, heuristic approaches (e.g. S-shape, largest gap, aisle-by-aisle, or combined) can be applied to calculate the routes for each possible zone configuration instead of the R&R algorithm. In this way, the multi-picker dynamic zone-picking algorithm can be heuristically solved for a multi-block layout. For the multi-block OPP instance in Figure 1(b), Figure 9 shows the resulting 3-picker routes for S-shape, largest gap, aisle-by-aisle, and combined heuristic solutions, with minimum wave-picking lead times of 78, 76, 88, and 76 time units, respectively.

Figure 9. Resulting 3-picker heuristic solutions for the instance in Figure 1(b). (a) S-shape heuristic solution. (b) Largest gap heuristic solution. (c) Aisle-by-aisle heuristic solution. (d) Combined heuristic solution.

6. Computational experiments

In this section, we present the computational experiments conducted in line with those in the literature (Roodbergen and de Koster 2001a; Scholz et al. 2016). First, we test the performance of the two-picker min–max OPP algorithm by analysing the optimality gaps and computational times. Secondly, we aim to observe the impact of the number of pickers on lead time savings. Thirdly, we study the impact of zone-picking on the lead time by comparing the results of zone-picking and no zone-picking policies. Lastly, we test the performance of the algorithm on multi-block layouts by considering four well-known routing heuristics.

Following Roodbergen and de Koster (2001a), we use a set of 2,000 instances for each combination. We implement the models in AMPL modelling language and the algorithms in C++ in Microsoft Visual Studio 2019. Average run times of algorithms are below 0.1 s, and hence are not reported. In all settings, the horizontal length between two adjacent aisles set to 2 time units. The end of a sub-aisle (length) of a block also refers to the centre of the back cross-aisle of that block and the front cross-aisle of the next block.

6.1. Performance of the algorithms

In the first experiments, the performance of the two-picker min–max OPP algorithm is analysed using optimality gaps. We use the first set of instances where there are 7 or 15 aisles, each with a length of 10 or 30 time units, and 10 or 15 pick items in the picking list. The summary of the results is given in Table 1.

Table 1. Summary of the computational experiments.

						Savings (%)			VRP-Z Model
Aisles	Items	Length	Optimal %	Average Gap %	Standard Deviation of GAP %	VRP-MINMAX Model	Algorithm	Difference between Pickers after 2000 Picks (time units)	% of Solved Instances	Average Computing Time (s)
7	10	10	90.90	0.51	1.75	34.41	34.09	0	100.0%	0.27
7	10	30	69.50	1.59	3.01	39.40	38.47	12	100.0%	0.26
15	10	10	92.20	0.28	1.05	29.46	29.27	4	100.0%	2.14
15	10	30	66.55	1.25	2.27	37.77	37.01	6	100.0%	2.09
7	15	10	87.10	0.64	1.81	38.23	37.84	6	100.0%	2.19
7	15	30	60.75	1.70	2.67	44.05	43.10	4	100.0%	2.14
15	15	10	89.85	0.28	0.90	33.99	33.80	2	54.0%	34.73
15	15	30	60.30	1.14	1.80	42.37	41.71	10	60.3%	33.34

In Table 1, Optimal % refers to the percentage of the number of optimal instances out of 2000 instances for each setting. For each instance, the gap is calculated as $GAP=\frac{Z_H-Z_{MINMAX}^{\ast }}{Z_{MINMAX}^{\ast }}$ where $Z_{MINMAX}^{\ast }$, represents the optimal travel time for VRP-MINMAX problem and $Z_H$, represents the travel time of the latest picker calculated by the two-picker OPP algorithm. The results in Table 1 show that the algorithm leads to either optimal solutions or very small gaps from the VRP-MINMAX model. Overall settings, a maximum of 92.2% and an average of 77.1% of the solutions are optimal, and the average gap remains below 1.7%. Average Savings represent the average percent time savings when two pickers are used instead of a single picker. We can conclude that using two pickers reduces the order picking time at least about one-third with the best improvement of 44% for the VRP-MINMAX model and 43% for the heuristic. Furthermore, it can be inferred from Table 1 that the larger the number of items and the longer the length of an aisle, the more significant is the assigning of a second picker.

For each instance or picking wave, both pickers start collecting the orders together. When a picker arrives back to the depot earlier, s/he is assigned to the longer route for the next picking wave to keep the workload balanced in the long run. The average time difference between the pickers is shown on the next column of Table 1. On average, the average time difference between the two pickers is just 5.5 units, which shows that the algorithm can balance the workload substantially.

In the last two columns of Table 1, we present the average computational times of the VRP-Z formulation to compare its performance with one of the proposed exact algorithms for the min–max OPP under synchronised dynamic zone-picking. We test the VRP-Z formulation using the same instance set with up to 6 pickers by setting a time limit of 60 s. VRP-Z formulation results in significantly large number of unsolved instances when the number of pick locations and the number of aisles is even slightly larger. The results show that there are a maximum of 45% unsolved instances when the number of pick locations is increased from 10 to 15 and the number of aisles is increased from 7 to 15. Hence, we can conclude that the proposed VRP-Z formulation leads to large computing times when the number of pick locations the number of aisles is large. On the other hand, the proposed algorithm solves all instances in this set almost instantly (<0.01 s). Even, using the second set of instances (Scholz et al. 2016), as the number of pick locations is increased to 90 and the number of aisles is set as 30, the maximum computation time remains below 0.1 s.

6.2. Impact of multiple pickers on lead time of the picking wave for single block layout

To analyse the impact of the multiple pickers on lead time savings, we use the exact algorithm presented in Section 5 on two different sets of randomly generated instances. The first is the same as the one presented in Section 6.1, whereas the second set of instances is the subset of the instance set designed by Scholz et al. (2016), where we set the number of aisles as 10, 20 or 30, aisle length as 10, 30 or 50 time units, and number of pick items as 30, 60 or 90.

Figure 10 shows the averages of percentage reductions on the travel time gained by introducing each additional picker for 7-aisle and 15-aisle cases. As a baseline, we set the value of single-picker lead time as 100%. Figure 10 shows that assigning additional pickers significantly decreases the lead time of a picking wave, but to a certain extent and in a decreasing rate. In other words, the law of diminishing marginal returns applies.

Figure 10. Impact of number of pickers on lead time reduction.

According to the findings from the first set, there is an average of 35% reduction with the introduction of the second picker. However, the impact of reduction decreases to 9% with the 3rd and to 3% with the 4th picker. Although there is still some decrease with the introduction of a new picker, this difference reduces to below 1% for the 6th picker. As Figure 10 also shows, relatively larger aisle lengths (triangle markers on the plot) result in more savings with each additional picker. The results also suggest that if the number of pick locations is relatively larger, additional pickers yield more savings. The last important finding from Figure 10 is that an additional picker brings slightly more benefits if the number of aisles is relatively smaller.

We gain the same insights with the second set. The findings are depicted in Figure 11, which shows the averages of reductions gained by introducing a new picker for the 10-aisle, 20-aisle, and 30-aisle cases.

Figure 11. Impact of number of pickers on lead time reduction with Scholz et al. (2016) instances.

From Figure 11, there is an average of 43% reduction with the introduction of the second picker. The impact of reduction decreases to 13.5% with the 3rd and to 6.5% with the 4th picker. This difference drops below 1% after the 9th picker for the most extreme test instance. We also notice that assigning 9 pickers yields 82% savings in the most extreme case. Moreover, larger aisle length results in more savings with each additional picker. Figure 11 also shows that the most significant impact factors are the aisle length and the number of pick items. Another interesting result is that although the size of the instance set is more than doubled in the most extreme case when it is compared to the most extreme case of the previous instance set, the threshold number of pickers, beyond which no more significant saving is gained, is only increased by half.

In terms of finding a balanced configuration between the warehouse size and number of pickers, we observe that the number of aisles is not a significant factor. However, the length of aisle is significant in the sense that the deeper the aisles, the more significant is the assigning of an additional picker. Consequently, managers should consider assigning each additional picker more carefully due to decreasing pace in the lead time reduction. As a rule of thumb, managers can keep in my that, for relatively large aisles, assigning the 2nd picker results in about 45% reduction in lead time of a pick wave, independent of the warehouse size. A 3rd picker would lead to 15% reduction in average beyond which it will never reach 10% under synchronised zone-picking systems.

6.3. Comparison of zone-picking and no zone-picking cases

Next, we aim to assess the impact of zone-picking on travel time by comparing the gap between the results of the min–max OPP with those without zone-picking. We include 6 pickers in the first set of instances beyond which no value is added by additional pickers. Table 2 shows a summary of these gaps. For each of these combinations, best results are indicated in darker grey-colour scale. Equal Results % refers to the percentage of the number of instances with the same results out of 2000 instances. The first inference that can be drawn from Table 2 is that the percentage of equal results increases significantly with each additional picker as it increases from 60.9% in average while there are 2 pickers to 99.8% in average with 6 pickers.

Table 2. Gap analysis between zone-picking and no zone-picking cases.

			No. of Pickers
No. of Aisles	No. of Items	Length	2	3	4	5	6
			Equal Results %
7	10	10	79.70	84.00	96.80	99.75	100.00
7	10	30	56.65	66.00	82.60	95.80	99.95
15	10	10	77.05	78.80	95.15	99.70	100.00
15	10	30	48.65	48.75	65.25	86.70	97.15
7	15	10	73.55	79.80	96.15	99.65	100.00
7	15	30	44.80	60.45	73.80	92.60	99.65
15	15	10	68.50	73.65	86.65	97.80	99.85
15	15	30	38.05	38.60	43.60	66.00	85.40
			Average Gap %
7	10	10	1.26	1.11	0.22	0.02	0.00
7	10	30	2.69	2.06	1.05	0.26	0.00
15	10	10	0.92	0.87	0.19	0.01	0.00
15	10	30	2.33	2.55	1.70	0.65	0.11
7	15	10	1.42	1.19	0.27	0.03	0.00
7	15	30	2.95	2.06	1.36	0.37	0.02
15	15	10	0.92	1.03	0.50	0.09	0.01
15	15	30	2.41	2.92	2.69	1.55	0.77
			Standard Deviation of Gap %
7	10	10	2.85	2.78	1.24	0.38	0.00
7	10	30	4.07	3.60	3.65	1.47	0.11
15	10	10	1.93	1.84	0.89	0.28	0.00
15	10	30	3.13	3.41	2.91	1.97	0.71
7	15	10	2.66	2.52	1.45	0.42	0.00
7	15	30	3.49	3.18	2.77	1.60	0.33
15	15	10	1.51	1.94	1.41	0.66	0.15
15	15	30	2.60	3.35	3.07	2.66	2.13

Results from Table 2 also show that the extent of suboptimality from imposing zone picking, reduces significantly with each introduced picker (decrease from 1.86% with 2 pickers to 0.11% with 6 pickers). This is because possible movements become more limited when fewer aisles are assigned to each picker.

From Table 2, it can be inferred that aisle-length is also a significant, but negatively associated factor since an increase in the aisle-length leads to a reduction in the number of equal results (from 89.33% to 69.52% in average, p-value < 0.01) and a rise in the average (from 0.50% to 1.53% in average, p-value < 0.01) and standard deviation (from 1.25% to 2.50% in average, p-value < 0.01) of gaps.

6.4. Multiple order pickers for multi-block layout and a comparison of heuristics

Finally, we would like to analyse the performance of the multi-picker dynamic zone-picking algorithm on multi-block layouts by applying four well-known heuristics on the first set of instances with up to 5 blocks and 7 pickers. S-shape, largest gap, and combined heuristics are improved at the same extent by forcing that the entering aisle for the closest block to the depot should be the rightmost filled picking sub-aisle (Roodbergen and de Koster 2001a).

Table 3 gives the average minimum lead times of the picking waves. For each combination, the best heuristic is indicated in grey colour scale and bold-italic. Table 3 shows that the combined heuristic significantly outperforms other heuristics for multi-block layouts and the performance of the heuristics converges with the increase in the number of pickers.

Table 3. Minimum wave-picking lead times with each additional picker for multi-block layout settings.

				Number of Blocks
				1							2							3							4							5
				No. of Pickers							No. of Pickers							No. of Pickers							No. of Pickers							No. of Pickers
Method	No. of Aisles	No. of Items	Length	1	2	3	4	5	6	7	1	2	3	4	5	6	7	1	2	3	4	5	6	7	1	2	3	4	5	6	7	1	2	3	4	5	6	7
	7	10	10	79.2	49.2	40.0	36.9	36.4	36.6	37.2	100.4	63.3	54.8	52.9	52.7	52.9	53.5	122.6	79.8	71.9	70.3	70.1	70.3	70.9	141.0	97.5	89.4	87.8	87.7	87.8	88.2	159.5	115.3	106.8	105.3	105.2	105.4	106.0
	7	10	30	191.9	112.6	80.9	73.6	70.4	69.7	70.2	255.9	152.6	129.5	123.9	122.8	122.8	123.3	309.1	199.8	180.8	177.4	176.8	176.8	177.3	354.4	249.7	233.6	231.2	231.0	231.2	231.4	403.4	301.9	287.4	285.5	285.4	285.5	285.8
	15	10	10	127.3	83.2	69.9	65.3	64.0	63.9	63.9	143.5	94.4	82.7	79.6	79.0	79.0	79.0	174.2	111.3	98.5	95.1	94.6	94.5	94.5	194.1	129.0	114.9	111.7	111.1	111.0	111.0	217.2	147.7	132.6	129.1	128.5	128.4	128.4
	15	10	30	278.0	161.9	123.5	105.8	98.6	95.6	94.7	325.0	195.5	159.2	148.6	145.5	145.0	144.9	381.0	239.2	207.1	199.1	197.6	197.5	197.4	425.3	286.9	258.2	251.8	250.8	250.7	250.7	476.8	338.5	311.2	305.6	305.0	305.0	305.0
	7	15	10	88.5	54.2	42.7	38.8	37.8	37.8	38.1	121.5	73.1	59.1	55.4	54.8	54.8	55.0	154.3	91.0	76.4	73.1	72.5	72.5	72.8	174.3	108.8	94.4	91.1	90.5	90.5	90.8	195.3	127.0	112.7	109.4	108.8	108.8	109.1
	7	15	30	218.5	127.3	90.0	77.3	73.5	72.4	72.6	318.8	184.1	139.9	130.6	127.6	126.9	127.1	393.3	231.1	192.1	184.6	182.8	182.5	182.7	445.7	281.0	245.7	239.3	238.1	238.0	238.2	499.5	333.1	301.4	295.5	294.6	294.6	294.7
	15	15	10	151.3	94.8	77.4	70.0	67.1	66.5	66.4	178.0	110.6	90.7	84.3	82.6	82.2	82.2	223.5	129.9	107.6	100.9	99.2	98.8	98.8	243.0	147.9	124.7	117.7	116.0	115.7	115.7	267.7	166.8	142.9	135.6	133.7	133.4	133.4
	15	15	30	345.4	195.9	147.6	121.7	108.4	102.3	99.4	425.9	244.0	185.1	162.3	154.1	151.4	150.7	505.3	290.5	231.6	212.0	206.3	204.8	204.6	550.4	336.1	280.9	264.2	259.9	259.2	259.2	603.2	385.9	332.5	318.3	314.8	314.3	314.3
S-Shape
	7	10	10	76.0	46.7	39.4	36.8	36.4	36.6	37.2	95.8	61.6	54.6	52.9	52.7	52.9	53.5	114.2	78.4	71.8	70.3	70.1	70.3	70.9	132.8	96.3	89.2	87.8	87.7	87.8	88.2	152.0	114.3	106.8	105.3	105.2	105.4	106.0
	7	10	30	164.1	98.8	80.0	73.6	70.4	69.7	70.2	218.8	145.1	129.1	123.8	122.8	122.8	123.3	268.3	194.5	180.5	177.3	176.8	176.8	177.3	317.4	246.0	233.3	231.1	231.0	231.2	231.4	369.1	299.2	287.3	285.5	285.4	285.5	285.8
	15	10	10	123.7	79.8	69.2	65.0	64.0	63.9	63.9	146.0	92.2	82.2	79.5	79.0	79.0	79.0	168.7	109.1	97.9	95.0	94.6	94.5	94.5	188.9	127.0	114.6	111.6	111.1	111.0	111.0	211.7	145.8	132.3	129.0	128.5	128.4	128.4
	15	10	30	228.2	141.0	114.1	103.9	98.2	95.5	94.7	280.8	180.6	156.6	148.2	145.5	145.0	144.9	332.6	227.9	205.5	199.0	197.6	197.5	197.4	382.0	278.4	257.2	251.7	250.8	250.7	250.7	436.7	331.6	310.4	305.6	305.0	305.0	305.0
	7	15	10	88.5	52.2	42.1	38.6	37.8	37.8	38.1	116.3	69.7	58.5	55.4	54.8	54.8	55.0	140.9	87.1	76.0	73.1	72.5	72.5	72.8	161.2	105.4	94.1	91.1	90.5	90.5	90.8	181.0	123.9	112.4	109.3	108.8	108.8	109.1
	7	15	30	197.5	113.3	85.6	77.2	73.5	72.4	72.6	269.0	165.5	138.1	130.4	127.6	126.9	127.1	329.2	215.7	191.1	184.5	182.8	182.5	182.7	382.5	267.7	244.8	239.2	238.1	238.0	238.2	435.6	322.3	300.4	295.4	294.6	294.6	294.7
	15	15	10	146.8	91.1	75.1	69.2	66.9	66.4	66.4	179.3	106.9	89.2	84.0	82.5	82.2	82.2	212.9	124.5	106.1	100.6	99.1	98.8	98.8	237.1	142.5	123.4	117.4	116.0	115.7	115.7	260.3	162.1	141.7	135.3	133.7	133.4	133.4
	15	15	30	284.0	167.8	129.9	113.4	105.8	101.5	99.2	353.3	214.3	173.8	159.5	153.5	151.3	150.7	419.9	263.5	223.8	210.4	206.0	204.8	204.6	474.1	312.7	275.3	263.1	259.8	259.2	259.2	527.7	365.3	328.3	317.5	314.7	314.3	314.3
Largest Gap
	7	10	10	70.8	45.5	38.5	36.6	36.4	36.6	37.2	97.1	62.9	54.4	52.8	52.7	52.9	53.5	126.5	81.9	71.6	70.2	70.1	70.3	70.9	157.4	101.6	88.8	87.7	87.7	87.8	88.2	188.2	121.3	106.2	105.2	105.2	105.4	106.0
	7	10	30	163.5	97.6	77.3	71.6	69.7	69.6	70.2	244.6	151.5	127.4	123.2	122.7	122.8	123.3	333.7	209.2	179.7	177.0	176.8	176.8	177.3	424.9	267.6	233.1	231.0	230.9	231.2	231.4	517.9	327.0	287.0	285.4	285.4	285.5	285.8
	15	10	10	111.2	76.5	67.2	64.4	64.0	63.9	63.9	137.8	94.0	82.4	79.5	79.0	79.0	79.0	170.1	114.4	98.8	95.1	94.6	94.5	94.5	204.1	135.7	115.7	111.6	111.1	111.0	111.0	238.4	157.5	133.3	128.9	128.4	128.4	128.4
	15	10	30	226.6	139.6	110.8	100.1	95.9	94.8	94.6	307.3	194.6	157.8	147.4	145.3	144.9	144.9	403.0	256.3	209.4	198.9	197.5	197.4	197.4	505.9	323.1	262.1	251.9	250.7	250.7	250.7	610.0	388.4	317.2	305.7	305.0	305.0	305.0
	7	15	10	80.7	50.5	41.3	38.3	37.8	37.8	38.1	116.7	72.5	58.5	55.2	54.7	54.8	55.0	154.0	96.2	76.1	72.9	72.5	72.5	72.8	192.9	120.4	94.4	90.7	90.5	90.5	90.8	231.5	144.5	112.8	109.0	108.8	108.8	109.1
	7	15	30	193.0	113.9	84.5	75.9	73.0	72.4	72.6	301.6	181.7	137.5	128.9	127.1	126.9	127.1	415.3	253.2	191.5	183.4	182.6	182.5	182.7	528.1	324.0	247.2	238.6	238.1	238.0	238.2	650.8	400.0	303.9	294.9	294.6	294.6	294.7
	15	15	10	132.3	86.7	73.2	68.2	66.6	66.4	66.4	168.9	109.1	90.4	84.1	82.5	82.2	82.2	211.3	134.9	109.9	101.3	99.1	98.8	98.8	256.8	162.2	130.5	118.5	116.0	115.7	115.7	303.1	190.1	151.3	136.6	133.7	133.4	133.4
	15	15	30	283.8	167.5	129.4	110.9	103.1	99.6	98.4	394.6	237.5	184.3	160.3	152.8	151.0	150.7	525.3	319.7	245.6	213.9	206.1	204.7	204.6	658.8	400.9	309.0	268.5	259.9	259.2	259.1	795.4	485.2	371.9	323.8	315.1	314.3	314.3
Aisle-by-aisle
	7	10	10	70.8	45.5	38.5	36.6	36.4	36.6	37.2	88.8	60.1	54.0	52.8	52.7	52.9	53.5	111.3	77.5	71.4	70.2	70.1	70.3	70.9	130.6	95.5	88.9	87.7	87.7	87.8	88.2	150.6	113.6	106.5	105.3	105.2	105.4	106.0
	7	10	30	163.5	97.6	77.3	71.6	69.7	69.6	70.2	218.8	141.7	126.5	123.1	122.7	122.8	123.3	272.1	192.1	179.0	177.0	176.8	176.8	177.3	321.3	243.9	232.6	231.0	230.9	231.2	231.4	373.3	297.3	286.6	285.4	285.4	285.5	285.8
	15	10	10	111.2	76.5	67.2	64.4	64.0	63.9	63.9	126.9	89.6	81.2	79.3	79.0	79.0	79.0	158.7	107.4	97.2	94.8	94.6	94.5	94.5	180.7	125.8	114.1	111.5	111.1	111.0	111.0	205.5	145.1	131.9	128.9	128.5	128.4	128.4
	15	10	30	226.6	139.6	110.8	100.1	95.9	94.8	94.6	272.1	176.9	153.0	146.5	145.2	144.9	144.9	332.4	225.8	203.4	198.2	197.5	197.4	197.4	381.9	276.6	255.7	251.3	250.7	250.7	250.7	438.0	330.3	309.3	305.4	305.0	305.0	305.0
	7	15	10	80.7	50.5	41.3	38.3	37.8	37.8	38.1	107.1	67.8	57.5	55.1	54.7	54.8	55.0	137.4	86.1	75.3	72.9	72.5	72.5	72.8	157.6	104.5	93.5	90.9	90.5	90.5	90.8	178.5	123.3	112.0	109.2	108.8	108.8	109.1
	7	15	30	193.0	113.9	84.5	75.9	73.0	72.4	72.6	271.4	165.6	135.1	128.6	127.0	126.9	127.1	338.9	214.8	188.2	183.4	182.6	182.5	182.7	391.7	266.8	242.8	238.6	238.1	238.0	238.2	445.1	320.7	298.9	295.0	294.6	294.6	294.7
	15	15	10	132.3	86.7	73.2	68.2	66.6	66.4	66.4	154.2	101.7	87.4	83.3	82.3	82.2	82.2	198.8	121.9	104.9	100.1	99.0	98.8	98.8	219.8	140.9	122.5	117.0	115.9	115.7	115.7	246.1	160.8	141.0	135.1	133.6	133.4	133.4
	15	15	30	283.8	167.5	129.4	110.9	103.1	99.6	98.4	348.1	213.1	171.0	156.4	151.9	150.8	150.7	425.4	263.3	220.9	208.5	205.3	204.7	204.6	475.5	312.4	272.9	261.9	259.5	259.2	259.1	530.4	365.5	326.6	316.6	314.5	314.3	314.2
Combined

The combined heuristic has the best performance in 259 of the 280 settings and is only outperformed where the aisle-length/aisle-number ratio is large. Moreover, the performance of the aisle-by-aisle heuristic quickly approaches the combined heuristic with the increase of the number of pickers. Table 3 also shows that the S-shape heuristic never has the best performance alone. The largest gap strategy solely has the best performance in 14 settings, each of which emerges when the aisle-length/aisle-number ratio is large. The aisle-by-aisle heuristic solely has the best performance in seven settings and performs the same as combined for the single block layout as in line with the literature (Roodbergen and de Koster 2001a). However, employing more pickers quickly improves the performance of these heuristics.

Finally, we examine the impact of each additional picker on savings. Table 4 shows the percentage savings with each additional picker where the best heuristic is indicated in grey colour scale and bold-italic. For the single block layout, average percentage savings are slightly higher when compared to the optimal. When we compare the heuristics, additional pickers yield better savings for S-shape and largest gap heuristics at single block layouts. With the increase in the number of blocks, each additional picker results in more savings for the aisle-by-aisle heuristic. The largest gap strategy performs poorly in terms of percentage savings with each additional picker. The combined heuristic never has the best performance alone for the percentage savings, although it still maintains its overall best performance on the minimum lead times. This can be explained by the fact that underperforming heuristics lead to more savings with each additional picker since the performance of the heuristics converges with the increase in the number of pickers.

Table 4. Percentage savings with each additional picker for multi-block layout settings.

				Savings After Each Additional Picker for Multiple-Block Layout (%)
				Number of Blocks
				1						2						3						4						5
				No. of Pickers						No. of Pickers						No. of Pickers						No. of Pickers						No. of Pickers
Method	No. of Aisles	No. of Items	Length	2	3	4	5	6	7	2	3	4	5	6	7	2	3	4	5	6	7	2	3	4	5	6	7	2	3	4	5	6	7
	7	10	10	37.88	18.70	7.75	1.36	0.00	0.00	36.95	13.43	3.47	0.38	0.00	0.00	34.91	9.90	2.23	0.28	0.00	0.00	30.85	8.31	1.79	0.11	0.00	0.00	27.71	7.37	1.40	0.09	0.00	0.00
	7	10	30	41.32	28.15	9.02	4.35	0.99	0.00	40.37	15.14	4.32	0.89	0.00	0.00	35.36	9.51	1.88	0.34	0.00	0.00	29.54	6.45	1.03	0.09	0.00	0.00	25.16	4.80	0.66	0.04	0.00	0.00
	15	10	10	34.64	15.99	6.58	1.99	0.16	0.00	34.22	12.39	3.75	0.75	0.00	0.00	36.11	11.50	3.45	0.53	0.11	0.00	33.54	10.93	2.79	0.54	0.09	0.00	32.00	10.22	2.64	0.46	0.08	0.00
	15	10	30	41.76	23.72	14.33	6.81	3.04	0.94	39.85	18.57	6.66	2.09	0.34	0.07	37.22	13.42	3.86	0.75	0.05	0.05	32.54	10.00	2.48	0.40	0.04	0.00	29.01	8.06	1.80	0.20	0.00	0.00
	7	15	10	38.76	21.22	9.13	2.58	0.00	0.00	39.84	19.15	6.26	1.08	0.00	0.00	41.02	16.04	4.32	0.82	0.00	0.00	37.58	13.24	3.50	0.66	0.00	0.00	34.97	11.26	2.93	0.55	0.00	0.00
	7	15	30	41.74	29.30	14.11	4.92	1.50	0.00	42.25	24.01	6.65	2.30	0.55	0.00	41.24	16.88	3.90	0.98	0.16	0.00	36.95	12.56	2.60	0.50	0.04	0.00	33.31	9.52	1.96	0.30	0.00	0.00
	15	15	10	37.34	18.35	9.56	4.14	0.89	0.15	37.87	17.99	7.06	2.02	0.48	0.00	41.88	17.17	6.23	1.68	0.40	0.00	39.14	15.69	5.61	1.44	0.26	0.00	37.69	14.33	5.11	1.40	0.22	0.00
	15	15	30	43.28	24.66	17.55	10.93	5.63	2.83	42.71	24.14	12.32	5.05	1.75	0.46	42.51	20.28	8.46	2.69	0.73	0.10	38.94	16.42	5.95	1.63	0.27	0.00	36.02	13.84	4.27	1.10	0.16	0.00
S-Shape
	7	10	10	38.55	15.63	6.60	1.09	0.00	0.00	35.70	11.36	3.11	0.38	0.00	0.00	31.35	8.42	2.09	0.28	0.00	0.00	27.48	7.37	1.57	0.11	0.00	0.00	24.80	6.56	1.40	0.09	0.00	0.00
	7	10	30	39.79	19.03	8.00	4.35	0.99	0.00	33.68	11.03	4.11	0.81	0.00	0.00	27.51	7.20	1.77	0.28	0.00	0.00	22.50	5.16	0.94	0.04	0.00	0.00	18.94	3.98	0.63	0.04	0.00	0.00
	15	10	10	35.49	13.28	6.07	1.54	0.16	0.00	36.85	10.85	3.28	0.63	0.00	0.00	35.33	10.27	2.96	0.42	0.11	0.00	32.77	9.76	2.62	0.45	0.09	0.00	31.13	9.26	2.49	0.39	0.08	0.00
	15	10	30	38.21	19.08	8.94	5.49	2.75	0.84	35.68	13.29	5.36	1.82	0.34	0.07	31.48	9.83	3.16	0.70	0.05	0.05	27.12	7.61	2.14	0.36	0.04	0.00	24.07	6.39	1.55	0.20	0.00	0.00
	7	15	10	41.02	19.35	8.31	2.07	0.00	0.00	40.07	16.07	5.30	1.08	0.00	0.00	38.18	12.74	3.82	0.82	0.00	0.00	34.62	10.72	3.19	0.66	0.00	0.00	31.55	9.28	2.76	0.46	0.00	0.00
	7	15	30	42.63	24.45	9.81	4.79	1.50	0.00	38.48	16.56	5.58	2.15	0.55	0.00	34.48	11.40	3.45	0.92	0.16	0.00	30.01	8.55	2.29	0.46	0.04	0.00	26.01	6.79	1.66	0.27	0.00	0.00
	15	15	10	37.94	17.56	7.86	3.32	0.75	0.00	40.38	16.56	5.83	1.79	0.36	0.00	41.52	14.78	5.18	1.49	0.30	0.00	39.90	13.40	4.86	1.19	0.26	0.00	37.73	12.58	4.52	1.18	0.22	0.00
	15	15	30	40.92	22.59	12.70	6.70	4.06	2.27	39.34	18.90	8.23	3.76	1.43	0.40	37.25	15.07	5.99	2.09	0.58	0.10	34.04	11.96	4.43	1.25	0.23	0.00	30.78	10.13	3.29	0.88	0.13	0.00
Largest Gap
	7	10	10	35.73	15.38	4.94	0.55	0.00	0.00	35.22	13.51	2.94	0.19	0.00	0.00	35.26	12.58	1.96	0.14	0.00	0.00	35.45	12.60	1.24	0.00	0.00	0.00	35.55	12.45	0.94	0.00	0.00	0.00
	7	10	30	40.31	20.80	7.37	2.65	0.14	0.00	38.06	15.91	3.30	0.41	0.00	0.00	37.31	14.10	1.50	0.11	0.00	0.00	37.02	12.89	0.90	0.04	0.00	0.00	36.86	12.23	0.56	0.00	0.00	0.00
	15	10	10	31.21	12.16	4.17	0.62	0.16	0.00	31.79	12.34	3.52	0.63	0.00	0.00	32.75	13.64	3.74	0.53	0.11	0.00	33.51	14.74	3.54	0.45	0.09	0.00	33.93	15.37	3.30	0.39	0.00	0.00
	15	10	30	38.39	20.63	9.66	4.20	1.15	0.21	36.67	18.91	6.59	1.42	0.28	0.00	36.40	18.30	5.01	0.70	0.05	0.00	36.13	18.88	3.89	0.48	0.00	0.00	36.33	18.33	3.63	0.23	0.00	0.00
	7	15	10	37.42	18.22	7.26	1.31	0.00	0.00	37.87	19.31	5.64	0.91	0.00	0.00	37.53	20.89	4.20	0.55	0.00	0.00	37.58	21.59	3.92	0.22	0.00	0.00	37.58	21.94	3.37	0.18	0.00	0.00
	7	15	30	40.98	25.81	10.18	3.82	0.82	0.00	39.75	24.33	6.25	1.40	0.16	0.00	39.03	24.37	4.23	0.44	0.05	0.00	38.65	23.70	3.48	0.21	0.04	0.00	38.54	24.03	2.96	0.10	0.00	0.00
	15	15	10	34.47	15.57	6.83	2.35	0.30	0.00	35.41	17.14	6.97	1.90	0.36	0.00	36.16	18.53	7.83	2.17	0.30	0.00	36.84	19.54	9.20	2.11	0.26	0.00	37.28	20.41	9.72	2.12	0.22	0.00
	15	15	30	40.98	22.75	14.30	7.03	3.39	1.20	39.81	22.40	13.02	4.68	1.18	0.20	39.14	23.18	12.91	3.65	0.68	0.05	39.15	22.92	13.11	3.20	0.27	0.04	39.00	23.35	12.93	2.69	0.25	0.00
Aisle-by-aisle
	7	10	10	35.73	15.38	4.94	0.55	0.00	0.00	32.32	10.15	2.22	0.19	0.00	0.00	30.37	7.87	1.68	0.14	0.00	0.00	26.88	6.91	1.35	0.00	0.00	0.00	24.57	6.25	1.13	0.09	0.00	0.00
	7	10	30	40.31	20.80	7.37	2.65	0.14	0.00	35.24	10.73	2.69	0.32	0.00	0.00	29.40	6.82	1.12	0.11	0.00	0.00	24.09	4.63	0.69	0.04	0.00	0.00	20.36	3.60	0.42	0.00	0.00	0.00
	15	10	10	31.21	12.16	4.17	0.62	0.16	0.00	29.39	9.37	2.34	0.38	0.00	0.00	32.33	9.50	2.47	0.21	0.11	0.00	30.38	9.30	2.28	0.36	0.09	0.00	29.39	9.10	2.27	0.31	0.08	0.00
	15	10	30	38.39	20.63	9.66	4.20	1.15	0.21	34.99	13.51	4.25	0.89	0.21	0.00	32.07	9.92	2.56	0.35	0.05	0.00	27.57	7.56	1.72	0.24	0.00	0.00	24.59	6.36	1.26	0.13	0.00	0.00
	7	15	10	37.42	18.22	7.26	1.31	0.00	0.00	36.69	15.19	4.17	0.73	0.00	0.00	37.34	12.54	3.19	0.55	0.00	0.00	33.69	10.53	2.78	0.44	0.00	0.00	30.92	9.16	2.50	0.37	0.00	0.00
	7	15	30	40.98	25.81	10.18	3.82	0.82	0.00	38.98	18.42	4.81	1.24	0.08	0.00	36.62	12.38	2.55	0.44	0.05	0.00	31.89	9.00	1.73	0.21	0.04	0.00	27.95	6.80	1.30	0.14	0.00	0.00
	15	15	10	34.47	15.57	6.83	2.35	0.30	0.00	34.05	14.06	4.69	1.20	0.12	0.00	38.68	13.95	4.58	1.10	0.20	0.00	35.90	13.06	4.49	0.94	0.17	0.00	34.66	12.31	4.18	1.11	0.15	0.00
	15	15	30	40.98	22.75	14.30	7.03	3.39	1.20	38.78	19.76	8.54	2.88	0.72	0.07	38.11	16.10	5.61	1.53	0.29	0.05	34.30	12.64	4.03	0.92	0.12	0.04	31.09	10.64	3.06	0.66	0.06	0.03ik
Combined

Overall, we observe that the combined heuristic performs relatively the best for the multi-picker, multi-block dynamic zone-picking problem, while the performance of largest gap heuristic increases with the number of blocks and that of aisle-by-aisle heuristics increases with the number of pickers.

7. Conclusions and further research directions

In this paper, we have focused on the multi-picker OPP in parallel-aisle warehouses under a synchronised dynamic zone-picking policy, with the objective of minimising order lead time by minimising the maximum travel time of each picker, while aiming to ensure the balance among pickers. This problem is important in the sense of making practical and effective use of resources while fulfilling the customer orders within increasingly competitive due dates.

The paper has introduced a knapsack-based DP heuristic for the two-picker min–max OPP without zoning, as well as a novel polynomial-time exact algorithm for the min–max OPP in synchronised dynamic zone-picking systems. This DP algorithm assigns pickers for zone-picking and returns the optimal combination of zone assignments for multiple pickers.

Important findings obtained from our computational experiments are that: (i) the proposed algorithm for the min–max OPP with two pickers generates efficient solutions very quickly as the optimality gap averages and the standard deviations are quite low, (ii) for relatively large aisles, assigning a second picker reduces the order picking time around 45% in average while this impact exponentially diminishes each with additional picker, (iii) the proposed synchronised dynamic zone-picking approach with a min–max objective spontaneously leads to the balanced partition of the pickers’ workload thus reduces management supervision, and (iv) the travel time gap between ‘no zoning’ and ‘zoning’ strategies quickly disappears with the introduction of additional pickers. It is important to note that we have worked on uniformly distributed pick locations. That is no demand frequency is taken into account. If a class-based storage policy, which fast moving class products are stored in the closest aisles, is applied, the advantage of dynamic zoning policy would be more significant. This is because the possibility of having a pick location in the further aisles would be relatively small. For the same reason, the proposed algorithm will terminate faster.

For further research, the integrated work in this study can be improved by considering batch-picking approach. The cost factor is not considered in this study and can be a future research direction. Since each additional picker reduces the zone-picking lead time in a decreasing pace, the optimal configuration of zoning and the number of pickers can be further explored with consideration of the cost and service level objectives. Moreover, a cost-related study should also consider other cost factors that vary with the number of zones. For example, as dynamic zones create a more challenging environment for the pickers, a successful operation requires an intact communication and coordination with the help of supporting systems such as pick-by-voice systems. Also, warehouse-specific properties, such as intersection points between picking aisles and cross aisles, intra-aisle and inter-aisle movement types, can be included in the formulations. Such an extension could strengthen the formulation for the multi-picker OPP. The integer programming model can be adapted to a mathematical programming-based heuristic to improve the algorithm. The proposed travel time balancing algorithm could also be embedded into various heuristics for further improvement purposes.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

There are no restrictions on sharing of the data in this paper due to data ownership or the inclusion of personally identifiable information. All data is available upon request from the authors.

Additional information

Notes on contributors

Serhat Saylam

Serhat Saylam is a Ph.D. Candidate at the Department of Industrial Engineering, Middle East Technical University, Ankara, Turkey. He holds a master’s degree in Logistics & Supply Chain Management from U.S. Air Force Institute of Technology. Dayton, Ohio. His research interests focus on operational research, supply chain optimisation, logistics, and routing problems. Currently, he is working as a lecturer at the Department of Industrial Engineering, Turkish Air Force Academy, National Defence University, Istanbul, Turkey.

Melih Çelik

Melih Çelik is an associate professor at the School of Management in the University of Bath (United Kingdom). He holds a Ph.D. in industrial engineering from the Georgia Institute of Technology (Atlanta, USA) as well as a master’s degree in operations research from the same institution. Prior to joining the University of Bath, he was an assistant professor at the Industrial Engineering Department of Middle East Technical University (Ankara, Turkey). His research interests cover warehouse planning, design, and control; non-profit and humanitarian applications of operations research; design, recovery and restoration of vulnerable infrastructure networks; and facility location and layout.

Haldun Süral

Haldun Süral is a professor of industrial engineering at Middle East Technical University (METU), Ankara, Turkey. He received his B.S., M.S., and Ph.D. in industrial engineering from METU. His work experience includes teaching/research positions at METU, INSEAD (France), University of Waterloo and Wilfrid Laurier University (Canada). His research interests range from supply/production/distribution network design to restructuring a large humanitarian aid organisation and waste management system design.

Appendix

Proof of Proposition 1

This arises from the assumption that a zone is a set of adjacent aisles. There is only a single possibility for a zone consisting of $\left|M\right|$ aisles. R&R algorithm runs in $O\left(\left|M\right|\right)$. There are two possibilities to construct a zone consisting of $\left(\left|M\right|-1\right)$ aisles with $O\left(\left|M\right|-1\right)$ running time for each. There are $\left(\left|M\right|-1\right)$ different ways to form zones consisting of $2$ aisles with $O\left(2\right)$ running time for each. Finally, there are $\left|M\right|$ different ways to form a $1$-aisle zone configuration with $O\left(1\right)$ running time for each. Then, for the total number of routing calculation, the proof is the same as the one of sum of finite arithmetic series formula by induction, thus $\frac{\left(\left|M\right|\right)\left(\left|M\right|+1\right)}{2}$. When the running times are also included in the summation, the overall running time ends up with: $=\left(1\right)\left(\left|M\right|\right)+\left(2\right)\left(\left|M\right|-1\right)+\cdots +\left(\left|M\right|-1\right)\left(2\right)+\left(\left|M\right|\right)\left(1\right)$ $=\sum _{r=1}^{\left|M\right|}r\left(\left|M\right|+1-r\right)$ $=\left(\left|M\right|+1\right)\sum _{r=1}^{\left|M\right|}r-\sum _{r=1}^{\left|M\right|}{r}^2$ $=\left(\left|M\right|+1\right)\frac{\left(\left|M\right|\right)\left(\left|M\right|+1\right)}{2}-\frac{\left(\left|M\right|\right)\left(\left|M\right|+1\right)\left(2\left|M\right|+1\right)}{6}$ $=\frac{\left(\left|M\right|\right)\left(\left|M\right|+1\right)\left(\left|M\right|+2\right)}{6}$

Proof of Proposition 2

This can be shown by the ‘Stars and Bars’ technique by Feller (2008). Suppose $\left|M\right|$ aisles (stars) are fixed and $\left(\left|M\right|-1\right)$ gaps between aisles, in each of which there may or may not be a ‘bar’. A zone configuration is obtained by ‘bar’ing $\left(k-1\right)$ of these $\left(\left|M\right|-1\right)$ gaps.