# An Integrated Metaheuristic Routing Method for Multiple-Block Warehouses with Ultranarrow Aisles and Access Restriction

Authors: Fangyu Chen; Gangyan Xu; Yongchang Wei
Journal: Complexity
 (2019)

---

## Abstract

A problem-specific routing algorithm integrating ant colony optimization (ACO) and integer-coded genetic algorithm (GA) is developed to address the newly observed limitations imposed by ultranarrow aisles and access restriction, which exist in the largest e-commerce enterprise with self-run logistics in China. Those limitations prohibit pickers from walking through the whole aisle, and the access restriction even allows them to access the pick aisles only from specific entrances. The ant colony optimization is mainly responsible for generating the initial chromosomes for the genetic algorithm, which then searches the near-optimal solutions of picker-routing with our novel chromosome design by recording the detailed information of access modes and subaisles. To demonstrate the merits of the proposed algorithm, a comprehensive simulation for comparison is conducted with 12 warehouse layouts with real order information. The simulation results show that the proposed hybrid algorithm is superior to dedicated heuristics in terms of solution quality. The impacts of the parameters with respect to warehouse layout on the picking efficiency are analyzed as well. Setting more connect aisles and cross aisles is suggested to effectively optimize the picking-service efficiency in the presence of access limitations.


---

## Body

## 1. Introduction

For most e-commerce enterprises or online distributors, a well-designed order-picking strategy (from warehouse location [1] to routing method [2]) can promote the efficiency of the entire supply chain [3]. Given the advent of e-commerce, the significance of order-picking has grown [4, 5]. Therefore, we concentrate on a picker-routing problem based on the observation in a Chinese e-commerce enterprise.The order service time is one of the main performance measurements of warehouse systems. In a picker-to-parts warehouse, Petersen [6] pointed out that service time can be represented as a positive correlation function of one picker’s travel distance. Accordingly, an appropriate routing method that identifies the shortest picking route can minimize the order service time and therefore improve the picking efficiency. One alternative option that is capable of reducing warehouse management costs is to increase the space utilization, which is typically made by warehouse owners to minimize the pick aisles’ width, culminating in the widespread adoption of the narrow-parallel aisles in picker-to-parts warehouses. In a narrow-aisle warehouse with multiple order pickers, congestions may happen [7].Recently, we observed an interesting warehouse system with ultranarrow aisles in a realistic Chinese online retailer with self-run logistics,D Company, meaning that the pick aisles’ widths are narrowed further, relative to the aforementioned narrow aisles. The ultranarrow aisles impede order pickers to enter while pushing their picking carts. They should deposit their carts at the entrance. When all the picks are finished, they should walk out the aisles to get their carts. The connect aisles and cross aisles, which are located in the warehouse, allow the pickers to change working aisle, because the width of them is sufficient for walking with carts, as shown in Figure 1. For such a warehouse, there is little utility for existing routing methods that permit the order pickers to walk through the whole pick aisles. Additionally, constraints in physical space lead to access restrictions. For example, the racks that are located in the front of a warehouse system may be placed against the front wall; order pickers can only access these aisles through the back entrances. To promote the e-commerce boom, this paper aims to propose efficient routing methods for the warehouses taking both ultranarrow aisles and access restriction into consideration.Figure 1
Order picking in the ultranarrow aisles.We propose a method by integrating ant colony optimization (ACO) and genetic algorithm (GA), which is named asAGNA (hybridACO andGA for ultranarrow aisles and access restriction). The novelties ofAGNA are as follows. Firstly, to avoid traversing aisles, all the aisles with picks are restricted to be visited by specified access modes, and the access mode will map the picks at the certain entrances. Secondly, to deal with the unique characteristics induced by access restriction, the mechanism of determining the feasible travel routes between designated entrances is embedded inAGNA. Thirdly, to improve the convergence speed and performance of the routing method,ACO is responsible for generating the initial chromosome forGA, and the integer-codedGA is designed to search the near-optimal solutions mainly through our novel chromosome design that represents all the access modes for all the aisles with picks. To validate the effectiveness of the improved routing method, a comprehensive simulation study was performed with the data collected from the aforementionedD company. Meanwhile, the impact of the warehouse layout is elucidated. We found that theAGNA method can be readily deployed in different warehouse-layout scenarios due to its flexibility.The main contributions of this research lie in the following aspects. Firstly, we developed a hybridAGNA-based routing method to address the methodological challenges for the warehouses with ultranarrow aisles and access restriction. To cope with the unique characteristics of routing problem in this kind of warehouses, many innovative mechanisms with respect to feasibility judgment and chromosome coding are significantly incorporated in our hybridAGNA-based algorithm. Secondly, with the real data of customer order information and warehouse configuration collected from theD company, a simulation study is employed to show the effectiveness and efficacies of the proposed method. The negative impacts brought by new features are analyzed as well.The remainder of this paper is arranged as follows. Section2 presents a review of the related literature and introduces some existing dedicated heuristics for single-block warehouses. Some of these heuristics can be applied in the warehouse concerned in this paper after improvement, and the modified heuristics are compared with our designedAGNA method. In Section 3, the optimization model tailored to the concerned routing problem in the warehouse is defined. TheAGNA is presented in Section 4. A comprehensive simulation is implemented to validate the efficiency of the proposed method in Section 5. Finally, the paper is concluded in Section 6 and our ongoing research topics are introduced as well.


## 2. Literature Review

The literature closely related to our research can be grouped into two main streams: one is the impact of aisles width, which constitutes a key feature in our research, while the other is the picker-routing problem. In the following, we will review these two streams of literature separately.


### 2.1. The Impact of Aisle Width

Reducing the pick aisles’ width is an alternative to enlarge the space utilization [7]. Nevertheless, narrow aisles lead to more frequent congestion. In this regard, by changing the ratio of the pick  : walk-time, analytical models to assess the order picker congestion (blocking) in both narrow-aisle and wide-aisle warehouses are developed by Parikh and Meller [8, 9]. Hong et al. [10] proposed a batching method in warehouses with narrow aisle. Similarly, Chen et al. [11, 12] introduced some routing methods for narrow-aisle warehouses with the consideration of congestion.Most of the previous literature primarily considers the traditional wide-aisle or narrow-aisle warehouse systems. Although Chen et al. [13] proposed a set of heuristic routing methods for the ultranarrow aisle warehouse system with consideration of access restriction, these heuristics are developed on the existing methods for basic warehouse layout. These methods have the advantage in the ease of implementation. Nevertheless, they can deviate from the optimal solutions seriously, which further increase operational costs. To this end, to get a better optimization effect on picking efficiency, we concentrate on designing a judicious routing method based on metaheuristics.


### 2.2. Routing Method

We can divide all the existing routing methods in the related literature into two groups: dedicated heuristics and metaheuristics. The dedicated heuristics have found prevalent application for order picking, given the ease of their deployment [14–16]. In the existing dedicated heuristics, only theLargest Gap andReturn methods forbid the order pickers from traversing the subaisles for most situations, as shown in Figure 2. However, these two methods cannot be readily deployed in the warehouse system concerned in this paper. For example, theLargest Gap method requests the order pickers to walk through the first aisle with picks to reach the back of the block.Figure 2
A sketch ofReturn andLargest Gap.
(a)
Return from single block (b)
Largest Gap from single blockFor more complicated environments, metaheuristics are more suitable [17–19]. Except for generating picking routes in complicated environments such as multiple-order pickers [12], much of the relevant literature has focused on designing integrated solutions for both order-batching and picker-routing [20–22]. Although many metaheuristics have been presented, such as Particle Swarm Optimization [23] and Simulated Annealing [24],ACO is the most popular for the picker-routing problem [25–27]. To design the picking route for the warehouse of interest in our research, we design a routing method by integratingACO andGA. This integrated method can dynamically control the invocation time of bothACO andGA and improve the convergence speed and performance of the algorithm.


## 2.1. The Impact of Aisle Width

Reducing the pick aisles’ width is an alternative to enlarge the space utilization [7]. Nevertheless, narrow aisles lead to more frequent congestion. In this regard, by changing the ratio of the pick  : walk-time, analytical models to assess the order picker congestion (blocking) in both narrow-aisle and wide-aisle warehouses are developed by Parikh and Meller [8, 9]. Hong et al. [10] proposed a batching method in warehouses with narrow aisle. Similarly, Chen et al. [11, 12] introduced some routing methods for narrow-aisle warehouses with the consideration of congestion.Most of the previous literature primarily considers the traditional wide-aisle or narrow-aisle warehouse systems. Although Chen et al. [13] proposed a set of heuristic routing methods for the ultranarrow aisle warehouse system with consideration of access restriction, these heuristics are developed on the existing methods for basic warehouse layout. These methods have the advantage in the ease of implementation. Nevertheless, they can deviate from the optimal solutions seriously, which further increase operational costs. To this end, to get a better optimization effect on picking efficiency, we concentrate on designing a judicious routing method based on metaheuristics.


