Assigning and sequencing storage locations under a two level storage policy: Optimization model and matheuristic approaches

We deal with a problem which combines storage location assignment with sequencing decisions about the assigned storage locations. Given a set of different product types, with the corresponding storage demand, a set of capacitated storage locations has to be assigned to each product type for the corresponding storing operations. In addition, a suitable sequencing of the assigned storage locations must be devised for each product type, i.e., it has to be decided the ordering with which the storage locations will be filled up during the storing operations. A motivation is that a First-In First-Out (FIFO) picking criterion among storage locations is required per product type. The sequencing established for the assigned storage locations will therefore allow to easily implement the FIFO policy in the successive order picking. Moreover, the selected sequencing also determines the availability of extra storage per product type, on top of pairs of consecutive storage locations along the sequence. The goal is to maximize the storage capacity which remains available after the assignment of the storage locations. We prove the NP-Hardness of the problem and we model it as a constrained multicommodity flow problem on an auxiliary graph. We then propose a Mixed-Integer Linear Programming (MILP) model, with some valid inequalities, based on the multicommodity flow formulation. Two relaxations are proposed as well to estimate the quality of the model solutions. Two matheuristic approaches are then designed starting from the MILP model. The proposed methodology is applied to a case study related to a large warehouse with a high stock rotation index in tissue logistics, which motivated our study. Computational results on a wide test bed related to such a real application context show the efficiency and the efficacy of the presented approaches.