A heuristic method for online warehouse storage assignment problem
Jing Xu, Andrew E. B. Lim, Chenghao Shen, Huangwei Li · 2008
The warehouse storage location assignment is a widely studied stochastic resource allocation problem. Many assignment policies have been developed to solve various restricted versions of this online problem providing manual guidelines for practice. In this paper, we solve a more general version of this online problem through a brand-new deterministic approach. We first show that the deterministic storage assignment problem can be modelled as the optimal cost chromatic partition(OCCP) problem, which is NP-Hard. Then we study the properties of the optimal solution. Based on the properties, we propose a framework of iterative heuristic algorithm, together with two different kinds of neighborhoods, GREEDY-neighborhood and SWAP-neighborhood. We prove that the SWAP-neighborhood performs the best 2-zone improvement on any feasible solution. Using this neighborhood, we roll the heuristic algorithm along time horizon to solve the final online problem. Through analysis and experiments, we demonstrate that the proposed methods can solve the problem very well and they are much more flexible compared to the traditional policies in current practice.