The parallel stack loading problem: Polynomial solvability in the unlimited-capacity case and exact approaches for the finite-capacity case
研究了仓库中并行堆栈装载问题，目标是最小化阻碍后续取货的坏放置物品数量；证明了无限容量时多项式可解，并针对有限容量提出了分支切割和组合Benders分解两种精确算法。
• The parallel stack loading problem of minimizing the number of badly-placed items. • Polynomial-time solvability of the problem under unlimited stack capacity. • Valid inequalities for an existing integer programming formulation. • A combinatorial Benders decomposition algorithm. • Assessment of the two exact approaches via comprehensive numerical experiments. This study addresses the parallel stack loading problem, a logistical challenge encountered in warehouses and storage yards. Its objective is to load incoming items into parallel stacks so that the workload for retrieving them later on is minimized. Among several existing measures for evaluating the workload, we adopt the number of badly-placed items that block the retrieval of items below them. Our contributions are twofold. First, we prove that the problem becomes polynomially solvable when the stack capacity is unlimited. Second, we propose two exact approaches for the problem under finite stack capacity. One is an improvement for an existing integer programming formulation by valid inequalities, leading to a branch-and-cut algorithm. The other is a combinatorial Benders decomposition algorithm based on the polynomially solvable case. Computational experiments using benchmark instances assess the effectiveness of the exact approaches.