## 2.2. Routing Method

We can divide all the existing routing methods in the related literature into two groups: dedicated heuristics and metaheuristics. The dedicated heuristics have found prevalent application for order picking, given the ease of their deployment [14–16]. In the existing dedicated heuristics, only theLargest Gap andReturn methods forbid the order pickers from traversing the subaisles for most situations, as shown in Figure 2. However, these two methods cannot be readily deployed in the warehouse system concerned in this paper. For example, theLargest Gap method requests the order pickers to walk through the first aisle with picks to reach the back of the block.Figure 2
A sketch ofReturn andLargest Gap.
(a)
Return from single block (b)
Largest Gap from single blockFor more complicated environments, metaheuristics are more suitable [17–19]. Except for generating picking routes in complicated environments such as multiple-order pickers [12], much of the relevant literature has focused on designing integrated solutions for both order-batching and picker-routing [20–22]. Although many metaheuristics have been presented, such as Particle Swarm Optimization [23] and Simulated Annealing [24],ACO is the most popular for the picker-routing problem [25–27]. To design the picking route for the warehouse of interest in our research, we design a routing method by integratingACO andGA. This integrated method can dynamically control the invocation time of bothACO andGA and improve the convergence speed and performance of the algorithm.


## 3. Problem Definition

### 3.1. Warehouse Configuration and Assumption

The related literature [4, 28] and practice focus commonly on a multiple-block picker-to-parts warehouse, which is concerned in our paper as well, as shown in Figure 3. The main difference of our research is that the widths of all the parallel pick aisles are assumed to be ultranarrow. Additionally, some aisles may have access restriction on designated entrances. TheCAs (cross aisles) are located in the front-back direction. Likewise, there areCNA (connect aisles) in the left-right direction. The widths ofCA andCNA are sufficient to permit order pickers walking with their picking carts, which allows order pickers to change working aisles. Thecross point is the intersection between aCA and aCNA. The warehouse is divided into multiple blocks (B) by theseCAs andCNAs in front-back and left-right directions. Each single pick aisle is also divided into a number of subaisles (S).Figure 3
Multiple-block warehouse system with ultranarrow aisles and access restriction.ARow contains the blocks arranged in the left-right direction, and correspondingly aColumn refers to those in the front-back direction. For anS, Ef and Eb indicate the front entrance and back entrance, respectively. For a single block, there are two adjacentCAs, one is CAf (front cross aisle), and the other is CAb (back cross aisle). For an order picker, the working cross aisle is denoted as CAc (current cross aisle). To describe a route from one subaisle to another, Sb (Begin Subaisle) denotes the subaisle where the order picker begins, and St (Target Subaisle) denotes the subaisle which the order picker is going to visit. Moreover, the front entrances of Sb and St are Ebf and Etf, respectively, and their back entrances are Ebb and Etb, respectively. Given this layout, some assumptions are noteworthy. Firstly, in such a warehouse, the two-sided picking policy is chosen by the order pickers [29]. Meanwhile, we ignore the time cost on reaching the different layers and sides of shelves.In the warehouse of e-commerce enterprise, the dynamic arrival of customers’ orders means that we can composite all the orders into batches depending only on their arrival time. We assume that the warehouse adopts random-storage policy [30]. We impose restriction on the capacity of picking carts to avoid overload [31], and the picker congestion is ignored. For simplicity, we ignore the difference in the order pickers’ walking speed and the time of finishing a picking task is assumed to be constant [32, 33]. The order pickers have no constraint and can change walking direction in any aisles [34]. The picking operation begins and finishes at the depot, where the operating time is ignored in this paper.


### 3.2. Routing Model

According to theLargest Gap andReturn methods, to avoid traversing and deal with the access restriction, the most effective picking solution for each subaisle with picks can be illustrated by three access modes:Front-return,Back-return, andGap-return (as shown in Figure 4). TheFront-return mode inquires the order pickers to walk into and depart from a subaisle through the front entrance after visiting all the picks. Correspondingly, in theBack-return mode, the order pickers only use the back entrance for both entry and departure. In theGap-return mode, the order pickers enter a pick aisle but make a U-turn at the largest gap. The order pickers may have to visit the subaisle twice: once by Ef and another by Eb. Because the largest gap may cut the subaisle into two parts, this implies that theGap-return mode corresponds to two access modes: accessing the front part and the back part. TheGap-return mode does not necessitate the order pickers to visit the remaining part immediately after they finish one part of a subaisle. Once the access mode is determined for a subaisle, the picking route in this subaisle is determined as well, and the picks therein will be mapped to the entrance which should be visited by the order pickers. TheFront-return mode will map all the picks to Ef, theBack-return mode will map all the picks to Eb, and theGap-return mode will map the picks to Ef and Eb, respectively. Then, routing methods only need to find a satisfactory moving route passing all the entrances with mapped picks. Finally, an integrated route is generated by combining this moving route and the picking routes in subaisles with picks. Consequently, the routing problem can be equivalently expressed by determining the best access modes and finding the best visiting sequence for all the subaisles with picks.Figure 4
Access modes for subaisles with picks.Based on the assumptions and the access modes aforementioned, the objective is to minimize the total travel distance of serving a batch. Then, we can formulate a 0-1 integer linear optimization model.Indices and Sets Ω: Set of subaisles with picks and the depot i , j ∈ Ω: Indexes of subaisles with picks and depot, in which i=0 means the depot R i , j: Set of the feasible moving routes from subaisles i to j r ∈ R i , j: Index of the feasible moving routes from subaisles i to j M j: Set of the feasible access modes of subaisle j m ∈ M j: Index of the feasible access modes of subaisle jParameters and Sets D i j: Set of the moving distances of the feasible moving routes from subaisles i to j d i j r ∈ D i j: Moving distance of the rth feasible moving route from subaisles i to j D ′ j: Set of the picking distances of the feasible access modes of subaisle j d j m ′ ∈ D ′ j: Picking distance of the mth feasible access mode of subaisle jDecision Variables x i j: Binary decision that equals 1 (xij=1) means that subaisle i is visited directly after subaisle j y i j r: Binary decision that equals 1 (yijr=1) means that the rth feasible moving route is selected to move from subaisles i to j z j m: Binary decision that equals 1 (zjm=1) means that the mth feasible access mode is selected to visit subaisle i to jModel Formulation (1) m i n ∑ i ∈ Ω ∑ j ∈ Ω x i j ∑ k ∈ T i j y i j r d i j r + ∑ m ∈ M j z j m d ′ j msubject to(2)∑r∈Rijyijr=1,∀i,j∈Ω(3)∑m∈Mjzjm=1,∀j∈Ω(4)xij∈0,1,∀i,j∈Ω(5)yijr∈0,1,∀i,j∈Ω,∀r∈Rij(6)zjm∈0,1,∀j≠0∈Ω,∀m∈MjFunction (1) is the objective function that minimizes the total travel distance of serving a batch. Constraint (2) ensures that only one moving route is selected when the order pickers move from subaisle i to j. Constraint (3) ensures that each subaisle selects only one access mode. Constraints (4) to (6) define the variable domains.The routing model differs from the basic picker-routing problem, which can be defined as the Steiner-TSP (Steiner Travelling Salesman Problem) [14]. All the cities (subaisles) in the TSP need to be visited only once. However, if a subaisle (city) chooses theGap-return mode, the order pickers may visit this subaisle twice: once by Ef and another time by Eb. For our model, this removes the necessity for the common constraint in TSP that each subaisle (city) has exact only one predecessor and successor. Besides, when theGap-return mode is determined for a subaisle and the order pickers are required to visit Ef immediately after Eb, the common constraint in TSP that there is only a single tour is likewise rendered unnecessary for our model.Furthermore, the impact of access restriction cannot be incorporated into the model. When the selected blocks have access restriction, some access modes will become infeasible for the subaisles. For example, ifCAf of a block has access restriction, only theBack-return mode may be chosen for the subaisles in this block. Moreover, the choice of the access mode will affect the moving route between subaisles. For example, if theFront-return mode is selected for both Sb and St, the order pickers will have to enter and leave these subaisles by Ebf and Etf, signifying that the moving route between Sb and St must pass Ebf and Etf.Generally, there is an interaction between the values ofZjm and yijr. Before the routing-construction begins, for each subaisle, we can just get a set of the “selectable” access modes and the corresponding detailed picking routes for these access modes are also contingent upon the access restriction constraint. The set of the “selectable” moving routes between any two subaisles can be confirmed in this stage as well.When the order picker chooses the access mode forSt, by extracting from the set of the “selectable” moving routes, we can determine the set of feasible moving routes between Sb and St. The access mode of the current St will also affect the choice of the moving route from the current St to the next St, once the access mode of the next St is determined. Due to the aforementioned characteristics, the accurate set of Dij can not be determined prior to the selection of optimal routing solutions. Thus, our problem cannot be solved simply by optimization solvers, such as Lingo and CPLEX, which motivates us to design metaheuristic-based routing methods.


