We consider the uncapacitated three-level lot-sizing and replenishment problem with a distribution structure. In this NP-hard 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. 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 a multi-commodity MIP formulation and a multi-start randomized bottom-up dynamic programming based heuristic. 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 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.
翻译:我们认为,在分配结构方面,存在着3级无能力的批量化和补充问题。在这个NP-硬性的问题中,一个生产厂将生产的产品从向零售商发送的仓库补充到补充仓库,以满足零售商在有限的规划范围内的需求;问题的目标是确定一个综合生产和分配计划,以尽量减少总成本,包括固定生产和运输设置以及可变库存持有成本;我们描述了在标准混合整列方案拟定和新的替代扩展MIP配方方面,存在新的有效的不平等;我们表明,使用这种扩大的配方,具有与标准一类似结构的有效不平等,从而可以实现更严格线宽宽的放松。此外,我们建议采用一种预处理办法,以减少多通货制和多启动的自下而有活力的编制方案规模。我们所作的比较实验表明,在部门与执行部门之间使用有效的不平等,以及采用新的替代性方案拟订方式,可以大大提高解决最佳化问题的平均解决办法的能力。此外,在扩大的公式方面,在一定的时间范围内实现显著的不平等,在一定的时间范围内,在一种标准基础上,在一种最短的计算方法范围内,在一种最短的计算方法中,可以产生一个最短的时间范围内,在一种最短的计算方法内实现大幅度地解决。