Solving the picker routing problem in multi-block high-level storage systems using metaheuristics

Depósito de Investigación de la Universidad de Sevilla https://idus.us.es/ This version of the article has been accepted for publication, after peer review and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: https://doi.org/10.1007/s10696-022- 09445-y SOLVING THE PICKER ROUTING PROBLEM IN MULTI-BLOCK HIGHLEVEL STORAGE SYSTEMS USING METAHEURISTICS Abstract This study minimizes the travel time in multi-block high-level storage systems considering height level constraints for picking devices to leave aisles. Considering these operating environments, the formulation of minimum travel times between each pair of storage positions is proposed and the picker routing problem (PRP) is solved by means of Genetic Algorithms (GA) and Ant Colony Optimization (ACO). A parameter tuning is performed for both metaheuristics, and the performance of the GA and ACO is compared with the optimal solution for small-sized problems demonstrating the reliability of the algorithms solving the PRP. The performance of the GA and ACO is tested under several warehouse configurations and pick-list sizes obtaining that both metaheuristics provide highquality solutions within short computing times. It is concluded that the GA outperforms the ACO in both efficiency and computing time, so it is recommended to implement the GA to solve the PRP in joint order picking problems. Keywords: Order picking; picker routing problem; ant colony optimization; genetic algorithms; warehouse management; highlevel warehouses 1. INTRODUCTION Warehouses in business-to-consumer e-commerce companies or regular business are handling a large number of orders with minimum amounts of multiple items, and customers expect an accurate and fast delivery, putting the logistic activities of the supply chain under pressure (Zhang et al. 2017; Ramaekers et al. 2018; Pinto and Nagano 2019). Then, warehouses are critical for any supply chain and an efficient order picking operation is indispensable to fulfill the customer orders, minimizing logistics costs, and improving the performance of the entire supply chain (Van Gils et al. 2018a; Chen et al. 2019). Within warehouse management, automated (Parts-to-picker systems) and manual (picker-to-parts systems) order picking systems can be found, where the automated systems utilize automated guided vehicles (AGV) and/or automated storage/retrieval systems (AS/RS) to handle and transport the requested items to stationary pickers or picking stations (Roodbergen and Vis 2009). In manual systems, the order picking operation is responsible for retrieving items from the warehouse racks to fulfill customer orders, moving pickers from a depot to the picking locations and returning to the depot to deliver the collected products (Henn 2012). Despite the considerable advances on automated systems in recent years, manual systems operated by human pickers prevail in practice (Jiang et al. 2018), estimating up to 80% of warehouses remain manually operated (Grosse et al. 2017) because these systems provide fewer investment requirements and greater flexibility for adapting to real-time changes regarding to capacity, items size, and items weight (Van Gils et al. 2019a; Zhang et al. 2019). In manual warehouses, the order picking is considered the most laborintensive operation since it generates 50–75% of the warehouse’s operating costs (Bartholdi and Hackman 2014). Therefore, the success of warehouse management depends on how customer orders are retrieved in the order picking process (Menéndez et al. 2017). Several activities such as lifting, moving, searching, retrieving, loading, packing, and traveling are required to perform the order picker operation (Lee et al. 2015), highlighting that traveling consumes at least 50% of the costs and processing time in picking systems (De Koster et al. 2007). Consequently, many studies have focused on minimizing travel time (Damayanti et al. 2018) because traveling is considered as an unproductive and a non-value-added activity (Öztürko 2019), and because an organization can significantly improve the warehouse performance by improving the travel time (Ardjmand et al. 2019). Consequently, the picker routing problem (PRP) aims to provide the shortest route to minimize the travel time and distance by determining the sequence for human pickers to visit several picking locations in a warehouse, starting and ending at a point called Depot to retrieve the items requested by customer orders (Scholz et al. 2016; Damayanti et al. 2018). The PRP can be modeled as a traveling salesman problem (TSP) by adapting the paths to allow picking devices moving from one aisle to another (Lin et al. 2016; Scholz et al. 2016). For multi-parallel-aisle warehouses, the PRP can be considered as a Steiner TSP (STSP) because some nodes do not have to be visited whereas the remaining nodes can be visited more than once since they are picking positions or the depot (Theys et al. 2010), and the STSP can be reformulated as a classic TSP by computing the minimum distances between each pair of picking locations using Manhattan distances (Scholz et al. 2017), therefore, a distance calculation structure can be applied to arbitrary warehouse configurations (Lin et al. 2016), including multiple-block high-level warehouses. In many real warehouses there are more than two cross-aisles, which divide the warehouse into multiple blocks, so given NC as the number of cross-aisles then NC-1 blocks are obtained in a warehouse (Çelik and Süral 2018). Considering multiple-block warehouses represent a critical issue for order picking systems because a prudent addition of cross-aisles provides greater flexibility in the routing of order pickers and can improve the performance of order pickers (Roodbergen and De Koster 2001). Likewise, many warehouses employ high-level storage systems (3D-warehouses) to store products (Van Gils et al. 2019b), and order pickers travel to the pick locations on board of a picking device that stops in front of the appropriate picking location to perform the pick (Wang et al. 2013), and as a consequence, several studies have focused in recent years on solving order picking problems for high-level storage systems. Unlike the studies of (Pan et al. 2014) and (Chabot et al. 2018), this study will address multi-block high-level storage systems and will analyze multiple warehouse configurations by varying the number of picks, aisles, storage locations per aisle side, and levels, providing more extensive scenarios that allow to validate and determine the performance of solution methods for the PRP in high-level storage systems. Although the studies of (Azadnia et al. 2013), (Tsai et al. 2008), (Ene and Öztürk 2012), (Wang et al. 2013), (Fu et al. 2011), and (Wang et al. 2012) propose travel time formulations between storage locations, no formulations for 3D-warehouses have been identified considering a height reference level to leave aisles and ensure the safe operation of picking devices. On the other hand, the literature indicates that the most common solution methods to solve the PRP in multi-block warehouses are exact algorithms, heuristics and metaheuristics, highlighting the use of metaheuristics like genetic algorithms and ant colony optimization (Masae et al. 2020), as they serve to solve complex order picking problems such as joint order picking problems (Van Gils et al. 2018b). The main contributions of this paper are as follows: 1) novel formulations for 3D-warehouses considering a height reference level to leave aisles and ensure the safe operation of picking devices; 2) the generation of multiple warehouse configurations for 2-block and 3-block 3D- warehouses to test the efficiency of routing methods; 3) the comparison of the performance of the most used metaheuristics to solve the PRP (GA and ACO) with the optimal solution, heuristics, and routing policies; 4) the identification of warehouse environments in which the solution methods provide better performance for the PRP. Therefore, this article aims to propose a GA and an ACO to solve the PRP in multi-block high-level storage systems considering height reference levels to leave aisles to minimize the travel time and provide highquality solutions within short computing times. The remainder of the article is as follows: Section 2 introduces the literature review for the PRP in high-level storage systems and solution approaches for the PRP. Section 3 presents the PRP formulation. In Section 4, the proposed GA and ACO for the PRP are presented. Section 5 describes the parameter tuning experiments for the proposed GA and ACO, as well as the experimental parameters to validate the efficiency of the proposed metaheuristics. Section 6demonstrates the performance of the proposed algorithms through a computational study. Finally, the paper is concluded in Section 7 and an outlook on future research topics are introduced as well. 2. LITERATURE REVIEW This section introduces the literature review for the PRP in high-level storage systems and solution approaches for the PRP. As shown in Table 1, the studies considering 3D-warehouses are mainly focused on minimizing travel time, picking time, traveled distance, and tardiness, therefore, the calculation of time is prioritized in 3D environments due to the appearance of horizontal and vertical movements that can be executed simultaneously or sequentially. Likewise, most studies address single-block high-level storage systems, while the studies of (Fu et al. 2011), (Ene and Öztürk 2012), (Wang et al. 2012), (Wang et al. 2013), (Li et al. 2017), and (Pinto and Nagano 2019) consider 2-block 3D-warehouses, and only the study of (Van Gils et al. 2019b) considers a 3-block 3D-warehouse for a joint order picking problem. Regarding the number of warehouse configurations used in the experiments in previous studies, it is identified that generally, these studies consider a single warehouse configuration, which limits the scope, robustness, and impact of the solution method proposed for the PRP in high-level storage systems. Accordingly, it is highlighted that only the study of (Pan et al. 2014) analyzes three warehouse configurations, all of them consisting of single-block high-level storage systems, while (Chabot et al. 2018) analyze five warehouse configurations, however, they assume the PRP for a single-aisle, so they actually solve a 2D problem. Table 1. Order picking studies considering high-level storage systems Author Objective function Solution approaches Warehouse configuration (Hsu et al. 2005) Minimize traveled distance S-shape A single configuration of a single-block 3D-warehouse. The characteristics of the warehouse are unspecified. (Won and Olafsson 2005) Minimize picking time 2-opt heuristic A single configuration of a single-block 3D-warehouse with 1,000 storage locations, 1 aisle, 50 locations per side and 20 levels. Picking device with a horizontal and a vertical velocity of 50 ft/min. (Tsai et al. 2008). Minimize total travel cost, tardiness, and earliness GA A single configuration of a single-block 3D-warehouse. The characteristics of the warehouse are unspecified. (Fu et al. 2011) Minimize picking time GA and ACO A single configuration of a 2-block 3D-warehouse with 7,200 storage locations, 10 levels, 20 rows, and 36 columns. A single route with 30 picks. (Ene and Öztürk 2012) Minimize travel cost GA A single configuration of a 2-block 3D-warehouse de 2,280 picking locations, 7 aisles, 19 locations per side and 5 levels. Each route consists of 3 picks. (Wang et al. 2012) Minimize travel time ACO A single configuration of a 2-block 3D-warehouse with 2,400 picking locations, 10 levels, 20 rows, and 12 columns. Picking device with a horizontal velocity of 2 m/s and a vertical velocity of 0.3 m/s. A single route with 10 picks. (Azadnia et al. 2013) Minimize tardiness GA Single-block 3D-warehouse with 3,000 storage locations. Picking device with a horizontal velocity of 2 m/s. The number of picks is determined with a uniform distribution from 1 to 10 picks. (Wang et al. 2013) Minimize travel time GA A single configuration of a 2-block 3D-warehouse with 2,880 picking locations, 9 aisles, 8 locations per side, 10 levels. Picking device with a horizontal velocity of 2 m/s and a vertical velocity of 1 m/s. A single route with 20 picks. (Chirici and Wang 2014) Minimize traveled distance S-shape A single configuration of a single-block warehouse with 900 storage locations, 10 aisles, 45 locations per side, and one elevator to transport items from the ground to other levels. (Pan et al. 2014) Picking time estimation Routing policies Four warehouse configurations consisting of single-block warehouses with 1,000 storage locations, 10 aisles, varying the number of locations per side (50, 25, 10, 5) and the number of levels (1, 2, 5, 10). Picking device with a horizontal velocity of 300 ft/min and a vertical velocity of 100 ft/min. A single route with 10 picks. (Zuniga et al. 2015) Minimize traveled distance TSP software A single configuration of a single-block 3D-warehouse with 180 storage locations, 5 aisles, 6 locations per side, and 3 levels. Picking device with a horizontal velocity of 5 km/h. (Gómez et al. 2016). Minimize picking time Tabu search A single configuration of a single-block 3D-warehouse with 45 storage locations, 5 aisles. Picking device with a horizontal velocity of 5 km/h. (Li et al. 2017) Minimize traveled distance ACO A single configuration of a 2-block 3D-warehouse with 2,000 picking locations, 40 rows, and 50 columns. Picking device with a horizontal velocity and a vertical velocity of 0.25 m/s. (Chabot et al. 2018) Minimize traveled distance ALNS Five warehouse configurations for single-aisle and single-block warehouses with 4 levels, varying the storage locations (96, 192, 288, 384, 480), varying the number of locations per side (12, 24, 36, 48, 60) and the number of levels (1, 2, 5, 10). Picking device with a horizontal velocity of 5 km/h. The number of picks varies from 10 to 100. (Damayanti et al. 2018) Minimize travel time GA A single configuration of a single-block 3D-warehouse. The characteristics of the warehouse are unspecified. A single route with 10 picks. Picking device with a horizontal velocity of 2.5 m/s and a vertical velocity of 0.27 m/s. (Pinto and Nagano 2019) Minimize travel time GA A real-life case of a 2-block 3D-warehouse with 306 picking locations and 5 aisles. (Van Gils et al. 2019b) Minimize makespan ILS and LKH heuristic A real-life case of a 3-block 3D-warehouse with 11 aisles, 140 locations per level per side and 7 levels. Regarding distances and travel times in 3D warehouses, (Azadnia et al. 2013) show the distance calculation for storage locations in the same aisle, while (Tsai et al. 2008) present the distance calculation for storage locations belonging to different aisles in single-block high-level storage systems. (Ene and Öztürk 2012) and (Wang et al. 2013) propose formulas to compute vertical and horizontal distances in high-level storage systems, however, they calculate the total travel time as the horizontal travel time divided the horizontal velocity plus the vertical travel time divided the vertical velocity, which means considering sequential movements for picking devices. (Damayanti et al. 2018) also consider sequential movements for pickers by calculating the total picking time as the sum of horizontal travel time, vertical travel time, retrieving time and double handling time, and they calculate lifting speed taking into account the weight of the products. On the other hand, (Fu et al. 2011) and (Wang et al. 2012) introduce the travel time between two storage locations considering simultaneous movements for picking devices, but without complying with height reference levels to leave aisles, and (Li et al. 2017) consider the medium level of a rack as a height reference level for picking devices to move within an aisle. (Cano et al. 2019a) introduced a travel time formulation adapted for multiple-block 3D warehouses, however, this formulation has some shortcomings when calculating minimum distances for warehouses with 3 or more blocks. Accordingly, a travel time formulation between each pair of storage locations for multi-block high-level storage systems has not been found in the literature, nor the consideration of a height reference level for a picking device to leave aisles and ensure the safety of the operations inside warehouses and distribution centers where multiple pickers converge. In this sense, ignoring real-life features causes substantial performance inefficiencies because incorporating safety conditions in vertical warehouses induce additional travel and wait times (Van Gils et al. 2019a) Concerning solution approaches for the PRP, Table 1 illustrates that metaheuristics are usually used to a greater extent to minimize distances, travel and picking times, and tardiness in high-level storage systems, followed by heuristics and routing policies (Masae et al. 2020). This highlights the use of population-based metaheuristics such as genetic algorithms (GA) and ant colony optimization (ACO), which have equally been applied to solve the PRP for 2D-warehouses considering different objective functions and either considering single or multiple blocks. In this regard, Table 2 indicates the main studies addressing the PRP using GA and ACO, demonstrating the extensive application of these solution approaches for different types of order picking problems and warehouse configurations. Table 2. GA and ACO solution approaches for the PRP Author GA ACO 2D 3D Singleblock Multiblock Function objective Special considerations (Tsai et al. 2008) ✔ ✔ ✔ Travel cost, tardiness, and earliness Multi-objective (Fu et al. 2011) ✔ ✔ ✔ ✔ Travel time Hybrid algorithm (Ene and Öztürk 2012) ✔ ✔ ✔ Travel cost (Wang et al. 2012) ✔ ✔ ✔ Travel time (Azadnia et al. 2013) ✔ ✔ ✔ Tardiness (Chen et al. 2013) ✔ ✔ ✔ Picking time and waiting time Two pickers and congestion (Wang et al. 2013) ✔ ✔ ✔ Travel time Author GA ACO 2D 3D Singleblock Multiblock Function objective Special considerations (Xu et al. 2014) ✔ ✔ ✔ Distance (Chen et al. 2015) ✔ ✔ ✔ Tardiness (Cheng et al. 2015) ✔ ✔ ✔ Distance (Chen et al. 2016) ✔ ✔ ✔ Total order service time Multiple pickers, congestion, and online problem (Jin et al. 2017) ✔ ✔ ✔ Refilling time (Li et al. 2017) ✔ ✔ ✔ Distance (Schrotenboer et al. 2017) ✔ ✔ ✔ Travel cost Multiple pickers and interaction effects (Ardjmand et al. 2018) ✔ ✔ ✔ Makespan (Damayanti et al. 2018) ✔ ✔ ✔ Travel time Lifting speed as a function of the product weight (De Santis et al. 2018) ✔ ✔ ✔ Distance (Cano et al. 2019b) ✔ ✔ ✔ Distance (Chen et al. 2019) ✔ ✔ ✔ ✔ Distance Hybrid algorithm, ultra narrow aisles, and access restriction (Pinto and Nagano 2019) ✔ ✔ ✔ Travel time Real case warehouse From Table 2 it is also highlighted that most of the studies using ACO to solve the PRP are focused on 2D- warehouses, except for the works of (Wang et al. 2012) and (Li et al. 2017) that are focused on 3D- warehouses, while GAs have been widely applied to solve the PRP for both 2D and 3D-warehouses. Additionally, it is important to mention that the works of (Fu et al. 2011) and (Chen et al. 2019) propose ACO-GA hybrid algorithms to obtain the greatest benefit of both solution methods. However, a proposal to solve the PRP using GA and ACO for multi-block high-level storage systems has not yet been identified in the literature to compare the performance of both metaheuristics under different operating and warehouse configuration scenarios. This type of study can contribute to identify the warehouse environments in which a specific solution method provides better performance for the PRP concerning travel time, which is a performance measurement that enables other objective functions for joint order picking problems like tardiness, earliness, and makespan (maximum completion time). 3. PRP DESCRIPTION Since the PRP is formulated as an STSP, then it can be modeled as a classic TSP by calculating an L x L matrix, where the element ij represents the minimum travel distance or the minimum travel time from the storage location i to the storage location j, it is necessary to formulate the distances and travel times between each pair of storage locations considering the warehouse configuration. In this case, minimum distance and travel time formulas must be proposed between storage positions for multiple-block 3D-warehouses. For multi-block 3D-warehouses, where 𝑟∈𝑅 and R is the set of blocks in a warehouse, Tr represents the ycoordinate of the top of the block r, and Br represents the y-coordinate of the bottom of the block r. Figure 1 shows the layout of a 3-block 3D warehouse with the coordinates representing the top and bottom of each block, that is, (0, B1 ,0) and (0, T1 ,0) for block 1, (0, B2 ,0) and (0, T2 ,0) for block 2, and (0, B3 ,0) and (0, T3 ,0) for block 3. Likewise, given two picking positions i and j represented by 𝑖=(𝑥i,𝑦i,𝑧𝑖) and 𝑗= (𝑥j,𝑦j,𝑧𝑗), 𝐵𝑖 and 𝐵𝑗 represent the y-coordinate of the bottom of the block to which position i and j belong, and 𝑇𝑖 and 𝑇𝑗 represent the y-coordinate of the top of the block to which position i and j belong. Therefore, the Manhattan distance 𝑑𝑖𝑗 between i and j such that 1≤𝑖≠𝑗≤𝐿 is calculated through Eq. (1) when i and j belong to the same aisle and block. As shown in Figure 2, when considering a height reference level to leave a picking aisle, it is necessary to consider the vertical distances between i and j as the sum of the z-coordinates (𝑧𝑖+𝑧𝑗), therefore Eq.(2) is used if i and j belong to different aisles in the same block, that is 𝐵𝑖=𝐵𝑗=𝐵 and 𝑇𝑖=𝑇𝑗=𝑇. Consequently, Eq.(3) is used when i and j belong to different blocks, that is 𝐵𝑖≠𝐵𝑗 and 𝑇𝑖≠𝑇𝑗. Figure 1. Layout of a multiple-block 3D warehouse 𝑑𝑖𝑗=|𝑥𝑖−𝑥𝑗|+|𝑦𝑖−𝑦𝑗|+|𝑧𝑖−𝑧𝑗| (1) 𝑑𝑖𝑗=|𝑥𝑖−𝑥𝑗|+𝑚𝑖𝑛{|𝑦𝑖−𝑇|+|𝑇−𝑦𝑗|,|𝑦𝑖−𝐵|+|𝐵−𝑦𝑗|}+(𝑧𝑖+𝑧𝑗) (2) 𝑑𝑖𝑗=|𝑥𝑖−𝑥𝑗|+|𝑦𝑖−𝑦𝑗|+(𝑧𝑖+𝑧𝑗) (3) Figure 2. Vertical distance considering height reference level to leave an aisle When considering the simultaneity of vertical and horizontal movements, Tchebychev metrics are used to establish the travel time 𝑡𝑖𝑗 between two different picking positions i and j belonging to the same aisle, computing 𝑡𝑖𝑗 as the maximum between the horizontal and vertical travel time (Won and Olafsson 2005; Wang et al. 2012; Pan et al. 2014) as shown in Eq. (4), given 𝑣ℎ as the horizontal velocity and 𝑣𝑣 as the vertical velocity of the picking device. 𝑡𝑖𝑗=𝑚𝑎𝑥{|𝑥𝑖−𝑥𝑗|+|𝑦𝑖−𝑦𝑗| 𝑣ℎ ,|𝑧𝑖−𝑧𝑗| 𝑣𝑣 } (4) Then, Eq.(5) is used when i and j belong to different aisles in the same block, and 𝑡𝑖𝑗 is measured as the minimum time required between going from position i to the top cross-aisle plus going from the top crossaisle to the position j, and going from position i to the bottom cross-aisle plus going from the bottom crossaisle to the position j. Eq. (5) guarantees Tchebychev metrics within each picking aisle and the floor level as the height reference level to exit and enter each aisle. 𝑡𝑖𝑗=|𝑥𝑖−𝑥𝑗| 𝑣ℎ+𝑚𝑖𝑛{𝑚𝑎𝑥{|𝑦𝑖−𝑇| 𝑣ℎ ,𝑧𝑖 𝑣𝑣 }+𝑚𝑎𝑥{|𝑇−𝑦𝑗| 𝑣ℎ ,𝑧𝑗 𝑣𝑣 },𝑚𝑎𝑥{|𝑦𝑖−𝐵| 𝑣ℎ ,𝑧𝑖 𝑣𝑣 }+𝑚𝑎𝑥{|𝐵−𝑦𝑗| 𝑣ℎ ,𝑧𝑗 𝑣𝑣 }} (5) If i and j belong to different blocks and 𝐵𝑖>𝐵𝑗 and 𝑇𝑖>𝑇𝑗 then Eq.(6) is used ensuring that the picker leaves the block of the position i through 𝐵𝑖 and enters the block of the position j through 𝑇𝑗. 𝑡𝑖𝑗=|𝑥𝑖−𝑥𝑗| 𝑣ℎ+𝑚𝑎𝑥{𝑦𝑖−𝐵𝑖 𝑣ℎ ,𝑧𝑖 𝑣𝑣 }+𝐵𝑖−𝑇𝑗 𝑣ℎ+𝑚𝑎𝑥{𝑇𝑗−𝑦𝑗 𝑣ℎ ,𝑧𝑗 𝑣𝑣 } (6) Eq. (7) is used when i and j belong to different blocks 𝐵𝑖<𝐵𝑗 and 𝑇𝑖<𝑇𝑗 guaranteeing that the picker leaves the block of the position i through 𝑇𝑖 and enters the block of the position j through 𝐵𝑗. 𝑡𝑖𝑗=|𝑥𝑖−𝑥𝑗| 𝑣ℎ+𝑚𝑎𝑥{𝑇𝑖−𝑦𝑖 𝑣ℎ ,𝑧𝑖 𝑣𝑣 }+𝐵𝑗−𝑇𝑖 𝑣ℎ+𝑚𝑎𝑥{𝑦𝑗−𝐵𝑗 𝑣ℎ ,𝑧𝑗 𝑣𝑣 } (7) Once the calculations of minimum distances and minimum travel times are provided for each pair of picking locations i and j in a multi-block high-level storage system, the formulation of a mathematical model for the PRP can be made considering the following assumptions: • An item is stored only in a single storage location. • Picking devices can traverse the picking aisles and cross-aisles in both directions and pickers can change direction in the aisle. • Each picking tour starts and ends at a single depot. • Random storage assignment policy is used. • The distance or travel time between any two positions is known in advance. • This study considers a single picker and thus congestion or picker blocking is not evaluated, researchers interested in this matter can consult the studies of (Chen et al. 2013) (Chen et al. 2016) (Chen et al. 2019). 4. METAHEURISTICS APPROACHES FOR THE PRP In this section, this study introduces a genetic algorithm, and ant colony optimization algorithm and a local search procedure to solve the PRP in 3D warehouses 4.1. Genetic Algorithms for the PRP GA is a well-known population-based metaheuristic where each individual (chromosome) represents a PRP solution, and through an evolutionary process that emulates natural processes of selection, crossover, elitism, immigration, and mutation, the best solution is found after a determined number of generations. GAs have been widely used to solve the PRP because this is a combinatorial and complex problem aiming to find the best sequence of storage locations to visit in a route to satisfy an objective function. The design of the GA for the PRP starts with the encoding of P individuals from the population, and in each chromosome, each gene represents a picking location, so the length of each chromosome is fixed and equal to the number of picking locations to visit, and the sequence of appearance of the genes indicates the picking route to perform. The initial population contains well-performing individuals inspired on routing policies or heuristics to begin the evolutionary process with good-quality genetic information, and it can also contain individuals created with Monte Carlo simulation to ensure an adequate exploration of the solution space. In this case, nine individuals are created arbitrarily following different procedures: 1) s-shape multi-block heuristic; 2) s-shape single-block heuristic starting from the front block; 3) s-shape single-block heuristic starting from the back block; 4) aisle-by-aisle multi-block heuristic; 5) visiting storage locations sorted from highest to lowest according to their number; 6) visiting storage locations sorted from lowest to highest according to their number; 7) local search applied to storage locations sorted from highest to lowest according to their number; 8) local search applied to storage locations sorted from lowest to highest according to their number; 9) traversing each aisle from the front to the back block. The remaining P-9 individuals are created randomly using Monte Carlo simulation. The fitness function measures the performance of each individual through the calculation of the travel time required to visit all picking positions, starting and ending at the depot. The survival operator is applied to preserve the best-performing individuals for the next generation according to an elitism rate 𝐸𝑟. Then, based on a crossover rate 𝐶𝑟, an amount of 2×𝑃×𝐶𝑟 chromosomes are selected using the linear ranking method where the best performing individuals are most likely to be selected, and a two-point crossover method that divides each chromosome into three sections is applied to the selected parents where the middle section is exchanged between each pair of parents. As shown in Figure 3, if offspring resulting from the crossover operator are unfeasible, a correction mechanism eliminates repeated genes from the new section in each offspring and replaces them randomly with the missing genes. This process is replicated until obtaining 𝑃×𝐶𝑟 new chromosomes for the next generation. Figure 3. Crossover operator To complete the next generation, the immigration operator creates 𝑃×𝐼𝑟 individuals using Monte Carlo simulation, therefore ensuring the exploration of the solution space. Likewise, the mutation operator diversifies the solution space search by altering some individuals from the new generation, selected according to a mutation rate 𝑀𝑟, and a mutation method between the SWAP Mutation, Mutation Region, and Local Search Mutation is randomly assigned to each selected chromosome. The SWAP Mutation exchanges two randomly selected genes, the Mutation Region reverses the sequence of genes belonging to a region bounded by two randomly chosen points in a chromosome (see Figure 4), and the Local Search Mutation applies a local search procedure explained in Section 3.3. executed on a PC (Intel i5 2.8 GHz CPU, 8 GB memory). 6. RESULTS AND DISCUSSION The results of the experiments for the GA and ACO performance are shown in Appendix D, highlighting that the GA offers shorter travel times compared to the ACO, LS and SS in 91.7% (44/48), 95.8% (46/48) and 100% (48/48) of the scenarios respectively, and equals the travel time of the LS in 4.2% (2/48) scenarios. Similarly, ACO generates shorter travel time than the LS and SS in 68.8% (33/48) and 91.7% (44/48) of the scenarios respectively and equals the travel time of LS in 4.2% (2/48) of the scenarios; while LS generates better results when compared to SS in 77.1% (37/48) of the scenarios and equals its performance in 6.3% (3/48) of the scenarios. Regarding travel time savings between the analyzed picker routing methods, Table 6 illustrates that the GA provides maximum savings of 6.6% over ACO when considering a warehouse configuration of 2 blocks, 3 levels, 10 locations per aisle side and 10 aisles, and visiting 30 picking positions. For this same warehouse configuration and visiting 10 picking positions, the GA provides maximum savings of 11.2% over the LS and provides maximum savings of 19.2% over the SS when visiting 30 picking locations and considering warehouse configurations of 2 blocks, 3 levels, 20 locations per aisle side, 5 aisles, and 3 blocks, 7 levels, 10 locations per aisle side, 5 aisles. These results determine that the GA on average performs better than ACO, LS and SS by 2.3%, 3.9% and 7.4% respectively, so its use in 3D warehouse environments is recommended to obtain the most significant decrease of picking time. The good performance of the GA against the ACO is partly since the ACO is a constructivist algorithm that generates new solutions in each iteration, while the GA works with complete solutions in each individual. This allows including good quality initial solutions in the individuals through heuristics and routing policies, ensuring satisfactory performance of the algorithm regarding the global solution and the computing time. In this sense, it is highlighted that in all the scenarios the GA presented better average performance than the LS and SS because the GA uses individuals based on the LS and SS on the initial population. As for the ACO, this algorithm generates maximum savings of 8.3% when compared to the LS for a similar scenario where the GA generated maximum savings over the LS. Likewise, the ACO provides maximum savings of 17.9% compared to the SS in the same scenarios where the GA generated maximum savings over this benchmark. The LS procedure generates savings of up to 14.9% when compared to the SS in the same scenarios where GA and ACO generated maximum savings over this benchmark. Therefore, for the PRP in multi-block 3D warehouses considering height reference levels to leave aisles, the best performing routing methods are the GA and ACO by consistently offering better performance regarding heuristics like LS and SS in different warehouse configurations and problem sizes. Consequently, these metaheuristics can be applied in joint order picking problems and in real warehouse scenarios. Table 6. Travel time savings for PRP solution approaches Algorithms Maximum Savings Average Savings Minimum Savings Winning scenarios GA vs ACO 6,6% 2,3% -0,6% 44 / 48 GA vs LS 11,2% 3,9% 0,0% 46 / 48 GA vs S-s 19,1% 7,4% 0,6% 48 / 48 ACO vs LS 8,3% 1,7% -3,3% 33 / 48 ACO vs S-s 17,9% 5,2% -1,2% 44 / 48 LS vs S-s 14,9% 3,5% -4,4% 37 48 6.1 Warehouse configuration analysis The effect of warehouse configurations on travel time savings is analyzed for each solution approach addressed in this study. Figure 8(a) shows that the GA offers better performance than the ACO for warehouse configurations with fewer blocks, racks per side and a greater number of aisles. According to height levels, the results do not show significant average savings. Figure 8(b) shows that the GA shows better performance compared to the LS in warehouse configuration with fewer blocks, height levels, racks per side, and a greater number of aisles. (a) (b) Figure 8. Average travel time savings for GA vs ACO (a) and GA vs LS (b) Figure 9(a) shows that the GA outperforms the SS mainly in warehouse configurations considering fewer aisles, generating of 9.1% on travel time for warehouse configurations with 5 aisles. Regarding the performance of the ACO according to the warehouse configuration, Figure 9(b) indicates the ACO provides better performance over LS for warehouse configurations with fewer blocks, height levels, and racks per aisle side, generating average savings of 5.2% when considering 2 blocks, 3 levels and 10 racks per aisle side. (a) (b) Figure 9. Travel time savings for GA vs SS (a) and ACO vs LS (b) Likewise, the ACO presents greater travel time savings over the SS as shown in Figure 10(a), especially in warehouse configurations considering fewer aisles and blocks, generating on average savings of 7.1% for configurations with 5 aisles and 2 blocks. Figure 10(b) illustrates the savings of LS over SS, highlighting the performance of LS in warehouse configurations with fewer aisles, generating average savings of 5.6% when considering 5 aisles. 2,2% 4,0% 2,4%2,2% 1,6% 2,7% 3,1%2,9%2,6% 3,0% 0,3% 0,9% 1,4% 2,8% 2,3% 1,6% 0,0% 1,0% 2,0% 3,0% 4,0% 5,0% 5 10 5 10 5 10 5 10 5 10 5 10 5 10 5 10 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles 6,9% 9,5% 5,5%4,8% 1,8%2,1% 3,4%2,8% 4,3%4,3% 1,7% 3,2%3,2%3,7% 2,5%3,0% 0,0% 2,0% 4,0% 6,0% 8,0% 10,0% 5 10 5 10 5 10 5 10 5 10 5 10 5 10 5 10 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles 8,4%8,0% 14,3% 5,4% 6,8% 5,1% 7,9% 4,3% 6,1%6,9%7,8%7,3% 11,9% 5,0% 9,8% 2,6% 0,0% 4,0% 8,0% 12,0% 16,0% 5 10 5 10 5 10 5 10 5 10 5 10 5 10 5 10 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles 4,7% 5,6% 3,1% 2,6% 0,1% 0,3% 1,8% 1,3%1,5% 2,3%1,9% 0,9% 0,1% 1,4% 0,0% 2,0% 4,0% 6,0% 510 510 510 510 510 510 510 510 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles -0,6% -0,1% (a) (b) Figure 10. Travel time savings for ACO vs SS (a) and LS vs SS (b) 6.2 Performance by pick-list size The performance of the routing methods for multi-block 3D warehouses according to the pick-list size is shown in Figure 11, identifying that no significant performance savings are obtained when comparing the GA with ACO and LS, and when comparing ACO with LS; while greater travel time savings are observed when comparing GA, ACO, and LS with the SS as the picks increases, especially when the pick-list size is equal to 30. Therefore, the conditions impacting mostly the performance of the GA, ACO, and LS are related to the warehouse configuration. Figure 11. Algorithms performance by the number of picks 6.3 Computing time analysis Analyzing the computing time to establish the applicability of the proposed algorithms in real warehouse environments, Figure 12 shows that increasing the pick-list size increases the execution time of each algorithm exponentially. However, the computing times for the GA and ACO are considered reasonable and feasible for warehouse operational environments to provide an efficient picking route. Likewise, the ACO generates computing times much longer than the GA, especially as the pick-list size increases, since in the case of 30 picks the ACO provides an average computing time 5.5 times higher than the GA. 6,3% 4,1% 12,2% 3,3% 5,1% 2,5% 4,9% 1,4% 3,6%4,1% 7,6%6,5% 10,7% 2,3% 7,6% 1,0% 0,0% 3,0% 6,0% 9,0% 12,0% 15,0% 5 10 5 10 5 10 5 10 5 10 5 10 5 10 5 10 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles 1,6% 9,3% 0,5% 5,1% 3,0% 4,6% 1,5%1,9% 2,8% 6,1% 4,2% 9,0% 1,4% 7,6% 0,0% 2,0% 4,0% 6,0% 8,0% 10,0% 5 10 5 10 5 10 5 10 5 10 5 10 5 10 5 10 10 20 10 20 10 20 10 20 3 7 3 7 2 3 Racks per side Levels Blocks Aisles -0,4% -1,7% 1,9% 3,7% 6,9% 1,8% 5,1% 3,3% 2,6% 4,0% 7,0% 1,5% 4,5% 3,0% 2,3% 4,0% 8,2% 1,7% 6,0% 4,2% 0,0% 3,0% 6,0% 9,0% GA vs ACO GA vs LS GA vs SS ACO vs LS ACO vs SS LS vs SS 10 20 30 Figure 12. Computing time (seconds) for the GA and ACO It is comprehensible that the GA outperforms the ACO on efficiency and computing time in multiple warehouse configurations, therefore, it is recommended to use the GA as a routing method for the PRP in joint order picking problems (JOPP) like the joint order batching and picker routing problem (JOBPRP), and the joint order batching, sequencing and picker routing problem (JOBSPRP). Consequently, it is significant to analyze the computing time consumed by the GA in case that the proposed algorithm is integrated into order batching problems (OBP) and batch sequencing problems (BSP) that are solved using population-based metaheuristics, thus, Appendix D shows the total average time that the GA could consume in a JOPP according to the number of iterations and population size chosen to solve the OBP and BSP. As the size of the JOPP increases, the computation time required to resolve the PRP increases, therefore changes in the population size and number of iterations of the GA can be implemented to address this issue. Regarding the population size, according to the experimental data in Section 4.1, reducing the population size from 40 to 20 chromosomes reduces the computing time by 26.3% and increases the travel time by 0.84%. Likewise, if the number of generations of the GA is reduced from 40 to 20, the computing time is reduced by 26.9% in exchange for an increase of 0.55% in travel time. Additionally, the LS algorithm can also be implemented to refine the best solution at the end of the GA, allowing a reduction in the number of iterations and individuals to obtain feasible computation times for the JOPP. Finally, these strategies generate a satisfactory trade-off between solution quality and computing time, allowing the integration of the proposed GA into JOPP. 7. CONCLUSIONS In summary, this study develops a GA and an ACO algorithm to solve the PRP in multi-block high-level storage systems to minimize the travel time, considering real-life features like height reference levels to change from an aisle to another. After the parameter tuning for the proposed algorithms and several experiments involving warehouse configurations, picks in a tour and picking device velocities, it is concluded that the proposed algorithms offer high precision solutions when compared to optimal solutions, thus representing efficient approaches to solve the PRP in daily operations for vertical warehouses. In this way, the proposed metaheuristics would improve picking performance and allow customer demands to be met rapidly. From the proposed algorithms, the GA solves both small and large problems well and performs better than the ACO in both efficiency and computation time, and also outperformed the local search procedure and the SS heuristic used as benchmarks. Consequently, it is recommended to use the GA for joint order picking problems that require multiple times to execute the PRP for each batch in each iteration, since the GA provides fast and efficient solutions. Therefore, the main contributions of this article are focused on proposing and analyzing the performance of metaheuristics for the PRP in multiple configurations of multi-block high-level storage systems, and formulating for the first time the minimum travel times for multi-block 3D stores considering the floor level 0,08 0,11 0,27 0,99 0,73 4,04 0,00 1,00 2,00 3,00 4,00 5,00 GA ACO 10 20 30 as the height reference level for picking devices to exit an aisle. Future research can consider congestion and picker blocking conditions, integrate local search algorithms to refine the efficiency and the computing time of the proposed GA and ACO, and test the performance of the proposed algorithms in non-conventional 3D-warehouses. REFERENCES Ardjmand E, Sanei O, Youssef E (2019) Using list-based simulated annealing and genetic algorithm for order batching and picker routing in put wall based picking systems. Appl Soft Comput J 75:106–119. https://doi.org/10.1016/j.asoc.2018.11.019 Ardjmand E, Shakeri H, Singh M, Sanei Bajgiran O (2018) Minimizing order picking makespan with multiple pickers in a wave picking warehouse. Int J Prod Econ 206:169–183. https://doi.org/10.1016/j.ijpe.2018.10.001 Azadnia AH, Taheri S, Ghadimi P, et al (2013) Order batching in warehouses by minimizing total tardiness: A hybrid approach of weighted association rule mining and genetic algorithms. Sci World J 2013:1–13. https://doi.org/10.1155/2013/246578 Bartholdi JJ, Hackman ST (2014) Warehouse & Distribution Science. The Supply Chain and Logistics Institute, Michigan Cano JA, Correa-espinal A, Gómez RA, Cortés P (2019a) Distance and travel time modeling in high-level picker-to-part systems (3-D warehouses). J Southwest Jiaotong Univ 54:. https://doi.org/https://doi.org/10.35741/issn.0258-2724.54.6.1 Cano JA, Correa-Espinal AA, Gómez-Montoya RA, Cortés P (2019b) Genetic Algorithms for the Picker Routing Problem in Multi-block Warehouses. In: Abramowicz W, Corchuelo R (eds) Lecture Notes in Business Information Processing. Springer, Cham, Switzerland, pp 313–322 Çelik M, Süral H (2018) Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic. Int J Prod Res 0:1–19. https://doi.org/10.1080/00207543.2018.1489154 Chabot T, Coelho LC, Renaud J, Côté JF (2018) Mathematical model, heuristics and exact method for order picking in narrow aisles. J Oper Res Soc 69:1242–1253. https://doi.org/10.1080/01605682.2017.1390532 Chen F, Wang H, Qi C, Xie Y (2013) An ant colony optimization routing algorithm for two order pickers with congestion consideration. Comput Ind Eng 66:77–85. https://doi.org/10.1016/j.cie.2013.06.013 Chen F, Wang H, Xie Y, Qi C (2016) An ACO-based online routing method for multiple order pickers with congestion consideration in warehouse. J Intell Manuf 27:389–408. https://doi.org/10.1007/s10845-014-0871-1 Chen F, Xu G, Wei Y (2019) An Integrated Metaheuristic Routing Method for Multiple-Block Warehouses with Ultranarrow Aisles and Access Restriction. Complexity 2019:1–14. https://doi.org/10.1155/2019/1280285 Chen TL, Cheng CY, Chen YY, Chan LK (2015) An efficient hybrid algorithm for integrated order batching, sequencing and routing problem. Int J Prod Econ 159:158–167. https://doi.org/10.1016/j.ijpe.2014.09.029 Cheng C-Y, Chen Y-Y, Chen T-L, Yoo JJ-W (2015) Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem. Int J Prod Econ 170:1–10. https://doi.org/10.1016/j.ijpe.2015.03.021 Chirici L, Wang KS (2014) Tackling the storage problem through genetic algorithms. Adv Manuf 2:203–211. https://doi.org/10.1007/s40436-014-0074-1 Damayanti DD, Setyawan EB, Andrawina L, Santosa B (2018) Warehouse picking model for single picker routing problem in multi dimensional warehouse layout using genetic algorithm approach to minimize delay. Adv Intell Syst Comput 700:124–134. https://doi.org/10.1007/978-3-319-72550-5_13 De Koster R, Le-Duc T, Roodbergen KJ (2007) Design and control of warehouse order picking: A literature review. Eur J Oper Res 182:481–501. https://doi.org/10.1016/j.ejor.2006.07.009 De Santis R, Montanari R, Vignali G, Bottani E (2018) An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses. Eur J Oper Res 267:120–137. https://doi.org/10.1016/j.ejor.2017.11.017 Dorigo M, Birattari M, Stützle T (2006) Ant colony optimization: Artificial ants as a computational intelligence technique. IEEE Comput Intell Mag 1:28–39 Dorigo M, Maniezzo V, Colorni A (1996) Ant system: Optimization by a colony of cooperating agents. IEEE Trans Syst Man, Cybern - Part B Cybern 26:29–41. https://doi.org/10.1109/3477.484436 Ene S, Öztürk N (2012) Storage location assignment and order picking optimization in the automotive industry. Int J Adv Manuf Technol 60:787–797. https://doi.org/10.1007/s00170-011-3593-y Fu C, Wang Y, Gu Y, et al (2011) Routing optimization of high-level orderpickers in a rectangular warehouse. In: 2011 International Conference on Consumer Electronics, Communications and Networks, CECNet 2011 - Proceedings. XianNing, pp 4388–4391 Gómez RA, Giraldo OG, Campo EA (2016) Minimum time order batching in the put away operation considering k homogeneous equipment using metaheuristics [Conformación de Lotes Mínimo Tiempo en la Operación de Acomodo Considerando k Equipos Homogéneos usando Metaheurísticos]. Inf Tecnol 27:53–62. https://doi.org/10.4067/S0718-07642016000600006 Grosse EH, Glock CH, Neumann WP (2017) Human factors in order picking: a content analysis of the literature. Int J Prod Res 55:1260–1276. https://doi.org/10.1080/00207543.2016.1186296 Henn S (2012) Algorithms for on-line order batching in an order picking warehouse. Comput Oper Res 39:2549–2563. https://doi.org/10.1016/j.cor.2011.12.019 Hsu C-M, Chen K-Y, Chen M-C (2005) Batching orders in warehouses by minimizing travel distance with genetic algorithms. Comput Ind 56:169–178. https://doi.org/10.1016/j.compind.2004.06.001 Jiang X, Zhou Y, Zhang Y, et al (2018) Order batching and sequencing problem under the pick-and-sort Order batching and sequencing problem under the pick-and-sort strategy in online supermarkets strategy in online supermarkets. Procedia Comput Sci 126:1985–1993. https://doi.org/10.1016/j.procs.2018.07.254 Jin H, Wang W, Cai M, et al (2017) Ant colony optimization model with characterization-based speed and multi-driver for the refilling system in hospital. Adv Mech Eng 9:1–18. https://doi.org/10.1177/1687814017713700 Lee JA, Chang YS, Shim H-J, Cho S-J (2015) A Study on the Picking Process Time. In: 6th International Conference on Applied Human Factors and Ergonomics (AHFE 2015) and the Affiliated Conferences, AHFE 2015. Elsevier B.V., Las Vegas, United States, pp 731–738 Li J, Huang R, Dai JB (2017) Joint optimisation of order batching and picker routing in the online retailer’s warehouse in China. Int J Prod Res 55:447–461. https://doi.org/10.1080/00207543.2016.1187313 Lin C-C, Kang J-R, Hou C-C, Cheng C-Y (2016) Joint order batching and picker Manhattan routing problem. Comput Ind Eng 95:164–174. https://doi.org/10.1016/j.cie.2016.03.009 Masae M, Glock CH, Grosse EH (2020) Order picker routing in warehouses: A systematic literature review. Int J Prod Econ 224:107564. https://doi.org/10.1016/j.ijpe.2019.107564 Menéndez B, Pardo EG, Sánchez-Oro J, Duarte A (2017) Parallel variable neighborhood search for the min-max order batching problem. Int Trans Oper Res 24:635–662. https://doi.org/10.1111/itor.12309 Öztürko Ö (2019) Discrete Optimization A discrete cross aisle design model for order-picking warehouses. Eur J Oper Res 275:411–430. https://doi.org/10.1016/j.ejor.2018.11.037 Pan JC-H, Wu M-H, Chang W-L (2014) A travel time estimation model for a high-level picker-to-part system with class-based storage policies. Eur J Oper Res 237:1054–1066. https://doi.org/10.1016/j.ejor.2014.02.037 Pinto ARF, Nagano MS (2019) Genetic algorithms applied to integration and optimization of billing and picking processes. J Intell Manuf 1–19. https://doi.org/10.1007/s10845-019-01470-3 Ramaekers K, Caris A, Moons S, Gils T Van (2018) Using an integrated order picking-vehicle routing problem to study the impact of delivery time windows in e-commerce. Eur Transp Res Rev 10:1–11 Roodbergen KJ, De Koster R (2001) Routing methods for warehouses with multiple cross aisles. Int J Prod Res 39:1865–1883. https://doi.org/10.1080/00207540110028128 Roodbergen KJ, Vis IFA (2009) A survey of literature on automated storage and retrieval systems. Eur J Oper Res 194:343–362. https://doi.org/10.1016/j.ejor.2008.01.038 Scholz A, Henn S, Stuhlmann M, Wäscher G (2016) A new mathematical programming formulation for the Single-Picker Routing Problem. Eur J Oper Res 253:68–84. https://doi.org/10.1016/j.ejor.2016.02.018 Scholz A, Schubert D, Wäscher G (2017) Order picking with multiple pickers and due dates –Simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems. Eur J Oper Res 263:461–478. https://doi.org/10.1016/j.ejor.2017.04.038 Schrotenboer AH, Wruck S, Roodbergen KJ, et al (2017) Order picker routing with product returns and interaction delays. Int J Prod Res 55:6394–6406. https://doi.org/10.1080/00207543.2016.1206982 Theys C, Bräysy O, Dullaert W, Raa B (2010) Using a TSP heuristic for routing order pickers in warehouses. Eur J Oper Res 200:755–763. https://doi.org/10.1016/j.ejor.2009.01.036 Tsai C-Y, Liou JJH, Huang T-M (2008) Using a multiple-GA method to solve the batch picking problem: considering travel distance and order due time. Int J Prod Res 46:6533–6555. https://doi.org/10.1080/00207540701441947 Van Gils T, Caris A, Ramaekers K, et al (2019a) Designing efficient order picking systems: The effect of real-life features on the relationship among planning problems. Transp Res Part E 125:47–73. https://doi.org/10.1016/j.tre.2019.02.010 Van Gils T, Caris A, Ramaekers K, Braekers K (2019b) Formulating and Solving the Integrated Batching, Routing, and Picker Scheduling Problem in a Real-life Spare Parts Warehouse. Eur J Oper Res 277:814–830. https://doi.org/10.1016/J.EJOR.2019.03.012 Van Gils T, Ramaekers K, Braekers K, et al (2018a) Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions. Int Jovan Gils, T al, 2018 Increasing order Pick Effic by Integr storage, batching, Zo Pick routing policy Decis Int J Prod Econ 197(1), pp243–261 Available http//linkinghub 197:243–261. https://doi.org/10.1016/j.ijpe.2017.11.021 Van Gils T, Ramaekers K, Caris A, de Koster RBM (2018b) Designing Efficient Order Picking Systems by Combining Planning Problems: State-of-the-art Classification and Review. Eur J Oper Res 267:1–15. https://doi.org/10.1016/j.ejor.2017.09.002 Wang R, Zang L, Tan X (2013) An optimal routing model of high-level picker-to-part system. Lect Notes Electr Eng 185 LNEE:371–383. https://doi.org/10.1007/978-1-4471-4600-1_32 Wang Y, Fu C, Ma M, Wang L (2012) Routing optimization of high-level order picking truck based on swarm intelligent algorithm. Appl Mech Mater 101–102:414–417. https://doi.org/10.4028/www.scientific.net/AMM.101-102.414 Won J, Olafsson S (2005) Joint order batching and order picking in warehouse operations. Int J Prod Res 43:1427–1442. https://doi.org/10.1080/00207540410001733896 Xu W, Shi CY, Song HT, Chen YX (2014) Applied technology on improving the order picking efficiency in the area of EC of china post logistics based on ACO. Adv Mater Res 859:486–491. https://doi.org/10.4028/www.scientific.net/AMR.859.486 Zhang J, Wang X, Chan FTS, Ruan J (2017) On-line order batching and sequencing problem with multiple pickers: A hybrid rulebased algorithm. Appl Math Model 45:271–284. https://doi.org/10.1016/j.apm.2016.12.012 Zhang R, Wang M, Pan X (2019) New model of the storage location assignment problem considering demand correlation pattern. Comput Ind Eng 129:210–219. https://doi.org/10.1016/j.cie.2019.01.027 Zuniga CA, Olivares-Benitez E, Tenahua AM, Mujica MA (2015) A methodology to solve the Order Batching Problem. IFAC Proc Vol 48:1380–1386. https://doi.org/10.1016/j.ifacol.2015.06.279 Appendix A. Pseudo-code for GA, ACO, and LS Algorithm 1. Genetic Algorithm for the PRP Input Data(); Bestglobal() Initial_population() While not Finish()do For p:=1 to P Fitness Function(); If obj(p)< bestfit then bestfit:= obj(p); Bestglobal():= chromosome(p); End if End for x:=0; Sort population(); Elitism operator(); For i:=1 to int(P*Er) x=x+1; New_population(x):= Sorted_population(i); End for Linear ranking method(); Roulette wheel selection(); For i:=1 to int(P*Cr) parents(i,1):= rnd1; parents(i,2):= rnd2; End for Crossover Operator(); For i:= 1 to int(P*Cr) If Crossover(i) unfeasible then Correction mechanism(); End if x=x+1; New_population(x):= Offspring(i); End for Immigration Operator(); For i:=1 to int(P*Ir) x=x+1; New_population(x):= MonteCarlo(i); End for Mutation Operator(); For i:=1 to int(P*Mr) If rnd3:=1 then New_population(rnd4):= SWAP(rnd4); Elseif rnd3:=2 then New_population(rnd4):= Local Search(rnd4); Elseif rnd3:=3 then New_population(rnd4):= Mutation Region(rnd4); End if End for Endwhile Output Data(); Note: P denotes the number of individuals, obj() is the fitness value of a solution, rnd1 and rnd2 are random values ϵ[1;P] and rnd1≠rnd2, rnd3 is a random value ϵ[1;3], rnd4 is a random value ϵ[1;P]. Algorithm 2. Ant Colony Optimization for the PRP Input Data(); Bestglobal() While not Finish()do For k:=1 to K Pijk() Mk() For n:=1 to N Calculate Pijk(); a:=Selectnode(); If a ϵ Mk() n:=n-1 Else Mk(n):= a End if End for Fitness Function(); If obj(Mk())< L then L:= obj(Mk()); Bestglobal():= Mk(); End if End for For i:=1 to N For j:=1 to N If edge(i,j) ϵ Mk() increasepheromone(i,j); Else decreasepheromone(i,j); End if End for End for End while Output Data(); Note: N denotes the number of nodes, K denotes the number of ants, Pijk() is the probability that ant k moves through edge ij, Mk() is the memory for ant k, obj() is the fitness value of a solution. Algorithm 3. Local Search Procedure for the PRP Input Data(); Bestglobal() While improvement=1 do improvement:=0; For i:=1 to N-1 For j:=i+1 to N Fitness Function(); If obj(SWAP(i,j)) < bestfit then bestfit := obj(SWAP(i,j)); improvement:=1; virtualglobal():=SWAP(i,j); End if End for End for If improvement=1 then Bestglobal():= virtualglobal(); End if Loop End while Output Data(); Note: N denotes the number of picking positions, SWAP(i,j) is the current solution swapping the picking positions i and j, and obj() is the fitness value of a solution. Appendix B. Parameter tuning for GA and ACO For the parameter tuning of the proposed GA, the parameter values found in several studies of the PRP shown in Table B.1 were taken as a basis. From these values, 𝐶𝑟= 70%, 80%, 90%; 𝑀𝑟= 5%, 10%, 20%; 𝑃= 20, 40; 𝐺= 20, 40 were considered. Accordingly, more importance is placed on the crossover and mutation operator because they represent the most relevant operators of a GA, and the values of P and G are relatively small to provide solutions in short computing times. The elitism rate and the immigration rate depend directly on the crossover rate and are calculated as 𝐸𝑟=𝐼𝑟=(1−𝐶𝑟)/2. These values provide 𝐶𝑟×𝑀𝑟×𝑃×𝐺 = 36 scenarios (3 x 3 x 2 x 2), and in each scenario, 10 replicas are generated for a total of 360 experimental runs. The warehouse configuration consists of 3 blocks, 10 aisles, 15 storage locations per aisle and five height levels for a total of 4,500 storage locations. The picking device utilizes a horizontal speed of 2.0 m/s and a vertical speed of 0.4 m/s, and 20 picking locations must be visited on each tour. Table B.1. GA parameters for the PRP proposed in the literature Parameters (Tsai et al. 2008) (Fu et al. 2011) (Ene and Öztürk 2012) (Azadnia et al. 2013) (Wang et al. 2013) (Schrotenboer et al. 2017) (Damayanti et al. 2018) (Cano et al. 2019b) (Chen et al. 2019) (Pinto and Nagano 2019) Population (P) 20 50 125 500 100 100 N/A 20 + n/2 Pick aisles 25, 35, 50 Crossover rate (𝐶𝑟) 90% 90% 70% 80% 90% 6% N/A 75% 75% 100%, 20%, 50% Mutation rate (𝑀𝑟) 4% 2% 0.8% 20% 5% 50% N/A 20% 10% 50%, 80%, 100% Elitism rate (𝐸𝑟) - - 4% - - 30% - 15% - - Immigration rate (𝐼𝑟) - - - - - - - 10% - - Generations (G) 10 1000 - 10000 200 1500 N/A 40 + n/3 100 x Pick aisles 50, 60, 60 Consecutive iterations without improving the best solution - - - - - iter / 5 - n/4 100 x Pick aisles - n: number of pick locations Table B.2 shows that the combinations providing the best results in travel time are C36:(Cr=0.9, Mr=0.2, P=40, G=40), C24:(Cr=0.8, Mr=0.2, P=40, G=40) and C12:(Cr=0.7, Mr=0.2, P=40, G=40) in which the combination of mutation rate, population and generations is the same; while the combinations offering worst travel time performance are C13:(Cr=0.8, Mr=0.05, P=20, G=20), C1:(Cr=0.7, Mr=0.05, P=20, G=20) and C5:(Cr=0.7, Mr=0.1, P=20, G =20) sharing identical values of population size and generations. The experiments show the greatest difference in travel time depends on the 𝑀𝑟 parameter, generating savings of 1.73% when comparing 𝑀𝑟 = 0.2 with 𝑀𝑟 = 0.05, while the parameter 𝐶𝑟 does not offer significant changes in the average travel time but the computing time is increased by 12.6% when 𝐶𝑟 increases from 0.7 to 0.9. Table B.2. Results for GA parameters 𝑪𝒓 𝑴𝒓 𝑷 iter. Travel Time Computing time Combination 70% 5% 20 20 456,0 0,13 C1 40 451,1 0,17 C2 40 20 446,5 0,21 C3 40 452,6 0,24 C4 10% 20 20 455,1 0,15 C5 40 450,5 0,19 C6 40 20 445,9 0,22 C7 40 444,3 0,30 C8 20% 20 20 446,9 0,18 C9 40 443,2 0,26 C10 40 20 444,1 0,28 C11 40 441,8 0,43 C12 80% 5% 20 20 456,4 0,14 C13 40 454,3 0,16 C14 40 20 449,8 0,19 C15 40 451,5 0,25 C16 10% 20 20 454,5 0,15 C17 40 446,1 0,19 C18 40 20 447,5 0,22 C19 40 448,5 0,29 C20 20% 20 20 450,8 0,17 C21 40 443,2 0,26 C22 40 20 443,1 0,28 C23 40 441,3 0,42 C24 90% 5% 20 20 453,8 0,13 C25 40 451,0 0,17 C26 40 20 452,7 0,19 C27 40 450,2 0,28 C28 10% 20 20 452,3 0,14 C29 40 445,9 0,19 C30 40 20 448,3 0,21 C31 40 444,2 0,30 C32 20% 20 20 445,7 0,16 C33 40 447,3 0,23 C34 40 20 443,4 0,28 C35 40 441,2 0,37 C36 Regarding the population size, considering P=20 chromosomes generates an average picking time of 450.2 seconds and considering P=40 generates a travel time of 446.5 seconds, representing savings of 0.83% and an increase of 36% in computing time. Likewise, by increasing the number of iterations from 20 to 40, the travel time is reduced by 0.55%, and the computing time is increased by 37%. Therefore, the combination C24 is selected because it offers an efficiency similar to the efficiency of the combination C36 and yields lower minimum values than those of the combination C36. Accordingly, the parameter values for the proposed GA are 𝐶𝑟=0.8, 𝑀𝑟=0.2, P=40, G=40, and consequently 𝐸𝑟=0.1 and 𝐼𝑟=0.1, ensuring better performance in travel time at a reasonable computing cost. Then, using the selected parameter values, it is identified that the average number of iterations required to obtain the global best is G=15, so as a stopping criterion the GA finish when 15 consecutive iterations fail to improve the global best. In order to obtain the parameters ensuring the best performance for the proposed ACO, Table B.3 present the parameter values proposed by several authors in the literature and used as the basis for parameter tuning. To reduce the computing time of the ACO, which is usually one of the main pitfalls of this metaheuristic, other parameter values are considered, like K = 10 and a number of iterations equal to 10. For the constant Q, the value Q = 1 is taken by default (Wang et al. 2012). Therefore (𝛼,𝛽)×𝜌×𝐾×𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 = 36 scenarios (2 x 3 x 3 x 2) are generated, performing 10 replicas in each scenario for a total of 360 experimental runs. The same warehouse configuration, picking device, and the number of picking locations proposed for the GA parameter tuning were used. Table B.3. ACO parameters for the PRP in the literature Parameter Values Author (𝛼,𝛽) (1,2) (1,5) (Fu et al. 2011; Wang et al. 2012) (Chen et al. 2016, 2019; Jin et al. 2017; Li et al. 2017; De Santis et al. 2018) 𝜌 0.15 0.5 0.9 (Chen et al. 2016, 2019) (Chen et al. 2015; Li et al. 2017) (Fu et al. 2011; Wang et al. 2012; De Santis et al. 2018) 𝑄 1 100 (Wang et al. 2012) (Jin et al. 2017) 𝐾 20 30 (Fu et al. 2011; Chen et al. 2015) (Wang et al. 2012; Chen et al. 2016; Jin et al. 2017) Iterations 30 (Fu et al. 2011) According to Table B.4, the parameter combinations showing the best results in travel time are C36:(α=1, β=5, 𝜌=0.9, m=30, iter=30), C35:(α=1, β=5, 𝜌=0.9, m=30, iter=10), C30:(α=1, β=5, 𝜌=0.5, m=30, iter=30) and C24:(α=1, β=5, 𝜌=0.15, m=30, iter=30); while the parameter combinations offering the worst travel time performance are C8:(α=1, β=2, 𝜌=0.5, m=10, iter=30), C13:(α=1, β=2, 𝜌=0.9, m=10, iter=10). The experiments show the greatest difference in picking time is obtained changing the parameters α and β, since (α=1, β=5) generates savings of 9% when compared to (α=1, β=2). Table B.4. Results for ACO parameters (α,β) ρ K Iterations Travel Time Computing time Combination (1 , 2) 0,15 10 10 515,8 0,4 C1 30 524,9 1,3 C2 20 10 499,9 0,8 C3 30 513,6 2,5 C4 30 10 505,7 1,2 C5 30 502,3 3,7 C6 0,5 10 10 525,2 0,4 C7 30 530,5 1,3 C8 20 10 515,4 0,8 C9 30 508,8 2,5 C10 30 10 496,7 1,3 C11 30 497,7 3,7 C12 0,9 10 10 531,1 0,4 C13 30 524,3 1,3 C14 20 10 520,0 0,8 C15