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

Abstract

Warehouses are 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 related to bin packing is proposed. It is solved with a column generation heuristic able to provide lower and upper bounds on the optimal value. We start by showing that the JOBPRSP-D is related to a bin packing problem as opposed to a 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 a few minutes. It is also able to prove optimality or to provide high-quality lower bounds on larger instances with 100 orders as long as the picker's capacity is small enough. Finally, new upper bounds are found on all the instances except two of the benchmark considered. To the best of our knowledge this is the first article that provides optimality guarantee on large size instances for the JOBPRSP-D; the results can therefore be used to assert the quality of heuristics proposed for the same problem.