Valid inequalities, preprocessing, and an effective heuristic for the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure

Jesus O. Cunha and Rafael A. Melo

European Journal of Operational Research, 2021, vol. 295, issue 3, 874-892

Abstract: We consider the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure. In this problem, a single production plant sends the produced items to replenish warehouses from where they are dispatched to the retailers in order to satisfy their demands over a finite planning horizon. Transfers between warehouses or retailers are not permitted, each retailer has a single predefined warehouse from which it receives its items, and there is no restriction on the amount that can be produced or transported in a given period. The goal of the problem is to determine an integrated production and distribution plan minimizing the total costs, which comprehends fixed production and transportation setup as well as variable inventory holding costs. We describe new valid inequalities both in the space of a standard mixed integer programming (MIP) formulation and in that of a new alternative extended MIP formulation. We show that using such extended formulation, valid inequalities having similar structures to those in the standard one allow achieving tighter linear relaxation bounds. Furthermore, we propose a preprocessing approach to reduce the size of an extended multi-commodity MIP formulation available in the literature. Such preprocessing relies on the removal of variables based on the problem’s cost structure while preserving optimality guarantees. We also propose a multi-start randomized bottom-up dynamic programming-based heuristic. The heuristic employs greedy randomization via changes in certain costs and solves subproblems related to each level using dynamic programming. Computational experiments indicate that the use of the valid inequalities in a branch-and-cut approach significantly increase the ability of a MIP solver to solve instances to optimality. Additionally, the valid inequalities for the new alternative extended formulation outperform those for the standard one in terms of number of solved instances, running time and number of enumerated nodes. Moreover, the proposed heuristic is able to generate solutions with considerably low optimality gaps within very short computational times even for large instances. Combining the preprocessing approach with the heuristic, one can achieve an increase in the number of solutions solved to optimality within the time limit together with significant reductions on the average times for solving them.

Keywords: Supply chain management; Multi-level lot-sizing; Mixed integer programming; Preprocessing; Heuristics (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721002551
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:295:y:2021:i:3:p:874-892

DOI: 10.1016/j.ejor.2021.03.029

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().