Lower and upper bounds for the joint batching, routing and sequencing problem

Olivier Briant (1) , Hadrien Cambazard (1) , Nicolas Catusse (1) , Diego Cattaruzza (2) , Anne-Laure Ladier (3) , Maxime Ogier (2)

1 G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
2 INOCS - Integrated Optimization with Complex Structure
3 DISP - Décision et Information pour les Systèmes de Production

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.

Keywords: Joint Order Batching; Picker Routing; Sequencing Problem with Deadlines; Rectangular warehouse

Domains: Operations Research [math.OC]

Olivier Briant, Hadrien Cambazard, Nicolas Catusse, Diego Cattaruzza, Anne-Laure Ladier, et al.. Lower and upper bounds for the joint batching, routing and sequencing problem. 2023. ⟨hal-04052967v1⟩