EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

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

Invited abstract in session MA-52: Combinatorial optimization approaches for freight deliveries and home services, stream Combinatorial Optimization.

Monday, 8:30-10:00
Room: 8003 (building: 202)

Authors (first author is the speaker)

1. Maxime Ogier
Centrale Lille
2. Hadrien Cambazard
Operations Research, G-SCOP
3. Nicolas Catusse
Grenoble INP / G-SCOP

Abstract

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 based on column generation.
A bottleneck of such approaches is to efficiently solve the pricing problem, that is 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.
At the core of this pricing problem lies a profitable traveling salesman problem (TSP) in a
rectangular warehouse.
Dynamic programming (DP) approaches can solve efficiently this TSP for such layouts.

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.
Such MIP formulation has been studied for the special case of warehouses with a single bloc of aisles.
We generalize to the case with several blocks, and propose state space restrictions of the DP to heuristically solve the pricing problem.

The proposed approach is validated on instances from the literature.

Keywords

Status: accepted

Back to the list of papers