# 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

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

## 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. Odysseus 2024-the Ninth International Workshop on Freight Transportation and Logistics, May 2024, Seville, Spain. hal-04865835

HAL Id: hal-04865835

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

Submitted on 6 Jan 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published 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_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A column generation approach to solve the Joint Order Batching and Picker Routing Problem with picker congestion

Pablo Torrealba-González

Univ. Lille, CNRS, Inria, Centrale Lille,
UMR 9189 CRISTAL, F-59000 Lille, France

Email:pablo.torrealba-gonzalez@inria.fr

Dominique Feillet

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

Maxime Ogier, Frédéric Semet

Univ. Lille, CNRS, Inria, Centrale Lille,
UMR 9189 CRISTAL, F-59000 Lille, France

## 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. It represents the majority of total operational costs. Warehouses can operate in different ways depending on the level of technology. Operations may involve humans, robots, or both, as presented in [3]. This work focuses on a classic picker-to-parts system, where pickers push a trolley around the warehouse to collect different items.

Despite the increasing popularity of robotic operations in recent years, many companies still employ human operators for several reasons. Firstly, humans offer flexibility by easily adapting to changes in operations such as highly fluctuating demand. Additionally, the high initial investment required to purchase infrastructure discourages the adoption of automated systems.

From an operational point of view, the main decisions are order batching and picker routing. The Order Batching Problem (OBP) deals with assigning different customer orders to a given set of pickers, and the Picker Routing Problem (PRP) is defined as determining, for a single picker, the sequence in which the products to be picked are collected. Both problems have as objective the minimization of the traveled distance or
time. When solving the OBP with an optimal routing policy, the focus shifts to integrating
both OBP and PRP. This integrated problem, known as the Joint Order Batching and
Picker Routing Problem (JOBPRP), is usually solved using a column generation based
approach as proposed in [2] or [4].

In warehouses, avoiding congestion is challenging and carries significant consequences for cost, performance, and safety [1]. The existing literature about congestion in warehouses mainly focuses on evaluating congestion by simulation in the context of narrow aisles or picker blocking. When solving the JOBPRP, works in the literature usually assume a no congestion situation. However, in practice, congestion is a very well known phenomenon in warehouses with human pickers. In this work, we propose a solution method for the JOBPRP that considers congestion aspects.

## 2 Modeling congestion and problem formulation

Given the complexities of human behavior, precise coordination of pickers does not seem
relevant. Therefore, we propose a rough estimation of congestion levels by introducing
time discretization, and dividing the planning horizon into time intervals. In our analysis,
we examine a rectangular warehouse layout featuring parallel cross and vertical aisles.
Vertical aisles contain the products, and cross-aisles serve as navigation paths for pickers
throughout the warehouse. In each time interval, an extra delay is determined by using
a function based on the number of pickers in each sub-aisle (the intersection of the space
between two consecutive cross-aisles and a vertical aisles). The delay is applied to all
pickers in that sub-aisle. It is crucial to note that congestion computation is typically
nonlinear, as delay in one period leads to additional delay in the future. Moreover, includ-
ing congestion in time minimization can result in undesirable situations. For instance,
an optimal solution could consider picker waiting times, or a picker walking a distance
longer than the shortest path between two consecutive picking locations. Such situations
are not realistic in practice and should be avoided in a feasible solution of JOBPRP when
considering congestion.

In particular, we consider a rectangular warehouse with *v* vertical aisles and *b* blocks, a set *K* of pickers with a trolley capacity *C*. 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 JOBPRP with picker congestion and provide a performance guarantee (lower and upper bounds), we propose a heuristic based on column generation. The linear relaxation of the extended MIP formulation is solved through a column generation approach. In each iteration, the pricing problem is tackled using a labeling algorithm. Note that column generation approaches for the JOBPRP without congestion do not use labeling algorithm techniques to solve the pricing problem since the order requirement (all products of an order must be collected in the same route) is challenging to consider. However, when considering congestion, the timing aspect does not permit easily adapting the existing pricing solvers in the literature. Using a labeling algorithm permits easily incorporating timing aspects and non-linearity of congestion.

The labeling algorithm relies on representing partial solutions as a set of attributes denoted as a label. Labels are propagated from a picking location to the next one until the represented solution reach the depot. To speed up the process and avoid evaluating every potential label, two main components have been introduced. A completion bound, derived from optimistic dual values, and a time bound obtained from the analysis of an optimal solution of the JOBPRP are proposed.

As mentioned earlier, congestion involves a nonlinear component that can lead to undesirable situations. As a main advantage, the labeling algorithm enables us to address these complexities by precisely computing the congestion value and discarding the exploration of labels with undesirable situations. The column generation algorithm starts with an initial set of columns derived from the optimal solution of the classic JOBPRP. At the end of the column generation process, we obtain a lower bound, which can be 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

