# Dynamic programming state space restrictions to solve the joint order batching and picker routing problem via column generation

Hadrien Cambazard, Nicolas Catusse, Maxime Ogier

► To cite this version:

Hadrien Cambazard, Nicolas Catusse, Maxime Ogier. Dynamic programming state space restrictions to solve the joint order batching and picker routing problem via column generation. EURO 2024-33rd Conference of the Association of European Operational Research Societies, Jul 2024, Copenhagen, Denmark. hal-04864958

HAL Id: hal-04864958

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

Submitted on 4 Feb 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
Dynamic programming state space restrictions in column
generation for order batching

Hadrien Cambazard¹, Nicolas Catusse¹, Maxime Ogier²

¹ CNRS, Grenoble INP, G-SCOP, University of Grenoble Alpes, Grenoble 38000, France
[hadrien.cambazard, nicolas.catusse]@grenoble-inp.fr

² Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISTAL, F-59000 Lille, France
maxime.ogier@centralelille.fr

**Mots-clés**: order batching, dynamic programming, state space restriction, pricing problem, column generation.

# 1 Introduction and motivation

This paper is concerned with warehouse management problems where the picker routing problem is a core sub-problem. More specifically, we address the joint order batching and picker routing problem (JOBPRP). Given a set of orders to collect, each order being composed of several items located in a warehouse, the JOBPRP consists in batching orders into capacitated trolleys such that the total travelled distance to collect all the items of the orders is minimized. We are interested in algorithms with optimality guarantees (lower and upper bounds). We investigate a class of algorithms based on exponential formulations solved using column generation techniques. A bottleneck of such approaches is to efficiently solve the pricing problem. The pricing can be stated as a profitable order picking problem where all products of an order must be collected together in the same tour and a price is gained for collecting an order. This price typically relates to the dual values of the master problem.

At the core of this pricing problem lies a profitable traveling salesman problem (TSP) in a rectangular warehouse made of vertical aisles and horizontal cross-aisles. It turns out that the TSP can be solved efficiently in practice for such layouts using dynamic programming (DP) approaches ([4, 2]). The column generation based approaches to solve the JOBPRP [1, 3, 5] are strongly based on this efficient solving of the TSP in rectangular warehouse. In this work, we extend the DP approach to the profitable variant. The directed acyclic graph underlying the DP can be used to provide a powerful Mixed Integer Programming (MIP) formulation where the order requirements (all products of an order must be collected together) can be taken into account with linking constraints. Moreover, additional side constraints related to orders such as capacity of the trolley can be easily added. The key idea of the proposed MIP formulation is to model the profitable TSP as a path in a directed acyclic graph thus leading to a very strong linear relaxation for the overall order batching problem. [3] proposed to use such MIP formulation for the pricing problem for the case of warehouses with a single bloc of aisles. In this work, we generalize to the case with several blocks.

# 2 Heuristically solving the pricing problem

Solving the pricing MIP model to optimality can be computationally difficult and is not required as long as a variable of negative reduced cost can be identified. Therefore, efficient pricing techniques often use fast heuristics to quickly identify a column of negative reduced cost when it exists avoiding costly calls to the exact pricing algorithm. An elegant way to implement this idea consists in restricting the size of the DP graph underlying the MIP model,
by only considering the vertices and arcs most likely to occur in a column of negative cost. The
resulting MIP model can be solved faster, providing feasible solutions (i.e upper bounds) for
the pricing problem. To restrict the DP graph, we propose two ideas detailed in the following.

## 2.1 State space restriction

A first restriction of the DP graph is based on limiting the types of vertices and arcs. This
can be seen as a state space restriction of the DP. It is defined by observing the most common
states/transitions involved in optimal paths. Typically, states corresponding to a partial path
involving more than one connected components, or transitions corresponding to a largest gap
traversal of a sub-aisle are not very frequent. Ignoring such states and transitions can greatly
reduce the size of the graph for a small loss regarding the objective value.

## 2.2 Sample restriction biased by dual values

Consider an optimal picker route to collect a batch of orders, it corresponds to a path in the
DP graph with its associated vertices and arcs. We can therefore evaluate the vertices and arcs
often required by sampling a set of interesting batches and their optimal routes. Starting from
an empty DP graph, a number of TSPs in rectangular warehouse are thus solved for random
batches to collect interesting vertices and arcs for augmenting the DP graph. Moreover, at a
given iteration of the column generation, the dual variable associated with an order gives the
incentive for including that order in the batch. Typically, a large value should increase the
chance of the order to belong to a column of negative reduced cost since the dual value can
compensate for the increase of distance more easily. A random batch sample can thus be built
with a random distribution biased by the dual values.

# 3 Results

We evaluate our pricing heuristics with state space restrictions and sample restrictions biased
by dual values on a set of 138 instances from the literature with two blocks warehouse and up to
50 orders. We can solve the linear relaxation to optimality within 2 hours for 133 instances ([1]
was solving 74 instances). By using the proposed pricing heuristics, the exact pricing is called
only 1.5 times in average per instance. We also validated that both ideas of graph restrictions
are necessary to obtain such results.

The future work is to propose a solving method to quickly provide good lower bounds for
the pricing problem.

Références

[1] Olivier Briant, Hadrien Cambazard, Diego Cattaruzza, Nicolas Catusse, Anne-Laure Ladier, and Maxime Ogier. An efficient and general approach for the joint order batching and picker routing problem. *Eur. J. Oper. Res.*, 285(2):497-512, 2020.

[2] Hadrien Cambazard and Nicolas Catusse. Fixed-parameter algorithms for rectilinear steiner tree and rectilinear traveling salesman problem in the plane. *European Journal of Operational Research*, 270(2):419-429, 2018.

[3] Katrin Heßler and Stefan Irnich. Modeling and exact solution of picker routing and order batching problems. Technical Report LM-2022-03, Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz, Mainz, Germany, 2022.

[4] H Donald Ratliff and Arnon S Rosenthal. Order-picking in a rectangular warehouse : a solvable case of the traveling salesman problem. *Operations research*, 31(3):507-521, 1983.

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