## 3.1. Warehouse Configuration and Assumption

The related literature [4, 28] and practice focus commonly on a multiple-block picker-to-parts warehouse, which is concerned in our paper as well, as shown in Figure 3. The main difference of our research is that the widths of all the parallel pick aisles are assumed to be ultranarrow. Additionally, some aisles may have access restriction on designated entrances. TheCAs (cross aisles) are located in the front-back direction. Likewise, there areCNA (connect aisles) in the left-right direction. The widths ofCA andCNA are sufficient to permit order pickers walking with their picking carts, which allows order pickers to change working aisles. Thecross point is the intersection between aCA and aCNA. The warehouse is divided into multiple blocks (B) by theseCAs andCNAs in front-back and left-right directions. Each single pick aisle is also divided into a number of subaisles (S).Figure 3
Multiple-block warehouse system with ultranarrow aisles and access restriction.ARow contains the blocks arranged in the left-right direction, and correspondingly aColumn refers to those in the front-back direction. For anS, Ef and Eb indicate the front entrance and back entrance, respectively. For a single block, there are two adjacentCAs, one is CAf (front cross aisle), and the other is CAb (back cross aisle). For an order picker, the working cross aisle is denoted as CAc (current cross aisle). To describe a route from one subaisle to another, Sb (Begin Subaisle) denotes the subaisle where the order picker begins, and St (Target Subaisle) denotes the subaisle which the order picker is going to visit. Moreover, the front entrances of Sb and St are Ebf and Etf, respectively, and their back entrances are Ebb and Etb, respectively. Given this layout, some assumptions are noteworthy. Firstly, in such a warehouse, the two-sided picking policy is chosen by the order pickers [29]. Meanwhile, we ignore the time cost on reaching the different layers and sides of shelves.In the warehouse of e-commerce enterprise, the dynamic arrival of customers’ orders means that we can composite all the orders into batches depending only on their arrival time. We assume that the warehouse adopts random-storage policy [30]. We impose restriction on the capacity of picking carts to avoid overload [31], and the picker congestion is ignored. For simplicity, we ignore the difference in the order pickers’ walking speed and the time of finishing a picking task is assumed to be constant [32, 33]. The order pickers have no constraint and can change walking direction in any aisles [34]. The picking operation begins and finishes at the depot, where the operating time is ignored in this paper.


## 3.2. Routing Model

According to theLargest Gap andReturn methods, to avoid traversing and deal with the access restriction, the most effective picking solution for each subaisle with picks can be illustrated by three access modes:Front-return,Back-return, andGap-return (as shown in Figure 4). TheFront-return mode inquires the order pickers to walk into and depart from a subaisle through the front entrance after visiting all the picks. Correspondingly, in theBack-return mode, the order pickers only use the back entrance for both entry and departure. In theGap-return mode, the order pickers enter a pick aisle but make a U-turn at the largest gap. The order pickers may have to visit the subaisle twice: once by Ef and another by Eb. Because the largest gap may cut the subaisle into two parts, this implies that theGap-return mode corresponds to two access modes: accessing the front part and the back part. TheGap-return mode does not necessitate the order pickers to visit the remaining part immediately after they finish one part of a subaisle. Once the access mode is determined for a subaisle, the picking route in this subaisle is determined as well, and the picks therein will be mapped to the entrance which should be visited by the order pickers. TheFront-return mode will map all the picks to Ef, theBack-return mode will map all the picks to Eb, and theGap-return mode will map the picks to Ef and Eb, respectively. Then, routing methods only need to find a satisfactory moving route passing all the entrances with mapped picks. Finally, an integrated route is generated by combining this moving route and the picking routes in subaisles with picks. Consequently, the routing problem can be equivalently expressed by determining the best access modes and finding the best visiting sequence for all the subaisles with picks.Figure 4
Access modes for subaisles with picks.Based on the assumptions and the access modes aforementioned, the objective is to minimize the total travel distance of serving a batch. Then, we can formulate a 0-1 integer linear optimization model.Indices and Sets Ω: Set of subaisles with picks and the depot i , j ∈ Ω: Indexes of subaisles with picks and depot, in which i=0 means the depot R i , j: Set of the feasible moving routes from subaisles i to j r ∈ R i , j: Index of the feasible moving routes from subaisles i to j M j: Set of the feasible access modes of subaisle j m ∈ M j: Index of the feasible access modes of subaisle jParameters and Sets D i j: Set of the moving distances of the feasible moving routes from subaisles i to j d i j r ∈ D i j: Moving distance of the rth feasible moving route from subaisles i to j D ′ j: Set of the picking distances of the feasible access modes of subaisle j d j m ′ ∈ D ′ j: Picking distance of the mth feasible access mode of subaisle jDecision Variables x i j: Binary decision that equals 1 (xij=1) means that subaisle i is visited directly after subaisle j y i j r: Binary decision that equals 1 (yijr=1) means that the rth feasible moving route is selected to move from subaisles i to j z j m: Binary decision that equals 1 (zjm=1) means that the mth feasible access mode is selected to visit subaisle i to jModel Formulation (1) m i n ∑ i ∈ Ω ∑ j ∈ Ω x i j ∑ k ∈ T i j y i j r d i j r + ∑ m ∈ M j z j m d ′ j msubject to(2)∑r∈Rijyijr=1,∀i,j∈Ω(3)∑m∈Mjzjm=1,∀j∈Ω(4)xij∈0,1,∀i,j∈Ω(5)yijr∈0,1,∀i,j∈Ω,∀r∈Rij(6)zjm∈0,1,∀j≠0∈Ω,∀m∈MjFunction (1) is the objective function that minimizes the total travel distance of serving a batch. Constraint (2) ensures that only one moving route is selected when the order pickers move from subaisle i to j. Constraint (3) ensures that each subaisle selects only one access mode. Constraints (4) to (6) define the variable domains.The routing model differs from the basic picker-routing problem, which can be defined as the Steiner-TSP (Steiner Travelling Salesman Problem) [14]. All the cities (subaisles) in the TSP need to be visited only once. However, if a subaisle (city) chooses theGap-return mode, the order pickers may visit this subaisle twice: once by Ef and another time by Eb. For our model, this removes the necessity for the common constraint in TSP that each subaisle (city) has exact only one predecessor and successor. Besides, when theGap-return mode is determined for a subaisle and the order pickers are required to visit Ef immediately after Eb, the common constraint in TSP that there is only a single tour is likewise rendered unnecessary for our model.Furthermore, the impact of access restriction cannot be incorporated into the model. When the selected blocks have access restriction, some access modes will become infeasible for the subaisles. For example, ifCAf of a block has access restriction, only theBack-return mode may be chosen for the subaisles in this block. Moreover, the choice of the access mode will affect the moving route between subaisles. For example, if theFront-return mode is selected for both Sb and St, the order pickers will have to enter and leave these subaisles by Ebf and Etf, signifying that the moving route between Sb and St must pass Ebf and Etf.Generally, there is an interaction between the values ofZjm and yijr. Before the routing-construction begins, for each subaisle, we can just get a set of the “selectable” access modes and the corresponding detailed picking routes for these access modes are also contingent upon the access restriction constraint. The set of the “selectable” moving routes between any two subaisles can be confirmed in this stage as well.When the order picker chooses the access mode forSt, by extracting from the set of the “selectable” moving routes, we can determine the set of feasible moving routes between Sb and St. The access mode of the current St will also affect the choice of the moving route from the current St to the next St, once the access mode of the next St is determined. Due to the aforementioned characteristics, the accurate set of Dij can not be determined prior to the selection of optimal routing solutions. Thus, our problem cannot be solved simply by optimization solvers, such as Lingo and CPLEX, which motivates us to design metaheuristic-based routing methods.


## 4. Solution Methods

In this section, a hybrid algorithm integratingACO (ant colony optimization) and integer-codedGA (genetic algorithm) is developed to deal with the specified routing problem. On one hand, theACO generates the initial chromosome for the integer-codedGA during the initialization. This structure can not only dynamically control the invocation time of both theGA andACO but also improve the convergence speed and performance of the algorithm. On the other hand, the integer-codedGA searches a near-optimal solution for picker-routing. The total travel distance of serving a batch could be defined as the fitness values of the integer-coded chromosomes obtained from theGA.


### 4.1. Distance Initialization

