Online Order Batching Problem: a heuristic approach for single and multiple pickers


The recent expansion of electronic commerce has promoted the development of numerous sectors around it. Among these sectors are those related to the supply chain management. Within the supply chain, logistic warehouses play a key role, being responsible for receiving, storing, and collecting products, which must be delivered to other warehouses or final customers. Generally, the objective of the operations in a warehouse are devoted to reducing delivery times. To that aim it is important to have efficient storage and collection strategies. There are multiple problems within logistic warehouses that need to be solved. Many of these problems can be defined as optimization problems. Among them, problems related to theorder picking process stands out. Order picking can be tackled with different picking policies. Among the best-known order picking policies, we can find “Strict Order Picking” and “OrderBatching”. The former one is characterized by picking each order individually, i.e. the picker starts a new collection route each time a new order needs to be picked. On the other hand, theOrder Batching policy is characterized by the fact that orders are grouped into batches, and thecollection of all the orders associated with the same batch is carried out on the same picking route, normally by a single picker. This Doctoral Thesis focuses on solving several optimization problems belonging to thefamily of Order Batching Problems (OBP), which appear when a batch collection policy isused in the picking process of a warehouse. More specifically, this Doctoral Thesis focuseson solving the task of determining the grouping of orders into batches, commonly named as “batching”. The resolution of a problem belonging to the OBP family implies also addressing other tasks such as: determining the next batch to be picked, selecting the order picker whowill carry out the picking, establishing the picking route within the warehouse, determining the time that a picker must wait before starting a new route, etc. These tasks vary dependingon the variant of the problem studied. A possible classification of the variants would divide them into Offline/Online, depending on the availability of information regarding to the arrivalof new orders. It is also possible to classify them as single picker/multiple pickers depending onwhether there are one or several pickers collecting the orders simultaneously. Variants of theproblem can also be identified according to the objective function studied. This Doctoral thesis focuses on the online variants of the problem, which are characterized by being dynamic optimization problems where orders arrive at the system continuously, i.e., while the collection process is undergo. In this context, there is no information about the nextorder that will arrive at the system. This type of scenario could be considered the most realistic nowadays, given that the online sale of products is continuously happening, as e-Commerce platforms operate 24 hours a day. Among the different online variants of the OBP family, inthis Doctoral Thesis, the batching task is studied both: single picker context, and multiplepickers context. In addition, the task that determines the time window is also highlighted and studied. This task occurs only in online variants of the problem and it has been little studied inthe literature, but it has a great impact on the obtained results. Determining the time window consists of determining the best time for the picker to leave and collect the generated batch.Delaying the start of the picking route means that new orders may arrive at the system, which could benefit a better composition of the remaining batches. The resolution of the batching task belongs to the NP-hard computational complexity class, so it is not possible to efficiently determine the optimal solution to the problem in a reasonableamount of time, when the size of the problem is large, as it is the case in most real situations. Heuristic and metaheuristic techniques are used to address the problems described above, since these techniques provide high-quality solutions for NP-Hard problems in short computingtimes. Heuristics are used both to generate an initial solution to the problem (constructive heuristics) and to search for better-quality solutions in the neighborhood about a given solution(search heuristics). The latter present the difficulty of being trapped in local optima, thatis, in the best possible solution within a specific neighborhood. Metaheuristics are high-level heuristics capable of escaping from a local optimum and reaching others belonging to different neighborhoods. In the case of this Doctoral Thesis, different construction and local search algorithms have been proposed to solve the problems, together with the use of the Variable Neighborhood Search and Greedy Randomized Adaptive Search Procedure metaheuristics. The algorithms proposed for each of the different variants studied have been able to improve, in their respective contexts, the existing algorithms in the state of the art. Finally, we point out that themost relevant results obtained have been published in prestigious international scientific forums.