A bin-packing formulation for the joint ...
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]
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 - 32nd Conference of the Association of European Operational Research Societies
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
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 >
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 :
Source :