For different access modes of one subaisle, the corresponding picking distances and picking routes differ from each other. Similarly, the moving route and moving distance betweenSb and St are also affected by their access modes. The access mode for a subaisle can be determined only when this subaisle is chosen as St. After that, its picking route and moving route can be correspondingly confirmed. To represent the routing problem as a combination optimization problem manageable by theAGNA, all the picking routes in subaisles and the moving routes between any two subaisles for different access modes should be recorded during the initialization.For a subaisle, each access mode will determine the corresponding picking route and picking distance. This applies especially to theGap-return mode, in which the front and the back parts lead to different picking routes and picking distances. This means that, for each subaisle without access restriction, four kinds of picking routes are usually available: for theFront-return mode, for theBack-return mode, for the front part of theGap-return mode, and for the back part of theGap-return mode. In the initialization, all the corresponding picking routes and picking distances will be calculated and recorded as the input for the routing method.Moreover, there are four cases of the moving route and moving distance betweenSb and St, which are affected by the access modes of Sb and St.Case 1.
TheFront-return mode is chosen for both Sb and St, or theGap-return mode is chosen for both of them, in which only the front part of Sb is completed and the front part of St needs to be visited. Then, the moving route will start from Ebf and end at Etf.Case 2.
TheFront-return mode is chosen for Sb, or theGap-return mode is chosen, in which only the front part is completed. Conversely, theBack-return mode is chosen for St, or theGap-return mode is chosen, in which only the back part needs to be visited. Then, the moving route will start from Ebf and end at Etb.Case 3.
TheBack-return mode is chosen for Sb, or theGap-return mode is chosen, in which only the back part is completed. Conversely, theFront-return mode is chosen for St, or theGap-return mode is chosen, in which only the front part needs to be visited. Then, the moving route will start from Ebb and end at Etf.Case 4.
TheBack-return mode is chosen for both Sb and St, or theGap-return mode is chosen for both of them, in which only the back part of Sb is completed and the back part of St needs to be visited. Then, the moving route will start from Ebb and end at Etb.It deserves attention that the moving route and its moving distance betweenSb and St still need to be computed for each case. The moving distance is usually calculated by the path between any two designated entrances with the Manhattan distance (Theys et al., 2010). However, the Manhattan distance cannot fully satisfy the layout with the ultranarrow aisles. According to the diversified spatial relationship between the designated entrances of Sb and St, as shown in Figure 5, the detailed definitions of the moving route and moving distance are described as follows [13].Figure 5
The definition rules of the moving routes.(i) Entrances in the Same CA. The order pickers can walk directly from the designated entrance of Sb to the designated entrance of St; see Route ⓐ shown in Figure 5.(ii) Entrances in Different CAs but in the Same Column. Usually, two optional moving routes between the designated entrance of Sb and the designated entrance of St are available to the order pickers. For simplicity, the shorter one is chosen; refer to Route ⓑ shown in Figure 5.(iii) Entrances in Different Columns. The order pickers walk along CAc by leaving Sb from the chosen entrance, until getting to theCNA adjacent to theCA which the chosen entrance of St belongs to. Then, after setting this CA as CAc, the order pickers walk along CAc and enter St; see Route ⓒ shown in Figure 5.All the moving routes and picking routes with respect to different access modes and their distances are recorded and will be used for route construction and fitness-value evaluation. If some access modes are infeasible due to access restriction, the related picking distance and moving distance will be recorded as infinity.


### 4.2. ACO-Based Chromosome Initialization

Based on the initialized distances, theACO is employed to initialize the population of the routing chromosomes. We assume that the ant colony contains N(N≥2) ants, which denote the order pickers. The ant finds St from the unfinished subaisles and determines the access mode of St. Next, it records the moving distance from Sb to St and the picking distance in St. When all the subaisles are finished, the ant will walk back to the depot. Then, L, the total travel distance, is composed by all the selected picking distances and moving distances, which will be seemed as the evaluation criterion. Before theACO starts, the initial value of the pheromone is calculated by(7)τijr0=1∑i∈Ω∑j∈ΩDijwhere τijr0 is the pheromone concentration in the rth feasible moving route from subaisle i to j at time 0 and ∑i∈Ω∑j∈ΩDij is the sum of the number of feasible moving routes among all the subaisles to be visited by the ants or order pickers.Each ant choosesSt and determines the moving route randomly depending on the transition probability pijrt that subaisle j will be visited immediately after finishing subaisle i at time t by the rth moving route, which is represented as(8)pijrt=τijrtαηijrβ∑j∈Uτijrtαηijrβ,ifj∈U,0,otherwise,where τijrt is the pheromone concentration on the rth moving route from subaisle i to j at time t, ηijr measures the visibility on this route, and U is the set of unfinished subaisles. The value of ηijr is usually defined as the reciprocal of the sum of the moving distance of the rth moving route from subaisle i to j and the corresponding picking distances in subaisles i and j. The definition of the transition probability leads to high superiority to the shortest travel and picking route, and τijrt impels the familiar moving route and picking route is chosen by these ants. It is well recognized that the parameters α and β coordinate the relative importance between the pheromone concentration and the route visibility (α≥1,β≥1). Usually, α and β are valued according to the former observation.When all the ants complete their picking tasks, the pheromone concentration on all the routes is updated by(9)τijrt+1=1-ρτijrt+Δτijrt,t+1where ρ is the recession parameter of the pheromone concentration (0<ρ<1). Δτijrt,t+1 is the alteration of the pheromone concentration laid on moving route r from subaisle i to subaisle j between times t and t+1, as determined by(10)Δτijrt,t+1=∑n=1NΔτijrnt,t+1where Δτijrnt,t+1 is the pheromone concentration left on the route r from subaisles i to j by the nth ant from times t to t+1, which is defined by(11)Δτijrnt,t+1=1Ln,ifthenthantchoosestherthroutetomovefromsub-aisleitosub-aislejbetweentimestandt+1,0,otherwise,where Ln means the total travel distance of the picking route completed by the nth ant.When all the ants complete the trips, some solutions will be saved in a queue (Q). If a new solution outside the queue but better than the worst solution in the queue is found, it will replace that worst solution in the queue. TheACO will stop after the iterations equal the predetermined number. When it terminates, the solutions saved in the queue will be used in the initialization of chromosomes in the integer-codedGA.


### 4.3. Integer-Coded Genetic Algorithm (GA)

#### 4.3.1. Chromosomal Representation and Initial-Population Generation

During the route construction process byACO, the order pickers choose St first and then decide the access mode. The unselected access modes of St may be ignored easily in the later iterations. To avoid converging to local optimum, the integer-codedGA generates the near-optimal solutions by searching the access modes and the visiting sequence of all the subaisles with picks. The value of each gene in a chromosome not only records the visiting sequence of a certain subaisle but also determines the access mode of this subaisle. In our algorithm, if a gene is associated with the ith subaisle and the mth mode, the value of this gene is defined as 2i-1∗3m-1. As is corresponding to all the access modes, we set m=1 as theFront-return mode, m=2 as theBack-return mode, m=3 as accessing the front part by theGap-return mode, and m=4 as accessing the front part by theGap-return mode. Consequently, this value formula helps us identify the unique subaisle and access mode for each gene.It is noteworthy that although theACO has already generated a visiting sequence passing all the subaisles with feasible access modes, this solution may be insufficiently effective and ignores other unselected access modes. The chromosomal representation should include all the subaisles and all the access modes for them, and the length of chromosome will be ∑i∈ΩMi. Therefore, the solution ofACO can be used as the encoding basis for the first few genes, and the remaining genes of the chromosome will be supplemented by random encoding. Figure 6 illustrates an example of the integer-coded chromosomal representation including four subaisles without access restriction, which means that the length of the chromosome is 16. The solutions generated byACO are sequentially represented as i=1,m=4, i=4,m=1, i=2,m=3, i=3,m=2, i=2,m=4, and i=1,m=3. Such sequential representation implies visits to all the subaisles with picks by the following sequence: (1) accessing the back part of the 1st subaisle by theGap-return mode; (2) accessing the 4th subaisle by theFront-return mode; (3) accessing the front part of the 2nd subaisle by theGap-return mode; (4) accessing the 3rd subaisle by theBack-return mode; (5) accessing the back part of the 2nd subaisle by theGap-return mode; and (6) accessing the front part of the 1st subaisle by theGap-return mode. Hence, in the chromosomal initialization, the first six genes will be valued as 27, 8, 18, 12, 54, and 9, whereas the remaining 10 genes will be randomly coded to cover the unselected access modes for further optimization.Figure 6
The illustration of integer-coding.The population of chromosome isP. When the encoding is finished for all the chromosomes, the crossover and mutation operation will begin.


#### 4.3.2. Fitness Value Evaluation

