关键词：
物块倒垛问题
集装箱堆场
板坯库
混合整数规划
下界
有效不等式
迭代算法
摘要：
物块倒垛问题(Block Relocation Problem,简称BRP)是广泛存在于制造业和物流业等领域的调度优化问题,是仓储调度系统中十分常见的倒垛堆垛问题。在实际应用中,对BRP的研究可以提升堆场调度效率,降低生产调度成本,把控供应链节奏,从而提升企业的抗风险能力,使企业在复杂的贸易环境中游刃有余,把握发展机遇。在理论上,BRP是一类非常具有挑战性的NP难问题,对它的研究一直受到学术界的关注。同时BRP还是一类基础优化问题,其问题结构相对简单,是一些复杂实际调度问题的子问题。因此,对BRP的研究可以提升基础优化问题的理论水平,并增强复杂实际调度问题的求解能力,具有非常重要的理论意义。本文以钢铁板坯库和集装箱堆场为背景,在分析和综述BRP在相关领域研究成果的基础上,建立了高效的数学规划模型,并设计了一系列决策优化方法。本文的主要研究内容和创新成果概括如下。
(1)针对研究和应用最广泛的一类无限制的BRP,定义了新的变量体系和约束条件,进而建立了一类规模更小、结构更紧凑的整数规划模型。构建了一个无限制BRP松弛问题的整数规划模型。将其与快速启发式算法相结合,嵌入到一个迭代计算框架中,设计了一个基于快速启发式的精确迭代算法。该算法利用下界收敛的方式,为数学规划方法精确求解BRP提供了一个新的角度。实验结果表明,本文的整数规划模型和精确迭代算法相对于作者当前掌握的文献中计算速度最快的数学规划模型,在计算速度上大幅超越。
(2)提出另一种变量体系和约束条件,建立了一类求解速度更快的混合整数规划模型。通过离散变量连续化和变量定值方法强化了模型。同时对混合整数规划模型进行个性化扩展,以求解不同类型和不同场景需求的BRP。实验结果表明,本文的混合整数规划模型具有更快的求解速度。同时验证了扩展模型的有效性。
(3)通过对BRP的问题结构进行分析,总结出BRP的四个结构性质,基于结构性质设计了一个关于无限制的BRP的下界。同时根据结构性质提取出了多组强有效不等式,并使用结构性质增强了变量定值方法。实验结果表明,加入有效不等式和变量定值方法极大地提高了模型的求解能力,对比当前文献中的数学规划模型,提升效果显著。优化后的模型是当前求解无限制的BRP最强的数学规划模型。
欢迎来到三峡大学图书馆！
