A hybrid heuristic for capacitated three-level lot-sizing and replenishment problems with a distribution structure. (November 2022) - Cunha, Jesus O.
Abstract: In this paper, we consider the capacitated three-level lot-sizing and replenishment problem with a distribution structure (3LSPD-C), recently proposed in the literature. In 3LSPD-C, a single production plant delivers items (of a single product or item type) to the warehouses from where they are distributed to their corresponding retailers. There is a capacity on the total amount the plant can produce in each period, whereas there are no capacity constraints on transportation. The goal of this NP-hard optimization problem consists in determining an integrated three-echelon production and distribution plan minimizing the total cost, which is composed of fixed costs for production and transportation setups as well as variable inventory holding costs. We propose a new hybrid mixed integer programming (MIP) heuristic consisting of a relax-and-fix approach to generate initial feasible solutions and a fix-and-optimize improvement procedure grounded on varying-size neighborhoods to obtain high-quality solutions which, to the best of our knowledge, stands as the first heuristic for the problem. The hybrid heuristic is flexible and can be applied to more general variants of the problem. Additionally, we introduce and consider a generalization of 3LSPD-C that also establishes storage capacity constraints (or inventory bounds) on the warehouses and/or retailers, given the importance of such characteristics in practical industrial and commercial environments. Such extension is denoted generalized capacitated three-level lot-sizing and replenishment problem with a distribution structure (G3LSPD-C). Computational experiments are performed to analyze the potential cost reductions achieved using the new hybrid heuristic when compared with a state-of-the-art MIP formulation given a specific time limit. The results show that the proposed hybrid heuristic can match or improve the solution quality obtained by the MIP formulation for the majority of the 3LSPD-C instances within the specified time limit. Additionally, such superior behavior remains valid when the approaches are applied to the more general G3LSPD-C. Furthermore, we investigate the economic impacts of the storage capacities and how they affect the performance of our newly proposed hybrid heuristic. Highlights: We study three-level lot-sizing and replenish problems with a distribution structure. We introduce a new generalized problem with storage capacities on warehouses/retailers. We propose a hybrid heuristic combining relax-and-fix with fix-and-optimize. The fix-and-optimize improvement procedure employs varying-size neighborhoods. We obtain solutions with small gaps improving over a state-of-the-art formulation.