A bin-packing formulation for the joint order batching, picker routing and picker sequencing problem

Briant, Olivier; Cambazard, Hadrien; Cattaruzza, Diego; Catusse, Nicolas; Ladier, Anne-Laure; Ogier, Maxime

Document type :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Title :

A bin-packing formulation for the joint order batching, picker routing and picker sequencing problem

Author(s) :

Briant, Olivier [Auteur]
Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Cambazard, Hadrien [Auteur]
Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
Catusse, Nicolas [Auteur]
Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Ladier, Anne-Laure [Auteur]
Décision et Information pour les Systèmes de Production [DISP]
Ogier, Maxime [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Conference title :

EURO 2022

City :

Espoo

Country :

Finlande

Start date of the conference :

2022-07-03

HAL domain(s) :

Informatique [cs]/Recherche opérationnelle [cs.RO]
Sciences cognitives/Informatique

English abstract : [en]

Picking is the process of retrieving products from inventory. It is considered the most expensive of warehouse operations. To reduce the picking cost, customer orders can be grouped into batches that are then collected by ...
Show more >Picking is the process of retrieving products from inventory. It is considered the most expensive of warehouse operations. To reduce the picking cost, customer orders can be grouped into batches that are then collected by pickers who travel the shortest possible distance.A column generation heuristic able to produce lower and upper bounds for the joint batching and routing problem was proposed in the literature. We show that the methodology can be extended to include the sequencing question, i.e. the additional assignment and sequencing of batches for each picker in order to meet the deadlines of the orders. This aspect is currently seen as a scheduling problem in the literature. We take a different view-point and propose a bin-packing formulation. As a result, the time aspect of the problem is considered indirectly with a drastical decrease of the number of needed variables. Moreover, we benefit from a strong family of cutting planes identified for packing problems and known as dual feasible functions. A stronger lower bound of the integrated problem can be therefore derived by adding such cuts in the formulation proposed for the joint batching and routing problem. Additionally, the bin-packing view-point provide new insights to design efficient heuristics.Optimal solutions are obtained in few seconds for small size instances with thousand of feasible batches. We also provide some results for larger instances with a column generation procedure.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL

A bin-packing formulation for the joint ... BibTeX CSV Excel RIS

A bin-packing formulation for the joint ...

BibTeX

CSV

Excel

RIS