Lower and upper bounds for the joint ...
Document type :
Pré-publication ou Document de travail
Permalink :
Title :
Lower and upper bounds for the joint batching, routing and 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]
Catusse, Nicolas [Auteur]
Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Cattaruzza, Diego [Auteur]
Integrated Optimization with Complex Structure [INOCS]
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]
Catusse, Nicolas [Auteur]
Laboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
Cattaruzza, Diego [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Ladier, Anne-Laure [Auteur]
Décision et Information pour les Systèmes de Production [DISP]
Ogier, Maxime [Auteur]

Integrated Optimization with Complex Structure [INOCS]
Publication date :
2023-03-30
English keyword(s) :
Joint Order Batching
Picker Routing
Sequencing Problem with Deadlines
Rectangular warehouse
Picker Routing
Sequencing Problem with Deadlines
Rectangular warehouse
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [en]
Warehouses are nowadays the scene of complex logistic problems integrating different decision layers. This paper addresses the Joint Order Batching, Picker Routing and Sequencing Problem with Deadlines (JOBPRSP-D) in ...
Show more >Warehouses are nowadays the scene of complex logistic problems integrating different decision layers. This paper addresses the Joint Order Batching, Picker Routing and Sequencing Problem with Deadlines (JOBPRSP-D) in rectangular warehouses. To tackle the problem an exponential linear programming formulation is proposed. It is solved with a column generation heuristic able to provide valid lower and upper bounds on the optimal value. We start by showing that the JOBPRSP-D is related to the bin packing problem rather than the scheduling problem. We take advantage of this aspect to derive a number of valid inequalities that enhance the resolution of the master problem. The proposed algorithm is evaluated on publicly available data-sets. It is able to optimally solve instances with up to 18 orders in few minutes. It is also able to prove optimality or to provide high-quality lower bounds on larger instances with 100 orders. To the best of our knowledge this is the first paper that provides optimality guarantee on large size instances for the JOBPRSP-D, thus the results can be used to assert the quality of heuristics proposed for the same problem.Show less >
Show more >Warehouses are nowadays the scene of complex logistic problems integrating different decision layers. This paper addresses the Joint Order Batching, Picker Routing and Sequencing Problem with Deadlines (JOBPRSP-D) in rectangular warehouses. To tackle the problem an exponential linear programming formulation is proposed. It is solved with a column generation heuristic able to provide valid lower and upper bounds on the optimal value. We start by showing that the JOBPRSP-D is related to the bin packing problem rather than the scheduling problem. We take advantage of this aspect to derive a number of valid inequalities that enhance the resolution of the master problem. The proposed algorithm is evaluated on publicly available data-sets. It is able to optimally solve instances with up to 18 orders in few minutes. It is also able to prove optimality or to provide high-quality lower bounds on larger instances with 100 orders. To the best of our knowledge this is the first paper that provides optimality guarantee on large size instances for the JOBPRSP-D, thus the results can be used to assert the quality of heuristics proposed for the same problem.Show less >
Language :
Anglais
Collections :
Source :
Submission date :
2023-05-04T23:22:17Z
Files
- main2.pdf
- Open access
- Access the document
- 2303.17834
- Open access
- Access the document
- document
- Open access
- Access the document