The total travel distances of all the integer-coded chromosomes are chosen as their fitness values. Because each chromosome contains all the access modes for each subaisle with picks, not all the genes need to be calculated in the evaluation of the fitness values. For example, if theith subaisle has already been indicated by a former gene to choose theFront-return mode, the remaining genes that indicate the ith subaisle to be accessed by other modes will be excluded. During the chromosomal decoding, the value of each gene should be validated to avoid any repeated or missed visits to the subaisles. If the subaisle is unfinished and the access mode is feasible, the gene will pass the validation and be calculated in the fitness values. The procedure of validation for each gene can be described as in Figure 7.Figure 7
The procedure of validation for each single gene.The calculation of the total travel distance of each chromosome is described as follows.Step 1.
SetL=0 and Sb=S0 to signify that the order pickers start from the depot.Step 2.
Get the next gene.Step 3.
Decode the gene to get the subaisle and the access mode.Step 4.
If the subaislei and access mode m pass the validation, set St=Si; then proceed to Step 5; otherwise, go back to Step 2.Step 5.
Based on the access modes ofSb and St, determine the moving route r from Sb to St. Get the moving distance dbtr and the picking distance dtr′; then set L=L+dbtr+dtr′ and Sb=St.Step 6.
If all the subaisles are finished, go on with Step 7; otherwise, revert to Step 2.Step 7.
Return to the depot and determine the moving router; set St=S0 and L=L+dbtr.Step 8.
The reciprocal value ofL is the fitness value of this solution.Step 9.
IfL is associated with a better fitness value than that of the near-optimal solution so far in the last population generation, set Lnear-optimal=L.


#### 4.3.3. Crossover and Mutation

The designating parents for the undergoing crossover and mutation are adopted by the approach of proportional selection. In this approach, the parents are selected randomly. However, the parents with higher fitness values tend to be selected with higher probability. Because the genes in the front of a chromosome are more likely to be calculated in the fitness value, the effective genes should be included in the crossover and mutation. To improve the evolutionary speed, the Four-Point Crossover method is adopted to create new offspring. Four segmentations with equal lengths are determined; the second and fourth gene segmentations are selected in crossover operation. Then, we use the Order Crossover in the Legality Repair. Figure8(a) illustrates the crossover operation.Figure 8
The illustration of crossover and mutation.
(a)
Cross operation (b)
Mutation operationThe mutation operation guarantees the diversity and avoids premature convergence.SBM (Swap-based mutation) − which selects two random elements (one from the first third part of the chromosome and the other from the remaining part) and exchanges their positions − is applied to generate the offspring. Figure 8(b) illustrates these mutation operators.


### 4.4. Stopping Criteria

TheGA algorithm terminates in two situations. The first one is as follows: once the iterations reaches a predetermined number of generations G, theGA will terminate. The second criteria is that theGA will terminate if the best solution remains the same for a fixed number of generations ep. The same criteria can be seen in theACO part, and the corresponding parameters are I and C, respectively. Figure 9 describes the overall procedure ofAGNA.Figure 9
The flowchart ofAGNA.


## 4.1. Distance Initialization

For different access modes of one subaisle, the corresponding picking distances and picking routes differ from each other. Similarly, the moving route and moving distance betweenSb and St are also affected by their access modes. The access mode for a subaisle can be determined only when this subaisle is chosen as St. After that, its picking route and moving route can be correspondingly confirmed. To represent the routing problem as a combination optimization problem manageable by theAGNA, all the picking routes in subaisles and the moving routes between any two subaisles for different access modes should be recorded during the initialization.For a subaisle, each access mode will determine the corresponding picking route and picking distance. This applies especially to theGap-return mode, in which the front and the back parts lead to different picking routes and picking distances. This means that, for each subaisle without access restriction, four kinds of picking routes are usually available: for theFront-return mode, for theBack-return mode, for the front part of theGap-return mode, and for the back part of theGap-return mode. In the initialization, all the corresponding picking routes and picking distances will be calculated and recorded as the input for the routing method.Moreover, there are four cases of the moving route and moving distance betweenSb and St, which are affected by the access modes of Sb and St.Case 1.
TheFront-return mode is chosen for both Sb and St, or theGap-return mode is chosen for both of them, in which only the front part of Sb is completed and the front part of St needs to be visited. Then, the moving route will start from Ebf and end at Etf.Case 2.
TheFront-return mode is chosen for Sb, or theGap-return mode is chosen, in which only the front part is completed. Conversely, theBack-return mode is chosen for St, or theGap-return mode is chosen, in which only the back part needs to be visited. Then, the moving route will start from Ebf and end at Etb.Case 3.
TheBack-return mode is chosen for Sb, or theGap-return mode is chosen, in which only the back part is completed. Conversely, theFront-return mode is chosen for St, or theGap-return mode is chosen, in which only the front part needs to be visited. Then, the moving route will start from Ebb and end at Etf.Case 4.
TheBack-return mode is chosen for both Sb and St, or theGap-return mode is chosen for both of them, in which only the back part of Sb is completed and the back part of St needs to be visited. Then, the moving route will start from Ebb and end at Etb.It deserves attention that the moving route and its moving distance betweenSb and St still need to be computed for each case. The moving distance is usually calculated by the path between any two designated entrances with the Manhattan distance (Theys et al., 2010). However, the Manhattan distance cannot fully satisfy the layout with the ultranarrow aisles. According to the diversified spatial relationship between the designated entrances of Sb and St, as shown in Figure 5, the detailed definitions of the moving route and moving distance are described as follows [13].Figure 5
The definition rules of the moving routes.(i) Entrances in the Same CA. The order pickers can walk directly from the designated entrance of Sb to the designated entrance of St; see Route ⓐ shown in Figure 5.(ii) Entrances in Different CAs but in the Same Column. Usually, two optional moving routes between the designated entrance of Sb and the designated entrance of St are available to the order pickers. For simplicity, the shorter one is chosen; refer to Route ⓑ shown in Figure 5.(iii) Entrances in Different Columns. The order pickers walk along CAc by leaving Sb from the chosen entrance, until getting to theCNA adjacent to theCA which the chosen entrance of St belongs to. Then, after setting this CA as CAc, the order pickers walk along CAc and enter St; see Route ⓒ shown in Figure 5.All the moving routes and picking routes with respect to different access modes and their distances are recorded and will be used for route construction and fitness-value evaluation. If some access modes are infeasible due to access restriction, the related picking distance and moving distance will be recorded as infinity.


## 4.2. ACO-Based Chromosome Initialization

Based on the initialized distances, theACO is employed to initialize the population of the routing chromosomes. We assume that the ant colony contains N(N≥2) ants, which denote the order pickers. The ant finds St from the unfinished subaisles and determines the access mode of St. Next, it records the moving distance from Sb to St and the picking distance in St. When all the subaisles are finished, the ant will walk back to the depot. Then, L, the total travel distance, is composed by all the selected picking distances and moving distances, which will be seemed as the evaluation criterion. Before theACO starts, the initial value of the pheromone is calculated by(7)τijr0=1∑i∈Ω∑j∈ΩDijwhere τijr0 is the pheromone concentration in the rth feasible moving route from subaisle i to j at time 0 and ∑i∈Ω∑j∈ΩDij is the sum of the number of feasible moving routes among all the subaisles to be visited by the ants or order pickers.Each ant choosesSt and determines the moving route randomly depending on the transition probability pijrt that subaisle j will be visited immediately after finishing subaisle i at time t by the rth moving route, which is represented as(8)pijrt=τijrtαηijrβ∑j∈Uτijrtαηijrβ,ifj∈U,0,otherwise,where τijrt is the pheromone concentration on the rth moving route from subaisle i to j at time t, ηijr measures the visibility on this route, and U is the set of unfinished subaisles. The value of ηijr is usually defined as the reciprocal of the sum of the moving distance of the rth moving route from subaisle i to j and the corresponding picking distances in subaisles i and j. The definition of the transition probability leads to high superiority to the shortest travel and picking route, and τijrt impels the familiar moving route and picking route is chosen by these ants. It is well recognized that the parameters α and β coordinate the relative importance between the pheromone concentration and the route visibility (α≥1,β≥1). Usually, α and β are valued according to the former observation.When all the ants complete their picking tasks, the pheromone concentration on all the routes is updated by(9)τijrt+1=1-ρτijrt+Δτijrt,t+1where ρ is the recession parameter of the pheromone concentration (0<ρ<1). Δτijrt,t+1 is the alteration of the pheromone concentration laid on moving route r from subaisle i to subaisle j between times t and t+1, as determined by(10)Δτijrt,t+1=∑n=1NΔτijrnt,t+1where Δτijrnt,t+1 is the pheromone concentration left on the route r from subaisles i to j by the nth ant from times t to t+1, which is defined by(11)Δτijrnt,t+1=1Ln,ifthenthantchoosestherthroutetomovefromsub-aisleitosub-aislejbetweentimestandt+1,0,otherwise,where Ln means the total travel distance of the picking route completed by the nth ant.When all the ants complete the trips, some solutions will be saved in a queue (Q). If a new solution outside the queue but better than the worst solution in the queue is found, it will replace that worst solution in the queue. TheACO will stop after the iterations equal the predetermined number. When it terminates, the solutions saved in the queue will be used in the initialization of chromosomes in the integer-codedGA.


