key: cord-0939986-pow192ie authors: Ardjmand, Ehsan; Singh, Manjeet; Shakeri, Heman; Tavasoli, Ali; Young II, William A. title: Mitigating the risk of infection spread in manual order picking operations: A multi-objective approach date: 2020-11-30 journal: Appl Soft Comput DOI: 10.1016/j.asoc.2020.106953 sha: 5ee8c19fcc058870c3f68e749cad6c5cd3f137a9 doc_id: 939986 cord_uid: pow192ie In the aftermath of the COVID-19 pandemic, supply chains experienced an unprecedented challenge to fulfill consumers’ demand. As a vital operational component, manual order picking operations are highly prone to infection spread among the workers, and thus, susceptible to interruption. This study revisits the well-known order batching problem by considering a new overlap objective that measures the time pickers work in close vicinity of each other and acts as a proxy of infection spread risk. For this purpose, a multi-objective optimization model and three multi-objective metaheuristics with an effective seeding procedure are proposed and are tested on the data obtained from a major US-based logistics company. Through extensive numerical experiments and comparison with the company’s current practices, the results are discussed, and some managerial insights are offered. It is found that the picking capacity can have a determining impact on reducing the risk of infection spread through minimizing the picking overlap. In December 2019, a novel coronavirus named COVID-19 (SARS-CoV-2) was first documented in Wuhan, China. By early March 2020, 114 countries reported cases of the virus contractions, and the World Health Organization declared the rapidly spreading outbreak a pandemic. While writing this article, there are more than 10,000,000 reported confirmed cases of the infection worldwide [1] , and current projections anticipate approximately 175,000 deaths by the end of August 2020 in the US [2] . Promptly after the outbreak, it became evident that the supply chains will be severely disrupted, and depending on the outbreak size, demand disruption, and recovery synchronicity of the firms, the performance of the supply chains will be proportionally deteriorated [3] . In the context of supply chains, epidemic outbreaks are a form of disruption risk that impacts operational performance measures. Operational activities ordinarily involve humans and are prone to interruption if the employees are in close physical contact. Physical distancing is advocated by epidemiologists as an infection spread mitigation strategy [4] [5] [6] , and can be adapted to labor-intensive operational tasks for minimizing the likelihood of personnel contracting the infection, and hence, maintaining the performance. Manual order picking operations are highly labor-intensive, and due to their criticality, cannot be suspended during a crisis. Furthermore, since the pickers may work in close vicinity, an order picking environment may bring about an elevated risk of virus transmission among the personnel. Thus, physical distancing policies can be utilized to reduce the likelihood of virus propagation among the pickers. Depending on the type of picking environment, such policies may have different consequences and must be selected in accordance with parameters such as picking objectives and warehouse design. For example, a warehouse whose operations are centered around wave picking may need to implement physical distancing practices that have the least conflict with its picking makespan. The objective of this paper is to revisit the well-known order picking problem in manual order picking warehouse while considering physical distancing practices and aims to investigate the performance and managerial implications of implementing such practices. For this purpose, a tri-objective formulation of the order picking problem is proposed where the total picking time, makespan, and the time over which the workers are picking closer than a minimum physical distance are to be minimized. The third objective, henceforth referred to as picking overlap, is https://doi.org/10.1016/j.asoc.2020.106953 1568-4946/© 2020 Elsevier B.V. All rights reserved. computed by measuring the time each pair of pickers are stationed at the proximity of each other as controlled by a distance parameter ∆. Thus, a more substantial overlap must be calculated if more than two pickers are positioned close to each other during picking. Indeed, a more congested area has a higher infection transmission potential. As defined in this study, picking overlap is mainly concerned with the picking time when the pickers have limited motions due to their physical position in relation to the pick locations. One has to draw a distinction between the picking overlap and walking overlap where at least one picker is walking. This study is primarily concerned with the picking overlap. Thus, walking pickers are exempt from the overlap computations. This assumption works best for many warehouses where the picking aisles are wide enough for the pickers to respect a physical distance while passing by each other. It is noteworthy that the picking overlap can provide the decision-makers with a proxy measure of the picking plus walking overlap. Thus, it can be utilized in warehouses with narrow aisles where the aisles' distance does not allow for physical distancing. Additionally, the problem is parametrized by a distance constant ∆ that can be adjusted to favor the situations where it is preferred to have a single picker in an aisle. This study is modeled after the warehouse operations of a major logistics company located in the US and uses the order level data provided by the company. Moreover, the company's order picking practices are assessed to draw a comparison between the current state of affairs and solutions that acknowledge physical distancing. The company's current order picking operations are highly geared towards minimizing the total picking time, and as will be illustrated, improving the physical distancing measure while maintaining the status quo's level of picking efficiency is possible. In fact, there seems to be some degree of positive synergy among picking overlap and total picking time objectives. However, makespan demonstrates intense conflict with the other two objectives. This observation has unpropitious implications for wave picking environments, where makespan is typically prioritized. In other words, physical distancing practices seem to be more challenging to implement in wave picking warehouses when compared to the warehouses, where the objective is to minimize the total picking time. Conventionally, Order picking problems consist of several subproblems. In order picking with physical distancing (OPPD) considerations, one is interested in batching a set of orders and devising a picking route for each batch to optimize a set of predefined objectives while minimizing picking overlap amid the stationary pickers. The warehouse of this study utilizes the Sshape routing policy. Thus, the main results are derived using the same procedure. However, to explore the effect of routing policy on the results, the Midpoint policy is assessed in the numerical experiment section as well. While some evidence shows that the S-shape routing policy has anti-congestion properties [7, 8] , the results of applying the Midpoint policy in the context of the presented problem, does not confirm this hypothesis. As previously shown in the literature, order batching is NPhard and challenging to solve for large instances using exact methods [9] . This challenge is more amplified when multiple objectives are considered. This study proposes a mathematical tri-objective model along with three evolutionary algorithms, namely, Non-dominated Sorting GA-II (NSGAII) [10] , strength Pareto evolutionary algorithm (SPEA2) [11] , and Non-dominated Sorting GA-III (NSGAIII) [12] , to tackle the problem. The primary motivation for using three evolutionary metaheuristics comes from some earlier evidence in the literature where evolutionary methods have yielded promising results for multi-objective order picking problems [13, 14] . Thus, this study will delve deeper into assessing evolutionary algorithms' applications in such problems as a side objective. There are numerous well-known approaches within the realm of multi-objective evolutionary methods, each utilizing a different strategy. While being far from being an exhaustive list of algorithms, NSGAII (with a non-dominated sorting strategy), NSGAIII (with a reference-point-based procedure), and SPEA2 (with a density estimation technique) represent three important approaches in multi-objective metaheuristics. Thus, evaluating these methods can potentially guide future direction on using multi-objective techniques in order picking. In this study, the company's order batching method is utilized to seed the proposed metaheuristics and significantly improve the results. The proposed methods' solutions are compared against the current practices of the studied company to draw managerial insights. This study contributes to the current body of the literature by considering a picking overlap objective whose utilization can mitigate the risk of infectious disease spread, such as the one caused by COVID-19. Additionally, this study's methods can be applied to order picking operations during flu seasons to avoid downtime in the warehouses due to personnel sickness. The remainder of this paper is structured as follows. In Section 2, related literature is reviewed. In Section 3, the structure of the problem is explained. Section 4 outlines the proposed optimization model. In Section 5, the order batching method of the case study's company and the proposed metaheuristics are introduced. Section 6 is dedicated to the numerical experiments. Section 7 discusses the managerial implications of the findings, and finally in Section 8 overall conclusion is stated. The presented study's central contribution revolves around mitigating the risk of contracting infectious diseases in warehouses by reevaluating the order picking problems and incorporating a picking overlap objective. The rationale behind the picking overlap objective is that being positioned reasonably apart while picking, abates the chance of infection spread. However, the extent of order picking performance deterioration, if any, in the presence of physical distancing is not fully investigated in the literature. Furthermore, to the best of authors' knowledge, picking overlap has not been recognized as an independent objective previously. This section examines the existing order picking literature that is most relevant to the subject of this study. Structurally, and from an operational standpoint, order picking problems are composed of four sub-problems of order batching, batch assignment, batch sequencing, and picker routing [15] [16] [17] , among which order batching and picker routing are the subjects of this study. Order batching is primarily revolving around grouping a set of customer orders in such a manner to achieve a set of operational objectives such as total travel time or tardiness minimization [18] [19] [20] . Typically, batching alone is not sufficient to accomplish the objectives, and typically is accompanied by a routing decision. The literature offers some evidence of performance independence between batching and routing sub-problems in particular cases [21] . However, an advantageous bilateral effect between these two sub-problems has been observed in several instances [8, 15, 22, 23] . In the picker routing problem, the objective is to form the shortest possible path for picking the batches. Warehouse routing problems are usually modeled as a special case of the traveling salesman problem (TSP), known as Steiner TSP, where each visiting node has a maximum degree of four [17] . Since it was shown that Steiner TSPs encountered in rectangular warehouses with two cross-aisles are solvable in polynomial time [24] , several solvable cases of warehouse TSPs have been introduced, and efficient methodologies are developed for more general warehouse architectures [25] [26] [27] . A major disadvantage of exact routing methods is the complexity of their produced paths for pickers to follow [8] . Thus, warehouses prefer to employ heuristic methods that generate paths with predictable patterns. The most widely used routing policies in the warehouses are S-shape, midpoint, return, and largest gap [28] . Besides exact and heuristic approaches, some studies have utilized metaheuristic methods for routing [16, [29] [30] [31] . When integrated, order batching and picker routing can result in significant efficiency gains [15] . However, the integrated problem poses computational challenges. To this end, exact and scalable (both exact and heuristic) methods of order batching and picker routing are extensively studied [67, 68] . To tame the complexity of the integrated problem, and replicate a more realistic scenario, some studies have concentrated on exact batching solutions in the presence of heuristic routing policies [7, 9, 51, 61] . On the other hand, some studies have exclusively applied heuristics and metaheuristics [29, 30, 46, 47, 57, 62, 69] , or a different combination of exact and heuristic approaches [17] . From a methodological point of view, the literature on multiobjective order picking problems is limited [68] , and few studies tackle two objectives [13, 14, 39, [70] [71] [72] [73] [74] . To the best of the authors' knowledge, with the exception of NSGAII [13, 14] , SPEA2 and NSGAIII have not been applied to multi-objective manual order picking problems before. Moreover, as discussed earlier, these three methods represent three notable approaches (i.e., nondominated sorting, reference points, and density estimation) in the multi-objective evolutionary algorithms. Thus, their application in the context of the proposed tri-objective model and the results of numerical experiments can offer an initial investigation of utilizing these multi-objective methods in the manual order picking literature. One distinctive feature of order picking problems is their choice of the objective function. Three objectives of total travel time, tardiness, and makespan are the most frequently utilized objectives in the literature, among which total travel time and makespan are the most and least regularly considered objectives [17] . While at least one of these objectives seem to fulfill the requirements of any warehouse, the recent supply chain disruptions pertaining to coronavirus outbreak (COVID-19/SARS-CoV-2) pandemic points to a possible gap in the order picking operational objectives. In a practical context, it is essential to protect the pickers from infectious diseases by assigning them picking tours that have less overlap and are more compliant with physical distancing recommendations. This study addresses the existing literature gap by introducing an overlap objective that acts as a measure of physical distancing practices in conjunction with total travel time and makespan objectives. This research intends to shed light on the performance implications of the overlap objective in a real setting by utilizing efficient metaheuristic designs. There is a vast literature on order batching and picker routing, and this study does not intend to examine the existing body of research fully. Thus an interested reader is referred to [8, 75, 76] , and Table 1 in which some of the most notable order batching and picker routing studies, sub-problems they have considered, methods applied, and the objectives utilized are summarized. This study's warehouse is modeled after a real warehouse belonging to a well-known logistics company in the USA. The warehouse operates in a wave picking setting where the profile of the next wave is known beforehand. Waves are ordinarily large, and each day is dedicated to picking a single wave. Warehouse's shape is rectangular with multiple parallel aisles, and two front and rear cross aisles. The walking speed of pickers is assumed constant, and the crossing time between two sides of an aisle is negligible. Each shelf can hold multiple products, and each product is located on only one shelf. There are N orders, each consisting of multiple products, to be picked. The warehouse stocks M different products, and there are a sufficient number of pickers to pick the orders. Picking commences with batching the orders and retrieving their products using S-shape routing policy starting from origin v 0 . Each picker is assigned a single batch, and there are a sufficient number of pickers to manage all batches. All tours begin simultaneously and at time 0. Orders cannot split among multiple picking tours, and orders assigned to a batch must not exceed pickers' capacity Q . Following physical distancing practices, pickers are preferred to be positioned less than ∆ (i.e., minimum social distance) units of a length away while in picking position. Thus, physical distancing considerations are only applied to stationary pickers. Products' dimensions are reasonably similar (i.e., there is no unusually large/small product), and instead of total volume, the capacity is determined as the number of items that a picker can handle. All products are located within reach of the pickers, and therefore, vertical distance is insignificant. Picking time at a location comprises the duration of searching, picking, and checking, and is estimated based on the number of units picked at the location. Fig. 1 depicts the order of operations in OPPD, in which initially a list of orders, each containing multiple items, is received and compiled. Next, the orders are grouped into batches. Finally, each batch is picked by traversing a route through the warehouse and by a picker. As presented in Fig. 1 , routing depends on batching decisions, and these two create an intertwined problem. While the presented study is primarily designed based on the logistics' company warehouse, it can be extended to other manual order picking environments as well. This extension is mainly viable due to the structure of the overlap objective function, which is based on the time pickers operate in proximity to each other. Almost in every manual order picking system, the pickers are bound to work close to each other occasionally and, thus, are prone to the risk of infection spread. Considering the pick overlap as an assessable picking performance that estimates the time pickers are closer than a minimum physical distance, it can be universally applied to different settings in the manual order picking literature. In order picking, warehouse graph representation is a central modeling component. Depending on the routing policy, it is possible to exploit the warehouse graph for obtaining optimum routing. For example, if an exact routing policy is of interest, it suffices to consider the picking locations solely, and the distance between two picking nodes will be the shortest distance between the nodes. In this manner, the warehouse graph will be reduced to a considerably smaller graph that is more convenient to be manipulated by exact methods [24] . Furthermore, warehouse graphs lend them to efficient valid inequalities that are demonstrated to be highly effective for modeling order picking problems [61] . When using heuristic routing policies, it is not necessary to solve for the sequence of the picking nodes, and thus, a model does not need to obtain the nodes' enter and exit times and hence, a less complicated model [7] . When modeling OPPD with an S-shape routing policy, the traversed distance between two nodes is not necessarily the shortest. Thus, the problem's graph cannot be treated as in the exact methods. On the other hand, the entrance and the exit times of each picking location need to be accurately determined in the model to calculate the picking overlap. Therefore, the benefits of sequence-less models cannot be utilized. This structure of OPPD [24] Dynamic programming Total distance/time [32] Branch and bound Makespan [33] Dynamic programming Total distance/time [34] Heuristics Total distance/time [35] Cluster analysis Order similarity [36] Association rule mining Order similarity [9] Column generation Total distance/time [37] Heuristic Response time [38] Heuristic Total distance/time [21] Heuristic Total distance/time [39] Multiple genetic algorithm Total distance time and due date [40] Variable neighborhood search Total distance/time [41] K-means self-organizing map Total distance/time Picking vehicle utility [42] Heuristic Makespan [43] Hill climbing Tabu search Total distance/time [44] Heuristic Total distance/time [45] Tabu search Total distance/time [46] Association rule mining Genetic algorithm Total tardiness [47] Heuristic Total tardiness [48] Heuristic Total distance/time [49] A*-algorithm simulated annealing Total distance/time [31] Genetic algorithm Ant colony optimization Total tardiness [30] Particle swarm optimization Ant colony optimization Total tardiness [50] Variable neighborhood search Total tardiness [51] Column Generation Travel cost [7] Heuristic Tabu Search Total distance/time [52] Group genetic algorithm Workload balance [53] Heuristic Total distance/time [54] Particle swarm optimization Total distance/time [55] Heuristic Total distance/time U-turns [14] NSGA-II Total distance/time [56] Variable neighborhood search Total distance/time [57] Tabu search Total distance/time [23] Ant colony optimization Total distance/time [58] Variable neighborhood search Total tardiness [19] Variable neighborhood search Total distance/time [59] Parallel Variable neighborhood search Batch retrieval time [26] Dynamic programming Total distance/time [15] Variable neighborhood search Total tardiness [60] Genetic algorithm Total distance/time [61] Branch & bound Total distance/time [16] Lagrangian decomposition-particle swarm optimization Parallel simulated annealing-ant colony optimization Makespan [62] A Memetic Algorithm Simulated annealing Total time [63] Branch & bound Makespan [64] Heuristic Total tardiness [18] Variable neighborhood search Tabu search Total distance/time [65] Heuristic Makespan delivery cost [66] Heuristic Total distance/time [17] Exact/Heuristic Makespan [13] Genetic algorithm Coevolutionary genetic algorithm Archived multi-objective simulated annealing Total distance/time Makespan formulation poses a unique challenge: determining the entry times of each picking node while traversing a path that is not necessarily the shortest. To resolve this issue, it is necessary to ascertain the entry times of all intermediary nodes where no picking takes place. This necessity itself poses a new challenge. If the entry times of each node (intermediary and picking) are to be determined, then the typical sub-tour elimination constraints cannot be applied because some nodes are visited more than once. Fig. 2 depicts an S-shape picking tour where some nodes are visited twice. Typical sub-tour elimination constraints cannot handle the situations where a location is visited more than once. Thus, the Steiner graph of a warehouse is inadequate for modeling OPPD. To overcome the problem of multiple location visits and implement sub-tour elimination constraints, multiple connected replications of the Steiner graph, henceforth referred to as extended Steiner graph (or extended graph in short), must be utilized. In the example of Fig. 2 , an extended graph where sub-tour elimination constraints are fulfilled can be obtained by connecting two replicas of a Steiner graph. In this regard, each node in the original Steiner graph is associated with two nodes (replicas) in the extended graph. The distance between the replicas of a node in the extended graph is assumed to be 0, to preserve the length of a tour. The new higher dimensional, extended graph can be used to create a tour where each node is visited at most once, and sub-tour elimination constraints can be implemented. Fig. 3 illustrates how to utilize an extended Steiner graph to transform the tour of Fig. 2 with two replicas r 1 and r 2 for each node and visit each location at most once. In Fig. 3 , instead of backtracking the tour, and for avoiding a location revisitation, the tour stretches to another replica of the Steiner graph in the extended graph. Since this lateral transition has no time associated with it, it does not alter the primary duration of the tour. Considering the extended Steiner graph representation introduced earlier, the warehouse of this study can be modeled as a graph G = (V, E), where V and E are the sets of nodes, and edges of the graph. Each node v ∈ V has R replicas, corresponding to R Steiner graphs. Storage node of the jth product is denoted by l(j). In other words, l acts as a function whose input is a product and outputs a storage node in the Steiner graph (i.e., l : M → V). Function a : M → K associates the location of each product j ∈ M to an aisle k ∈ K. In the proposed model, functions l and a is separated from indices by a comma to avoid confusion. Characteristic functionq : N × M → {0, 1} outputs 1 if order i ∈ N contains product j ∈ M, otherwise outputs 0. Characteristic function δ ∆ : V × V → {0, 1} determines whether the distance between two nodes v 1 and v 2 is less than the minimum acceptable physical distance ∆ or not. Note that in this study, the terms 'node' and 'location' are often used interchangeably, and when a physical site is intended, the term physical location is preferred. The indices, parameters/functions, and decision variables of the model are defined as follows: : picking time overlap between node v 1 in batch b 1 and node v 2 in batch b 2 The proposed model P is formulated as follows: subject to Eqs. (4)- (35) which are given in Box I. In model P, (1) to (3) measure the total travel time, makespan and the total overlap, respectively. Constraint (4) assigns each order to exactly one batch and in order to break solution symmetries, it assigns order i 1 to batch b 1 , order i 2 to either batch b 1 or batch b 2 , and so forth [61] . Batch capacity is imposed in Constraint (5). Constraint (6) ensures that picking activities take place when the first replica of a picking node is visited. Constraint (7) limits the number of nodal visits to one. Constraint (8) makes the caps the number of visiting origin node to one. Constraint (9) equates the number of entries and exits for all nodes replicas. Constraints (10) and (11) guarantee that there is no reversal and double traversal on the back aisle's edges. Constraints (12) allows a movement reversal only on the rightmost aisle of each batch. Constraints (13) to (18) determine the visiting and rightmost aisles of each batch. Constraint (19) calculates the picking time on each node. Constraints (20) to (22) specifies the entry and exit time of each node and eliminates the sub-tours. Constraint (23) measures the finishing time of each batch. Constraint (24) determines the makespan, and constraints (25)- (27) determine the overlap among nodes across different batches. Finally, constraints (28) to (31) specify the type and domain of each decision variable. As can be observed, constraints (25) to (27) in model P are non-linear. However, linearizing these constraints are quite straightforward and commercial solvers such as Gurobi automatically handles them. In this section, the company's order batching method is described. Moreover, the application of three metaheuristics, namely, NSGAII, SPEA2, and NSGAIII, in solving the proposed model, P, is explained. The proposed metaheuristics use the company's order batching schema as a seeding procedure for initializing the evolution process. As will be illustrated later, using this seeding procedure improves the results significantly. Finally, a full factorial experiment is conducted to determine the best set of parameters for each metaheuristic. Box I. The company's order batching heuristic forms a single batch at each step. For this purpose, it starts with determining the most visited aisle by all unassigned orders. Then, it proceeds with selecting the orders that require a minimum extra distance to be traversed if selected into the batch. Selecting new orders is controlled through a penalty parameter that is updated every time a new order is added to the batch. The structure of this heuristic is designed with S-shape routing policy in mind. Parameters and variables used by the company's order batching heuristic are as follows: : Calibration vector where ψ k is the penalty for visiting aisle k by a new order i best : order with least penalty s i : total penalty of order i k left : index of the most left aisle that a batch visits k right : index of the most right aisle that a batch visits Algorithm 1 outlines the company's order batching steps. Batches formed by Algorithm 1 create a solution that will be used as a seed in the proposed metaheuristics. As will be discussed later, this type of seeding has a significant positive performance effect on all proposed metaheuristics. The core components of evolutionary algorithms are its solution representation (i.e., chromosome), fitness function, and crossover, mutation, and selection operators. [77, 78] . In this section, elements of the proposed NSGAII, SPEA2, and NSGAIII are introduced. A widely-used approach to define a chromosome is by utilizing a binary matrix whose arrays show the assignment of orders to catches. However, matrix representation has two main drawbacks. First, since each order is assigned to precisely one batch, the assignment matrix will be a sizeable sparse matrix and Table 3 Results of company's current method. Each component of chromosome Ω corresponds to an order i ∈ N while its value is a batch number b ∈ B i . Thus, the first order i 1 can only be assigned to the batch b 1 while the last order i N can be assigned to any of the batches. For this representation to function properly, it is necessary to have an equal number of batches and orders, i.e., B = N. Moreover, this equality is necessary to satisfy the capacity constraint in case each order occupies a single batch. Fig. 4 illustrates a chromosome consisting of seven orders and the batches to which each order belongs. Additionally, Fig. 4 depicts the batch choices that each chromosome element, associated with an order, can have. While forming the initial population, each chromosome is generated in Table 4 Best objective values and CPU times obtained by Gurobi, NSGAII, SPEA2, and NSGAIII. such a way to ensure feasibility. Each chromosome's fitness value is computed by measuring its total travel time, makespan, and total overlap using the S-shape routing policy. Remember that in this study, it is assumed that there are a sufficient number of pickers to pick the batches, and each batch is assigned to a separate picker. In this study, a standard two-point crossover is utilized. It is noteworthy that the two-point crossover does not violate the structure of a chromosome. Thus, after crossover, for each chro- In other words, each order is assigned to a batch whose index is less than the order index to break the solutions' symmetry. To ensure feasibility and in the case of generating infeasible offspring, crossover operation is repeated up to five times. If no feasible offspring is generated after the fifth time, the crossover operation is aborted. To perform a mutation, a chromosome's component ω i is randomly chosen, and its value is changed to a random value ω ′ i ∈ B i . In case the mutant is infeasible, it is discarded, and a new mutant is generated. Similar to the crossover, this process is repeated up to a maximum of five times to find a feasible mutant, and if no feasible solution is generated after the fifth time, mutation operation is aborted. A distinctive feature of NSGAII, SPEA2, and NSGAIII is their selection process. In this study, the works of [10] [11] [12] are closely followed for implementing the selection operator. Parameters of the metaheuristics have a determining impact on their performance. In this study, a full factorial method was utilized for tuning the parameters of the metaheuristics. Tuning parameters of the NSGAII, SPEA2, and NSGAIII include the probability of crossover p c , probability of mutation p m , probability of altering a gene during mutation process p g , number of selected individuals for the next generation µ, and number of offsprings at each generation λ. Since a higher number of generations positively impacts the results, it was omitted from the tuning process and was set to 200 for all experiments. For each parameter, three levels were considered, as shown in Table 2 The factorial experiments found no significant relationship between the parameters and their interaction with the performance of the algorithms in terms of Hypervolume. However, a significant relationship was observed when the CPU time was considered as the response variable. Fig. 5 depicts the standardized effect of parameters on Hypervolume and CPU time for NSGAII. As can be observed, none of the parameters' standardized effect reaches the threshold to be considered significant for the Hypervolume. However, three parameters and their interaction were determined significant when considered with the CPU time. Since no performance difference was detected, the parameters were set to minimize the CPU time (µ + λ = 50 + 150, p c = 0.6, p m = 0.05, and p g = 0.25). This section presents the results of applying NSGAII, SPEA2, and NSGAIII to a set of problems sampled from the order level data of the studied logistics company, and compares them against the company's current practices. On average, each order contains 4.32 units of products. In the less frequent instances of orders containing unusually large numbers (i.e., larger than capacity), they are modified to fit the batches' capacity. This modification was deemed essential to investigate the effect of batch size on the solutions. Number of orders in each problem is selected from closely follows one of the company's warehouses (i.e., rectangular with parallel aisles and two cross-aisles). However, the dimensions, number of aisles, and pick faces are modified to replicate a more controlled experiment environment. Note that this modification does not change the overall performance of the proposed algorithms or the conclusions drawn from results. Each problem is attempted five times, and the results detailed are based on the overall performance of each algorithm over the total number of trials for each problem. All algorithms are implemented in Python 3.7 and executed on a 64-bit Windows operating system with an Intel Core i9-7940X CPU and 64 GB RAM. Table 3 lists the total time F , makespan C max , and overlap Φ obtained from applying the company's method to the problems. As will be shown later, these results are highly efficient in terms of total travel time. However, the solutions it suggests are not efficient in terms of overlap as they are designed with a single total travel time objective in mind. As will be discussed in the remainder of this section, it is possible to maintain or minimally deteriorate the same level of total time efficiency while improving the overlap considerably. However, the same statement is not necessarily applicable to the makespan due to its negative correlation with both overlap and total travel time. Table 4 lists the best objective values and CPU times obtained by Gurobi, NSGAII, SPEA2, and NSGAIII. As can be observed, even for small instances with 25 orders, Gurobi is unable to find any feasible solution in the allotted one hour. Compared to the company's method in Table 3 , all proposed metaheuristics of Table 4 find superior or equal solutions for all instances of the problem. This higher quality is especially notable for makespan and overlap. The results of Table 4 demonstrate the extent to which each metaheuristic has been able to improve the solutions. However, it does not reveal any information on the relative performance of the methods. A multi-objective algorithm can be examined on several fronts. Some of the deciding performance measures of a multi-objective method are the number, quality, and diversity of the solutions it finds. The following metrics are utilized to compare the performance of the proposed multi-objective algorithms from various aspects [14, 79, 80] : 3i , and f 2 1i , f 2 2i and f 2 3i are the value of the objective functions for the ith non-dominated solution. • Spread of Non-dominated Solutions (SNS): assesses the diversity of the non-dominated solutions and is defined as: • Rate of Achievement Simultaneously to two objectives (RAS): measures the quality of the non-dominated solutions in relation with the minimum objective function, and is computed as: where F i = min{f 1i , f 2i , f 3i }. • Hypervolume (HV): represents both quality and diversity of a set of solutions on a Pareto frontier (P) by calculating the hypervolume of the Pareto front in regards with a reference point, and is computed as follows: where x i is a solution in P, and A(x i ) is the rectangular area confined between the points x i and a reference point. Table 5 shows the logarithm of hypervolume and CPU times of Gurobi, NSGAII, SPEA2, and NSGAIII. Log hypervolume conveys the same information as hypervolume. However, due to the large size of hypervolume numbers, log hypervolume is used in Table 5 . A non-parametric Kruskal-Wallis test on the hypervolume ranks of averages was conducted to compare the results of Gurobi, NSGAII, SPEA2, and NSGAIII. At a 0.95 significance level, it was found that there is no statistically meaningful difference in terms of log HV among the metaheuristics. Due to its small sample size, Gurobi was not involved in the test. However, a general assessment of the Gurobi's log HV results illustrates an inferior performance compared to the other proposed methods. A similar Kruskal-Wallis test was performed to compare the CPU times, and a significant difference was observed. Subsequently, a Mann-Whitney pairwise test with significance level 0.01 was conducted to find the method with the lowest CPU time, and NSGAII was determined as the fastest approach. Table 6 tabulates the average NPS, MID, SNS, and RAS values obtained by Gurobi, NSGAII, SPEA2, and NSGAIII rounded to the nearest integer. Similar to the log HV value in Table 5 , the performance of the proposed metaheuristics was evaluated using a non-parametric Kruskal-Wallis test, and it was found there is no statistically significant difference between the algorithms. Thus, the only differentiating parameter among the algorithms is their CPU time in which NSGAII outperforms the other algorithms. While there might be several reasons as to why a method such as NSGAIII that is designed for a larger number of objectives cannot outperform NSGAII and SPEA2, one possible explanation may lie in the seeding procedure of algorithms. As was discussed earlier, the seeding process provides high-quality solutions in terms of total travel time. Thus, the algorithms find it easier to explore the feasible space for solutions with lower makespan and overlap at the start. In other words, the evolutionary force of the algorithms is mostly concentrated on the makespan and overlap, and a smaller feasible space needs to be examined. In a smaller search space, the algorithms' performance can converge easier, and hence, equal solution quality. 10 50 0 1230 530 1310 780 1230 530 1230 530 1230 530 10 50 10 1230 530 1320 790 1230 530 1230 530 1230 530 10 50 30 1250 535 1395 780 1250 535 1230 535 1250 535 10 100 0 1080 530 1080 1080 1080 530 1080 530 1080 530 10 100 10 1080 530 1080 1080 1080 530 1080 530 1080 530 10 100 30 1080 535 1080 1080 1080 535 1080 535 1080 535 25 50 0 NA NA 2370 820 2370 820 2350 820 2350 820 25 50 In this section, the results of the proposed metaheuristics are compared against the case study's current practices. Fig. 6 depicts the current practices of the company against the Pareto frontier obtained by NSGAII. As can be observed, NSGAII offers a more diverse array of solutions. As was argued earlier, the company's method is quite efficient in terms of total travel time. However, as Fig. 6 illustrates, there are many other possibilities to choose from in order to have solutions with less overlap while maintaining travel time efficiency. Further comparison of the Pareto and company's solutions reveals two intriguing trends. First, when picking capacity is low, there are more solutions with the company's level of total time efficiency and lower overlap to select from. For example, in the problem with N = 50, Q = 50, and ∆ = 30, one can sustain the company's total travel time and improve the overlap by approximately 8.7%. Additionally, it seems smaller waves have a higher chance of obtaining a better overlap value for the same total travel time level. The second observation pertains to the relationship between overlap and total travel time. When the picking capacity increases, total travel time and overlap's correlation increases. Thus, low travel time solutions yield a lower overlap. This effect will be examined in more detail in the following sections. In some circumstances, one may be interested in no overlap scenarios where the pickers avoid picking overlap by waiting until the other pickers have cleared the shelf. In this case, no pick overlap will translate into an increase in the total travel time, and the overlap objective will be eliminated. Appendix A presents a no pick overlap model P ′ along with the results of NSGAII, SPEA2, and NSGAIII with no overlap considerations and S-shape routing procedure. To implement the no overlap policy, a first-in-firstout (FIFO) pick procedure is applied where the picker who has arrived at a pick location earlier starts picking first. At the same time, other pickers wait for the pick area to clear off. As can be observed from Appendix A, the proposed metaheuristics are quite competent for dealing with high overlap instances compared to the company's current practice. In fact, when no overlap is allowed, the proposed metaheuristics tend to significantly improve the company's solutions compared to the cases where the overlap is permitted. Notably, as the minimum physical distance increases (and consequently waiting times increases), the percentage of the company's total travel time improvement obtained by the metaheuristics also increases. This observation shows the superior performance of the proposed multi-objective methods when dealing with no-overlap instances. While the metaheuristics perform well on the no overlap instances, it is noteworthy that accepting a certain level of pick overlap may be preferred to zero overlap due to two reasons. First, reducing overlap is one infection spread mitigation strategy that must be considered in conjunction with the utilization of appropriate personal protective equipment (PPE) and testing procedures. In the presence of medical tests and PPE usage, mandating zero overlaps may result in unnecessarily conservative solutions with excessive total picking times. Second, a model that requires zero overlaps may not be suitable for less severe diseases. In model P, pick overlap is considered as an objective Algorithm 1 Company's order batching algorithm 7: if k ̸ = k max then 8: Ψ K [k] = −(n + γ |k − k max |) 9: else 10: end if 12: end for 13: while batch capacity allows do 14: for i ∈ N − do 15: s i = 0 16: for k ∈ K do 17: for k ∈ K do 23: if v i best k = 1 and v ′ k = 0 then 24: v ′ k = 1 25: end if 26: end for 27: determine k left and k right 28: for k ∈ {1, 2, ..., k left } do 29 : end for 31: for k ∈ {k left , k left + 1, ..., k right } do 32: if v ′ k = 0 then end for 36: for k ∈ {k right , k right + 1, ..., K } do 37: Ψ K [k] = −(n + γ |k − k right |) 38: end for 39: end while (soft constraint) so that depending on the severity of the disease, the solutions can be adjusted. For example, during a less severe flu season, it may be reasonable to emphasize total picking time compared to overlap. Routing policy can impact the quality of solutions. Specifically, when an infection spread is of concern, one may prefer to use a routing policy that decreases the risk of spread. The model and main results of this study are derived using the Sshape policy as it is the current routing procedure of the study's warehouse. The S-shape policy is hypothesized to have anticongestion properties [8] , and since picker congestion can act as an infection spread facilitator, it may be a suitable procedure for the infection risk mitigation. On the other hand, there is some evidence that the S-shape policy may lead to excessively long travel times, which could be the result of both long travel distances and frequent blocking and congestion [81] . To evaluate the S-shape policy's effectiveness for the problem of this study, a Midpoint policy was implemented. Conducting statistical tests and comparisons between the policies revealed that the S-shape policy does not hold any advantage over the Midpoint policy in Φ 10 50 0 1280 790 0 10 50 10 1280 790 0 10 50 30 1280 790 0 10 100 0 1060 1060 0 10 100 10 1060 1060 0 10 100 30 1060 1060 0 25 50 0 2350 810 0 25 50 10 2350 810 520 25 50 30 2350 810 560 25 100 0 2150 1340 0 25 100 10 2150 1340 10 25 100 30 2150 1340 70 50 50 0 6130 910 0 50 50 10 6130 910 3090 50 terms of overlap. In fact, the Hypervolumes comparison showed that the Midpoint policy offers a slightly better tradeoff between the objectives. Finding the best routing policy that minimizes the infection spread requires a comprehensive routing policy comparison that falls beyond the current study's scope. The details of the Midpoint policy results are tabulated in Appendix B. Note that computational times are not reported in Appendix B as no significant difference was observed between S-shape and Midpoint policies in terms of CPU time. Moreover, since model P is formulated based on the S-shape policy, no exact approach result is reported in Appendix B. In this section, the effectiveness of the proposed seeding procedure is examined. Fig. 7 illustrates the convergence of NSGAII, SPEA2, and NSGAIII in terms of log hypervolume over the first 200 generations. As observed, when seeded, all algorithms significantly outperform their not seeded counterparts. The same effect is observed for different values of Q and ∆. However, the gap between the seeded and not seeded solutions seem to be more prevalent for more constrained instances of the problem (i.e., smaller Q ). This effect may be attributed to the difficulty of finding high-quality feasible solutions in tightly constrained search spaces, and the fact that seeding can bypass this difficulty. Furthermore, the seeding procedure produces highly efficient solutions in terms of total travel time, which have little room for improvement. As a result, the proposed algorithms mostly concentrate on enhancing makespan and overlap. In other words, seeding with a superior solution in terms of one of the objectives, functions as if the objective is relaxed and thus, the algorithm has a more manageable feasible space to search. 10 50 0 1210 490 0 1210 490 0 1210 490 0 10 50 10 1210 490 0 1210 490 0 1210 490 0 10 50 30 1210 490 0 1210 490 0 1210 490 0 10 100 0 1060 490 0 1060 490 0 1060 490 0 10 100 10 1060 490 0 1060 490 0 1060 490 0 10 100 30 1060 490 0 1060 490 0 1060 490 0 25 50 0 2330 810 0 2330 810 0 2330 810 0 25 50 In this section, the managerial implications of the model and considering overlap objective are discussed. As was illustrated earlier, picking capacity Q is a determining factor in the relationship between the total travel time and overlap. To investigate this observation further, the correlation between the three objectives was measured throughout NSGAII's evolution process. Fig. 8 depicts the Pearson correlation ρ between total travel time F , makespan C max , and overlap Φ for the best found solutions at each generation of NSGAII and for various picking capacities. As can be observed, correlations eventually converge for all instances. However, the limit to which the correlations converge is different for each picking capacity. When Q = 50, total travel time and overlap correlation ρ F ,Φ reaches converges to a negative value. In other words, for tight picking capacities, total travel time and overlap act as conflicting objectives. However, as Q increases, the convergent correlation between total travel time and overlap increases. A positive correlation between total travel time and overlap suggests that the two objectives are cooperating, and one can be improved by improving the other one. Another intriguing observation is the correlation between makespan and the other two objectives. As Q increases, makespan's correlation with other objectives points to a more conflicting state. From a managerial standpoint, the aforementioned observations can be interpreted as follows. When a warehouse's objective is to minimize the total travel time, it may benefit from increasing the picking capacity as it allows for reducing the overlap. In other words, for warehouses to minimize total travel time, increasing picking capacity helps with mitigating the risk of infection spread. This dynamic can be explained by considering that an increased picking capacity means fewer batches and fewer walking pickers to interact. Thus, increasing picking capacity contributes to lower overlap by reducing the number of pickers that are required to traverse the warehouse at a time. 1 A second managerial lesson of this study originates from the correlation between makespan and overlap. As observed in Fig. 8 , makespan always correlates with the other objectives negatively. However, this correlation's absolute value is smaller for the lower values of the picking capacity Q . Thus, a lower picking capacity provides a more favorable tradeoff between overlap and makespan. Thus, warehouse environments where the makespan is of significance, such as a wave-picking warehouse, may benefit from reducing the picking capacity to control the overlap and spread of infection. Remember that in this study, each batch is picked by a separate picker. Therefore, lower picking capacity translates into smaller waves, which means reducing the wave size can help mitigate the risk of infection spread in wave picking warehouses. It is noteworthy that reducing the wave size can potentially eliminate the benefits of picking postponement. Consequently, wave picking warehouses may find themselves at Another managerial implication of this study pertains to the tradeoff patterns between the objectives. Fig. 9 depicts the Pareto frontier of the instance with 50 orders (N = 50) and minimum physical distance's walking time of 30 (∆ = 30) while picking capacity Q varies from 50 to 400. 2 As can be observed, the tradeoff between total travel time and makespan remains almost linear for different values of Q . However, the tradeoff between the makespan and overlap gradually shifts towards an exponential decay pattern with diminishing returns. From a managerial perspective, this observation shows that there is a threshold for larger picking capacities, after which reducing makespan requires a much higher level of overlap. Thus, as was previously demonstrated through the correlation analysis of the objectives, makespan-driven warehouses may benefit from a lower picking capacity and a subsequent more favorable tradeoff between makespan and overlap. Being a significant source of expenses in a supply chain, order picking operations are not well-positioned to rise to pandemic challenges such as the ones posed by COVID-19. This inability is mainly due to a cost-driven mindset in the order picking 2 To better visualize the Pareto front, a curve of the form C max = c 1 F + c 2 Φ + operations, which seems reasonable in a normal situation. This study suggests that the risk of pickers contracting Coronavirus or any other infectious disease must be taken into account in the order picking problems. For this purpose, the well-known order batching problem was revisited and reformulated by considering the risk of infection spread due to workers picking orders in close vicinity of each other. A tri-objective model was proposed that aimed to simultaneously minimize the total travel time, makespan, and picking overlap among the pickers. Furthermore, three evolutionary methods, namely, NSGAII, SPEA2, and NSGAIII, were proposed to solve the problem. The model and the proposed methods were tested on the data of a major US-based logistics company and compared against the company's current practices. It was found that while the company performs at an efficient level of total travel time, their method is not well suited when the pickers' overlap is considered. Through an extensive numerical experiment and comparison with the company's method, it was found that reducing the picking overlap, as a proxy of infection spread, and minimizing the total travel time are not necessarily conflicting objectives. However, makespan was observed at odds with the overlap in all experiments. This study has two key takeaways for practitioners and managers. First, it is possible to maintain the order batching solutions' travel time efficiency while minimizing the overlap. In fact, these two objectives seem to correlate positively. However, for such a correlation to be realized, it is necessary to have a sufficient picking capacity. This study showed that a low picking capacity could erode all the overlap cross-benefits obtained as a result of minimizing the total travel time. Second, it was found that minimizing the makespan has an adverse effect on the overlap, and thus, some wave-picking warehouses may find it more challenging to prepare for the pandemic situation. To surmount this hurdle, a wave size reduction was suggested for such warehouses. The main limitation of the presented study pertains to the stochastic nature of pickers' travel times. When batching, one typically assumes a constant picker speed and reliably uniform picking times, which makes the calculation of the objectives feasible. However, a decision-maker needs to consider the impact of a non-uniform walking speed on calculations of overlap and possibly equip the batching method with simple heuristics that regulate how pickers should behave in case of overlaps occurrence. One possible strategy to mitigate the effect of travel time uncertainty on the overlap calculation is to increase the minimum physical distance to overemphasize the importance of overlap when constructing solutions. However, this may lead to sub-optimal solutions in terms of makespan or total travel time. Thus, a robust or stochastic oriented approach to reduce the pick overlap remains an important future research direction. Incorporation of infection risk considerations in order picking problems poses a new set of challenges in the operational level of supply chains. In this context, two future research directions are suggested. First, virtually all order picking problems can be revisited with a pandemic lens of investigation to ensure a safe environment for the pickers. Second, there are tactical problems that are directly affected by the pandemic. For example, warehouses typically prefer to locate products that are ordered together frequently in the proximity of each other. However, this routine may not be entirely desirable as it may cause pickers' routes to overlap further. Thus, it is necessary to rethink the order association among the products to ensure a safer workplace. Coronavirus covid-19 global cases Predicting the impacts of epidemic outbreaks on global supply chains: A simulation-based analysis on the coronavirus outbreak (covid-19/sars-cov-2) case Targeted social distancing designs for pandemic influenza Game theory of social distancing in response to an epidemic Simulation suggests that rapid activation of social distancing can arrest epidemic development due to a novel strain of influenza Milp formulations and an iterated local search algorithm with tabu thresholding for the order batching problem Design and control of warehouse order picking: A literature review Order batching to minimize total travel time in a parallel-aisle warehouse A fast and elitist multiobjective genetic algorithm: Nsga-ii SPEA2: Improving the Strength Pareto Evolutionary Algorithm, TIK-report 103, Eidgenössische Technische Hochschule Zürich (ETH), Institut für Technische An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints A multi-objective model for minimising makespan and total travel time in put wall-based picking systems Coordinated warehouse order picking and production scheduling: A nsga-ii approach Order picking with multiple pickers and due dates-simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems Minimizing order picking makespan with multiple pickers in a wave picking warehouse A hybrid artificial neural network, genetic algorithm and column generation heuristic for minimizing makespan in manual order picking operations A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem Variable neighborhood search strategies for the order batching problem A route-selecting order batching model with the S-shape routes in a parallel-aisle order picking system Order-batching methods for an order-picking warehouse with two cross aisles A study on order-batching methods of order-picking in a distribution centre with two cross-aisles Joint optimisation of order batching and picker routing in the online retailer's warehouse in China Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem A new mathematical programming formulation for the single-picker routing problem Exact algorithms for the order picking problem Optimal order picker routing in the chevron warehouse Routing policies in multi-parallel warehouses: an analysis of computing times An aco-based online routing method for multiple order pickers with congestion consideration in warehouse Using a hybrid approach based on the particle swarm optimization and ant colony optimization to solve a joint order batching and picker routing problem An efficient hybrid algorithm for integrated order batching, sequencing and routing problem An order batching algorithm for wave picking in a parallel-aisle warehouse Routing order pickers in a warehouse with a middle aisle An evaluation of routing policies for order-picking operations in low-level picker-to-part system Order-batching heuristics based on cluster analysis in a low-level picker-to-part warehousing system Aggregation of orders in distribution centers using data mining Joint order batching and order picking in warehouse operations Order batching in walk-and-pick order picking systems Using a multiple-ga method to solve the batch picking problem: considering travel distance and order due time Variable neighborhood search for order batching in a warehouse New batch construction heuristics to optimise the performance of order picking systems Algorithms for on-line order batching in an order picking warehouse Tabu search heuristics for the order batching problem in manual order picking systems Large-scale order batching in parallel-aisle picking systems Joint order batching and picker routing in single and multiple-cross-aisle warehouses using cluster-based tabu search algorithms Order batching in warehouses by minimizing total tardiness: a hybrid approach of weighted association rule mining and genetic algorithms Metaheuristics for order batching and sequencing in manual order picking systems Order picking under random and turnover-based storage policies in fishbone aisle warehouses A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse Order batching and sequencing for the minimization of the total tardiness in picker-to-part warehouses An exact solution approach for the order batching problem Order batching in a pick-and-pass warehousing system with group genetic algorithm Optimizing the order picking of a scholar and office supplies warehouse Joint order batching and picker manhattan routing problem Order picking in a parallel-aisle warehouse with turn penalties Mathematical model, heuristics and exact method for order picking in narrow aisles A tabu search approach to solving the picking routing problem for large-and medium-size distribution centres considering the availability of inventory and k heterogeneous material handling equipment General variable neighborhood search for the order batching and sequencing problem Parallel variable neighborhood search for the min-max order batching problem Order picker routing with product returns and interaction delays Optimally solving the joint order batching and picker routing problem Bacterial memetic algorithms for order picking routing problem with loading constraints Robotics in order picking: evaluating warehouse layouts for pick, place, and transport vehicle routing systems Integrated order picking and vehicle routing with due dates On-line scheduling of order picking and delivery with multiple zones and limited vehicle capacity Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse Order batching operations: an overview of classification, solution techniques, and future research A review of research trends in order batching, sequencing and picker routing problems Using list-based simulated annealing and genetic algorithm for order batching and picker routing in put wall based picking systems Two-stage storage assignment to minimize travel time and congestion for warehouse order picking operations Human energy expenditure in order picking storage assignment: A bi-objective method Implementation of an ant colony approach to solve multi-objective order picking problem in beverage warehousing with drive-in rack system Order picking along a crane-supplied pick face: The sku switching problem A pseudo-polynomial time algorithm for a special multiobjective order picking problem Order batching operations: an overview of classification, solution techniques, and future research Order picker routing in warehouses: A systematic literature review Applying genetic algorithm to a new bi-objective stochastic model for transportation, location, and allocation of hazardous materials Applying genetic algorithm to a new location and routing model of hazardous materials Bi-objective group scheduling in hybrid flexible flowshop: a multi-phase approach Performance assessment of multiobjective optimizers: An analysis and review An investigation of the effects of storage assignment and picker routing on the occurrence of picker blocking in manual picker-to-parts warehouses The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. No overlap model P ′ , is formulated as follows:min (1) and (2) subject to constraints (4) to (24) , (28) to (32) , (34) and (35) Additionally, constraints (A.1) to (A.3) ensure no picking overlap among locations that are positioned closer than the minimum physical distance (see Table A .7). See Tables B.8-B.11.