We generated a new benchmark of instances, considering scenarios of interest in terms of congestion. Table 1 presents preliminary results obtained by running our Column Generation Heuristic (CGH) with a time limit of 40 minutes. The first six columns report information about the instances: *ID*: an identifier, *v*: the number of vertical aisles, *b*: the number of blocks, *|K|*: the number of pickers, *C*: the capacity of each trolley, *|OLN|*: total number of order lines (for a given order an order line indicates a product to be collected). The next two columns report information about an initial solution, obtained by solving the JOBPRP with no congestion. $Z_j^*$ is the optimal objective, and $UB_j$ is an upper bound obtained by computing the congestion in the JOBPRP solution. The last columns report
<table><caption>Table 1: Preliminary results</caption><thead><tr><th rowspan="2">ID</th><th colspan="5">Instance</th><th colspan="2">Initial Solution</th><th colspan="4">Column generation heuristic</th></tr><tr><th>v</th><th>b</th><th>|K|</th><th>C</th><th>|OLN|</th><th>Z<sup>*</sup><sub>J</sub></th><th>UB<sub>J</sub></th><th>LB<sub>CG</sub></th><th>UB<sub>CG</sub></th><th>opt gap</th><th>imp</th></tr></thead><tbody><tr><td>1</td><td>12</td><td>1</td><td>6</td><td>9</td><td>30</td><td>594</td><td>628</td><td>594</td><td>596.8</td><td>0.5%</td><td>5.0%</td></tr><tr><td>2</td><td>6</td><td>3</td><td>4</td><td>20</td><td>35</td><td>656</td><td>714.4</td><td>656</td><td>691.4</td><td>5.1%</td><td>3.2%</td></tr><tr><td>3</td><td>12</td><td>1</td><td>8</td><td>9</td><td>37</td><td>834</td><td>878.7</td><td>834</td><td>838.4</td><td>0.5%</td><td>4.6%</td></tr><tr><td>4</td><td>6</td><td>3</td><td>6</td><td>14</td><td>43</td><td>814</td><td>853.1</td><td>814</td><td>817.6</td><td>0.4%</td><td>4.2%</td></tr><tr><td>5</td><td>12</td><td>2</td><td>10</td><td>9</td><td>49</td><td>1430</td><td>1505</td><td>1430</td><td>1484.9</td><td>3.7%</td><td>1.3%</td></tr><tr><td>6</td><td>16</td><td>2</td><td>10</td><td>9</td><td>49</td><td>1954</td><td>2084.4</td><td>1965</td><td>1979.6</td><td>0.7%</td><td>5.0%</td></tr><tr><td>7</td><td>6</td><td>3</td><td>10</td><td>9</td><td>49</td><td>1328</td><td>1431.5</td><td>1328</td><td>1402.5</td><td>5.3%</td><td>2.0%</td></tr><tr><td>8</td><td>12</td><td>1</td><td>6</td><td>20</td><td>57</td><td>914</td><td>964.3</td><td>914</td><td>927.7</td><td>1.5%</td><td>3.8%</td></tr><tr><td>9</td><td>6</td><td>3</td><td>6</td><td>20</td><td>57</td><td>1054</td><td>1128.5</td><td>1054</td><td>1102.9</td><td>4.4%</td><td>2.3%</td></tr><tr><td>10</td><td>16</td><td>2</td><td>6</td><td>20</td><td>59</td><td>1744</td><td>1838.5</td><td>1744</td><td>1746.3</td><td>0.1%</td><td>5.0%</td></tr><tr><td>11</td><td>12</td><td>1</td><td>5</td><td>30</td><td>92</td><td>994</td><td>1045.4</td><td>994</td><td>1004.4</td><td>1.0%</td><td>3.9%</td></tr><tr><td>12</td><td>12</td><td>1</td><td>5</td><td>68</td><td>219</td><td>1644</td><td>1769.3</td><td>1644</td><td>1690.4</td><td>2.7%</td><td>4.5%</td></tr></tbody></table>

information about CGH: $LB_{CG}$ and $UB_{CG}$ report the lower and upper bounds, gap is the optimality gap and imp reports the improvement of the solution w.r.t. the initial solution.

The 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 optimality pricing problem, representing a significant challenge. Future research aims to evaluate the approach on larger instances and enhance the labeling prioritization to accelerate the production of promising columns.

## 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] O. Briant, N. Catusse A. Ladier H. Cambazard, D. Cattaruzza, and M. 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.

[3] M. Melacini G. Marchet and S. Perotti. Investigating order picking system adoption: a case-study-based approach. *International Journal of Logistics Research and Applications*, 18(1):82-98, August 2014.

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