MASARYK U N I V E R S I T Y FACULTY OF INFORMATICS Optimization of multi-floor warehouse throughput Master's Thesis SAMUEL KŘIVÁNEK Brno, Fall 2024 MASARYK U N I V E R S I T Y FACULTY OF INFORMATICS Optimization of multi-floor warehouse throughput Master's Thesis SAMUEL KŘIVÁNEK Advisor: doc. Mgr. Hana Rudova, Ph.D. Department of Machine Le arning and Data Proce ssing Brno, Fall 2024 Declaration Hereby I declare that this paper is my original authorial work, which I have worked out on my own. A l l sources, references, and literature used or excerpted during elaboration of this work are properly cited and listed in complete reference to the due source. Samuel Křivánek Advisor: doc. Mgr. Hana Rudová, Ph.D. iii Acknowledgements First and foremost, I would like to express my sincere gratitude to my supervisor, doc. Hana Rudová, Ph.D., and my consultant, Mgr. Václav Sobotka, for their valuable knowledge, advice, guidance, and outstanding feedback, which were priceless to me during the creation of this thesis. In addition, we want to thank the company Notino for their cooperation, which included providing the production data and participating in countless meetings that helped us better understand their processes. Special thanks go to Mgr. M artin Kavřík and his colleagues, who facilitated the entire cooperation and assisted us in many aspects. I would also like to extend my thanks to my family and friends, especially Be. Ema Králová, Mgr. Romana Kanásová, and Be. Daniel Vojnar, for their constant encouragement and support. They made my university studies much more enjoyable and helped me stay sane throughout the entire process. Computational resources were provided by the e­INFRA CZ project (ID:90254), supported by the Ministry of Education, Youth and Sports of the Czech Republic. iv Abstract This thesis addresses the multi-floor order-picking problem. O n a daily basis, warehouses handle tens of thousands of orders, each consisting of multiple products. Efficient batching of these orders for collective fulfillment is crucial for competitive advantage and resource minimization. This thesis tackles the planning problem of the realworld warehouse by designing, implementing, and comparing several strategies with the aim of minimizing the tardiness of orders and maximizing warehouse throughput. The problem involves batching customer orders on the warehouse level for collective fulfillment and selecting floors where these batches will be collected. The thesis reviews relevant literature, design and describes implemented strategies, and compares their performance using simulation analysis on production data. The production data, as well as inspiration for the problem, comes from the Notino company. Keywords Warehouse planning, batching, order picking, multi-floor picking, progressive bypass zone picking system, optimization, clustering v Contents 1 Introduction 1 2 Problem description 3 2.1 Operating warehouse 3 2.1.1 Warehouse operations 4 2.2 Order picking 6 2.2.1 Order picking methods 6 2.2.2 Objectives 8 2.3 Our problem 10 3 Existing methodologies 14 3.1 Order batching into pick boxes 14 3.1.1 Exact algorithms 15 3.1.2 Heuristic algorithms 16 3.1.3 Metaheuristic algorithms 19 3.2 Floor selection 20 4 Implemented strategies 22 4.1 Floor selection 22 4.1.1 Random floor selection 22 4.1.2 Greedy floor selection 23 4.1.3 M H S floor selection 23 4.2 Order batching 27 4.2.1 E D D order batching 29 4.2.2 Savings order batching 29 4.2.3 Seed order batching 33 4.2.4 MSF order batching 37 5 Simulator 43 5.1 Components 43 5.2 Computation 44 5.3 Simplifications 49 6 Experimental evaluation 50 6.1 Datasets 50 6.2 Shared parameter setting 54 vi 6.3 Experiments 55 6.3.1 Selecting strategies 57 6.3.2 Selecting strategies' execution order 57 6.3.3 Fine-tuning seed-based batching strategies . . . 63 6.3.4 Fine-tuning batching strategies 65 6.3.5 Final results 67 6.4 Summary 72 7 Conclusion 73 Bibliography 74 A Archive 80 B Notation 81 C Simple procedures 83 C . l Floor selection 83 C . l . l Random floor selection 83 C.l.2 Greedy floor selection 83 C.1.3 M H S floor selection 87 C.2 Order batching 90 C.2.1 E D D order batching 90 C.2.2 Savings order batching 92 C.2.3 Seed order batching 94 C.2.4 MSF order batching 95 C.3 MHSSIZE procedure 95 D Simulator parameters 101 E Detailed tabular results 104 F Additional comparisons 110 vii 1 Introduction Warehouses play a crucial role in supply chains, where they have multiple functions. They mainly buffer material flow to accommodate variability from factors such as product seasonality and consolidate products from various suppliers for joint delivery to customers [1]. With the rise of e-commerce and the increasing significance of warehouses in the customer buying journey, efficiently coordinated warehouse operations have become an essential source of competitive advantage for supply chain companies [2]. The primary warehouse operations are receiving, storage, order picking, and shipping. Order picking is commonly known as the most costly operation in a warehouse, primarily due to its labor-intensive nature or the significant capital requirement [1]. Order picking can account for over 55% of total expenses [3]. The primary objective of this thesis is the design, implementation, and comparison of several strategies for addressing the planning problem in the multi-floor order-picking warehouse with the aim of minimizing the tardiness of orders and maximizing warehouse throughput. The problem involves batching orders into pick boxes, which are containers holding closely related groups of orders through the whole picking process, and selecting floors on which these pick boxes will be further processed. The multi-floor warehouses are less studied problem in the literature [1], and those two sub-problems appears in the literature, often with notable simplifications and deviations. Nevertheless, we have explored the literature on order-picking processes and have taken inspiration from related strategies, which we have adapted to our needs. The problems addressed in this thesis arise from the interests of Notino, a company that cooperated with us and provided production data from 6 months of processing in their Czech warehouse. Notino is an online retailer specializing in a wide range of cosmetics and fragrance products. Founded in 2004, the company has expanded to multiple European countries. In 2022, Notino employed around 2,500 people and served approximately 20 million customers. That year, their annual turnover was 1,035 million EUR, an increase of 32% over the previous year. 1 i . INTRODUCTION The thesis is organized as follows. Chapter 2 introduces the terminology and processes involved in warehouse operations. It then focuses on the problem and methods of order picking and concludes with a detailed description of the main problem addressed in this thesis. Chapter 3 explores existing methodologies and approaches used in the literature to tackle order-picking problems. Chapter 4 provides a detailed description of the implemented strategies. Chapter 5 briefly describes the simulator developed as part of the thesis to evaluate the implemented strategies. Finally, Chapter 6 examines datasets used and compares the implemented strategies through simulation analysis. 2 2 Problem description This chapter introduces the terminology used throughout the thesis. It then examines various tasks that constitute order-picking methods, as well as objective functions relevant to order-picking. Finally, Section 2.3 provides a detailed description of the main problem addressed in this thesis. Unless specified otherwise, this chapter is inspired by the article [2]. 2.1 Operating warehouse Warehouses play a crucial role in supply chains, serving multiple functions. They buffer material flow to accommodate variability from factors such as product seasonality, as well as production and transportation batching. Additionally, warehouses consolidate products from various suppliers for joint delivery to customers and perform value-added tasks such as kitting, pricing, labeling, and product customization [2]. Every day, warehouses receive orders from customers containing a list of products that require retrieval from their current location, transportation to a common area, packaging, and shipment to the customer. The operational management of the warehouse is responsible for multiple decisions in this process. Firstly, it must determine the order in which these products are collected and the most relevant product positions. Secondly, it needs to assign a picker responsible for collecting the products, specifying both the route the picker must follow and the exact starting time for the picking process. Decisions and transactions between different entities involved in the process are typically classified into strategic, tactical, and operational [1]. With the rise of e-commerce and the increasing significance of warehouses in the customer buying journey, efficiently coordinated warehouse operations have become an essential source of competitive advantage for supply chain companies. Consequently, inefficiencies in these operations can negatively impact customer satisfaction and diminish overall profitability. Therefore, warehouse operations management must prioritize the optimization of processes [4]. 3 2. PROBLEM DESCRIPTION 2.1.1 Warehouse operations Warehouse operations are a set of warehouse activities and processes that ensure the goods are handled efficiently and accurately within the warehouse [4]. The basic warehouse operations are receiving, storage, order picking, and shipping. The warehouse interface for incoming and outgoing material flow is encapsulated in receiving and shipping. Incoming shipments are transported to the warehouse, unloaded at the receiving dock, and individual Stock Keeping Units are stored. Stock Keeping Unit or S K U refers to a uniquely identified item of stock that is completely specific to function, style, size, and color [5]. In this thesis, the term products refers to all items, encompassing different SKUs as well as multiple items of the same SKU. Meanwhile, the warehouse receives orders from customers, retrieves SKUs from storage, assembles orders, and dispatches them to customers through shipping docks. These operations include tasks such as assigning trucks to specific docks and scheduling both loading and unloading activities. Storage is focused on arranging SKUs to maximize space utilization and streamline material handling. SKUs can be organized into various departments based on a range of factors. These factors include the physical characteristics of SKUs, like whether they are suited for pallet storage or case storage. Pallet storage refers to a storage method where SKUs are placed on pallets. Pallets are flat transport structures that support SKUs in a stable fashion while being lifted by forklifts, pallet jacks, or other lifting devices. They enable easy access to larger amounts of SKUs and efficient use of space. Case storage involves storing SKUs in cases, boxes, or cartons. This method is typically used for smaller SKUs that are either too small to be stored individually on a pallet or when SKUs need to be grouped in specific quantities or assortments. Case storage systems might involve shelving units, drawers, or bins, allowing for easy organization and retrieval of the SKUs . It is a common approach in retail settings or in parts of a warehouse where SKUs are picked at a case level rather than a full pallet. Other factors influencing the organization of SKUs include management decisions, such as a dedicated storage area for a specific 4 2. PROBLEM DESCRIPTION customer, or material handling considerations, such as a forward area forfast picking. The assignment of SKUs to particular storage locations plays a critical role within each department or zone. This placement not only affects the warehouse's storage capacity but also significantly impacts tracking inventory and facilitating the order picking process. Storage assignment policies are concerned with the assignment of SKUs to specific storage locations in a warehouse. Three common storage allocation strategies are discussed in the literature [6]. Firstly, random storage assignment, where SKUs are placed in any available location. Secondly, dedicated storage assignment involves assigning SKUs to specific shelf locations based on characteristics like size, weight, or usage rate. Lastly, class-based storage is a method where the warehouse is segmented into zones according to SKU characteristics. Within these zones, the storage space allocation for SKUs is done randomly. The dedicated storage assignment strategy can also be compared to the shared storage assignment strategy. With dedicated storage, each SKU is assigned to a fixed storage position. This allows for highdemand SKUs to be placed in more accessible locations, enhancing efficiency. However, this approach can lead to underutilized storage space since each designated storage position must be able to accommodate the peak inventory level for its SKU, regardless of current stock levels. On the other hand, a shared storage strategy assigns incoming SKUs to any available suitable space, optimizing the use of storage capacity. While this method improves space utilization, it introduces complexity by dispersing a single S K U across multiple storage positions, increasing the effort required for inventory management and potentially complicating retrieval processes. A variation of the shared storage approach is the scattered storage strategy, also known as mixed shelves. This method involves breaking down unit loads and the single units are spread throughout the warehouse. While this can further enhance space utilization, it similarly results in multiple locations per SKU, adding to the operational complexity and potential for organizational challenges [7]. Storage space can be physically segmented into distinct zones, each with its own dedicated storage area and operational resources [8]. The zoning problem involves dividing the whole picking area into several smaller zones and assigning pickers to pick requested SKUs within the zone [9]. Conveyors usually interconnect these zones. The literature 5 2. PROBLEM DESCRIPTION generally presents two methods for retrieving lists of SKUs to fulfill one or more orders. The first method is a parallel picking system, where a list of SKUs is simultaneously picked from various zones and then directed to a sortation system, where the items are assembled into orders and prepared for shipping [8]. The second method, referred to as progressive zoning, also known as the pick-and-pass or sequential system, involves picking a batch of SKUs in one zone at a time before passing it to the next zone, where picking can continue [9]. Warehouses can have various layouts, including both conventional and non-conventional. The conventional layout is rectangular, characterized by parallel aisles arranged orthogonally to the walls. In contrast, unconventional layouts include the fishbone, U-shaped, and flying-V designs. The fishbone layout incorporates two diagonal cross-aisles, with the lower zone aisles running perpendicular to those in the upper zones. The U-shaped layout is characterized by a central aisle shaped like an inverted U , connected to the depot by a front cross-aisle. The flying-V layout features a central aisle that splits from the depot into a V shape, extending towards the furthest pick aisles on either side [3]. Order picking, the process of retrieving SKUs from storage locations to fulfill customer orders, is a major cost factor in warehouse operations, accounting for over 55% of total expenses [3]. Order picking is commonly known as the most costly operation in a warehouse, primarily due to its labor-intensive nature or the significant capital requirement [2]. This cost factor is particularly evident in manual pickerto-parts systems. In these systems, workers physically walk through the warehouse aisles, locate and pick the required SKUs, and then transport them to a central depot for consolidation [3]. 2.2 Order picking 2.2.1 Order picking methods Managing the order-picking process involves organizing both the orders to be picked and the associated material-handling tasks. The choice of order-picking method is a strategic decision, significantly influencing numerous aspects of warehouse design and operation. Methods such as batching with sort-after-pick, or concurrent zone picking without batching in the zones are examples of the different approaches 6 2. PROBLEM DESCRIPTION used in the order picking, which components will be explained in the next part. Various methods exist, each incorporating a combination of basic tasks, which may include batching, waiting, as well as selecting or sequencing. Additional tasks are assigning, routing, and sorting [1]. Each mentioned task in the order-picking process is briefly explained in the following paragraphs. The batching task involves grouping multiple orders into a single batch before initiating the picking process. This means that items belonging to orders in the same batch must be retrieved together, for example, on the same picking route. Each batch is limited by a maximum capacity, which may be defined in weight, volume, number of items, or number of orders[l]. From another perspective, batching is part of the operational decision in order picking. This operational decision involves choosing between collecting orders individually, known as strict or single-order picking, or grouping them before picking, referred to as order batching. Strict order picking is a straightforward approach where each order is assigned to a picker, who collects all the SKUs in that order. After all SKUs are gathered and placed in a depot, the system assigns a new order to the picker. It is usually considered a naive strategy. In contrast, order batching is a more sophisticated strategy. This approach involves grouping several orders into a single batch that does not exceed a predefined capacity. Once the batch is formed, it is assigned to a picker who retrieves all SKUs of the batch on a single route. The order batching policy has proven to be much more effective than the strict order picking policy, with the potential to reduce travel time by up to 35% when routes are designed with batching in mind. However, it is important to note that order batching is particularly beneficial in Business-to-Customer scenarios, also known as B2C, where it is common to pick several small SKUs together. In contrast, Businessto-Business or B2B contexts typically involve picking entire pallets. In B2B situations, strict order picking is sometimes necessary due to the nature of the orders. Beyond these methods, other strategies like zone picking and wave picking are also used. Zone picking assigns a picker to a specific area of the warehouse, responsible for picking SKUs only within that zone. Wave picking, on the other hand, involves synchronizing multiple picking routes of different pickers. 7 2. PROBLEM DESCRIPTION The remaining tasks related to this topic were comprehensively explained in the article [1]. The subsequent paragraphs in this section draw inspiration from the insights presented in that article. The waiting task involves calculating the duration an available picker should wait before beginning a new route. The underlying idea here is that allowing the picker to wait longer increases the number of available orders in the system. This, in turn, should help to construct more compact batches. The task of selecting and sequencing is concerned with deciding the order in which available batches are collected. When the process focuses on choosing just one batch as the next to be collected, it is generally referred to as selecting. However, when all available batches are prioritized and sorted, this task is typically known as sequencing. The assigning task is about deciding which available picker will be assigned to collect the next batch. This task is relevant in scenarios where there are multiple pickers. It plays a crucial role in ensuring a balanced workload distribution among the pickers. The routing task consists of determining the sequence of steps a picker must follow within the warehouse to gather all SKUs for the orders in their assigned batch. This route typically begins and ends at a designated point known as the depot, where SKUs are deposited once collected. The sorting task involves establishing the strategy to organize SKUs picked into their respective orders. In a batching strategy, where a picker collects SKUs from different orders along the same route, sorting is essential. These SKUs must be classified into individual orders either during or after the picking process. If sorting occurs during picking, often called sort-while-pick, it is usually achieved by the picking cart equipped with separate bins for each order. Alternatively, in sortafter-pick, sorting is done using a separate downstream system after the picking is complete. This latter method raises several operational questions regarding the functioning of the sorting system. 2.2.2 Objectives Objective functions typically focus on either maximizing or minimizing a specific dimension. Some objectives are closely related to each other. At times, minimizing one objective can also lead to the minimiza- 8 2. PROBLEM DESCRIPTION tion of another objective. In the context of this thesis, it is particularly evident in the relationship between distance and time when the travel velocity is constant [1]. The most common dimensions measured by objective functions in the context of order batching, as mentioned in the article [1], are listed below. • Distance is measured in units of length that operators need to traverse to collect all SKUs in processed orders. • Picking time refers to units of time required to perform the picking task when collecting SKUs in orders processed by the warehouse. • Cost dimension measures an economic indicator related to the picking operation in the warehouse. Cost is expressed in a unit of value. • Throughput refers to the number of orders completed per time interval. • Tardiness is quantified in units of time corresponding to the delay in handling an order relative to a predefined due time. This category also includes earliness, which indicates fulfilling an order ahead of its due time. • Completion time is measured in units of time needed to collect all orders that have arrived at the warehouse. It includes both the picking time and the waiting time for the arrival of new orders. • Turnover time refers to units of time that an order remains in the system. It is calculated as the difference between the instant when the order is shipped and the instant when it arrives. • Workload balance dimension indicates the differences in the amount of work performed by different operators, also known as pickers. Work balance is usually measured in time. However, other dimensions like distance traversed, number of orders, or batches retrieved can also be used. In the article [10], workload balance is calculated as the difference between the maximum picking time required by any picker 9 2. PROBLEM DESCRIPTION to complete their assigned tasks and the average picking time across all pickers. • Blocking time refers to units of time a picker waits before completing a task, often due to blockage by another picker or machine. This is also known in the literature as congestion. Customer orders are bound by specific due times to ensure timely shipment. Many studies such as [11,12] focus on reducing the total tardiness across all customer orders. In this thesis, total tardiness serves as a key objective function for evaluating the effectiveness of implemented strategies in minimizing delays. Total tardiness t is calculated as the sum of individual tardiness values T; for each order. The value of Ty is calculated as the difference between the completion time of a batch Cy and its due time dj, with the condition that T, defaults to zero if this difference is not positive. In practice, solutions in which one or more customer orders will be picked after the picking due time are typically unacceptable for most warehouses. This is because such delays can lead to a decrease in the level of customer service. Instead of tolerating tardiness, warehouses often increase resource capacity to avoid delayed picking. This increase could involve reallocating workers from other departments. Additionally, tardiness can arise from unexpected factors like technical malfunctions or inventory shortages [13]. 2.3 Our problem This thesis considers a simplified version of a multi-floor warehouse set in the Business-to-Customer context. The warehouse adopts a conventional, rectangular layout. The specific implementation of this layout may vary across different floors. In the warehouse considered in this thesis, a scattered storage strategy is employed, utilizing low-level storage racks that negate the need for T = L T J (2.1) (2.2) 10 2. PROBLEM DESCRIPTION vertical movement. Additionally, the warehouse uses a case storage system, as is expected in B2C contexts. The operational strategy involves a manual picker-to-parts system where workers walk through aisles to fulfill orders. On a daily basis, such a warehouse could handle tens of thousands of orders, each comprising multiple SKUs. These orders are bound by due time constraints dictated by shipping due times. The order fulfillment process involves several batching levels. Initially, orders are batched into pick boxes, which are containers holding closely related groups of orders collected together. These orders are collected together throughout the entire passage of the warehouse, considering the volume constraint of the pick box. Subsequently, pick boxes are then grouped into picking carts. A picking cart is a group of pick boxes collected together while traversing a single floor, and it is constrained by the number of pick boxes that can fit in it. The picking system schema is shown in Figure 2.1. The warehouse adopts a progressive bypass zone picking approach with batching. Each zone corresponds to a single floor and houses multiple pickers responsible for simultaneously picking all SKUs within their assigned picking cart. A conveyor belt sequentially passes through each warehouse floor to facilitate the movement of pick boxes across floors. Pick boxes must visit floors containing at least one reserved SKU destined for the corresponding pick box, allowing them to bypass floors without reserved SKUs. Notably, orders within a pick box are picked together and remain unsorted during the picking process, a strategy referred to as sort-after-pick. Efficiency is crucial in minimizing delays, as each stop of a pick box on a floor significantly impacts the order transit time through the warehouse. Thus, efforts are directed toward collecting SKUs for a pick box from as few floors as possible. The main problem of this thesis is to compare several strategies for batching orders into pick boxes and selecting picking locations to fulfill orders. Selecting picking locations is necessary because each SKU can be found in multiple locations within the warehouse. In the context of this thesis, we are particularly interested in a set of floors and the corresponding quantities from each floor selected to meet the demand for each SKU. Therefore, we will refer to this problem as the floor selection problem. This level of detail is our focus because we delegate 11 2. PROBLEM DESCRIPTION Floor 1 Floor n Floor selection & Batching into pick boxes Customer orders - - ) J L . . . ) . . . . Floor i Figure 2.1: Order picking system 12 2. PROBLEM DESCRIPTION the responsibility of choosing the exact picking location on a given floor to the process of batching pick boxes into picking carts and planning picking routes. We anticipate that this approach will enhance the efficiency of routing by leveraging the selection. The primary objectives are to minimize total tardiness and maximize warehouse throughput, with a concurrent consideration of minimizing the number of pickers and balancing pick efforts across floors, all of which contribute to achieving the overarching goal. Customer orders are bound by specific due times to ensure timely shipment. Respecting due time constraints while planning picking operations is a critical issue for warehouses since accuracy in delivery times is an essential performance indicator. 13 3 Existing methodologies This chapter explores existing methodologies and approaches used in the literature to tackle the problem of order batching into pick boxes and the floor selection problem. These problems can be solved jointly or separately. Although the literature explores joint approaches to problems like batching, routing, and sequencing, it fails to provide a foundational basis or even a hint of inspiration for a joint solution to our specific problems. Consequently, we have chosen to solve these problems separately, as this approach allows us to draw upon existing methodologies. When addressed separately, it is logical to tackle these problems sequentially, using the solution of one problem to inform the decisionmaking process for the next. However, there is no predetermined sequence for this approach. Batching before floor selection allows us to work with multiple possibilities of S K U locations during the decision process, albeit at the cost of increased complexity. O n the other hand, floor selection first decreases the size of both problems but also imposes more restrictions. 3.1 Order batching into pick boxes The problem referred to in this thesis as the order batching into pick boxes, which are tightly grouped for an entire pass through the warehouse, is sporadically mentioned in the literature and always with notable simplifications and deviations. Instead of multi-floor warehouses, we generalize to multizone warehouses. Several studies that consider multiple zones primarily focus on the layout design of these zones and the assignment of SKUs across multiple zones [8]. The article [9] considers a progressive zone picking system similar to ours but aims to analyze the impact of order batching and picking area zoning. It employs a naive strategy to create batches, which will be discussed later in the text under the First-Come First-Served algorithm. The study [14] also considers a progressive zone picking system and proposes an order batching approach based on a group genetic metaheuristic. However, the zones in this study are each assigned a 14 3. EXISTING METHODOLOGIES single picker, SKUs are allocated to a single location in the warehouse, and the focus is on minimizing the number of batches and balancing the workload. In further exploration of related research, the study [15] highlights a significant gap in the literature: "The zoning (i.e., zone location, zone assignment, and zone picking) and workforce (i.e., workforce level, workforce allocation, and job assignment) related planning problems, as well as the problem of order consolidation and sorting have received little research attention in combination with other planning problems." While the specific problem of order batching into pick boxes as it is defined is not directly addressed, there are instances where the concept of order batching is explored in different contexts. Specifically, the order batching problem is often intertwined with routing, focusing on minimizing distance or picking time as the primary objective. Our problem of batching diverges from it, as we have entirely different objectives, and we do not consider routes. Each extra floor visited by the pick box introduces additional delays beyond the routing concerns. Nevertheless, some algorithms are versatile enough to be applicable or at least provide a conceptual foundation, allowing us to derive inspiration from the methodologies employed in more specific techniques. Algorithms addressing these problems can be categorized as exact, heuristic, or metaheuristic. For the batching task, heuristic algorithms are predominantly used, with only a handful of instances where exact algorithms have been applied to resolve the batching problem. 3.1.1 Exact algorithms The article [16] has shown that the order batching problem is NP-hard. In the article, the authors also show that order batching is solvable in polynomial time if no batch contains more than two orders. Several studies, including [17,18,19] have formulated their batching problem as Mixed-Integer Linear Program. They have employed optimization software such as CPLEX [20] or Gurobi [21] to find solutions to these problems. Due to the proven complexity, off-the-shelf solvers will fail to solve instances of real-world size. However, we are interested in finding good solutions in an acceptable amount of time. 15 3. EXISTING METHODOLOGIES 3.1.2 Heuristic algorithms The most basic and widely recognized heuristic algorithm applied is the First Come First Serve or FCFS. In the context of zone picking, its application has been documented in several studies, including [9,14, 22], and it was also used for batching in studies not considering zones, including [23, 24, 25, 26]. The FCFS batching heuristic is straightforward, and due to its simplicity, it can be described as naive batching. We expect that the original list of orders is implicitly ordered by the creation time of orders. The FCFS heuristic involves grouping initial n orders from the input list to form the batch so that the batch size is as close to the desired size as possible. Subsequently, the next m orders are grouped in a similar fashion, also aiming to match the target batch size. This process is repeated until all the orders are batched [23]. A slightly more sophisticated heuristic algorithm used is the Earliest Due Date or EDD. The algorithm has been used by several authors, including studies [27, 28, 29], for constructing an initial solution to the problem, later improved with a metaheuristic. The E D D algorithm begins by arranging the orders in ascending order based on their due times. Following this ordered sequence, orders are sequentially allocated to batches while ensuring the batch capacity limit is not exceeded. This process involves filling a batch until the next order does not fit into the batch. At this point, a new batch is created, the order that could not fit in the previous batch is added to the new batch, and the process continues in this manner [27]. There are two major non-naive types of batching heuristics used, namely the Seed algorithm and the Savings heuristic. At the heart of these algorithms is a metric known as the order-to-route closeness, which is crucial for defining the rule for adding orders in seed algorithms and for combining orders in savings algorithms. This metric can range from fine-grained, such as savings in travel when two orders are combined, to more coarse-grained, like the number of additional aisles required when two orders are combined. Alternative metrics might include combined number of locations of two orders, number of common locations between two orders, or other metrics that are tailored to specific warehouse characteristics [2]. 16 3. EXISTING METHODOLOGIES The Seed algorithm [26] begins by selecting an initial order for the batch, referred to as a seed order. The seed order is chosen based on the requirement to visit the smallest number of subaisles. Following the selection of the seed order, additional orders are incorporated according to their proximity to the existing route, determined by the chosen metric. This process continues until the addition of further orders is restricted by the capacity limitations of the batch. Following this, a new seed order is selected, and batching repeats in the same manner. The Seed algorithm has been used in several studies, including studies like [26, 30] that have demonstrated its effectiveness when integrating multiple decisions. On the other hand, studies like [31,32] have provided valuable insights into the performance of various order batching algorithms. Additionally, an article [33] introduced batch construction heuristics called K-means Batching or KMB. Although it claims to draw inspiration from the K-means clustering algorithm, it essentially mirrors the Seed algorithm in function. Savings algorithms draw inspiration from the Clarke and Wright algorithm [2], initially developed for solving the vehicle routing problem [26]. The process begins by assigning each order to a separate batch. The algorithm subsequently iteratively merges pairs of batches, focusing on those combinations that offer the most significant savings, considering metric. In other words, it prioritizes merging batches whose corresponding routes result in the route with least increase in the objective function. This merging continues until it is restricted by capacity limitations of a batch. The heuristic has been used by several authors, including [24, 25,17]. The algorithm Self-Organisation Map Batching, also known as SOMB, was introduced in the article [33]. The simulation experiment in the article focuses on only 300 orders selected from a pool of 10,000 orders generated randomly. The study encompasses 400 SKUs, with 80 SKUs comprising 80% of the order picking operations. The SOMB algorithm operates by grouping orders with higher similarity into one batch based on the clustering function of the Self-Organising Map neural network. The fundamental principle of the Self-Organising Map or SOM is to replicate the organizational patterns found in brain structures, where cells with similar functions naturally cluster together. It maps a collection of unlabeled data onto a lower-dimensional space. 17 3. EXISTING METHODOLOGIES This mapping by the artificial neurons creates what is known as a topological mapping framework or a topological network, where the coordinates are interconnected and hold relative relations. Crucial input features in the article are the number of aisles covered for a batch, the number of SKUs in an order, and the number of the same aisles covered between two orders. The SOMB algorithm initiates by representing each order into a three-dimensional grid of features, subsequently flattening it into a two-dimensional space. In the context of the SOM, the input layer consists of orders, which serve as the input variables. These orders, represented as artificial neurons, are interconnected through the S O M framework. The connections between neurons are determined by weights, representing the similarities between orders. The batching process starts by creating an initial empty batch. The process selects the order with the highest number of SKUs as the superior artificial neuron. The selected order is then added to the batch, batch volume is updated, and the order is removed from the pool of remaining orders. The temporary set of orders is created from remaining orders based on their SKU volumes, ensuring each order can individually fit within the batch's available capacity. Orders closest to the superior neuron are chosen from the temporary set using a total travel distance as a distance metric, continuously updating the batch until it reaches capacity. This process repeats, accommodating orders into new batches until all orders are batched. Another approach used in [33, 34] is Association-based clustering approach which combines Association Rule Mining or ARM with 0-1 integer programming. The study [34] utilizes six examples in experiments, with order quantities ranging from 40 to 300 orders, representing a small problem again. The A R M algorithm uses the order database to find relationships between orders, utilizing support and confidence metrics to quantify these associations. These metrics reveal customer demand patterns by analyzing SKUs within each order, identifying SKUs that are commonly purchased together. Orders that exhibit similar purchasing patterns are then strategically grouped into batches. The approach utilizes 0-1 integer programming to cluster orders, enhancing customer demand relationships and ensuring that strongly associated orders are batched together. 18 3. EXISTING METHODOLOGIES 3.1.3 Metaheuristic algorithms Many recent studies have used various metaheuristic algorithms to solve the order batching problem. For instance, Tabu Search has been utilized in studies such as [19,17, 35], while the Genetic Algorithm has been featured in [36,17,37]. Additionally, Hybrid Algorithms have been explored in [38,39,40]. To get an idea of the sizes of problems addressed in these studies, it is worth noting that only the article [17] utilizes real-world data. This study examines data from two different sectors. The largest instance from the French hospital warehouse dataset includes 63 orders, 130 order lines, and a batch limit of 6 orders. Each order line corresponds to the required quantity of a specific product for an order. Similarly, the largest instance from a Swiss manufacturing company contains 145 orders, 364 order lines, and a batch limit of 8 orders. In both cases, the instances correspond to a single day's operations. Other studies, such as [35, 38, 39], analyze artificially generated data. The largest instance examined in each of these studies comprises 100 orders, with the number of products per order sampled from a uniform distribution ranging from 5 to 25, and a batch limit of 75 products. The article [40] addresses a similar problem, with the only difference being that the number of products per order is sampled from a uniform distribution ranging from 2 to 10. Additionally, the article [38] explores instances that it describes as large-scale, with the largest including 600 orders. In this case, the number of products per order is sampled from a uniform distribution between 1 and 5, with a batch limit of 6 products. The article [19] considers instances with up to 300 orders, where the number of products per order follows a negative binomial distribution with a mean of 1.4, and the batch limit is 10 orders. Conversely, the smallest problem addressed in the reviewed studies is presented in [36]. In this work, the largest instance comprises 40 orders, with order sizes sampled from a uniform distribution between 5 and 25 units, and the number of products per order sampled from a uniform distribution between 5 and 15. The batch limit in this study is set to 50 units. 19 3. EXISTING METHODOLOGIES The problems addressed in these studies are significantly smaller than ours, where we need to handle tens of thousands of orders per day, corresponding to thousands of orders per hour. Current metaheuristic approaches apply complex algorithms that only lead to solutions for small problems. In our implemented methodologies, we have avoided using metaheuristics and instead explored heuristic methods that can provide sufficiently good solutions more quickly and with less computational complexity. It could be worthwhile to consider simpler variations of methods based on the application of local search moves in hill climbing style. This could be an interesting direction for future work. 3.2 Floor selection Thefloor selection problem, as defined in the previous chapter, is unique and not directly addressed in the literature. While the order batching problem is often intertwined with routing, focusing primarily on minimizing distance as the primary objective, the floor selection problem presents a higher-level view of choosing a specific location. However, each additional floor introduces delays beyond routing concerns. Reviewed studies considering progressive zone picking also do not address this problem directly. For instance, the study [9] employs FCFS heuristic for batching, and its approximation model does not explicitly determine which zones to visit. Conversely, the study [14] considers only a single location for each SKU, and zones are therefore implicitly determined for picking based on batch content. While mixed shelves warehouses allow for multiple picking locations for SKUs, the focus of existing studies [7, 41, 42] is primarily on routing and minimizing route lengths, which does not align with our problem. When we relax the floor selection problem by allowing each S K U demand to be entirely satisfied on a single floor without dividing fulfillment of S K U demand across multiple floors, it aligns with the well-known Minimal Hitting Set problem, also called MHS. The Minimal Hitting Set is a classical problem in combinatorial optimization. Given ground set S 4— { 1 , n } of elements and a set S <— { S i , S m } of subsets of the set S, the objective is to identify the smallest set SF C S that intersects every subset in the set S [43]. 20 3. EXISTING METHODOLOGIES procedure MINIMUMHITTINGSETGREEDYHEURISTIC(S, C) input S ground set of elements S set of subsets of S output SF set of elements 1: 2: 3: 4: 6: 7: SN «- S (not hit sets) SF ^ 0 while which is a set of 24 4. IMPLEMENTED STRATEGIES all single-floor options for the tuple (s,q), indexed by the S K U s. The procedure is detailed in Figure C.5. Example (Figure 4.1 (continuation)). In thefirst iterationfor the item (a, 3), let sets on lines 5 and 6 be assigned, such that F = { 2 , 4 } , P = {(a, 2 , 1 ) , (a,4, 2)},andZs = {{2},{3}}. On line 7, all single-floor options Z.s and the multi-floor option F are added to an aggregating set A. Lines 7 and 8 update the variables As and P by adding corresponding elements. Example (Figure 4.1 (continuation)). In thefirst iteration for the item (a, 3), on lines 7-9, sets are assigned such that A = { { { 2 } , {3}, { 2 , 4 } } } , As = {{{2}, {3}}a }, andP = {(a.,2,1), (a,4,2)}. After processing all items in I, A = { { { 2 } , { 3 } , { 2 , 4 } } , { { 2 } , { 6 } } , { { 1 , 2 } } } , ^ S = { { { 2 } , { 3 } } a , {{2},{6}}h},andP= {(a,2,1), (a,4,2), (c,2,2), (c, 1,3)}/toW. On line 10, the procedure MHSCOVERINGGREEDYHEURISTIC is called, which is derived from the procedure defined in Figure 3.1. However, this generalized version is capable of handling multi-floor options. The procedure heuristically computes the smallest set of floors F v necessary to fulfill the items I, and it is detailed in Figure 4.2. Example (Figure 4.1 (continuation)). Let, the set returned on line 10from the MHSCOVERINGGREEDYHEURISTIC procedure satisfy F v = {1,2}. Finally, on line 11, the helper procedure MHSCREATEPICKTICKET is called. This procedure creates the final pick ticket P. It is designed such that if any floor / from the selected floors F v contains the item (s, q) in any single-floor option within the set J-s, then that floor is used in (s,f,q) E P. Otherwise, it uses all tuples from the multi-floor pick ticket P corresponding to the S K U s. The simple code of this procedure is detailed in Figure C.6. Example (Figure 4.1 (continuation)). The pick ticket P returnedfrom the procedure, on line 11, satisfies P = {(a,2,3), (b,2,1), (c,2,2), (c, 1,3)}. The MHSCOVERINGGREEDYHEURISTIC procedure heuristically computes the smallest set of floors F v necessary to fulfill the items I. The 25 4. IMPLEMENTED STRATEGIES procedure MHSCOVERINGGREEDYHEURISTIC(A) input A Set of J7 , set of sets of floors options output F v Set of selected floors to visit 1: F v <- 0 2: while A^Q) do (selects floor f that maximizes its weighted coverage across all options J7 ) 3: f<- argmax/ € F a ( e ^ € ^ m a x f e J • 1{/€ F })) 4: F v <- F v U {/} (removesfloor f from all options) 5: ^ ^ { { ? \ { / } \FeT} \FEA} 6: i ^ { J | J 7 £ i , 0 ^ 7 } 7: return Fv Figure 4.2: Pseudo-code of the MHSCOVERINGGREEDYHEURISTIC proce- dure. procedure is outlined in Figure 4.2 and it does this by selecting the floor that covers the largest portion of the remaining floor options. Floor options for SKUs that are already covered are removed. The procedure continues until each S K U has at least one option covered. The MHSCOVERINGGREEDYHEURISTIC starts on line 1 by initializing a set of floors F v selected to be visited with an empty set. The procedure iterates on lines 2-6 until the entire input set A is processed. This means each floor option set F E A is hit, meaning there exists an F G J such that F C F v . Example (Figure4.2). Let A = {{{2}, {3}, {2,4}}, {{2}, {6}}, {{1,2}}}. Line 3 identifies the floor / that is most effective in reducing the overall coverage cost by being the most frequently needed part of the smallest sets of floors F within the options T E A . More precisely, the procedure selects the floor / that maximizes the weighted coverage across all floor option sets F E A . To find this floor, it computes a score for each floor / from all warehouse floors Fa . The indicator function l{/eF} is used to check if the floor / is included in the set of floors F. 26 4. IMPLEMENTED STRATEGIES It evaluates to 1 if / G F and 0 otherwise. For each set of floors F within J7 , if / is part of F, the term ^ scales this indicator value by the inverse of the size of F. This gives higher importance to floors / that are part of smaller sets F, thus prioritizing floors that are in smaller, more specific floor options. The procedure then selects the maximum weighted contribution of floor / across all floor options F G J . This step identifies the best coverage contribution of floor / in each set J7 . Summing these maximum contributions across all J7 G A yields the total coverage score for the floor /. The floor / that has the highest total score is then chosen. Example (Figure 4.2 (continuation)). In the first iteration, the floor f = 2 is selected on line 3, as it yields the highest total sum of maximum contribution, equal to the value 2.5 = 1 + 1 + 0.5, since {2} is in first two sets J7 G A and {1,2} is present in the last. On line 4, the procedure adds the floor / to the set of selected floors F v . Then, on line 5, this floor / is removed from all sets of floors F within each floor option set J7 G A . On line 6, the procedure eliminates any floor option set J7 from A that contains an empty set of floors F. This indicates that the option set J7 has been hit or covered, meaning there exists a subset F within J7 such that F C F v . Example (Figure 4.2 (continuation)). In thefirst iteration on line 4, the set F v is updated such that F v = {2}. On line 5, the set A is updated such that A = {{&, {3}, {4}}, {0, {6}}, {{1}}}. After line 6, A = {{{1}}}. In the second iteration, on line 3, f = 1 is selected. On line 4, the set F v is updated, such that Fv = {1,2} and then removed accordinglyfrom A on lines 5-6, resulting in A = 0 . Therefore, the while cycle is exited, and the procedure ends with Fv = {1,2}. 4.2 Order batching The goal of the order batching is to select customer orders, which would be processed together. The procedures for the order batching problem take a set of orders O as an input. Each order o G O is represented as a tuple (z, t, I), where i is a unique identifier used to distinguish orders with identical contents, f1 is the limit time for picking the order, indicating the latest time by which the order must reach 27 4. IMPLEMENTED STRATEGIES the sorting system, and items I is the set of tuples (s,q). The output of these procedures is a set of batches B, where each batch B E B is a set of orders. It is important to note that not all orders o E O need to be included in a batch in the output. Some orders may be postponed to be considered in the next batching cycle. The CLUSTERDISTANCE equation is employed in various procedures to calculate the distance between two clusters, and B2. It is detailed in the Equation 4.1, written in this style for better understanding. CLUSTERDISTANCE(BJ,B£) = (MHSSIZE(BJ U BC 2) - M H S S I Z E ( B J ) ) + (MHSSIZE(BJ U BC 2) - MHSSIZE(B^)) (4.1) In this context, the helper procedure MHSSIZE, detailed in Figure C.14, is used to heuristically determine the minimum number of floors required to fulfill the clusters. The procedure does it based on which floors are capable of fulfilling SKUs within these clusters. The equation returns oo if the volume of the joint cluster B\ U B2 exceeds the maximum allowed pick box's volume ^ m a x . Otherwise, it computes the additional number of floors to be visited if these two clusters are merged. This is calculated by taking the total number of additional floors that must be visited to fulfill orders from the first cluster if clusters are merged, given by MHSSIZE(BJ U S ^ ) - M H S S I Z E ( B J ) , and similarly for the second cluster B2, expressed as MHSSIZE(BJ U B2) — MHSSIZE(£>2). The formula essentially sums these differences in floor requirements, reflecting the additional floors needed when merging each original cluster. Example (Equation 4.1). Let us consider two clusters B\ = {a} and B2 = {b}. Let assume that merging these clusters would not exceed vm *x , and that order a has only one multi-floor option { 1 , 4 } , while order b has two single-floor options {3} and {4}. When merging these two clusters, the best minimal set offloors to visit in the best case would be {1,4}. This would mean that MHSSIZE(B^) = |{1,4}| = 2, MHSSIZE(B2) = {3}| = |{4}| = 1, and MHSSIZE(B^ U B2) = |{1,4}| = 2. Therefore, CLUSTERDISTANCE(B\, BC 2) = (2 - 2) + (2 - 1) = 1. 28 4. IMPLEMENTED STRATEGIES 4.2.1 EDD order batching The Earliest Due Date order batching strategy is the baseline implemented strategy for the order batching problem. It is based on the EDD algorithm mentioned in Section 3.1.2. The EDDBATCHING procedure iterates as long as the number of remaining orders O exceeds a specified parameter u, which denotes the constant number of orders that should remain unbatched. During each iteration, it forms batch B comprising orders with the earliest limit time t, continuing until the upper volume limit y m a x of a pick box is reached. The pseudocode for the procedure creates batches by selecting orders one by one based on the earliest limit time from the set of orders. However, in the implemented strategies, we first sort the orders by their limit times, as it is more efficient. This introduces sorting complexity, but this sorting is necessary for other non-naive strategies as well. Once the orders are sorted, the remaining operations execute with linear time complexity relative to the number of orders. The EDDBATCHING procedure is detailed in Figure C.7. The batch volume is determined by calling the VOLUME procedure, which calculates the physical volume of a batch or order. This can be done by summing the volumes of the individual SKUs. The volume of individual SKUs is omitted from procedures to simplify them. 4.2.2 Savings order batching The SAVINGSBATCHING procedure for the Savings order batching strategy is presented in Figure 4.3, and it is based on the Savings algorithm mentioned in Section 3.1.2 on page 17. Let us start by outlining the main principles guiding the SAVINGSBATCHING procedure, which produces a set of batches B. The procedure first creates clusters, each containing a single order. It then iteratively merges two clusters, which results in the smallest increase in the number of floors visited when combined. If the produced cluster satisfies the minimum pick box's volume vmm , it is added to the set of batches B and does not participate in further merging. Merging continues as long as there are enough orders, and merging would not cause overflowed pick boxes. 29 4. IMPLEMENTED STRATEGIES procedure SAVINGSBATCHING(OW ) input 0 W Order selection of of size w, set of orders o output B Batches, set of B constants u Number of orders to be left unbatched vmm M i n i m u m pick box's volume 1: B ^ 0 2: Bc «— {{o} | o G O W } (clusters initialization) 3: " P C ^— SAVINGSINITIALIZEDISTANCES(£>C ) 4: while Vc ^ 0 do 5: d,B\,B\ « - SAVINGSMINDISTANCE(X>C ) 6: if d = oo then 7: break 8: £ C <- B C \ { B J , B ^ } 9: Bc ^ BJ U B£ (filters out triples that includes one ofB\, B£) 10: £>c <- {(d', Bf, B|') | (d'r Bf, B£') G £>c , {Bf,B^}n{BJ,B^} = 0} 11: if V O L U M E ( B C ) > z ; m i n then 12: O W ^ O W \ Bc 13: if |OW | < u then 14: break 15: B^BU{BC } 16: else 17: X>C <— " P C U SAVINGSINCREMENTALDISTANCES(£>C , B C ) 18: Bc <- Bc U {Bc } 19: return H Figure 4.3: Pseudo-code of the SAVINGSBATCHING procedure. 30 4. IMPLEMENTED STRATEGIES The SAVINGSBATCHING procedure has cubic time complexity with respect to the number of orders. This is because merging two batches requires finding the pair of batches with the minimal distance, which is done by enumerating distances between every possible pair of orders. In the worst-case scenario, this process continues until all batches are merged. To address this, before calling the procedure, we divide a potentially large set of orders O into more manageable sets O w , called order selections. The main logic of the savings strategy is then applied to these order selections by calling the SAVINGSBATCHING procedure. Furthermore, we implicitly batch orders with similar limit times by taking the top w orders with the smallest limit time as the order selection O w . Example (Figure 4.3). Let O w = {a,b, c,d}, VOLUME (a) = 1, VoLUME(b) = 3, VOLUME(C) = 4, VOLUME(CI) = l , z ; m i n = 5,vmax = 6, u = 0, and w — 4. Let assume that order a has only one multi-floor option {1,4}, order b has two single-floor options {3} and {4}, order c has two single-floor options {2} and {3}, and order d has only one multi-floor option {4,5}. The procedure begins, on line 1, by initializing the set of batches B with an empty set. On line 2, it initializes the set of clusters Bc , where each cluster initially contains a single order from the order selection O w . Next, on line 3, the procedure calls the helper procedure SAVINGSINITIALIZEDISTANCES, detailed in Figure C.9. It computes the set Vc , where each element specifies the distance between a pair of clusters, and contains elements for all possible pairs. Example (Figure 4.3 (continuation)). On line 2, the set Bc is initialized, such that Bc = {{a}, {b}, {c}, {d}}. Let have the set Vc returned on line 3 satisfy Vc = {(l,{a},{b}),(3,{a},{c}),(2,{a},{d}),(oo,{b},{c}), (l,{b},{d}),(3,{c},{d})}. The SAVINGSINITIALIZEDISTANCES procedure uses Equation 4.1 for calculating distances. Therefore, the distance value oo would be returned between clusters {b} and {c} because merging these two clusters would exceed the maximal pick box's size vmax , as VoLUME({b} U {c}) = 3 + 4 = 7, which exceeds vm&x = 6. The distance value between clusters {a} and {b} is calculated in the examplefor Equation 4.1 on page 28. Other distance values would be calculated accordingly using their respectivefloor options. 31 4. IMPLEMENTED STRATEGIES On lines 4-18, the procedure iterates until the set T>c is empty or the conditions specified on lines 6 or 13 are met. If Vc ^ 0 , it means there are at least two clusters that could be potentially merged. In each finished iteration, the procedure merges two clusters. On line 5, the smallest distance value d between any two clusters, and B^, is selected using the helper procedure SAVINGSMINDISTANCE, which is detailed in Figure C.10. Example (Figure 4.3 (continuation)). In thefirst iteration, on line 5 the procedure returns the triple with values d = \,B\ = {b},B\ = {d}. On line 6, the procedure then checks if the distance value d equals oo, which indicates that merging these clusters would exceed the maximum allowed pick box's volume y m a x . If this is the case, no further clusters can be merged, and the procedure breaks out of the loop. On line 8, clusters B^ and B^ are removed from the set Bc , and on line 9, they are merged into a new cluster BC . Line 10 retains in set VC only elements that do not involve cluster B^ or B^. Example (Figure 4.3 (continuation)). As the value d ^ oo the procedure continues to line 8. On lines 8-9, sets are updated, such that Bc = {{a}, {c}}, and BC = {b, d}. On line 10 the set Vc is refined, such that Vc = {(3, {a}, {c})}, since all elements including {b} or {d} are removed. Line 11 checks if the new cluster BC satisfies a pick box's minimum volume vmm . If it does, the cluster BC is removed from the order selection O W as outlined in line 12. If creating the cluster BC from the order selection O W would result in fewer remaining orders than the parameter u, then the procedure breaks out of the loop as shown in line 13. Otherwise, the cluster BC is added to the set of batches B, as shown on line 15. The parameter u denotes the constant number of orders that should remain unbatched. If the volume of the cluster BC is smaller than vmm , the procedure incrementally recomputes distances on line 17, between the new cluster BC and all other clusters Bc using the helper procedure SAVINGSINCREMENTALDISTANCES, presented in Figure C . l l . Finally, on line 18, the newly formed cluster BC is added back to the set of clusters Bc . Example (Figure 4.3 (continuation)). As VOLUME(BC ) = VoLUME({b}) + VoLUME({d}) = 3 + 1 = 4 , which is less than vmm = 5, the procedure 32 4. IMPLEMENTED STRATEGIES continues to line 17. On line 17, the set Vc is updated, such that Vc = {(3, {a}, {c}), (2, {b,d}, {a}), (oo, {b,d}, {c})}, and on line 18, the set of clusters is updated, such that Bc = {{a}, {c}, {b, d}}. As Vc 7^ 0 , the procedure continues to the second iteration, where on line 5, d = 2, B\ = {b,d}, = {a } is assigned. As the d ^ oo, the procedure continues to line 8, where the set of clusters Bc is updated, such that Bc = {{c}}, and on line 9, clusters are merge, such that BC = {a, b, d}. On line 10, the set VC is refined, such that VC = 0 Now VOLUME(BC ) = 5, which equals to z ; m m = 5 and the procedure continue to line 12. On line 12, the order selection O w is updated, such that Ow = {c}. As |Ow | > u, where u = 0, the procedure continues to line 15, where the cluster is added to set of batches, such that B = {{a,b, d}}. As the set Vc = 0 , the loop is exited and the procedure ends with £ c = {{a,b,d}} It is worth mentioning that instead of representing Vc as a set, we could use a min-heap data structure to improve the complexity. This would improve the overall asymptotic complexity of the SAVINGSBATCHING procedure to the square of the number of orders multiplied by the logarithm of the number of orders. In our implementation, we have chosen to retain the use of the set for simplicity and to avoid the additional overhead of managing a min-heap. 4.2.3 Seed order batching The SEEDBATCHING procedure for the Seed order batching strategy is presented in Figure 4.4. It is based on the Seed algorithm mentioned in Section 3.1.2 on page 17. Before delving into the details, it's essential to understand the core ideas behind the SEEDBATCHING procedure, which produces a set of batches B. The procedure initializes the cluster by selecting a the first order as a seed. It then incrementally adds other orders to the cluster, aiming to minimize the increase in the number of floors visited. This process continues until the cluster reaches the minimum pick box's volume z ; m m . The cluster is then added to the set of batches B, and the process is repeated as long as there are enough orders. The SEEDBATCHING procedure has a quadratic time complexity with respect to the number of orders. Each time the algorithm wants to 33 4. IMPLEMENTED STRATEGIES procedure SEEDBATCHING(OW ) input 0 W Orders, set of o output B Batches, set of B constants u Number of orders to be left unbatched ymax ]y[a ximum pick box's volume vmm Minimum pick box's volume 1: B <- vmin do 3: BC 4- {SEEDINITIALORDER(OW )} 4: 0 W <-0W \BC 5: while V O L U M E ( B C ) < vmax do (selects ordersfitting by the volume size) 6: O R <- {o | o e O W , V O L U M E ( B C U {O}) < z;m a x } 7: if O R = 0 then 8: break 9: o SEEDCLOSESTORDER(BC , O R ) 10: O W <- O W \ {o} 11: B C <- B C U{o} 12: if ( V O L U M E ( B C ) < z;m i n ) V (|OW | < u) then 13: break 14: else 15: B<-BU{BC } 16: return H Figure 4.4: Pseudo-code of the SEEDBATCHING procedure. 34 4. IMPLEMENTED STRATEGIES incrementally add an order to the batch, it needs to calculate the distance between the batch and all unbatch orders. While this procedure has a lower computational complexity compared to the SAVINGSBATCHING procedure, it does not produce batches of the same quality. This is because SEEDBATCHING focuses on optimizing individual batches rather than considering multiple batches at once. It remains crucial to partition the set of orders O into smaller, more manageable order selections O W before invoking the SEEDBATCHING procedure. Furthermore, the partitioning enables us to implicitly batch orders with similar limit times by taking the top w orders with the smallest limit time as the order selection O W . Example (Figure 4.4). Let O W = {a,b, c,d}, VOLUME (a) = 1, VoLUME(b) = 3, VOLUME(C) = 4, VOLUME(CI) = l , z ; m i n = 5,vmax = 6, u = 0, and w — 4. Let assume that order a has only one multi-floor option { 1 , 4 } , order b has two single-floor options { 3 } and {4}, order c has two single-floor options { 2 } and {3}, and order d has only one multi-floor option { 4 , 5 } (same setting as the example in Section 4.2.2 on page 31). On line 1, the procedure initializes the set of batches B with an empty set. On lines 2-15, the procedure iterates until the total volume of the remaining orders O W falls below the pick box's minimum volume vmm or the condition on line 12 is satisfied. The volume is checked to know if there are enough orders to create a pick box. In each finished iteration, a new batch B is created. On line 3, the procedure calls the helper procedure SEEDINITIALORDER, which selects a single order from the order selection O W . This order can be chosen based on various criteria, such as the earliest limit time or the largest minimal hitting set, and therefore, implementations of this procedure can vary. The selected order initializes a new cluster Bc , and as it shown on line 4, it is then removed from the order selection O W . Example (Figure 4.4 (continuation)). As VOLUME(OW ) = 1 + 3 + 4 + 1 = 9 is larger than vmm = 5, the procedure continues to line 3. Let c be selected as the initial order. Therefore, on line 3, in the first iteration of the outer loop, Bc = {c}. On line 4 the order selection Ow is updated, such that O W = {a,b,d}. Lines 5-11 handle the iterative expansion of the cluster Bc . The procedure continues to add orders to the cluster Bc as long as its 35 4. IMPLEMENTED STRATEGIES volume remains below the pick box's maximum volume ^ m a x and the condition on line 7 is not met. O n line 6, the procedure selects a set of orders O R from the order selection O W that can fit into the batch BC without exceeding the volume constraint. Line 7 checks if there are any fitting orders in O R . If not, the procedure breaks out of the inner loop. Example (Figure 4.4 (continuation)). As VOLUME(BC ) = 4 is smaller than ymax _ ^ ^ne p r o c e d u r e continues to line 6. On line 6, in thefirst iteration of the inner loop, the set offitting orders is selected such that O R = {a,d}, because only VOLUME(BC U {b}) = 7 is larger than u m a x = 6. As O R ^ 0 , the procedure continues to line 9. On line 9, the helper procedure SEEDCLOSESTORDER is called to find the distance d and the closest order o to the current cluster BC from the fitting orders Or . It is detailed in Figure C.12. On lines 10-11, the procedure removes the closest order o from the order selection O W and adds it to the cluster BC . Example (Figure 4.4 (continuation)). On line 9, let d = 1, and o = d. On line 10, the order selection O W is updated, such that O W = {a,b}, and on line 11, the cluster BC is updated, such that BC = {c,d}. As VOLUME(BC ) — 4 + 1 —5 is smaller than c m a x = 6, the procedure continues into the second iteration of the inner loop to line 6. On line 6, the set of fitting orders O R is selected such that O R = {a} because only VOLUME(BC U {a}) = 6 is smaller or equal to vm&x = 6. As O R ^ 0 , the procedure continues to line 9. On line 9, d = 1 and o = a hold. On line 10, the order selection O W is updated, such that O W = {b}, and on line 11, the cluster BC is updated, such that BC = {a, c, d}. As VOLUME(BC ) = 6 is equal to vm&x / the inner loop is exited and the procedure continues to line 12. On line 12, the procedure checks if the volume of the cluster BC is below the minimum pick box's volume vmm or if the number of remaining orders is less than the parameter u, representing a number of orders to be left unbatched. If either condition is met, the procedure breaks out of the outer loop. Otherwise, the completed cluster BC is added to the set of batches B. Example (Figure 4.4 (continuation)). The VOLUME(BC ) = 6 is larger than vmm = 5 and |OW | > u, where u = 0, so the procedure continues to line 15, 36 4. IMPLEMENTED STRATEGIES procedure MSFBATCHING(O) input O Orders, set of o output B Batches, set of B 1: 0 ^ 0 2: A0 <- 0 3: foreach o G O 4: Z 0 ORDERSINGLEFLOOROPTIONS(O) 5: if Z 0 ^ 0 then 6: i V i ° U {Z0 } 7: else 8: O ^ O U { o } 9: H ^— MSFBATCHSINGLEFLOORORDERS (*4°) 10: return B U FALLBACKBATCHING(O) Figure 4.5: Pseudo-code of the MSFBATCHING procedure. where the set B is updated such that B = {{a, c,d}}. As VOLUME(OW ) = 3 is lower than vmm = 5, the outer loop is exited and the procedure ends with H = {{a,c,d}}. 4.2.4 MSF order batching The MSF or the Maximize Single Floor order batching strategy is designed to explicitly prioritize the creation of pick boxes that require visits to only a single floor. The MSFBATCHING procedure, which implements this strategy, is detailed in Figure 4.5. Let us first discuss main ideas behind the MSFBATCHING procedure. The procedure begins by splitting orders into two categories. First, orders with at least one single-floor option, and second, the rest. For the single-floor orders, it calls the MSFBATCHSINGLEFLOORORDERS procedure. For non-single-floor orders, it uses any other batching strategy capable of handling multi-floor options represented by calling the FALLBACKBATCHING procedure. The MSFBATCHSINGLEFLOORORDERS procedure operates with linear time complexity relative to the number of orders, except for the step of sorting orders by limit time, which introduces additional sorting com- 37 4. IMPLEMENTED STRATEGIES plexity. This is comparable to the naive EDDBATCHING procedure. Since we expect a significant portion of orders to include at least one singlefloor option, allowing these orders to be batched efficiently in linear time after sorting. For the remaining orders, which lack single-floor options, more computationally intensive procedures with quadratic time complexity, such as SEEDBATCHING or SAVINGSBATCHING, may be used. This division ensures that the overall computational burden is minimized without compromising the quality of batches. On line 1, the MSFBATCHING procedure initializes the set of multifloor orders O, meaning orders without single-floor option, with an empty set. On line 2, the aggregated set A0 is initialized with an empty set. O n lines 3-8, the procedure iterates through all orders o E O to aggregate all single-floor options into the set A0 , and all multi-floor orders into the set O. Example (Figure 4.5). Let O = {a,b, c, d, e, f,g,h}. Let assume that only orders b, d, e, g, h have single-floor options. On line 4 , the helper procedure ORDERSINGLEFLOOROPTIONS, detailed in Figure C.16, is called. This procedure returns the set T^, which includes all single-floor options for the order o. Each singlefloor option F G 7 consists of a single floor /, such that F = {/}. If at least one single-floor option exists in T_ for an order o, the set J[0 , indexed by the order o, is added to the aggregate set. Otherwise, the order is added to the set of multi-floor orders, as shown on lines 5-8. Example (Figure 4.5 (continuation)). In the first iteration for the order a, since the order does not have any single-floor options, on line 4 we have £ a = 0 . Therefore, the condition on line 5 is not met, and the procedure continues to line 8. On line 8, the set O is updated toO = {a}. In the second iteration, the order b is processed. Let us assume that on line 4, F_h = {{5}} is returned. Therefore, the condition on line 5 is met, and the procedure continues to line 6. On line 6, the aggregated set is updated, such that A0 = {{{5}}b }. After processing all orders, let A0 = {{{5}}b/{{1}/{3}, {5}}d, {{2}, {3}, {5}}e , { { 4 } , {5}}g , { { 1 } , { 2 } , { 4 } } H } and O = {a, c,f } hold. On line 9, the procedure calls the helper procedure MSFBATCHSINGLEFLOORORDERS, detailed in Figure 4.6, which returns a set of batch- 38 4. IMPLEMENTED STRATEGIES es B. These batches are formed from the orders that have their options in the set ^4°. Example (Figure 4.5 (continuation)). Let the set B be assigned on line 9, such that B = { {b, d, g} }, meaning that e and h are not selectedfor the processing this time. Finally, on line 10, the procedure returns the union of the batches B with the result from the helper procedure FALLBACKBATCHING, applied to the set of multi-floor orders O. The FALLBACKBATCHING procedure can use any other batching strategy capable of handling multi-floor options, such as EDDBATCHING, SAVINGSBATCHING, or SEEDBATCHING. Example (Figure 4.5 (continuation)). Let the result of FALLBACKBATCHING be {{a, c}}. Then the result of the procedure is B = {{b, d,g}, {a, c}}. Let us now discuss the main ideas behind the MSFBATCHSINGLEFLOORORDERS procedure. The procedure creates a set of batches B from orders that can be picked from a single floor, which have the single-floor option in the set A0 . It starts by creating a set of orders for each warehouse floor, containing all orders that can be fulfilled on the corresponding floor. The procedure then iterates through these sets Oy G O in a Round-robin fashion. In each iteration, it creates a batch of orders with the smallest limit time from the set Oy, if possible. If not, it removes Oy from O. The set of sets O is iterated until it is empty. The idea behind creating at most one batch from each set Oy and then moving to the next set is to distribute batches more evenly across floors and prevent the overload of any particular floor. Example (Figure 4.6). Let A0 = {{{5}}b , {{1}, {3}, {5}}d , {{2}, {3}, {5}}e ,{{4},{5}}g ,{{l},{2},{4}}H },VOLUME(b) = 2,VOLUME(d) = 2,VOLUME(e) = 2,VOLUME(g) = 1, V0LUME(h) = l , v m m = 5. On line 1, the procedure initializes the set O of sets of orders with an empty set. O n lines 2-5, for each warehouse floor / G F a , the procedure identifies all orders Oy that can be picked from that floor, meaning there exists a single-floor option for each order o G Oy, such that {/} G F_0- These sets of orders Oy, indexed by their respective floors, are added to the set O. 39 4. IMPLEMENTED STRATEGIES procedure MSFBATCHSINGLEFLOORORDERS(A0 ) input A0 S e t o f f , set of sets of floor options indexed by order o output B Batches, set of B constants F a Set of all existing warehouse floors vmm Minimum pick box's volume 1: O ^ 0 2: foreach / e Fa (unions orders that have a single-floor option containingfloor f in the set A0 ) 3: Qf = U^eA0 , {f}eEo 0 4: if Of £ 0 then 5: O^OU {Of} 6: Of <— R A N D O M E L E M E N T ( C ) 7: while O ^ 0 do 8: B ^— MSFCREATEBATCH(Oy) 9: if VOLUME(B) < z ; m i n than 10: O <- O \ {Of} 11: —f^~ n e x t element of (9 selected in Round-robin fashion 12: continue 13: B^BU{B} 14: O <- {O'} \OfeO, O'} =Q_f\ B,0!'F £ 0} 15: Of <— next element of O selected in Round-robin fashion 16: return B Figure 4.6: Pseudo-code of the MSFBATCHSINGLEFLOORORDERS proce- dure. 40 4. IMPLEMENTED STRATEGIES On line 3, the procedure unions orders that have a single-floor option containing floor / in the set . 4 ° into the set Oy. If the set Oy is non-empty, it is added to the aggregated set O, as shown on lines 4-5. Example (Figure 4.6 (continuation)). In thefirstiterationfor thefloor 1, the procedure selects orders d and h on line 3. This is because {{1}, {3}, { 5 } } D e A0 and {{1}, {2}, { 4 } } H e A0 . Therefore, 01 = {d,h}. Since the condition on line 4 is met, the set O is updated to O = {{d, h}i}. After processing all orders, O = {{d, h}i, {e, h}2, {d, e}3, {g, h}4, {b, d,e,g}5 } hold. On line 6, the procedure selects a random set of floor orders Oy from set O using the helper procedure RANDOMELEMENT. Example (Figure 4.6 (continuation)). On line 6, let the set 0 4 = {g,h} be selected. On lines 7-15, the procedure iterates while there are still order sets Oy remaining in O. In each finished iteration, a batch B is created. On line 8, the procedure creates a batch B from some orders in Oy using helper procedure MSFCREATEBATCH, detailed in Figure C . 1 3 . If the volume of the batch B does not satisfy the minimum pick box's volume vmm , the set of orders Oy is removed from the set O, and a new set Oy is selected from O in a Round-robin fashion, as shown on lines 9-12. However, if the batch B satisfies the minimum pick box's volume vmm , the procedure continues on lines 13-15. Example (Figure 4.6 (continuation)). As 0 / 0 , the procedure continues to line 8. In thefirstiteration on line 8, let expect B = {g,h} is returned. As VOLUME(B) = 1 + 1 = 2 is smaller than vmm = 5 the procedure continues on line 10. On line 10, the set O is refined, such that O = {{d,h}i,{e,h}2,{d,e}3 ,{b,d,e,g}5 }. On line 11, 05 = {b,d,e,g} is selected and the procedure continues to the second iteration. In the second iteration on line 8, let expect B = {b, d,g} is returned. As VOLUME(B) = 2 + 2 + 1 = 5 is equal to vmm , the procedure continues to line 13. On line 13, the new batch B is added to the set of batches B. O n line 14, all orders appearing in the new batch B are removed from all order sets in O. On line 15, a new floor order set Oy is selected from O in a Round-robin fashion. 41 4. IMPLEMENTED STRATEGIES Example (Figure 4.6 (continuation)). On line 13, the set of batches B is updated, such that B = {{b,d,g}}. On line 14, the set O is refined, such that O = {{h}i,{e,h}2,{e}3,{e}s}. On line 15, 01 = {h} is selected, and the procedure continues to the third iteration. As VoLUME(e) = 2, and VOLUME(1O.) = 1, no additional batch could satisfy the condition on line 9, and thereforefollowing four iterations would be similar to the first iteration. At the end of sixth iteration O = 0 and procedurefinisheswith B = {{b, d,g}}. 42 5 Simulator The performance evaluation of proposed strategies was conducted through a simulation experiment. A significant portion of the work on the thesis involved developing the necessary simulator. The simulation model is intricately designed to encompass the essential processes required for an effective evaluation of these strategies. This chapter outlines the design, features, and key simplifications made to facilitate this analysis. The notation used throughout this section is summarized in Appendix D. 5.1 Components The implemented simulator comprises four main logical components, which are the Storage, the Transition system, the Planner, and the Simu- lation. The Storage module manages the inventory. It is divided into individual Floor inventories. Each Floor inventory solely monitors quantities of SKUs present on its respective floor. In this simulation, additional details about the storage, such as precise positions of SKUs on the floor, are unnecessary since routing is not a focus of this thesis. The Transition system module monitors the movement of pick boxes across different floors. On each floor, a pick box may either wait on the conveyor belt for a picker or be part of a picking cart, being actively picked by a picker. The Planner module is the focal point of the thesis. It processes orders and generates pick boxes with the picking list, also called a pick ticket. The pick ticket specifies the locations and quantities of SKUs to be retrieved, and it can also include routing information. The Planner is further divided into two sub-modules based on two primary decisions, which are Batching and Floor selection. The Batching sub-module groups orders into pick boxes, while the Floor selection sub-module assigns specific floors for visitation and determines SKU quantities to be picked. The Simulation module integrates all individual parts into a cohesive system. It encompasses input parsing, restocking processes, and the execution of the simulation itself. 43 5- SIMULATOR 5.2 Computation This section explains main processes in the implemented Simulator. The simplified procedure of the simulator is presented in Figure 5.1. The simulation progresses in discrete steps, occurring every fd units of time, each representing a momentary pause, allowing for necessary actions to take place. These actions predominantly include restocking, receiving and processing incoming orders, and managing picking carts. On line 1 in the SIMULATOR procedure, the current date-time t is initialized to the start of the day when the first order is received. The simulation progresses in discrete steps until the end of the day, when the last order is received, as outlined on line 2. The update by discrete step td occurs at the end of the loop, on line 11. At the midnight, as outlined on line 3, the simulator calculates the number of pickers needed for the following day. This calculation follows a specific process. The system first considers the number of products that were not picked from previous days, denoted as q, and adds it to the expected number of products in orders arriving the next day, denoted as qn . This expected number is multiplied by a factor r n , such that rn < 1, which reflects the portion of next day orders likely to arrive early enough to be processed within the day. The total number of pickers k* required for the following day is given by the following equation. k*= (ql + qn *rn )*rk /(h*qh ) (5.1) Constant h represents the warehouse shift length in hours, qh is the number of picked products by a single picker in an hour, and r k is a factor for adjusting the number of pickers k* for different simulation settings. The computed total number of pickers k* is then distributed uniformly across the warehouse floors. If the total number of pickers k# is not divisible by the number of floors /* in the warehouse, the remaining pickers, or the modulus, are assigned with priority to the floors with the highest number of pending pick boxes from the previous day. Restocking involves replenishing inventory at regular intervals occurring each tr units of time to meet the demands of orders anticipated in the upcoming hours. This process determines the quantity and type 44 5- SIMULATOR procedure SIMULATOR() constants g m a x Maximum number of products in the storage ft Shift start time td Simulation discrete step size te Shift end time fP Planner execution time tr Restocking period 1: t <— date-time of the start of the simulation 2: while t is smaller than simulation end do 3: if it is midnight then calculate the number of pickers k# and distribute them among floors 4: if it is tr units of time since the last restock then restock and distribute products until qmax of products is in the warehouse storage using STOCKDISTRIBUTION procedure 5: if th < TiME(t) < te then 6: trigger moving of pick boxes of picking carts, which picking has finished since the last time checked, to the next floor or to the sortation system 7: if it is fP units of time since the last Planner execution then spawn new pick boxes on respective floors 8: if there are enough pickers and pick boxes waiting on floors then put pick boxes on picking carts and trigger their picking 9: accept new orders that were received since the last accepting step 10: if it is fP units of time since the last Planner execution then trigger Planner on unprocessed orders 11: t^t + td Figure 5.1: Pseudo-code of the SIMULATOR procedure. 45 5- SIMULATOR of products based on the content of expected orders. In real-world scenarios, these orders are estimated based on trends. However, in a simulated environment, we have the advantage of accessing future input data directly. When a restocking event occurs, which is outlined on line 4 in the SIMULATOR procedure, the system evaluates the current inventory levels and the content of upcoming orders, beginning with the most recently processed order from the previous restocking cycle. It selects upcoming orders until the total number of products from these orders, after being adjusted by an overstocking factor rr , combined with the existing inventory, reaches the upper storage limit qmax . This upper limit represents the maximum number of products that can be stored in the warehouse. The system consolidates the quantity q of each S K U from the incoming orders. The quantity q is multiplied by the configurable overstocking factor rr , such that rr > 1, to ensure a sufficient buffer in the storage, preventing the depletion of stock down to the last item. The result of this multiplication, denoted as the adjusted quantity qa , represents the final quantity to be considered for each SKU to maintain the desired stock level. The system then repeatedly performs the allocation process, illustrated in the procedure in Figure 5.2, to distribute the entire adjusted quantity qa of each S K U in manageable doses. It uses the parameter qA to represent these distribution doses. In each iteration, a floor is randomly selected, and qA SKUs are allocated to it, or fewer if the remaining quantity is insufficient. This iterative process continues until the entire adjusted quantity qa is fully distributed. The simulated warehouse operates on work shifts that begin each day at fb and end at te , which is presented on line 5 in the SIMULATOR procedure. Outside this work shift, warehouse operations, except for restocking, are halted. On line 6 in the SIMULATOR procedure, the system monitors each floor to determine whether individual picking carts have reached their predetermined picking time. Once this time is reached, the corresponding pickers on their respective floors become available, and the pick boxes they have carried are placed on the conveyor belt. Pick boxes are directed to either the next floor indicated in the pick ticket or sent for consolidation in the sortation system. 46 5- SIMULATOR procedure STOCKDISTRIBUTION(S,^) input s S K U q Quantity of S K U s in expected orders constants rr Overstocking factor qA S K U distribution dose 1: q& «— q *rr 2: while qa > 0 do 3: f <— select random floor 4: ql *r- min(gd ,ga ) 5: qi of S K U s is added to floor / 6: q* <- q* - ql Figure 5.2: Pseudo-code of the STOCKDISTRIBUTION procedure. The time tm spent to move a pick box between two floors is calculated as shown in the following equation. f* = 2*1* + f*e (5.2) There are two configurable constants. The first, tf , represents the time it takes to move a pick box along an intra-floor conveyor, and t1 represents the time needed to move a pick box between two consecutive floors on an inter-floor conveyor. The value tf is accounted for twice because the pick box must first move on the intra-floor conveyor on the floor /f from which it is leaving and then move on another intra-floor conveyor on the floor /* to which it is arriving. Floors are identified numerically, starting from 0 for the first floor, 1 for the second floor, and so on. The number of floors /* involved in the move is determined by the difference between the target floor /* and the initial floor /f , so /* = /* — /f . We consider the number of floors in the warehouse to be denoted as /a . When moving a pick box from the floor where picking was completed to the sortation system, the number of floors f# is calculated as /* = /a — /f . This includes the transition to the sortation system after leaving the last floor in the pick ticket. A floor with at least one available picker and a sufficient number of waiting pick boxes triggers a prioritization process, outlined on line 8 47 5- SIMULATOR in the SIMULATOR procedure. In this process, pick boxes are ranked based on limit times of the most constrained orders they contain. The highest priority boxes are then grouped into a picking cart. The picking cart in the simulation has physical constraints on the minimum c m m and maximum c m a x number of pick boxes it can carry. Additionally, the simulator takes into account the end of the shift te , ensuring that as many pick boxes as possible are loaded onto the picking cart without exceeding its capacity and without requiring pickers to work beyond their designated shift. To calculate the picking time tc for the picking cart f = min((qc /qh ),tmin ) , (5.3) we first determine the total number of products of the picking cart, denoted as qc , that are scheduled to be picked on the respective floor, which counts the number of such products for each pick box on the picking cart. This total qc is then divided by the constant q^, which represents the number of picks a single picker can make in an hour. The resulting value provides an estimate of the picking time. Additionally, the constant tmm defines the minimum duration for the picking process of the pick cart, ensuring a baseline time for any picking activity. On line 9, in the SIMULATOR procedure, the system accepts all orders that have arrived since the last accepting step. If the previous Planner execution has already finished, as is checked on line 10, newly accepted orders, along with orders from previous steps that have not yet been batched, are fed into the Planner module. The Planner then generates pick boxes for selected orders, deciding which floors to visit and the quantities of SKUs to be picked on each floor. Some orders may be postponed for processing in later steps. The Planner operates in one of two possible ways. Either it first batches orders into pick boxes and then selects floors those pick boxes will visit, or it first selects floors for each order and then creates pick boxes based on those reservations. The simulation reserves a fixed time interval fP for the Planner's execution, ensuring that the Planner runs every fP units of time without the overlap, thus preventing conflicts in its decisions. A l l pick boxes assembled by the Planner in the same cycle are spawned fP units of time after the Planner's execution. Each pick box is spawned on its first 48 5- SIMULATOR floor, which is selected to be visited by the Planner. This is outlined on line 7 in the SIMULATOR procedure. 5.3 Simplifications Key simplifications implemented in the simulation model are listed below. They are outlined for emphasis in contrast to the complexities of real-world scenarios. • No congestion control on conveyors implies the simulation does not incorporate congestion control mechanisms for conveyors. Consequently, there is no upper limit to the number of pick boxes on conveyors. • Discrete step processing signifies that all processing activities within the simulation occur in discrete steps. • Discrete step restocking means that inventory restocking is also modeled to happen in individual, discrete steps. • Picker number based on order volume indicates that the number of pickers deployed is derived from the volume of orders expected for a given day. • Single-floor picker assignment implies that each picker is assigned exclusively to a single floor throughout their entire shift. • Uniform floor design reflects that all floors within the simulation environment are modeled as identical. The number of products on each floor is approximately the same, and the number of pickers between different floors can only differ by 1. 49 6 Experimental evaluation This chapter focuses on experimental evaluation of proposed strategies. The evaluation was done on the simulator, detailed in Chapter 5 implemented as a part of the thesis. This chapter firstly looks more into datasets used in the evaluation and then into the experimental setting of parameters, followed by individual executions of experiments. The chapter presents the results primarily through intuitive graphical representations, with a few exceptions. More detailed results, presented in tabular form, can be found in Appendix E. The experiments were conducted on Debian x86_64 Linux with an A M D EPYC 7543 CPU, using 1 CPU core and 4 GB of R A M for each run, within the MetaCentrum [47] distributed computing infrastructure in the Czech Republic. 6.1 Datasets The data used for experimental evaluation is derived from a half-year production data from the Notino warehouse in the Czech Republic. Instead of using the raw data directly, we segmented it into several distinct datasets for two primary reasons. Firstly, to protect sensitive information across the entire dataset and, secondly, to create datasets that reflect varying levels of warehouse utilization. From the original data, we generated 16 distinct datasets. Main datasets DataOl to Data06 were created to evaluate the performance of the best fine-tuned strategies together with the baseline. Tuning datasets TuneOl to TunelO were used to eliminate basic strategies and fine-tune simulator parameter settings as well as strategies hyperparameters, thereby reducing the number of combinations needing evaluation. Tuning datasets should represent typical warehouse usage, as they closely mirror the actual daily order average. Each dataset comprises 14 randomly selected days from the original Notino data. The days in the main datasets, DataOl to Data06, were selected to ensure the datasets have decreasing average numbers of orders, with no single day appearing in more than one dataset. Among the produced datasets, the highest daily volume is 160,712 orders, and the lowest is 41,424 orders. 50 6. EXPERIMENTAL EVALUATION 180,000 160,000 140,000 120,000 o 100,000 o I_ •S 80,000 o 60,000 40,000 20,000 0 Distribution of order count per day 10 11 12 13 14 Day Figure 6.1: Distribution of order count per day for main datasets From the remaining days of the original Notino data, we created 10 tuning datasets, TuneOl to TunelO, using days with a number of orders ranging from 45,000 to 65,000. In these tuning datasets, a single day from the original data can appear in multiple datasets due to the limited number of remaining days available for selection. However, not a single day appears multiple times in the same dataset. The generated datasets detail the contents of each order, including the order creation time, order limit time, order identifier, and the list of products. The order creation time indicates when the order enters the warehouse system. The order limit time specifies the latest possible time for the order to arrive to the sortation system to ensure timely delivery. The list of products includes S K U identifiers, the physical volume of each SKU, and the quantity. The distribution of order counts per day is presented in the Figure 6.1 and Figure 6.2. Table 6.1 compares the number of orders across the different datasets. It shows the mean, standard deviation, and the minimum and maximum number of orders per day. Table 6.2 provides summary statistics for product counts, including the average number of products per order and the average number of unique SKUs per order. It also presents the Mean raw duration, which is the average time 51 6. EXPERIMENTAL EVALUATION Distribution of order count per day Figure 6.2: Distribution of order count per day for tuning datasets in hours between the order creation time and the order limit time, and the Mean shift duration, which is the average time, in hours, during which the order creation and limit times overlap with the operational shift hours. For the Mean shift duration, the shift hours are set from 6:00 to 22:00, as detailed in Section 6.2. Table 6.1: Summary statistics of daily order counts Dataset Mean Std. dev. Min Max DataOl 116,774 17,383 99,574 160,712 Data02 89,008 4,967 83,024 96,771 Data03 75,256 3,909 70,707 81,859 Data04 65,378 2,667 61,803 69,087 Data05 54,633 3,175 51,140 60,450 Data06 46,405 2,634 41,424 50,148 TuneOl 50,745 4,590 45,390 59,992 Tune02 50,381 4,889 45,390 59,749 Tune03 51,884 4,491 46,312 60,050 Tune04 49,811 4,528 45,617 59,749 Continued on next page 52 6. EXPERIMENTAL EVALUATION Table 6.1 - continued from previous page Dataset Mean Std. dev. Min Max Tune05 50,532 4,626 45,917 59,992 Tune06 49,616 4,424 45,617 59,749 Tune07 51,520 4,904 46,312 60,050 Tune08 51,542 5,084 47,226 60,050 Tune09 50,431 4,580 45,617 59,749 TunelO 50,100 4,243 45,750 59,718 Table 6.2: Summary statistics of product counts and order limit times CD CO res+ J res Q 5H ,—, O QJ 1 1 £ o o .2 £ S 2 § o ri £ *a 15 0 ) 0 ) 0 ) 0 ) Q s s s s Tune09 4.70 3.87 17.34 10.95 TunelO 4.75 3.93 17.52 11.23 6.2 Shared parameter setting The simulation parameters shared across all executions are presented in Table 6.3. The symbols are ordered alphabetically for easier searching. Most of these parameters were provided by Notino and are close to real-world values. Exceptions include qA , rk , rn , and rr , which were adjusted during the development of the simulator to better align with real-world conditions. Table 6.3: Parameter setting Symbol Value Description ^max 8 Maximum number of pick boxes per picking cart ^min 4 Minimum number of pick boxes per picking cart 8 Number of warehouse floors h 16 h Shift length 10 Minimum number of products of single S K U restocked on randomly selected floor if possible Continued on next page 54 6. EXPERIMENTAL EVALUATION Table 6.3 - continued from previous page Symbol Value Description 160 Number of products picked per picker per hour ^max 1 700,000 Maximum number of products in the storage f 30 Maximum number of allowed products in a single order r k 0.96 Factor to adjust the number of pickers ^max 0.8 Factor of maximum usable pick box volume j,min 0.6 Factor of minimum acceptable pick box volume 0.9 Portion of day orders effecting number of pickers r r 1.2 Overstocking factor th 6:00 Shift start time td 1 min Simulation discrete step size te 22:00 Shift end time f.i 25 s Infra-floor conveyor belt moving time ii 20 s Inter-floor conveyor belt moving time xmin 5 min Minimum time to pick a picking cart a 2 h Restocking period U 50 Number of orders to be left unbatched V 20,325,996 m m 3 Physical volume of a pick box 6.3 Experiments Due to the extensive number of strategy combinations, datasets, and varying parameters, evaluating all possible combinations would be too extensive. Therefore, we assessed strategies in multiple evaluation steps, referred to as experiments, rather than exhaustively testing every combination. In each reported result, we excluded the first and last two days from each 14-day dataset to ensure stable warehouse operations. From 55 6. EXPERIMENTAL EVALUATION the point of orders, we omitted orders that either reached the sortation system before the 3rd day or were received after the 12th day In experiments described in Sections 6.3.1 - 6.3.4, each reported result is the average of the single simulation run on all tuning datasets for the specified configuration. These experiments help to fine-tune parameter values and optimize the performance of each evaluated strategy. In the final experiment described in Section 6.3.5, each reported result on the given dataset is an average of 10 simulation runs on the corresponding dataset for the specified configuration. This experiment compares strategy combinations with parameters that have already been fine-tuned. In our experiments, we did not evaluate the First Come First Serve batching strategy, considering it too naive. The simplest batching strategy we evaluated was Earliest Due Date, denoted FDD. We also assessed more sophisticated batching strategies, including Seed, Savings, and Maximize Single Floor. The Maximize Single Floor, denoted MSF strategy was paired only with more advanced strategies Seed and Savings. For floor selection, we employed all three strategies proposed in Section 4.1. In Section 6.3.5, we used the Greedy strategy as a reasonable baseline for floor selection, as the Random strategy was deemed too naive. For batching, F D D served as the baseline strategy. In the procedures presented in Chapter 4, we have several times selected a random floor. However, during the implementation of the simulator, we observed that choosing the floor with the fewest unpicked products was more effective. Unpicked products refer to products selected for picking on a given floor that have not yet been picked, either because they are still waiting for a free picker or are actively being picked. This approach better balances the workload. Consequently, we used this feature during the evaluation. During evaluation the main observer statistics are as follows. The Tardiness metric is calculated as the sum of the differences between the completion times and the limit times for all late orders, divided by the total number of completed orders, measured in minutes. The normalization by dividing was done to penalize for uncompleted orders. The Late orders metric indicates the percentage of orders completed after their limit time, the Mean floors denotes the average number of floors 56 6. EXPERIMENTAL EVALUATION visited per pick box, the Mean pickers represents the average number of pickers per day per floor, and the Pickers usage shows the proportion of picker-time utilized for picking tasks. The picker-time not used for picking includes periods spent waiting for enough pick boxes to fill a picking cart or time lost at the end of a shift when picking would not be completed before the shift ends. The Simulation runtime indicates the time in seconds required for the entire simulation to run on the target infrastructure. 6.3.1 Selecting strategies In the first experiment, we compared all combinations of selected batching strategies such as EDD, Seed, Savings, MSF_Seed, and MSF_Savings, with floor selection strategies such as Random, Greedy, and MHS. During this experiment, the planner execution time fP was set to 3 minutes, and the number of orders in order selection w was set to 250. For the seed-based floor selection strategies, the initial seed order was chosen based on the smallest limit time policy. The batching process preceded/Ioor selection. Figure 6.3 illustrates the Meanfloorsmetric. Strategy combinations containing the Random floor selection strategy or the E D D batching strategy have high Mean floors values exceeding 3, making them impractical. Therefore, we decided to exclude these strategies in later experiments. Additionally, we excluded the Greedy floor selection strategy because the MHS strategy proved superior in the Late orders and Tardiness metrics, as shown in Figure 6.4 and Figure 6.5. 6.3.2 Selecting strategies' execution order In the second experiment, we compared the sequence in which the batching and floor selection problems were addressed. During this experiment, the planner execution time fP was set to 3 minutes, and the number of orders in order selection w was set to 250. For the seed-based floor selection strategies, the initial seed order was chosen based on the smallest limit time policy. Figure 6.6 illustrates the Late orders metric. We observed that the 57 6. EXPERIMENTAL EVALUATION , Distribution of the number of Late orders 'o as Floor selection strategy Batching strategy Figure 6.4: Late orders metric for Selecting strategies 58 6. EXPERIMENTAL EVALUATION Distribution of the normalized mean tardiness Floor selection strategy Batching strategy Figure 6.5: Tardiness metric for Selecting strategies Distribution of the number of Late orders Batching precedes floor selection True Seed Savings MSF_Seed MSF_Savings Batching strategy Figure 6.6: Late orders metric for Selecting strategies' execution order 59 6. EXPERIMENTAL EVALUATION Seed and Savings strategies produced lower metric values when the batching process was performed before floor selection. In contrast, the MSF_Seed and MSF_Savings strategies resulted in better performance in terms of the Late order metric when the floor selection process was carried out before batching. A similar trend can be seen in the Tardiness metric, shown in Figure 6.7, although the differences between the strategies' execution orders are quite small. Based on these observations, we decided to use the batching process before/Zoor selection for Seed and Savings strategies, and the opposite order for MSF_Seed and MSF_Savings strategies in subsequent experiments. Batching before floor selection allows us to work with multiple possibilities of SKU locations during the decision-making process, which is expected to result in more efficient batches. This may explain the improved performance observed when this order of operations is applied to Seed and Savings strategies. When batching is performed first, an order may appear to be singlefloor, but without reserving the required SKUs, there is no guarantee that it will remain so. While there are usually sufficient products avail- 60 6. EXPERIMENTAL EVALUATION Distribution of the number of visited floors per pick box for M S F S e e d Number of visited floors Figure 6.8: Visited floors per pick box for MSF_Seed batching strategy able, exceptions can occur. As a result, a batch created from orders expected to be single-floor may end up spanning multiple floors. Conversely, when floor selection is prioritized, we can be certain that batches created from single-floor orders will only visit the intended floor. This fact is likely the cause of why MSF_Seed and MSF_Savings strategies performed better when floor selection preceded batching. Plots in Figure 6.8 and Figure 6.9 provide clear evidence to support this explanation. They illustrate the distribution of the number of visited floors for pick boxes under the MSF_Seed and MSF_Savings batching strategies. In both cases, there is a noticeable decrease in the number of single-floor pick boxes when batching precedes floor selection. In this experiment, it is interesting to compare the values of the Simulation runtime metric, which is presented in Figure 6.10. The Simulation runtime is consistently shorter whenfloor selection is performed first. This reduction can be attributed to the fact that solving the problems in this order results i n smaller individual problem sizes. For completeness, the Mean floors metric is presented in Figure 6.11. The values of this metric are quite low and do not always show a positive 61 6. EXPERIMENTAL EVALUATION Distribution of the number of visited floors per pick box for MSF_Savings Number of visited floors Figure 6.9: Visited floors per pick box for MSF_Savings batching strat- egy . Distribution of the simulation runtime l , 0 9 5 j i Batching precedes floor selection Batching strategy Figure 6.10: Simulation runtime metric for Selecting strategies' execution order 62 6. EXPERIMENTAL EVALUATION Batching strategy Figure 6.11: Mean floors metric for Selecting strategies' execution order correlation to the Late orders or Tardiness, which are our main interests. This can also be observed in later experiments. Additionally, the differences in metric values are quite small, further indicating that Mean floors is not a key factor in distinguishing performance. 6.3.3 Fine-tuning seed-based batching strategies In this experiment, we focused on fine-tuning the hyperparameters for seed-based batching strategies. Different approaches can be used for seed-based strategies to select the initial seed order. We compared two specific strategies for this purpose. The first strategy selects the order with the Smallest Limit Time, referred to as SLT. The second strategy selects the order with Largest Lower Bound on the number of floors estimated to be visited, referred to as LLB. During this experiment, the planner execution time fP was set to 3 minutes and number of orders in order selection w was set to 250. Based on Late orders, Tardiness, and Meanfloors metrics, the Smallest Limit Time strategy outperforms the Largest Lower Bound, as is presented in Figure 6.12, Figure 6.13, and Figure 6.14. Therefore, we have 63 6. EXPERIMENTAL EVALUATION 12% Distribution of the number of Late orders Seed Seed order strategy • Largest Lower Bound Smallest Limit Time MSF Seed Batching strategy Figure 6.12: Late orders metric for Fine-tuning seed-based batching strategies Distribution of the normalized mean tardiness 10 5 0 Seed order strategy • Largest Lower Bound • Smallest Limit Time Seed MSF Seed Batching strategy Figure 6.13: Tardiness metric for Fine-tuning seed-based batching strategies 64 6. EXPERIMENTAL EVALUATION Distribution of the mean number of floors visited per pick box Seed order strategy Batching strategy Figure 6.14: Mean floors metric for Fine-tuning seed-based batching strate- gies decided to use Smallest Limit Time in later experiments. 6.3.4 Fine-tuning batching strategies In this experiment, we focused on fine-tuning the hyperparameters for the remaining batching strategies. We tested different values for the planner period fP and the order selection size w used for batching. We considered 1 minute, 3 minutes, and 5 minutes as reasonable values for fP. The value of 1 minute was selected as the smallest possible, given that the discrete simulation size tA is also 1 minute. The other two values were selected to avoid having too large value for fP. For the selection size w, we compared values of 250, 350, and 450, which we considered to be reasonable given that from each selection size w, at least u = 50 orders are unbatch in each batching cycle where a single order selection is used. In all cases, the planner period tP set to 1 minute performed better than other values. Based on the Late orders metric, presented in Figure 6.15, we have selected the following values for the selection size w. For the Seed, we chose a value of 350. The best value for Savings was 65 6. EXPERIMENTAL EVALUATION Distribution of the number of Late orders Batching strategy Figure 6.15: Late orders metric for Fine-tuning batching strategies 450. For both MSF_Seed and MSF_Savings, the best performing value was 250. Setting the selection size w to 450 for the Savings strategy makes sense because the way this strategy merges clusters can result in many half-full unfinished clusters at the end of the procedure (see Figure 4.3). These clusters cannot be merged due to the volume limitations of the cluster. Therefore, having enough orders in the selection is necessary to create a meaningful number of pick boxes each time. On the other hand, the smaller value of 250 for MSF_Seed and MSF_Savings may be because the first part of these strategies only creates single-floor pick boxes, which are not limited by w, as shown in Figure 4.6. Only orders that cannot be fulfilled on a single floor proceed to a second stage where w is used. Thus, in the second stage, where other fallback strategies like Seed and Savings are used, only a limited number of orders continue, and waiting to have at least w orders here could sometimes lead to several planner executions. The value of 350 is in the middle of considered values, and it is used for the Seed strategy, where w is applied to all orders. However, 66 6. EXPERIMENTAL EVALUATION Distribution of the normalized mean tardiness Batching strategy Figure 6.16: Tardiness metric for Fine-tuning batching strategies there can only be one unfinished pick box when the procedure for w orders terminates, as presented in Figure 4.4. The Tardiness metric is presented in Figure 6.16 and the Meanfloors metric in Figure 6.17. In both cases, the differences in values are quite small when the batching strategy is fixed. The observed patterns also differ from those in Figure 6.15. However, we can conclude that setting the planner period fP to 1 minute resulted in better performance compared to other values. 6.3.5 Final results In the final experiment, we compared the best-performing batching strategies together with the baseline across all main datasets, DataOl to Data06. Each measured value is an average across 10 simulation runs. To recapitulate the parameters used in the final experiment, we used the shared parameters across all experiments as presented in Table 6.3. Additionally, parameters selected by previous experiments were used. The MHS strategy was applied for floor selection. The smallest 67 6. EXPERIMENTAL EVALUATION Distribution of the mean number of floors visited per pick box Batching strategy Figure 6.17: Mean floors metric for Fine-tuning batching strategies limit time strategy was used to select initial seed orders for seed-based strategies, and the planner period fP was set to 1 minute. The selection size w was individually set based on the batching strategy. For MSF_Seed and MSF_Savings, we used w = 250. For Seed, the bestperforming value was w = 350, and for Savings, we selected w = 450. We have used the Greedy floor selection strategy combined with the F D D batching strategy as a reasonable baseline. The batching process preceded floor selection when FDD, Seed and Savings were used for batching and the floor selection process preceded batching when MSF_Seed and MSF_Savings were used for batching. When comparing batching strategies per dataset, based on the Late orders metric, as it is shown in Figure 6.18, the ranking of strategies from best to worst is consistently Savings, MSF_Savings, MSF_Seed, Seed, and FDD. Interestingly, based on the Tardiness metric, presented in Figure 6.19, the Seed strategy outperformed MSF_Seed in all cases, while the ranking of the other strategies remained the same. The difference in performance between Seed and MSF_Seed is likely due to the fact that MSF_Seed explicitly focuses on single-floor orders. However, most late orders are multi-floor orders, which in this strategy 68 6. EXPERIMENTAL EVALUATION Distribution of the number of Late orders Batching strategy I EDD Dataset Figure 6.18: Late orders metric for Final results Distribution of the normalized mean tardiness Batching strategy EDD Seed Dataset Figure 6.19: Tardiness metric for Final results 69 6. EXPERIMENTAL EVALUATION are not grouped with single-floor orders in the same pick boxes. As a result, multi-floor orders are more prone to longer delays, as they are potentially delayed by other multi-floor orders. This leads to more orders being delayed for a longer time and fewer orders experiencing only slight delays in MSF_Seed compared to Seed. A similar explanation applies to the Savings and MSFjSavings strategies. Although their ranking does not reverse, their values in the Tardiness metric are much closer. For larger datasets, the Late orders and Tardiness metrics are generally lower compared to smaller datasets. This is likely because larger datasets provide more orders to choose from, allowing for better batch optimization. However, exceptions are observed in the datasets Data03 and Data06. These datasets are less restrictive, as the time window between order creation and order limit time is generally longer on average. This can be seen in Table 6.2, where the values of the Mean raw duration and Mean shift duration metrics for Data03 and Data06 are significantly higher than those for the other datasets. This is likely the cause of the deviation in trend. The Savings strategy, which was the best-performing batching strategy, exhibited a significantly longer runtime compared to other strategies, as shown in Figure 6.20. This is likely due to the creation of many half-full clusters during the process, as is mentioned in Experiment 6.3.4, resulting in wasted effort. In Figure 6.21, the plot illustrates the distribution of the number of visited floors for pick boxes. Almost no pick boxes visited more than six floors. The EDD baseline strategy exhibits a roughly normal distribution, with a peak at three floors. In contrast, the more sophisticated Seed strategy displays a skewed normal distribution, with most pick boxes visiting two floors. The Savings and MSF_Savings strategies show an exponential distribution, while MSF_Seed has the highest percentage of pick boxes visiting just one floor, with the remainder following a normal distribution. Figure 6.22 displays the percentage of late orders. The reported values in these plot are averaged across all main datasets. A similar pattern to Figure 6.18 can be observed, where the ranking of strategies from best to worst is Savings, MSF_Savings, MSF_Seed, Seed, and EDD. 70 6. EXPERIMENTAL EVALUATION 10,000 8,000 Distribution of the simulation runtime cu I 6,000 g JS 4,000 £ 2,000 |8,604.36 Batching strategy EDD Seed Savings ^ MSF Seed MSF Savings Seed Savings ^ MSF Seed MSF Savings CO Seed Savings ^ MSF Seed MSF Savings Seed Savings ^ MSF Seed MSF Savings in CO Seed Savings ^ MSF Seed MSF Savings CO q OJ en d CM o in ,833.0 o CN in I OJ CO in I OJ CO in I OJ CO in I OJ CO CO m m in I OJ CO CO |51.30 |l90.1 93.82 288. • 39.85 149.8 ^ CO CD T T CM 0 1 CO CM CO 0 0 i^_BB CO w 5- K lO CM d °^ j£_^m co in |64.22 |214.E 25.19 |123.4. I |66.49 |207.£ 22.05 |104.4! OJ CO lO <° CO CO d £ Data01 Data02 Data03 Data04 Dataset Data05 Data06 Figure 6.20: Simulation runtime metric for Final results Number of visited floors Figure 6.21: Visited floors per pick box across all datasets 71 6. EXPERIMENTAL EVALUATION Distribution of the number of Late orders EDD Seed Savings MSF_Seed MSF_Savings Batching strategy Figure 6.22: Late orders across all datasets 6.4 Summary We have done an evaluation in five experiments. In the first four experiments, we eliminated several configuration parameter values to avoid running all combinations. In the last experiment, we compared best-performing batching strategies and presented the final results. Overall, the best-performing strategy combination, based on the Late orders and Tardiness metrics, appears to be the Savings batching strategy combined with the MHS floor selection strategy, where the batching process precedes floor selection. However, this combination leads to significantly high values of Simulation runtime. The second best performing strategy combination seems to be the MSF_Savings batching strategy combined with the MHS floor selection strategy, where the floor selection process precedes batching. This combination shows slightly worse values for the Late orders and Tardiness metrics, but the Simulation runtime is improved by an order of magnitude. 72 7 Conclusion The goal of this thesis was to design, implement, and compare several strategies for addressing the planning problem in the multi-floor orderpicking warehouse, aiming to minimize total tardiness of orders and maximize warehouse throughput. The problem involves batching customer orders on the warehouse level for collective fulfillment and selecting floors where these batches will be collected. We reviewed relevant literature and implemented multiple strategies to solve these problems. For floor selection, three strategies were implemented, with the best-performing one based on a greedy heuristic for solving the Minimal Hitting Set problem. For order batching, we developed four strategies. The best-performing batching strategy involved the iterative merging of batch pairs, minimizing the increase in the number of floors visited when combined. The strategy with comparable performance but faster in order of magnitude initially batched orders identified as solvable on a single floor before applying iterative merging for the remaining orders. The study was based on a real-world warehouse owned by the Notino company, which provided us with production data and collaborated throughout the project. For simulation analysis, we have developed a simplified simulator of Notino's warehouse that could capture the main processes needed to compare our strategies. Finally, we compared implemented strategies through simulation analysis on the production data. We believe we have achieved our goal as our simulation analysis demonstrated significant improvements of the advanced strategies over the naive ones both in total tardiness and the number of late orders. The partial results of this thesis contributed to the publication [48], and several implemented strategies were directly integrated into the more detailed warehouse simulation developed as part of the master thesis [49]. The final versions of advanced strategies were also incorporated into the existing distribution of the detailed simulator within this thesis. As of submission, three other master theses are building upon the results of this work, focusing on low-level procedures, warehouse stocking, and visualization of warehouse simulation. 73 Bibliography 1. PARDO, Eduardo G.; GIL-BORRAS, Sergio; ALONSO-AYUSO, Antonio; DUARTE, Abraham. Order batching problems: Taxonomy and literature review. European Journal of Operational Research. 2024, vol. 313, pp. 1-24. 2. GU, Jinxiang; GOETSCHALCKX, Marc; MCGINNIS, Leon F. Research on warehouse operation: A comprehensive review. European Journal of Operational Research. 2007, vol. 177, pp. 1-21. 3. C A S E L L A , Giorgia; VOLPI, Andrea; M O N T A N A R I , Roberto; TEBALDI, Letizia; BOTTANI, Eleonora. Trends in order picking: a 2007-2022 review of the literature. Production & Manufacturing Research. 2023, vol. 11, pp. 1-74. 4. What is warehouse operations [online]. Consafe Logistics, 2023 [visited on 2023-11-17]. Available from: https : //www. consafe logistics.com/knowledge-center/blog/what-is-warehouse- operations. 5. V A N K A M P E N , Tim J.; A K K E R M A N , Renzo; PIETER V A N DONK, Dirk. SKU classification: A literature review and conceptual framework. International Journal of Operations & Production Management. 2012, vol. 32, no. 7, pp. 850-876. 6. MASAE, Makusee; GLOCK, Christoph H.; VICHITKUNAKORN, Panupong. Optimal order picker routing in a conventional warehouse with two blocks and arbitrary starting and ending points of a tour. International Journal of Production Research. 2020, vol. 58, no. 17, pp. 5337-5358. 7. WEIDINGER, Felix. Picker routing in rectangular mixed shelves warehouses. Computers & Operations Research. 2018, vol. 95,139 -150. 8. Y U A N , Rong; CEZIK, Tolga; GRAVES, Stephen C. Stowage decisions in multi-zone storage systems. International Journal of Production Research. 2018, vol. 56, no. 1-2, pp. 333-343. 74 BIBLIOGRAPHY 9. YU, Mengfei; DE KOSTER, René B.M. The impact of order batching and picking area zoning on order picking system performance. European Journal of Operational Research. 2009, vol. 198, no. 2, pp. 480-490. 10. GIL-BORRÁS, Sergio; PARDO, Eduardo G.; ALONSO-AYUSO, Antonio; DUARTE, Abraham. A heuristic approach for the online order batching problem with multiple pickers. Computers & Industrial Engineering. 2021, vol. 160, p. 107517. 11. C H E N , Tzu-Li; C H E N G , Chen-Yang; C H E N , Yin-Yann; C H A N , Li-Kai. A n efficient hybrid algorithm for integrated order batching, sequencing and routing problem. International Journal ofProduction Economics. 2015, vol. 159, pp. 158-167. 12. SCHOLZ, André; SCHUBERT, Daniel; WÄSCHER, Gerhard. Order picking with multiple pickers and due dates — Simultaneous solution of Order Batching, Batch Assignment and Sequencing, and Picker Routing Problems. European Journal of Operational Research. 2017, vol. 263, no. 2, pp. 461^78. 13. V A N H E U S D E N , Sarah; V A N GILS, Teun; R A M A E K E R S , Katrien; CORNELISSENS, Trijntje; CARIS, An. Practical factors in order picking planning: state-of-the-art classification and review. International Journal of Production Research. 2023, vol. 61, no. 6, pp. 2032-2056. 14. PAN, Jason Chao-Hsien; SHIH, Po-Hsun; W U , Ming-Hung. Order batching in a pick-and-pass warehousing system with group genetic algorithm. Omega. 2015, vol. 57, pp. 238-248. 15. V A N GILS, Teun; RAMAEKERS, Katrien; CARIS, An; DE KOSTER, René B.M. Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review. European journal of operational research. 2018, vol. 267, no. 1,1-15. 16. G A D E M A N N , Noud; VELDE, Steef. Order batching to minimize total travel time in a parallel-aisle warehouse. HE transactions. 2005, vol. 37, no. 1, pp. 63-75. 75 BIBLIOGRAPHY 17. NICOLAS, Lenoble; Y A N N I C K , Frein; RAMZI, Hammami. Order batching in an automated warehouse with several vertical lift modules: Optimization and experiments with real data. European Journal of Operational Research. 2018, vol. 267, no. 3, pp. 958-976. 18. MUTER, Ibrahim; ÓNCAN, Temel. A n exact solution approach for the order batching problem. HE Transactions. 2015, vol. 47, no. 7, pp. 728-738. 19. Y A N G , Peng; Z H A O , Zhijie; GUO, Huijie. Order batch picking optimization under different storage scenarios for e-commerce warehouses. Transportation Research Part E: Logistics and Transportation Review. 2020, vol. 136, p. 101897. 20. IBM CPLEX Optimizer [online]. [N.d.]. [visited on 2024-05-14]. Available from: https : //www. ibm. com/analytics/cplex-opti mizer. 21. Gurobi Optimization Software [online]. [N.d.]. [visited on 2024-05- 14]. Available from: https : //www. gurobi . com/. 22. PARIKH, Pratik J.; MELLER, Russell D. Selecting between batch and zone order picking strategies in a distribution center. Transportation Research Part E: Logistics and Transportation Review. 2008, vol. 44, no. 5, pp. 696-719. 23. GIBSON, David R ; SHARP, Gunter P. Order batching procedures. European Journal of Operational Research. 1992, vol. 58, no. 1, 57 -67. 24. DE KOSTER, René B.M.; V A N DER POORT, Edo S.; WOLTERS, M . Efficient orderbatching methods in warehouses. International Journal of Production Research. 1999, vol. 37, no. 7, pp. 1479-1504. 25. DUKIC, Goran; OLUIC, Cedomir. Order-picking methods: Improving order-picking efficiency. International Journal of Logistics Systems and Management. 2007, vol. 3, no. 4, pp. 451-460. 26. V A N GILS, Teun; RAMAEKERS, Katrien; BRAEKERS, Kris; DEPAIRE, Benoit; CARIS. Increasing order picking efficiency by integrating storage, batching, zone picking, and routing policy decisions. International Journal of Production Economics. 2018, vol. 197, pp. 243-261. 76 BIBLIOGRAPHY 27. BUSTILLO, Manuel; M E N E N D E Z , Borja; PARDO, Eduardo G.; DUARTE, Abraham. A n algorithm for batching, sequencing and picking operations in a warehouse. In: 2015 International Conference on Industrial Engineering and Systems Management. 2015, pp. 842-849. 28. H E N N , Sebastian; SCHMID, Verena. Metaheuristics for order batching and sequencing in manual order picking systems. Computers & Industrial Engineering. 2013, vol. 66, no. 2, pp. 338-351. 29. M E N E N D E Z , Borja; BUSTILLO, Manuel; PARDO, Eduardo G.; DUARTE, Abraham. General Variable Neighborhood Search for the Order Batching and Sequencing Problem. European Journal of Operational Research. 2017, vol. 263, no. 1, pp. 82-93. 30. ELSAYED, Elsayed A. Algorithms for optimal material handling in automatic warehousing systems. International journal of Production Research. 1981, vol. 19, no. 5, pp. 525-535. 31. P A N , CHAO-HSIEN; LIU, SY. A comparative study of order batching algorithms. Omega. 1995, vol. 23, no. 6, pp. 691-700. 32. ROSENWEIN, Moshe B. A comparison of heuristics for the problem of batching orders for warehouse selection. International Journal of Production Research. 1996, vol. 34, no. 3, pp. 657-664. 33. HSIEH, Ling-Feng; H U A N G , Yi-Chen. New batch construction heuristics to optimise the performance of order picking systems. International Journal of Production Economics. 2011, vol. 131, no. 2, pp. 618-630. 34. C H E N , Mu-Chen; W U , Hsiao-Pin. A n association-based clustering approach to order batching considering customer demand patterns. Omega. 2005, vol. 33, no. 4, pp. 333-343. 35. H E N N , Sebastian; WÄSCHER, Gerhard. Tabu search heuristics for the order batching problem in manual order picking systems. European Journal of Operational Research. 2012, vol. 222, no. 3, pp. 484-494. 36. C A N O , Jose Alejandro. Parameters for a genetic algorithm: A n application for the order batching problem. International Business Information Management Association Business Review. 2019, vol. 2019, paper no. 802597. 77 BIBLIOGRAPHY 37. C A N O , Jose Alejandro; CORREA-ESPINAL, Alexander Alberto; GOMEZ-MONTOYA, Rodrigo Andres. Solving the Order Batching Problem in Warehouses using Genetic Algorithms. Information Tecnologica. 2018, vol. 29, pp. 235-244. 38. ZULJ, Ivan; KRAMER, Sergej; SCHNEIDER, Michael. A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem. European Journal of Operational Research. 2018, vol. 264, no. 2, pp. 653-664. 39. MENENDEZ, Borja; PARDO, Eduardo G.; ALONSO-AYUSO, Antonio; M O L I N A , Elisenda; DUARTE, Abraham. Variable neighborhood search strategies for the order batching problem. Computers & Operations Research. 2017, vol. 78, pp. 500-512. 40. O N C A N , Temel. MILP formulations and an iterated local search algorithm with tabu thresholding for the order batching problem. European Journal of Operational Research. 2015, vol. 243, no. 1, pp. 142-155. 41. WEIDINGER, Felix; BOYSEN, Nils; SCHNEIDER, Michael. Picker routing in the mixed-shelves warehouses of e-commerce retailers. European Journal of Operational Research. 2019, vol. 274, no. 2, pp. 501-515. 42. XIE, Lin; LI, Hanyi; L U T T M A N N , Laurin. Formulating and solving integrated order batching and routing in multi-depot AGVassisted mixed-shelves warehouses. European Journal of Operational Research. 2023, vol. 307, no. 2, pp. 713-730. 43. ARPINO, Gabriel; DMITRIEV, Daniil; GROMETTO, Nicolo. Greedy heuristics and linear relaxations for the random hitting set problem. arXiv preprint arXiv:2305.05565. 2023. 44. KARP, Richard M . Reducibility among Combinatorial Problems. In: Boston, M A : Springer US, 1972, pp. 85-103. 45. JOHNSON, David S. Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences. 1974, vol. 9, no. 3, pp. 256-278. 78 BIBLIOGRAPHY 46. IBRAHIM , Fawaz. Minimum Hitting Set Code in Java [online]. 2014. [visited on 2023­04­22]. Available from: https : //medium, com/ Of awaz . ibrahim2014/minimum­hitting­ s e t ­ c o d e ­ i n ­ j a v a ­ 25d2bb0958c7. 47. MetaCentrum [online]. CESNET, 2024 [visited on 2024­11­21]. Available from: https : //metavo . metacentrum . cz/en/index . html. 48. KŘIVÁNEK, Samuel; RUDOVÁ, Hana; SOBOTKA, Václav. M ultiFloor Warehouse Planning. Knowledge Engineering for Planning and Scheduling (KEPS). 2024. 4 pages. Banff, Alberta, Canada. 49. KUBÍK, M ilan. Notino warehouse simulator. Brno, Czech Republic, 2024. Master's thesis. Masaryk University, Faculty of Informatics. 79 A Archive Files submitted into the master thesis archive in the Information System of Masaryk University: • thesis . pdf: Text of the thesis in the PDF format. • simulator .zip: Source codes of the implemented simulator. • synthetic_data.zip: Synthetic dataset. 80 B Notation This appendix presents Table B.l, which includes the notation used in procedures. In the notation, small mathematical letters like / represent simple elements, large letters like F represent sets of simple elements and calligraphical letters like F represent sets of sets. Superscripts, such as in /v , are used to distinguish between similar variables and often use the letter of a specific word in the description. Superscripts also use Roman style to differentiate them from variables, and subscripts are used for indexing. A n underline, as in F v , signifies that the variable pertains to a single-floor context. At the same time, an overline, as in F, indicates that the variable pertains to a multi-floor context. The symbols are ordered alphabetically for easier searching. Table B.1: Notation Symbol Description A Set of J7 , set of sets of floor options A0 Set of T_o> s e t °f s e t s °f single-floor options indexed by the order o As Set of T_s> set of sets of single-floor options indexed by the S K U s B Batch, set of orders o Bc Cluster, set of orders o B Batches, set of batches B Bc Clusters, set of clusters Bc Bw Batches created from order selection, set of batches B d Distance value Set of triplets (d, By B£), where each element specifies the distance between a pair of clusters f Floor r Selected floor to visit F Set of floors F Set of floors, multi-floor option to pick the S K U Fa Set of all existing warehouse floors F v Set of selected floors to visit Continued on next page 81 B. NOTATION Table B.l - continued from previous page Symbol Description F v Set of selected floors to visit for single-floor picking of the S K U T Set of floor options, set of F Ts Set of floor options for the S K U s Set of single-floor options for the order o, i.e., set of F, such that VF G T_0, |F| = 1 T_s Set of single-floor options for the S K U s, i.e., set of F, such that VF G T_s, |F| = 1 i Unique order identifier I Items, set of tuples (s, q) m Size of the minimal hitting set, upper estimate of floors needed to visit o Order, tuple (z, tl , I) O Orders, set of orders o O R Orders fitting to the batch, set of orders o O W Order selection, set of o O Set of orders with the single-floor option 0_j Set of orders with the single-floor option on floor / O Set of orders without single-floor option O Set of Of P Pick ticket, set of tuples (s,f,q) P Pick ticket for multi-floor picking, set of tuples (s, /, q) q Quantity of S K U qf Quantity of S K U on floor / qT Quantity of S K U to be reserved s S K U tl Limit time, latest time to arrive to the sorting system u Number of orders to be left unbatched ymax Maximum volume of the pick box Dmm Minimum volume of the pick box w Number of orders in the selection of order batching algorithms 82 C Simple procedures This appendix presents and describes the helper and more straightforward procedures of implemented strategies. C.1 Floor selection C.1.1 Random floor selection The RANDOMFLOORSELECTION procedure, detailed in Figure C.1 and introduced in Section 4.1.1, is implementing the Random floor selection strategy. The procedure begins on line 1 by initializing the pick ticket P with an empty set. On lines 2-10, the procedure iterates through all tuples (s, q) G I. In each iteration, the procedure updates the pick ticket P for the corresponding tuple (s, q) by selecting floors on which it will be picked. On line 3, the set of floors F is initialized to include all floors containing the S K U s. On lines 4-10, the procedure iterates until the entire quantity q of the S K U s is satisfied. On line 5, the procedure selects a floor / uniformly randomly from the set F using the helper procedure RANDOMELEMENT. Line 6 removes the selected floor / from the set F. On line 7, the procedure assigns the current quantity of the SKU s on the selected floor / to the quantity qf. On line 8, the procedure selects the smaller value between q and qy and assigns it to qr to determine the precise quantity that will be picked from the floor q. On line 9, the quantity qr is subtracted from the remaining quantity q needed to satisfy the requirement for the SKU s. Finally, on line 10, the pick ticket P is updated. C.1.2 Greedy floor selection The GREEDYFLOORSELECTION procedure, detailed in Figure C.2 and introduced in Section 4.1.2, is implementing the Greedy floor selection strategy. The procedure begins on line 1 by initializing pick ticket P with an empty set. On line 2, the set of floors F v is initialized with an empty 83 C . SIMPLE PROCEDURES procedure RANDOMFLOORSELECTION(I) input I Items, set of tuples (s, q) output P Pick ticket, set of tuples (s,f,q) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10 foreach (s,q) E I P ^ 0 F set of floors containing S K U s 11: return P Figure C.1: Pseudo-code of the RANDOMFLOORSELECTION procedure. set. The set F v aggregates all floors selected to be visited during the subsequent loop. On lines 3-10, the procedure iterates through all tuples (s, q) in the items I, ordered ascendingly by the number of floors containing the S K U s and descendingly by the quantity q needed. This ordering prioritizes the selection of floors for the most constrained items. In each iteration, the procedure updates the pick ticket P for the corresponding tuple (s, q) by selecting the floors on which the item will be picked. On line 4, the set of floors F is initialized to include all floors that contain the S K U s. The procedure iterates on lines 5-10 until the entire quantity q of the S K U s is fulfilled. O n line 6, the procedure calls the helper procedure GREEDYSELECTFLOORANDQUANTITY, detailed in Figure C . 3 . This procedure selects a floor / and a quantity qr based on the floors F containing the S K U s, the floors F v already selected to be visited, the S K U s and quantity q to be fulfilled. The helper procedure tries to select floors already appearing in F v if possible to minimize the number of different floors to be visited. If no such floors are suitable, it selects floors from F uniformly at random. 84 C . SIMPLE PROCEDURES procedure GREEDYFLOORSELECTION(I) input I Items, set of tuples (s, q) output P Pick ticket, set of tuples (s,f,q) 1: P ^ 0 2: F V ^— 0 (set ofselectedfloors to visit) 3: foreach (s,q) G I order by number of floors containing S K U s ascending quantity q descending 4: F ^— set of floors containing S K U s 5: while q > 0 do 6: / , qr <— GREEDYSELECTFLOORANDQUANTITY(F, F V , S, q) 7: F ^ F \ { / } 8: F V <- F V U {/} 9: q ^ q — qr 10: P<-PU{(s,/, 0 then tjy quantity of S K U s on floor / qr «— min(q,qf) q «— q — qr F > F U { / } P ^ P U { ( s , / Y ) } else break return F , P Figure C.4: Pseudo-code of the M H S F I N D O N E M U L T I F L O O R S K U O P T I O N procedure. The procedure begins on line 1 by initializing a set of multi-floor options F with an empty set. On line 2, the set of floors F is initialized to include all floors that contain the S K U s. On lines 3-10, the procedure iterates through all floors / G F in random order. In each iteration, it checks whether the required quantity q is already satisfied. If not, it uses as much of the available quantity qf as possible to meet the remaining quantity q. O n line 4, the procedure checks if the required quantity q is still non-zero. If quantity q is non-zero, the procedure continues on lines 5-9. 87 C. SIMPLE PROCEDURES procedure MHSFINDALLSINGLEFLOORSKUOPTIONS(S, q) input s S K U q Quantity of S K U s to be fulfilled output Ts Set of single-floor options to pick S K U s, set of F 1: Z s <- ® 2: F set of floors containing S K U s 3: foreach / G F in random order 4: «— quantity of S K U s on floor / (checks if there is enough quantity qt of SKU s to satisfy whole required quantity q) 5: if qf > q then 6: Z S ^ Z S U { { / } } 7: return Z s Figure C.5: Pseudo-code of the MHSFINDALLSINGLEFLOORSKUOPTIONS procedure. On line 5, the procedure assigns the current quantity of the S K U s on the selected floor / to the quantity qt. Then, on line 6, it selects the smaller value between q and q t, assigning it to qr to determine the precise quantity that will be picked from the floor. O n line 7, the quantity qT is subtracted from the remaining quantity q needed to satisfy the requirement for the S K U s. On line 8, the multi-floor option set F is updated, and on line 9, the multi-floor pick ticket P is updated. Finally, if the condition on line 4 is not satisfied, the procedure breaks out of the loop. The MHSFINDALLSINGLEFLOORSKUOPTIONS procedure, detailed in Figure C.5, is used in the MHSFLOORSELECTION procedure, detailed in Figure 4.1, and also in the ORDERSINGLEFLOOROPTIONS procedure, detailed in Figure C.16. On line 1, the procedure begins by initializing a set of all singlefloor options Z s with an empty set. On line 2, the set of floors F is initialized to include all floors that contain the S K U s. 88 C . SIMPLE PROCEDURES procedure MHSCREATEPICKTICKET (I, As , P, F V ) input I Items, set of tuples (s, q) As Set of single-floor options Fs p Pick ticket for multi-floor picking, set of tuples (s, /, q) py Set of selected floors to visit output P Pick ticket, set of tuples (s,f, q) 1: P ^ 0 2: foreach (s,q) e I (calculates a set offloors that are selected to be visited and are each able to satisfy whole required quantity q ofSKU s) 3 : F ^ F V n (Uzs e^, FeEs F ) 4: if F V £ 0 then 5: f <— R A N D O M E L E M E N T ( F V ) 6: P^PU{(s,f,q)} 7: else 8: P<-PU{(s',/', u do 3: B <— EDDCREATEBATCH(O) 4: if (VOLUME(B) < vm[n ) V (|0 \ B\ < u) then 5: break 6: B^BU{B} 7: 0^0\B 8: return B Figure C.7: Pseudo-code of the EDDBATCHING procedure. On line 1, the procedure begins by initializing the set of batches B with an empty set. On lines 2-7, the procedure iterates until either the 90 C . SIMPLE PROCEDURES procedure EDDCREATEBATCH(O) input O Orders, set of o, where o is tuple (z, t, I) output B Batch, set of o constants u Number of orders to be left unbatched ymax ]y[a ximum pick box's volume 1: B ^ 0 2: while |0| > u do 3: o ^ a r g m i n ^ ^ ^ 1 ' 4: if VOLUME(B U {O}) > vmax than 5: break 6: B ^ B U { o } 7: 0 ^ 0 \ { o } 8: return B Figure C.8: Pseudo-code of the EDDCREATEBATCH procedure. number of orders in the set O falls below the number of orders u to be left unbatched, or the condition on line 4 is not satisfied. In each completed iteration, a new batch B is created. On line 3, the procedure calls the helper procedure EDDCREATEBATCH, which forms a batch B from as many orders with the earliest limit time as can fit into the pick box, selected from the orders O. On line 4, the procedure checks whether the volume of the batch B is smaller than the minimum pick box's volume vmm or if the remaining number of orders after creating the batch is less than the number of orders u to be left unbatched. If either condition is met, the procedure breaks out of the loop. Otherwise, it adds the batch B to the set of batches B and removes the orders included in B from the set of orders O , as shown in lines 6 and 7. The volume of the batch B can be smaller than the minimum pick box's volume vmm when there are not enough remaining orders to fill the batch. The EDDCREATEBATCH procedure, detailed in Figure C . 8 , begins on line 1 by initializing the batch B with an empty set. O n lines 2-7, the procedure iterates until either the number of orders in the set O falls below the number of orders u to be left unbatched, or the condition 91 C. SIMPLE PROCEDURES on line 4 is not satisfied. During each iteration, a new order o is added to the batch B . On line 3, the procedure selects the order with the smallest limit time from the order set O. O n line 4, it checks if adding this order to batch B would cause the batch's volume to exceed the maximum pick box's volume ^ m a x . If this condition is met, the procedure breaks out of the loop. If not, on lines 6 and 7, the selected order is added to batch B, and then it is removed from the set of orders O. C.2.2 Savings order batching The SAVINGSINITIALIZEDISTANCES procedure, detailed in Figure C.9, is used in the SAVINGSBATCHING procedure, detailed in Figure 4.3. The procedure begins on line 1, by initializing the set of triplets Vc , specifying distance between pairs of batches, with an empty set. O n procedure SAVINGSINITIALIZEDISTANCES (Bc ) input Bc Clusters, set of Bc output Vc Set of triplets (d, B^BS^), where each element specifies the distance between a pair of clusters 1: Vc <- 0 2: foreach (BJ, B£) G (Bc x Bc ) (checks if clusters are same or already included in Vc ) 3: if (B{ = Bc 2) V (3(d',Bl',B$) E Vc , such that {Bf,B^/ } = {B1 C ,B^})then 4: continue 5: d <— CLUSTERDISTACE(BJ, B£) 6: Vc ^VC U{(d,Bc lrBc 2)} 7: return Vc Figure C.9: Pseudo-code of the SAVINGSINITIALIZEDISTANCES procedure. lines 2-6, the procedure iterates through all pairs of clusters (B\, B£), adding a new triplet to the set Vc in each completed iteration. On line 3, the procedure checks whether the clusters B J and B£ are the same or if their distance is already included in the set Vc . If either condition is true, the procedure proceeds to the next iteration. On line 5, 92 C . SIMPLE PROCEDURES procedure SAVINGSMINDISTANCE(DC ) input Vc Set of triplets (d, BJ, B2), where each element specifies the distance between a pair of clusters output d Distance value BJ, B2 Two clusters which have corresponding smallest distance d 1: d, { B J , B2} <— R A N D O M E L E M E N T ( X > C ) 2: foreach (d'fB{',Bl') e Vc (selects a triple with a smaller distance value or equal distance value between clusters with larger volume) 3: if (d1 < d) V ((d1 = d)A ( m a x ( V O L U M E ( B ^ ) , V O L U M E ^ ' ) ) > max (VOLUME (B \), VOLUME (B2 )))) then 4: d,B\,B\ «- (d',B^,Bc 2) 5: return d, B\, B2 Figure C.10: Pseudo-code of the SAVINGSMINDISTANCE procedure. the procedure calculates the distance value d between the clusters using Equation 4.1 (see page 28). Finally, on line 6, the calculated distance together with clusters is added to the set Vc . The SAVINGSMINDISTANCE procedure, detailed in Figure C . 1 0 , is used in the SAVINGSBATCHING procedure, detailed in Figure 4.3. The procedure returns the element of Vc with the smallest distance value. When distance values are the same, it prefers clusters with larger volumes as they are more constrained. The procedure begins on line 1 by selecting a distance between two clusters uniformly randomly from the set Vc . O n lines 2-4, the procedure iterates through all distances in Vc . On line 3, the procedure checks if the current distance value d' is smaller than the selected distance d, or if they are the same, whether the volume in the fuller cluster of the pair (By B2) is greater than the volume in the fuller cluster of the pair (B^', B2). If either condition is met, the iterated triple is selected, as detailed in line 4. 93 C . SIMPLE PROCEDURES procedure SAVINGSINCREMENTALDISTANCES (£>c , B C ) input Bc Other clusters, set of BC BC New cluster, set of o output VC Set of distances between pairs of clusters set of (d,{BJ,B^}) 1: VC <- 0 2: foreach BD E Bc 3: d <— CLUSTERDISTACE(BC , BC ') 4: VC ^VC U{(d,{BC ,BC '})} 5: return VC Figure C.11: Pseudo-code of the SAVINGSINCREMENTALDISTANCES proce- dure. The SAVINGSINCREMENTALDISTANCES procedure, detailed in Figure C . l l , is used in the SAVINGSBATCHING procedure, detailed in Figure 4.3. The procedure begins on line 1, by initializing the set of triplets VC with an empty set. O n lines 2-4, the procedure iterates through all clusters BC G Bc . During each iteration, as shown on line 3, the procedure calculates the distance value d between the new cluster B C and the iterated cluster BC ' using Equation 4.1 (see page 28). On line 4, the procedure updates VC with the new triplet (d, BC , BC '). C.2.3 Seed order batching The SEEDCLOSESTORDER procedure, detailed in Figure C . 1 2 , is used in the SEEDBATCHING procedure, detailed in Figure 4.4. The procedure begins on line 1 by initializing the distance value d and the order o with default values. O n lines 2-5, the procedure iterates through all orders o' in the set of fitting orders O R . During each iteration, it checks if the current order o' is closer than the previously selected order o. On line 3, the procedure calculates the distance value d! between the cluster BC and the new order o' using Equation 4.1 (see page 28). If the new distance d' is smaller than the currently selected distance d, 94 C. SIMPLE PROCEDURES procedure input SEEDCLOSESTORDER(BC , O R ) Bc Cluster, set of o O R Fitting orders, set of o output d Distance value o Closest order 1: d,o u on line 2. This adjustment is made to accommodate the creation of single-floor pick boxes without the constraint of a minimum number of remaining orders. C.3 M H S S I Z E procedure The MHSSIZE procedure, detailed in Figure C.14, is used in Equation 4.1 (see page 28). The procedure heuristically determines the minimum number of floors required to fulfill the set of orders O. It achieves this by aggregating the floor options T for each order o E O, in the set A. The procedure then returns the size of the minimal hitting set computed for the set A. 95 C . SIMPLE PROCEDURES procedure MSFCREATEBATCH(O) input O Orders, set of o, where o is tuple (i, t, I) output B Batch, set of o constants vm&x Maximum pick box's volume 1: B ^ 0 2: while O ^ 0 d o 3: o ^ a r g m i n ^ ^ ^ 1 ' 4: if VOLUME(B U {O}) > vmax than 5: break 6: B^BU{o} 7: 0 ^ 0 \ { o } 8: return B Figure C.13: Pseudo-code of the MSFCREATEBATCH procedure. procedure MHSSIZE(O) input O Orders, set of o output m Size of minimal hitting set 1: A ^— 0 (set of sets offloor options) 2: foreach o G O 3: J- ^— ORDEROPTIONS(O) 4: ^ <- ^ U { J 7 } 5: F v ^— MHSCOVERINGGREEDYHEURISTIC(W4) 6: return |FV | Figure C.14: Pseudo-code of the MHSSIZE procedure. The procedure begins on line 1 by initializing the set A with an empty set. The set A is used to collect floor options T associated with each order o. O n lines 2-4, the procedure iterates through all orders o E O. O n line 3, the procedure calls the helper procedure ORDEROPTIONS, detailed in Figure C.15, which returns the floor options T for the order o. These options are then added to the aggregating set A on line 4. 96 C . SIMPLE PROCEDURES Example (Figure C.14). Let O = {a,b, c}. In thefirst iteration for the order a, let sets on lines 3 and 4 be assigned, such that 7 = {{1}, {3}, {6}}, and A = { { { 1 } , {3}, { 6 } } } . In the second iteration for the order b, let T = {{2,3}}, and A = { { { 1 } , { 3 } , { 6 } } , { { 2 , 3 } } } . After processing all orders, let A = { { { 1 } , {3}, { 6 } } , {{2,3}}, { { 1 } , {2}}} hold. Subsequently, on line 5, the procedure invokes the MHSCOVERINGGREEDYHEURISTIC procedure, detailed in Figure 4.2 on page 26, which heuristically computes the smallest set of floors F V necessary to fulfill all orders in the set O. Finally, on line 6, the MHSSIZE procedure returns the number of floors in the set F V . Example (Figure C.14 (continuation)). Let, the set returned on line 5 from MHSCOVERINGGREEDYHEURISTIC procedure, satisfy F V = {2,3}. Therefore, the returned valuefrom the procedure ism = | {2,3} | = 2 . The ORDEROPTIONS procedure, detailed in Figure C . 1 5 , determines the set of floor options J- to fulfill the order o. Before delving into the details, it is essential to understand the core ideas behind the procedure. If Floor selection precedes Order batching, the result is already determined by the Floor selection process. Otherwise, the procedure unites single-floor options T_ for the order with the floors appearing in a pick ticket P generated by the MHSFLOORSELECTION procedure. These single-floor options are added at the top of the floors in the pick ticket because if an order can be fulfilled on a single floor, there are likely multiple floors where this is possible. In these cases, we prefer to have multiple options to choose from, as the MHSFLOORSELECTION would otherwise return a pick ticket with a single element from which we could create only one single-floor option. On line 1, the procedure checks whether the Floor selection precedes the Order batching. If this is the case, the procedure returns all floors that appear in the pick ticket P, which is the result of the floor selection process for the items I. Otherwise, the procedure continue on line 4. Example (Figure C.15). Let o = a with items I = {(x,2), (y,3)} and let expect that the Order batching precedes the Floor selection. Therefore, the condition on line 1 is not met and the procedure continues on line 4. 97 C. SIMPLE PROCEDURES procedure ORDEROPTIONS (o) input o Order, tuple (z, tl , I) output T Set of floor options, set of F 1: if Floor selection precedes Order batching then 2: P «— result of Floor selection called with attribute I 3: return {{/| (s, f,q) G P}} 4: P ^— MHSFLOORSELECTION(I) 5: T_ <— ORDERSINGLEFLOOROPTIONS(O) 6: return F U { { / | (s,/, CO .S O •i—i 0- N ' H O •i—i + J u .s .s o cu o o S 0) u 0 - S u o •I—I 3 en Seed 1 250 27.45 7.31 2.39 10.81 0.97 121.25 Seed 1 350 27.49 7.19 2.39 10.82 0.96 117.25 Seed 1 450 27.45 7.26 2.38 10.82 0.96 110.68 Seed 3 250 27.62 7.49 2.40 10.82 0.96 110.59 Seed 3 350 27.56 7.42 2.39 10.84 0.96 117.86 Seed 3 450 27.62 7.48 2.38 10.85 0.96 119.21 Seed 5 250 27.74 7.72 2.40 10.84 0.96 117.14 Continued on next page 104 E . DETAILED TABULAR RESULTS S3 Table E.7 - continued from previous page a; 'S O ai . . en 0) 3 I I 8 1 "2 £ B 3 u G Q J " ö a> tö tö ^ p Seed 5 350 27.76 7.64 2.39 10.85 0.96 108.81 Seed 5 450 27.80 7.75 2.38 10.87 0.96 109.46 Savings 1 250 25.27 3.87 1.74 10.72 0.97 1,106.34 Savings 1 350 25.21 3.71 1.72 10.73 0.97 1,735.92 Savings 1 450 25.15 3.63 1.71 10.74 0.97 3,404.32 Savings 3 250 25.35 3.98 1.74 10.73 0.97 1,076.39 Savings 3 350 25.28 3.86 1.72 10.74 0.97 1,796.99 Savings 3 450 25.20 3.79 1.71 10.75 0.97 3,084.87 Savings 5 250 25.45 4.22 1.74 10.74 0.97 1,109.29 Savings 5 350 25.34 4.01 1.72 10.75 0.97 1,872.89 Savings 5 450 25.30 3.98 1.71 10.76 0.97 3,016.99 MSF_Seed 1 250 27.83 5.74 1.90 10.80 0.97 63.10 MSF_Seed 1 350 27.98 5.85 1.86 10.81 0.96 61.64 MSF_Seed 1 450 28.20 5.97 1.84 10.82 0.96 60.68 MSF_Seed 3 250 28.26 6.24 1.89 10.82 0.97 57.73 MSF_Seed 3 350 28.33 6.25 1.86 10.83 0.96 59.91 MSF_Seed 3 450 28.52 6.35 1.84 10.85 0.96 61.22 MSF_Seed 5 250 28.44 6.49 1.89 10.83 0.96 56.66 MSF_Seed 5 350 28.61 6.60 1.86 10.86 0.96 55.03 MSF_Seed 5 450 28.79 6.71 1.84 10.86 0.96 56.78 MSF_Savings 1 250 26.30 5.07 1.64 10.76 0.97 190.72 MSF_Savings 1 350 26.31 5.13 1.62 10.77 0.97 260.76 MSF_Savings 1 450 26.37 5.22 1.61 10.78 0.97 376.75 MSF_Savings 3 250 26.46 5.53 1.64 10.78 0.97 191.34 MSF_Savings 3 350 26.53 5.48 1.62 10.79 0.97 266.15 Continued on next page 105 E. DETAILED TABULAR RESULTS Table E.7 - continued from previous page d• 1—I S 'S N S — co ft 00 h +3 Sri -3 IIIJ co K M (ö n co i 1 ^ ^ n co 5 d £ .9 £ ^ ^ £ * 2 d - G ^ ° d d c ü 3 u d cu ^3 o> cd cd ^ 5 MSF_Savings 3 450 26.62 5.56 1.61 10.80 0.96 369.18 MSF_Savings 5 250 26.71 5.74 1.64 10.79 0.97 194.02 MSF_Savings 5 350 26.77 5.78 1.62 10.81 0.96 271.97 MSF_Savings 5 450 26.82 5.84 1.61 10.82 0.96 388.21 Table E.8: Numerical values for the experiment in Section 6.3.5 0) co cd Cd p bJD CU +J cd SH 4-> CO bO .s X, u + J cd CQ in co .£ CO •~- 0 J o cd - J CD u O O d cd CO aj u d cd a; b C re d co co 0) d d d o cd •i-H en DataOl EDD 27.47 9.18 2.93 20.66 0.96 51.30 DataOl Seed 21.13 2.84 2.04 20.55 0.96 190.19 DataOl Savings 20.21 1.23 1.47 20.42 0.97 8,604.36 DataOl MSF_Seed 21.38 2.27 1.58 20.52 0.96 93.82 DataOl MSF_Savings 20.70 1.75 1.42 20.48 0.96 288.33 Data02 EDD 32.37 12.34 2.95 15.09 0.97 39.85 Data02 Seed 22.20 3.69 2.02 14.97 0.97 149.85 Data02 Savings 21.15 1.81 1.47 14.87 0.97 5,859.16 Data02 MSF_Seed 22.49 2.78 1.58 14.94 0.97 73.17 Continued on next page 106 E. DETAILED TABULAR RESULTS Table E.8 - continued from previous page +-> I I (/I s_i to •S I 1 « ^ e 3 jS u 0) tö tö ^ d fö cö tö M M .3 .3 Data02 MSF_Savings 21.73 2.29 1.42 14.90 0.97 228.94 Data03 EDD 33.29 11.68 3.16 12.64 0.98 33.66 Data03 Seed 24.66 3.84 2.12 12.52 0.98 139.16 Data03 Savings 23.56 1.68 1.54 12.43 0.99 4,676.03 Data03 MSF_Seed 25.07 2.94 1.67 12.49 0.99 65.68 Data03 MSF_Savings 24.20 2.47 1.48 12.47 0.99 215.70 Data04 EDD 44.62 18.91 3.24 12.85 0.97 30.44 Data04 Seed 26.44 6.76 2.20 12.77 0.97 127.97 Data04 Savings 24.40 3.66 1.59 12.67 0.97 4,520.47 Data04 MSF_Seed 26.52 5.22 1.74 12.74 0.97 64.22 Data04 MSF_Savings 25.34 4.70 1.53 12.70 0.97 214.82 Data05 EDD 57.63 23.45 3.58 11.54 0.97 25.19 Data05 Seed 31.93 9.22 2.38 11.35 0.98 123.44 Data05 Savings 29.04 4.90 1.72 11.29 0.99 3,833.00 Data05 MSF_Seed 32.16 7.37 1.90 11.34 0.98 66.49 Data05 MSF_Savings 30.30 6.61 1.65 11.31 0.99 207.59 Data06 EDD 42.34 16.70 3.61 9.57 0.97 22.05 Data06 Seed 28.71 7.21 2.38 9.43 0.98 104.49 Data06 Savings 26.36 3.55 1.69 9.37 0.99 3,231.20 Data06 MSF_Seed 29.30 5.76 1.89 9.41 0.98 59.35 Data06 MSF_Savings 27.56 5.11 1.63 9.39 0.98 168.68 107 E . DETAILED TABULAR RESULTS Table E.2: Numerical values for the experiment in Section 6.3.1 +-> res 5H u cu 5H o •I—I u "3 o o ft •i-H o o o S u 0- bO U EDD Random 78.10 26.70 5.22 11.36 0.93 EDD Greedy 47.51 18.91 3.61 10.99 0.96 EDD M H S 34.92 14.61 3.38 10.78 0.97 Seed Random 34.41 15.65 4.82 11.17 0.94 Seed Greedy 29.05 8.93 2.67 10.9 0.96 Seed M H S 27.63 7.52 2.40 10.82 0.96 Savings Random 28.24 10.11 4.24 10.91 0.97 Savings Greedy 25.87 5.35 2.10 10.74 0.97 Savings M H S 25.38 3.99 1.74 10.73 0.97 MSF_Seed Random 33.66 14.82 4.46 11.0 0.96 MSF_Seed Greedy 28.94 7.83 2.22 10.83 0.96 MSF_Seed M H S 28.40 6.48 1.88 10.83 0.96 MSF_Savings Random 33.14 14.35 4.33 10.97 0.96 MSF_Savings Greedy 27.69 7.10 2.04 10.78 0.97 MSF_Savings M H S 26.84 5.84 1.72 10.78 0.97 108 E . DETAILED TABULAR RESULTS Table E.4: Numerical values for the experiment in Section 6.3.2 Q J bC Q J -t—' b C u cG CQ C D b C .su + J cG CQ C O 1/1 s to u Q J X3 S H O Q J + J tC C O S-H O o CG QJ to J-H u •i-H p . g cC Q J Q J b C cC co cn CU u c 0 •i—I +-> CC 1 Seed F 28.18 8.07 Seed T 27.60 7.49 Savings F 25.58 4.32 Savings T 25.38 4.03 MSF_Seed F 28.23 6.19 MSF_Seed T 28.34 6.43 MSF_Savings F 26.53 5.42 MSF_Savings T 26.79 5.83 2.61 10.82 0.97 89.41 2.40 10.82 0.96 113.88 1.74 10.73 0.97 807.59 1.74 10.73 0.97 1095.71 1.90 10.81 0.96 58.96 1.88 10.84 0.96 185.87 1.64 10.77 0.97 195.93 1.71 10.79 0.97 304.49 Table E.6: Numerical values for the experiment in Section 6.3.3 b C CU •4-" cS b C CQ o 4-" u JQJ " Q J C O T3 Q J CD co co CU C co Q J o Q J + J Co —1 co S H O O cG Q J co S H Q J U •i—I O H cG Q J Q J bJD cG C O C O u % Seed SLT 27.61 7.50 2.40 10.82 0.96 Seed L L B 31.61 10.46 2.63 10.78 0.97 MSF_Seed SLT 28.22 6.16 1.9 10.81 0.96 MSF_Seed LLB 29.11 6.24 1.91 10.81 0.96 109 F Additional comparisons In this appendix, we present additional plots comparing a single representative simulation run of the baseline, consisting of the EDD batching strategy combined with the Greedy floor selection strategy, against the best-performing Savings batching strategy combined with the MHS floor selection strategy. The simulation run is performed on the dataset DataOl. These additional plots aim to better illustrate how the performance is reflected in the simulation run. Figure F.l shows how throughput changes over time. The EDD batching strategy exhibits more pronounced peaks in the number of orders completed per hour, while the Savings strategy produces a much smoother curve. Figure F.2 presents a histogram of earliness, which represents the difference between the limit time and the completion time of an order. Negative earliness values indicate late orders, with each histogram column representing a 10-minute interval. The results highlight that the E D D batching strategy generates significantly more late orders compared to the Savings strategy. The observed peaks and valleys in the histogram can be explained by the operational schedule. During the period from 22:00 to 6:00, orders are not processed. A s a result, orders that were nearly completed but missed entering the sorting system before this downtime are still early, but their earliness is reduced by up to 8 hours, creating noticeable patterns in the histogram. Figure F.3 focuses on shift earliness, a metric that accounts only for the time overlapping with the warehouse shift. Unlike the earliness metric, only positive values are considered here, as negative values would not be meaningful in this context. Each column again represents a 10-minute interval. The results show a small number of orders completed with earliness larger than the total shift duration of 960 minutes. Figure F.4 compares the average time taken for different activities. Moving refers to the time spent on a conveyor belt, In queue refers to the time spent waiting for a free picker in a queue, and Picking refers to the time spent on the picking cart. The Savings strategy consistently shows lower times across all activities, with the most notable difference in 110 F. ADDITIONAL COMPARISONS T h r o u g h p u t by time 03 04 05 06 07 08 09 10 11 12 13 Day Figure F.1: Throughput by time E a r l i n e s s h i s t o g r a m Earliness [min] Figure F.2: Earliness histogram 111 F. ADDITIONAL COMPARISONS Shift earliness histogram Shift earliness [min] Figure F.3: Shift earliness histogram the time spent waiting in queues, where Savings is almost twice as efficient. Figure F.5 compares the distribution of the number of floors visited per pick box. The F D D baseline strategy exhibits a roughly normal distribution with a peak at three floors, while the Savings strategy displays an exponential distribution. 112 F. ADDITIONAL COMPARISONS Figure F.4: Activity duration Number of visited floors Figure F.5: Visited floors per pick box 113