## 4.3. Integer-Coded Genetic Algorithm (GA)

### 4.3.1. Chromosomal Representation and Initial-Population Generation

During the route construction process byACO, the order pickers choose St first and then decide the access mode. The unselected access modes of St may be ignored easily in the later iterations. To avoid converging to local optimum, the integer-codedGA generates the near-optimal solutions by searching the access modes and the visiting sequence of all the subaisles with picks. The value of each gene in a chromosome not only records the visiting sequence of a certain subaisle but also determines the access mode of this subaisle. In our algorithm, if a gene is associated with the ith subaisle and the mth mode, the value of this gene is defined as 2i-1∗3m-1. As is corresponding to all the access modes, we set m=1 as theFront-return mode, m=2 as theBack-return mode, m=3 as accessing the front part by theGap-return mode, and m=4 as accessing the front part by theGap-return mode. Consequently, this value formula helps us identify the unique subaisle and access mode for each gene.It is noteworthy that although theACO has already generated a visiting sequence passing all the subaisles with feasible access modes, this solution may be insufficiently effective and ignores other unselected access modes. The chromosomal representation should include all the subaisles and all the access modes for them, and the length of chromosome will be ∑i∈ΩMi. Therefore, the solution ofACO can be used as the encoding basis for the first few genes, and the remaining genes of the chromosome will be supplemented by random encoding. Figure 6 illustrates an example of the integer-coded chromosomal representation including four subaisles without access restriction, which means that the length of the chromosome is 16. The solutions generated byACO are sequentially represented as i=1,m=4, i=4,m=1, i=2,m=3, i=3,m=2, i=2,m=4, and i=1,m=3. Such sequential representation implies visits to all the subaisles with picks by the following sequence: (1) accessing the back part of the 1st subaisle by theGap-return mode; (2) accessing the 4th subaisle by theFront-return mode; (3) accessing the front part of the 2nd subaisle by theGap-return mode; (4) accessing the 3rd subaisle by theBack-return mode; (5) accessing the back part of the 2nd subaisle by theGap-return mode; and (6) accessing the front part of the 1st subaisle by theGap-return mode. Hence, in the chromosomal initialization, the first six genes will be valued as 27, 8, 18, 12, 54, and 9, whereas the remaining 10 genes will be randomly coded to cover the unselected access modes for further optimization.Figure 6
The illustration of integer-coding.The population of chromosome isP. When the encoding is finished for all the chromosomes, the crossover and mutation operation will begin.


### 4.3.2. Fitness Value Evaluation

The total travel distances of all the integer-coded chromosomes are chosen as their fitness values. Because each chromosome contains all the access modes for each subaisle with picks, not all the genes need to be calculated in the evaluation of the fitness values. For example, if theith subaisle has already been indicated by a former gene to choose theFront-return mode, the remaining genes that indicate the ith subaisle to be accessed by other modes will be excluded. During the chromosomal decoding, the value of each gene should be validated to avoid any repeated or missed visits to the subaisles. If the subaisle is unfinished and the access mode is feasible, the gene will pass the validation and be calculated in the fitness values. The procedure of validation for each gene can be described as in Figure 7.Figure 7
The procedure of validation for each single gene.The calculation of the total travel distance of each chromosome is described as follows.Step 1.
SetL=0 and Sb=S0 to signify that the order pickers start from the depot.Step 2.
Get the next gene.Step 3.
Decode the gene to get the subaisle and the access mode.Step 4.
If the subaislei and access mode m pass the validation, set St=Si; then proceed to Step 5; otherwise, go back to Step 2.Step 5.
Based on the access modes ofSb and St, determine the moving route r from Sb to St. Get the moving distance dbtr and the picking distance dtr′; then set L=L+dbtr+dtr′ and Sb=St.Step 6.
If all the subaisles are finished, go on with Step 7; otherwise, revert to Step 2.Step 7.
Return to the depot and determine the moving router; set St=S0 and L=L+dbtr.Step 8.
The reciprocal value ofL is the fitness value of this solution.Step 9.
IfL is associated with a better fitness value than that of the near-optimal solution so far in the last population generation, set Lnear-optimal=L.


### 4.3.3. Crossover and Mutation

The designating parents for the undergoing crossover and mutation are adopted by the approach of proportional selection. In this approach, the parents are selected randomly. However, the parents with higher fitness values tend to be selected with higher probability. Because the genes in the front of a chromosome are more likely to be calculated in the fitness value, the effective genes should be included in the crossover and mutation. To improve the evolutionary speed, the Four-Point Crossover method is adopted to create new offspring. Four segmentations with equal lengths are determined; the second and fourth gene segmentations are selected in crossover operation. Then, we use the Order Crossover in the Legality Repair. Figure8(a) illustrates the crossover operation.Figure 8
The illustration of crossover and mutation.
(a)
Cross operation (b)
Mutation operationThe mutation operation guarantees the diversity and avoids premature convergence.SBM (Swap-based mutation) − which selects two random elements (one from the first third part of the chromosome and the other from the remaining part) and exchanges their positions − is applied to generate the offspring. Figure 8(b) illustrates these mutation operators.


## 4.3.1. Chromosomal Representation and Initial-Population Generation

During the route construction process byACO, the order pickers choose St first and then decide the access mode. The unselected access modes of St may be ignored easily in the later iterations. To avoid converging to local optimum, the integer-codedGA generates the near-optimal solutions by searching the access modes and the visiting sequence of all the subaisles with picks. The value of each gene in a chromosome not only records the visiting sequence of a certain subaisle but also determines the access mode of this subaisle. In our algorithm, if a gene is associated with the ith subaisle and the mth mode, the value of this gene is defined as 2i-1∗3m-1. As is corresponding to all the access modes, we set m=1 as theFront-return mode, m=2 as theBack-return mode, m=3 as accessing the front part by theGap-return mode, and m=4 as accessing the front part by theGap-return mode. Consequently, this value formula helps us identify the unique subaisle and access mode for each gene.It is noteworthy that although theACO has already generated a visiting sequence passing all the subaisles with feasible access modes, this solution may be insufficiently effective and ignores other unselected access modes. The chromosomal representation should include all the subaisles and all the access modes for them, and the length of chromosome will be ∑i∈ΩMi. Therefore, the solution ofACO can be used as the encoding basis for the first few genes, and the remaining genes of the chromosome will be supplemented by random encoding. Figure 6 illustrates an example of the integer-coded chromosomal representation including four subaisles without access restriction, which means that the length of the chromosome is 16. The solutions generated byACO are sequentially represented as i=1,m=4, i=4,m=1, i=2,m=3, i=3,m=2, i=2,m=4, and i=1,m=3. Such sequential representation implies visits to all the subaisles with picks by the following sequence: (1) accessing the back part of the 1st subaisle by theGap-return mode; (2) accessing the 4th subaisle by theFront-return mode; (3) accessing the front part of the 2nd subaisle by theGap-return mode; (4) accessing the 3rd subaisle by theBack-return mode; (5) accessing the back part of the 2nd subaisle by theGap-return mode; and (6) accessing the front part of the 1st subaisle by theGap-return mode. Hence, in the chromosomal initialization, the first six genes will be valued as 27, 8, 18, 12, 54, and 9, whereas the remaining 10 genes will be randomly coded to cover the unselected access modes for further optimization.Figure 6
The illustration of integer-coding.The population of chromosome isP. When the encoding is finished for all the chromosomes, the crossover and mutation operation will begin.


## 4.3.2. Fitness Value Evaluation

The total travel distances of all the integer-coded chromosomes are chosen as their fitness values. Because each chromosome contains all the access modes for each subaisle with picks, not all the genes need to be calculated in the evaluation of the fitness values. For example, if theith subaisle has already been indicated by a former gene to choose theFront-return mode, the remaining genes that indicate the ith subaisle to be accessed by other modes will be excluded. During the chromosomal decoding, the value of each gene should be validated to avoid any repeated or missed visits to the subaisles. If the subaisle is unfinished and the access mode is feasible, the gene will pass the validation and be calculated in the fitness values. The procedure of validation for each gene can be described as in Figure 7.Figure 7
The procedure of validation for each single gene.The calculation of the total travel distance of each chromosome is described as follows.Step 1.
SetL=0 and Sb=S0 to signify that the order pickers start from the depot.Step 2.
Get the next gene.Step 3.
Decode the gene to get the subaisle and the access mode.Step 4.
If the subaislei and access mode m pass the validation, set St=Si; then proceed to Step 5; otherwise, go back to Step 2.Step 5.
Based on the access modes ofSb and St, determine the moving route r from Sb to St. Get the moving distance dbtr and the picking distance dtr′; then set L=L+dbtr+dtr′ and Sb=St.Step 6.
If all the subaisles are finished, go on with Step 7; otherwise, revert to Step 2.Step 7.
Return to the depot and determine the moving router; set St=S0 and L=L+dbtr.Step 8.
The reciprocal value ofL is the fitness value of this solution.Step 9.
IfL is associated with a better fitness value than that of the near-optimal solution so far in the last population generation, set Lnear-optimal=L.


