Titre :

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

Auteur(s) :

Cambazard, Hadrien [Auteur]
Groupe Recherche Opérationnelle de Grenoble [G-SCOP_GROG]
Catusse, Nicolas [Auteur]
Groupe Recherche Opérationnelle de Grenoble [G-SCOP_GROG]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Titre de la manifestation scientifique :

EURO 2024-33rd Conference of the Association of European Operational Research Societies

Ville :

Copenhague

Pays :

Danemark

Date de début de la manifestation scientifique :

2024-07-01

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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 arectangular 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 intoaccount 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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL