# Integrating picker congestion in the solving of the Joint Order Batching and Picker Routing Problem

Pablo Torrealba-González, Dominique Feillet, Maxime Ogier, Frédéric Semet

► To cite this version:

Pablo Torrealba-González, Dominique Feillet, Maxime Ogier, Frédéric Semet. Integrating picker con- gestion in the solving of the Joint Order Batching and Picker Routing Problem. ROADEF 2024: 25ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Mar 2024, Amiens, France. hal-04865813

HAL Id: hal-04865813

https://hal.science/hal-04865813v1

Submitted on 6 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Integrating picker congestion in the solving of the Joint Order
Batching and Picker Routing Problem

Pablo Torrealba-González¹, Dominique Feillet², Maxime Ogier¹, Frédéric Semet¹

¹ Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France
{pablo.torrealba-gonzalez,maxime.ogier,frederic.semet}@centralelille.fr,

² Mines Saint-Etienne, Univ. Clermont Auvergne, LIMOS UMR CNRS 6158, Centre CMP, Gardanne F-13541, France
feillet@emse.fr

Mots-clés: picker routing, order batching, congestion, dynamic programming

# 1 Introduction and motivation

In the context of warehouse operations, order picking stands out as one of the most crucial processes. Customers place orders for various products, and the primary objective of the order picking process is to efficiently prepare these orders. In this work, we examine a rectangular warehouse layout featuring parallel cross and vertical aisles. Vertical aisles contain the products, and cross-aisles serve as navigation paths throughout the warehouse.

Typically, human operators are responsible to perform picking activities. They navigate through the warehouse, pushing a trolley, and collecting the required products for each order. From a managerial perspective, the initial decision involves determining how to group different orders and assign them to the pickers. The Order Batching Problem (OBP) answers this question by minimizing the distance traveled for a fixed routing policy as s-shape or largest gap. The second decision is to determine, for each picker, the path to follow in order to collect a set of products in the warehouse, with the objective of minimising the total distance or time. This problem is known as the Picker Routing Problem (PRP). When both decisions are considered in an integrated way, the problem to be solved is refered as the Joint Order Batching and Picker Routing problem (JOBPRP).

In existing literature, the common objective function is to minimize the total distance or time, assuming no congestion effects. In practice the effect of congestion could not be ignored, and is recognized as an undesirable situation that can produce an extra delay on total time or even accidents. In this work, we present an algorithm that simulates the travelling of a set of pikers operating at the same time in the warehouse. This algorithm provides an evaluation of the total time including delays due to congestion. In addition, we propose an exponential Mixed Integer Programming (MIP) formulation and a solving algorithm to address the JOBPRP including congestion.

# 2 Modeling congestion

One of the primary challenges in incorporating congestion into a mathematical model lies in the human nature of the picker. The complexities of human behavior make it difficult to precisely coordinate pickers. As a solution, we propose a rough approach to estimate congestion levels by introducing time discretization, dividing the planning horizon into discrete intervals. To compute congestion within each time interval, we calculate the number of pickers visiting a specific sub-aisle (intersection between two consecutive cross-aisles and a vertical aisle) and determine an additional travel delay. This delay is then applied uniformly to all pickers operating in that sub-aisle.
It is important to note that congestion models are typically non-linear due to the recursive nature of delays caused by congestion. In our work, we propose a mathematical formula to quantify the total time of an aisle traversal, including the extra delay induced by congestion. This formula is used in a computational algorithm designed to calculate the total completion time for a group of pickers operating at the same time.

# 3 The JOBPRP including congestion

In the existing literature, the Joint Order Batching and Picker Routing Problem (JOBPRP) is commonly solved using a column generation-based approach, as is presented in [1] or [2]. In our approach, to incorporate congestion, we introduce an exponential Mixed Integer Programming (MIP) formulation. In this formulation, variables represents exact sequences and timing of each location visited within the warehouse. The proposed formulation ensures the selection of a feasible number of routes (available pickers) that are compatible in terms of congestion, and collect all customer orders.

Traditionally, the pricing problem in the literature is tackled using a dynamic programming approach, using the characteristics of a rectangular warehouse to compute optimal distances. However, when congestion is taken into account, the pricing problem must incorporate timing considerations and precisely define the tour direction. Consequently, we introduce a new pricing algorithm designed to handle these complexities. The pricing is executed through a labeling algorithm. The algorithm is capable of addressing the non-linearity of congestion and avoid undesirable situations that may arise while minimizing congestion, such as following inefficient paths or imposing waiting times on pickers. The JOBPRP including congestion is solved using a column generation heuristic, based on the resolution of the linear relaxation through column generation. At the end of this process, both a lower and an upper bound are reported.

# 4 Experimentation and conclusions

To assess congestion, we generated a new benchmark of instances, considering various scenarios that are particularly relevant for congestion, such as warehouse size, storage policy, and orders composition. Computational experiments were conducted with two primary objectives : firstly, to evaluate the congestion in an optimal solution of the JOBPRP and its characteristics, and secondly, to evaluate the performance of the proposed solving algorithm.

This work introduces a mathematical approach to model congestion in the picking process, emphasizing the significance of its most relevant components. Specifically, we applied this approach to the JOBPRP and presented a column generation heuristic to address the problem. Column generation heuristic demonstrated its effectiveness in improving initial solutions.

Future work is directed towards refining the solving procedure, with a focus on improving the quality of the lower bound and enhancing the speed of searching for negative reduced-cost columns.

# Références

[1] Olivier Briant, Hadrien Cambazard, Diego Cattaruzza, Nicolas Catusse, Anne-Laure Laidier, and Maxime Ogier. An efficient and general approach for the joint order batching and picker routing problem. *European Journal of Operational Research*, 285(2):497-512, September 2020.

[2] Julia Wahlen and Timo Gschwind. Branch-price-and-cut-based solution of order batching problems. *Transportation Science*, 57(3):756-777, 2023.