# A column generation approach to solve the Joint Order Batching and Picker Routing Problem with picker congestion

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. A column generation approach to solve the Joint Order Batching and Picker Routing Problem with picker congestion. MIP South America 2025 - Mixed Integer Programming Workshop South America, Dec 2025, Vina del Mar, Chile. hal-05461702

HAL Id: hal-05461702

https://inria.hal.science/hal-05461702v1

Submitted on 16 Jan 2026

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 CC BY 4.0 - Attribution - International License
# A column generation approach to solve the Joint Order Batching and Picker Routing Problem with picker congestion

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

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

³ School of Industrial Engineering, Pontificia Universidad Católica de Valparaíso, Valparaíso, Chile

## 1 Introduction and motivation

In warehouse operations, order picking stands out as one of the most critical processes, with its primary objective being the preparation of customer orders. This work focuses on a classic picker-to-parts system, where human pickers push a trolley around the warehouse to collect different items. From an operational point of view, two main decisions must be taken: order batching and picker routing. The Order Batching Problem (OBP) deals with assigning customer orders to pickers, while the Picker Routing Problem (PRP) consists in determining, for a single picker, the sequence in which the products are collected. The integration of both decisions defines the Joint Order Batching and Picker Routing Problem (JOBPRP), which remains challenging to solve [2].

While congestion is a well-known phenomenon in warehouses with human pickers, it is rarely considered in optimization studies. The existing literature mainly analyzes congestion through simulation, often as an isolated effect, whereas most works addressing the JOBPRP assume ideal conditions without congestion, despite its significant impact on cost, performance, and safety [1]. This work proposes a mathematical model and a solution method for the JOBPRP that explicitly considers congestion aspects.

## 2 Modeling congestion and problem formulation

We propose a rough estimation of congestion levels by introducing a time discretization. In each time interval of the planning horizon, an extra delay is determined by using a non-linear function based on the number of pickers in each sub-aisle. The delay is incurred by all pickers in that sub-aisle.
To tackle the problem, we proposed an exponential Mixed Integer Programming (MIP) formulation. In this formulation, variables (or picker routes) are depicted as a sequence of locations followed by the picker, along with the time each location is visited and the level of congestion in each visited sub-aisle and time intervals. As the timing on the routes depends on the levels of congestion, the mathematical formulations guarantee to select routes that are compatible (have same levels of congestion), ensuring that each order is collected without using more than the available pickers.

# 3 A column generation heuristic

To solve the Joint Order Batching and Picker Routing Problem (JOBPRP) with picker congestion, we propose a column generation-based heuristic based on the resolution of the root node. In each iteration of the procedure, the pricing problem is tackled using a dedicated labeling algorithm. As a main advantage, the labeling algorithm enables us to address the main problem complexities by precisely computing the congestion value and discarding the exploration of not relevant labels. The column generation algorithm starts with an initial set of columns derived from the optimal solution of the classic JOBPRP and reinforce the performance by a primal heuristic.

At the end of the column generation process, a lower bound is reported. This bound is derived from a lower bound of the solution of the JOBPRP, a Lagrangian bound, or the optimal solution of the linear relaxation of the extended formulation. Finally, an upper bound is obtained by solving the integer problem with the columns generated so far.

# 4 Computational experiments

Results show the ability of the algorithm to improve the initially provided solution and reduce the initial optimality gap. The algorithm is strongly dependent on the number of order lines, limiting its performance in large-sized instances. Although there are instances where the initial lower bound of the JOBPRP can be improved, its computation requires solving the pricing problem to optimality, representing a significant challenge.

# References

[1] F. Ciarallo B. Heath and R. Hill. An agent-based modeling approach to analyze the impact of warehouse congestion on cost and performance. *The International Journal of Advanced Manufacturing Technology*, 67(1-4):563–574, October 2012.

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