## 4.3.3. Crossover and Mutation

The designating parents for the undergoing crossover and mutation are adopted by the approach of proportional selection. In this approach, the parents are selected randomly. However, the parents with higher fitness values tend to be selected with higher probability. Because the genes in the front of a chromosome are more likely to be calculated in the fitness value, the effective genes should be included in the crossover and mutation. To improve the evolutionary speed, the Four-Point Crossover method is adopted to create new offspring. Four segmentations with equal lengths are determined; the second and fourth gene segmentations are selected in crossover operation. Then, we use the Order Crossover in the Legality Repair. Figure8(a) illustrates the crossover operation.Figure 8
The illustration of crossover and mutation.
(a)
Cross operation (b)
Mutation operationThe mutation operation guarantees the diversity and avoids premature convergence.SBM (Swap-based mutation) − which selects two random elements (one from the first third part of the chromosome and the other from the remaining part) and exchanges their positions − is applied to generate the offspring. Figure 8(b) illustrates these mutation operators.


## 4.4. Stopping Criteria

TheGA algorithm terminates in two situations. The first one is as follows: once the iterations reaches a predetermined number of generations G, theGA will terminate. The second criteria is that theGA will terminate if the best solution remains the same for a fixed number of generations ep. The same criteria can be seen in theACO part, and the corresponding parameters are I and C, respectively. Figure 9 describes the overall procedure ofAGNA.Figure 9
The flowchart ofAGNA.


## 5. Experimental Study

### 5.1. Experimental Design

We conduct a comprehensive experiment to evaluate the effectiveness of the proposed method, which contains 12 kinds of warehouse layout scenarios extracted from a realistic warehouse system inD company, as shown in Figure 10. The detailed configuration parameters are shown in Table 1, which is referred to Chen et al. [13].Table 1
Detailed configurations of warehouse scenarios.
Layout scenario Number of blocks Number of cross aisles Number of connect aisles Front restriction Back restriction 1 1 1 2 Yes No 2 1 1 2 No Yes 3 1 2 2 No No 4 2 1 3 Yes No 5 2 1 3 No Yes 6 2 2 3 No No 7 2 2 2 Yes No 8 2 2 2 No Yes 9 2 3 2 No No 10 4 3 3 No No 11 4 3 2 Yes Yes 12 8 3 3 Yes YesFigure 10
Warehouse scenarios concerned in the experiment.There are usually at least 11 aisles in every single block. For each single subaisle, the minimum number of storage locations is 384. The average length and width of each single subaisle are 12.048 m and 0.8 m, respectively. For each single shelf, the average width is 0.7 m. Furthermore, the average widths of each singleCNA andCA are 3.64 m and 3.3 m, respectively.


### 5.2. Experimental Results

The simulation is input with the realistic order information over one month in this aforementioned warehouse. For all the scenarios, at least 547,754 orders arrived in this month. The order information only contains the designated storage locations, without other customer-related information. According to the practical situation, we restrict each picking cart to carry 60 items at most. Besides, there are usually only 1 to 2 items in an online customer order. To maximize the utilization of picking cart, orders are combined into batches. In this online warehouse, we use the VariableTime-Window Batching rule, also known asFirst-Come-First-Served, to composite all the orders into batches according to their arrival time. After the batching operation, 13,060 batches are generated. There are 1,165 picking tasks at least assigned to the scenario with single block. To compare our hybridAGNA method with the dedicated heuristics, we also improved the basicReturn andLargest Gap methods to adapt to the warehouse concerned in this paper, which, respectively, are named as theRNA (Return for ultranarrow aisles and access restriction) andLNA (Largest Gap for ultranarrow aisles and access restriction). For theRNA andLNA, each subaisle with picks also needs to choose access mode. TheRNA has theFront-return andBack-return modes, andLNA has theFront-return,Back-return, andGap-return modes. The procedures ofRNA andLNA are described as follows [13].Step 1.
Sort and index all theCAs progressively in theColumns and then in theRows.Step 2.
Choose feasible access modes with the shortest picking distance for all the subaisles with picks. Then, the picks will be mapped to the designated entrances.Step 3.
If the picking tasks are mapped to an entrance, theCA with this entrance can be labelled as aCA with picks.Step 4.
By traversing the indexes of theCAs incrementally, set the first foundCA with picks as CAc; then the order pickers will walk to the leftcross point of CAc.Step 5.
EnterCAc, and visit all the designated entrances with mapped picking tasks.Step 6.
If all theCAs with picks are visited, go on with Step 9; otherwise, go on with Step 7.Step 7.
If the nextCA with picks is in the sameColumn as CAc, leave CAc from the nearercross point; if the nextCA with picks is in differentColumns, leave CAc from the rightcross point of CAc.Step 8.
Reach the nextCA with picks, and set thisCA as CAc. Then, revert to Step 5.Step 9.
LeaveCAc and return to the depot.The simulation platform is developed by C#.net on a 4.00GHz PC. In all theAGNA solutions, the values of the following search parameters, as shown in Table 2, are validated to be robust in the previous research [11] andANOVA test. ForRNA andLNA, the average computation time for a batch was less than 1 s. ForAGNA, this time was less than 5 s. The results show that, in eight scenarios,AGNA gets the best performance. In the remaining four scenarios, the three routing methods get the same results, as shown in Table 3. Data in italic font means the best result in the corresponding scenario. Owing to the flexible definition of the visiting sequence for a subaisle,AGNA can optimize the travel route effectively. Additionally, the access modes are derived from existing basic heuristics, with which the order pickers are familiar. Accordingly, the order pickers can easily accept the newly designed routing method. Therefore,AGNA can be readily applied to the setting of multiple-block warehouse.Table 2
The parameter setting for theAGNA algorithm.
Parameter ACO GA Population Ω Ω Iterations (I) 2000 ∗ Ω Interval (C) 50 ∗ Ω α 1 β 5 ρ 0.15 Crossover rate  0.75 Mutation rate  0.1 G  100 ∗ Ω 2 ep  100 ∗ ΩTable 3
The average length of travel distances for all the methods (unit: meter).
Layout scenario RNA LNA AGNA 1 247.65 247.65 247.65 2 231.14 231.14 231.14 3 208.90 208.90 171.55 4 381.48 381.48 381.48 5 370.02 370.02 370.02 6 411.86 411.86 346.48 7 296.15 296.15 263.05 8 261.81 262.78 261.64 9 313.63 312.04 263.48 10 495.13 492.15 409.51 11 341.70 340.67 329.56 12 534.14 532.94 498.92


### 5.3. Discussions

Based on the results, we can analyze the effects of the following parameters.(  1) Access Restriction. In four scenarios, all the methods produce the same results. All of them are the layouts having only oneRow, and access restriction is imposed on one side for all the blocks implying that all the subaisles are allowed to be visited from only one entrance. This means that only one identical access mode with the same travel distance will be chosen by all the routing methods. For the same reason,AGNA outperformsRNA andLNA in the other eight scenarios with fewer access restrictions (see Table 4). We calculate the percentage differences by A/R=100×1-r(A)/r(R), A/L=100×1-r(A)/r(L), and L/R=100×1-r(L)/r(R), where r(R), r(L), and r(A) refer to the average travel distances ofRNA,LNA, andAGNA, respectively. The imposition of fewer access restrictions will increase the optimization space among these methods.Table 4
The percentage differences between different methods (unit: %).
Layout scenario A / R A / L L / R 1 0 0 0 2 0 0 0 3 17.88 17.88 0 4 0 0 0 5 0 0 0 6 15.87 15.87 0 7 11.18 11.18 0 8 0.06 0.43 -0.37 9 15.99 15.56 0.51 10 17.29 16.79 0.6 11 3.55 3.26 0.3 12 6.59 6.38 0.22(  2) Number of CNAs. Although theCNA is only responsible for the order pickers changing working aisles,AGNA produces better performance in a scenario with moreCNAs. For instance, the mild increase in the number ofCNAs from two (in the 3rd scenario) to three (in the 6th) translates into a significant synchronous increase in the percentage difference betweenAGNA andRNA. Similar comparisons betweenAGNA andRNA are shown in Figure 11. The implication of this observation is that the negative impacts of access restriction can be by mitigated by setting the optimal number ofCNAs.Figure 11
The percentage difference betweenAGNA andRNA in scenarios with two or threeCNAs.(  3) Number of CAs. The presence of moreCAs contributes to a reduced relative proportion of access restriction, by which the order pickers can enjoy greater flexibility. As shown in Table 4,AGNA outperforms other methods in the scenarios with moreCAs. If the access restriction is inevitable, we suggest that warehouse designers can set moreCAs.


