Date: October, 21st, 11h30
Place: Inria Lille-Nord Europe
Abstract: In internal warehousing logistics, the placement of the different items, i.e. SKU (Single Keeping Units), is one of the most impactful decision on the performance of warehouse activities. In the related literature, the Storage Location Assignment Problem (SLAP) has been extensively studied, almost only with class-based storage and frequency information on SKU. Most of the state-of-the-art models have been designed to be easy to implement and to tackle industrial-scale instances. Various solutions methods have been proposed in the form of policy-based heuristics. However, the pick-by-order feature, where all SKU of one order are picked altogether in one route, is often not considered with exact distances in mathematical programming, because of the class-based storage organisation. Furthermore, some recent work have been made on the integration of storage and routing decisions, but mostly with simulation methods. Few attempts have been made at tackling the problem with a full information on demand and order structure, and even less with exact methods.
Having a highly-constrained and combinatorial structure, the SLAP problem presents a strong academic interest to get a more thorough comprehension of the interactions between the layout, storage and routing decisions. This version of the SLAP problem was proven NP-hard in the strong sense. It also has a practical interest to model forward areas, where the storage assignment changes dynamically in a very versatile context. In forward areas, the storage decisions become thus more operational, and the picking policy gets a bigger impact.
In this talk, we introduce a novel formulation for the storage location assignment problem, accounting for the by-order structure of the demand. The proposed formulation presents a highly-structured constraint matrix, which is prone to decomposition methods. The Dantzig-Wolf reformulation is applied to the SLAP problem, leading to an integer linear problem, which presents the advantages of being independent from both: (i) the warehouse layout, and (ii) the chosen routing policy for order pickers. The aforementioned two aspects are convexified in the subproblems. The proposed extended formulation is tackled by a column-generation algorithm, with a decomposition of the pricing problems. Several polynomial and exponential families of valid inequalities are derived to enhance the resolution framework. The column generation is then integrated in a Branch-cut-and-Price solution method. Preliminary results show a major improvement of the dual bound between a compact mixed-integer formulation and the extended one. The branch-cut-and-price is also shown to be competitive with CPLEX. Further work is ongoing to develop new families of valid inequalities.