## 5.1. Experimental Design

We conduct a comprehensive experiment to evaluate the effectiveness of the proposed method, which contains 12 kinds of warehouse layout scenarios extracted from a realistic warehouse system inD company, as shown in Figure 10. The detailed configuration parameters are shown in Table 1, which is referred to Chen et al. [13].Table 1
Detailed configurations of warehouse scenarios.
Layout scenario Number of blocks Number of cross aisles Number of connect aisles Front restriction Back restriction 1 1 1 2 Yes No 2 1 1 2 No Yes 3 1 2 2 No No 4 2 1 3 Yes No 5 2 1 3 No Yes 6 2 2 3 No No 7 2 2 2 Yes No 8 2 2 2 No Yes 9 2 3 2 No No 10 4 3 3 No No 11 4 3 2 Yes Yes 12 8 3 3 Yes YesFigure 10
Warehouse scenarios concerned in the experiment.There are usually at least 11 aisles in every single block. For each single subaisle, the minimum number of storage locations is 384. The average length and width of each single subaisle are 12.048 m and 0.8 m, respectively. For each single shelf, the average width is 0.7 m. Furthermore, the average widths of each singleCNA andCA are 3.64 m and 3.3 m, respectively.


## 5.2. Experimental Results

The simulation is input with the realistic order information over one month in this aforementioned warehouse. For all the scenarios, at least 547,754 orders arrived in this month. The order information only contains the designated storage locations, without other customer-related information. According to the practical situation, we restrict each picking cart to carry 60 items at most. Besides, there are usually only 1 to 2 items in an online customer order. To maximize the utilization of picking cart, orders are combined into batches. In this online warehouse, we use the VariableTime-Window Batching rule, also known asFirst-Come-First-Served, to composite all the orders into batches according to their arrival time. After the batching operation, 13,060 batches are generated. There are 1,165 picking tasks at least assigned to the scenario with single block. To compare our hybridAGNA method with the dedicated heuristics, we also improved the basicReturn andLargest Gap methods to adapt to the warehouse concerned in this paper, which, respectively, are named as theRNA (Return for ultranarrow aisles and access restriction) andLNA (Largest Gap for ultranarrow aisles and access restriction). For theRNA andLNA, each subaisle with picks also needs to choose access mode. TheRNA has theFront-return andBack-return modes, andLNA has theFront-return,Back-return, andGap-return modes. The procedures ofRNA andLNA are described as follows [13].Step 1.
Sort and index all theCAs progressively in theColumns and then in theRows.Step 2.
Choose feasible access modes with the shortest picking distance for all the subaisles with picks. Then, the picks will be mapped to the designated entrances.Step 3.
If the picking tasks are mapped to an entrance, theCA with this entrance can be labelled as aCA with picks.Step 4.
By traversing the indexes of theCAs incrementally, set the first foundCA with picks as CAc; then the order pickers will walk to the leftcross point of CAc.Step 5.
EnterCAc, and visit all the designated entrances with mapped picking tasks.Step 6.
If all theCAs with picks are visited, go on with Step 9; otherwise, go on with Step 7.Step 7.
If the nextCA with picks is in the sameColumn as CAc, leave CAc from the nearercross point; if the nextCA with picks is in differentColumns, leave CAc from the rightcross point of CAc.Step 8.
Reach the nextCA with picks, and set thisCA as CAc. Then, revert to Step 5.Step 9.
LeaveCAc and return to the depot.The simulation platform is developed by C#.net on a 4.00GHz PC. In all theAGNA solutions, the values of the following search parameters, as shown in Table 2, are validated to be robust in the previous research [11] andANOVA test. ForRNA andLNA, the average computation time for a batch was less than 1 s. ForAGNA, this time was less than 5 s. The results show that, in eight scenarios,AGNA gets the best performance. In the remaining four scenarios, the three routing methods get the same results, as shown in Table 3. Data in italic font means the best result in the corresponding scenario. Owing to the flexible definition of the visiting sequence for a subaisle,AGNA can optimize the travel route effectively. Additionally, the access modes are derived from existing basic heuristics, with which the order pickers are familiar. Accordingly, the order pickers can easily accept the newly designed routing method. Therefore,AGNA can be readily applied to the setting of multiple-block warehouse.Table 2
The parameter setting for theAGNA algorithm.
Parameter ACO GA Population Ω Ω Iterations (I) 2000 ∗ Ω Interval (C) 50 ∗ Ω α 1 β 5 ρ 0.15 Crossover rate  0.75 Mutation rate  0.1 G  100 ∗ Ω 2 ep  100 ∗ ΩTable 3
The average length of travel distances for all the methods (unit: meter).
Layout scenario RNA LNA AGNA 1 247.65 247.65 247.65 2 231.14 231.14 231.14 3 208.90 208.90 171.55 4 381.48 381.48 381.48 5 370.02 370.02 370.02 6 411.86 411.86 346.48 7 296.15 296.15 263.05 8 261.81 262.78 261.64 9 313.63 312.04 263.48 10 495.13 492.15 409.51 11 341.70 340.67 329.56 12 534.14 532.94 498.92


## 5.3. Discussions

Based on the results, we can analyze the effects of the following parameters.(  1) Access Restriction. In four scenarios, all the methods produce the same results. All of them are the layouts having only oneRow, and access restriction is imposed on one side for all the blocks implying that all the subaisles are allowed to be visited from only one entrance. This means that only one identical access mode with the same travel distance will be chosen by all the routing methods. For the same reason,AGNA outperformsRNA andLNA in the other eight scenarios with fewer access restrictions (see Table 4). We calculate the percentage differences by A/R=100×1-r(A)/r(R), A/L=100×1-r(A)/r(L), and L/R=100×1-r(L)/r(R), where r(R), r(L), and r(A) refer to the average travel distances ofRNA,LNA, andAGNA, respectively. The imposition of fewer access restrictions will increase the optimization space among these methods.Table 4
The percentage differences between different methods (unit: %).
Layout scenario A / R A / L L / R 1 0 0 0 2 0 0 0 3 17.88 17.88 0 4 0 0 0 5 0 0 0 6 15.87 15.87 0 7 11.18 11.18 0 8 0.06 0.43 -0.37 9 15.99 15.56 0.51 10 17.29 16.79 0.6 11 3.55 3.26 0.3 12 6.59 6.38 0.22(  2) Number of CNAs. Although theCNA is only responsible for the order pickers changing working aisles,AGNA produces better performance in a scenario with moreCNAs. For instance, the mild increase in the number ofCNAs from two (in the 3rd scenario) to three (in the 6th) translates into a significant synchronous increase in the percentage difference betweenAGNA andRNA. Similar comparisons betweenAGNA andRNA are shown in Figure 11. The implication of this observation is that the negative impacts of access restriction can be by mitigated by setting the optimal number ofCNAs.Figure 11
The percentage difference betweenAGNA andRNA in scenarios with two or threeCNAs.(  3) Number of CAs. The presence of moreCAs contributes to a reduced relative proportion of access restriction, by which the order pickers can enjoy greater flexibility. As shown in Table 4,AGNA outperforms other methods in the scenarios with moreCAs. If the access restriction is inevitable, we suggest that warehouse designers can set moreCAs.


## 6. Conclusions

This paper studied a new kind of multiple-block warehouse with ultranarrow aisles as observed from one large-scale online retailer in China. In such a warehouse system, an order picker is prohibited from entering the ultranarrow aisles carrying a picking cart. In addition, we also take access restriction into account, which has been imposed on some special pick aisles to limit the order pickers to visit by a designated entrance. In such a warehouse, the existing routing methods cannot be immediately applied without modification. This study designed a routing method by integratingACO andGA to address those practical features with the aim to improve operational efficiency. Specifically, the core procedure of theAGNA lies in the identification of not only the best access mode but also the near-optimal visiting sequence and moving route that visits all the subaisles with picks.A comprehensive simulation is deliberately designed to verify the efficacies of the proposed method. The input data for the simulation, including the warehouse configurations and order information, are collected fromD company. Moreover, two improved dedicated heuristics were also examined for comparison. By simulation, we found thatAGNA can significantly improve the picking efficiency in most scenarios. Additionally, the mechanism ofAGNA which deals with the access restriction can be deployed in the warehouses with traditional aisles as well. Moreover, it appears that minimizing access restrictions by setting moreCAs andCNAs can effectively optimize the picking-service efficiency.In this paper, the proposed method is developed for already-designed warehouse layouts. If the ultranarrow aisles and access restriction are inevitable, designing the optimal layout is a problem that is worthy of further research. Moreover, the designation of storage assignment and order-batching methods in the setting of such a warehouse system also deserves ongoing further research.



---

*Source: 1280285-2019-06-18.xml*