论文部分内容阅读
随着经济全球化的发展,作为重要服务支撑的物流行业近年来得到快速增长,而以降低成本、提高效益为主要目的的物流优化也得到产业界和学术界的普遍关注。集装箱问题作为物流优化领域中的一个经典问题,具有很大的研究价值,对于提高配送效率、提高装载空间利用率、提升物流运输效率、节省运输成本和提升物流企业同行竞争力等都具有重要的意义。其中,三维装箱问题因其可扩展性,也不再局限于物流领域,目前已广泛应用于车辆路径研究、应用经济学研究、建筑学研究、土木工程学研究等多个学科领域。正是由于集装箱问题良好的应用背景,分析自2000年开始在不同子问题上的研究可以发现,启发式算法的应用占居多数,其中求解二维装箱问题的有五块优化模型算法、禁忌搜索算法、非线性算法、化学反应优化算法等;求解三维装箱问题的传统启发式算法(如遗传算法、模拟退火算法)等。但传统启发式算法存在计算量大、计算复杂度高等缺点。经研究发现新型启发式算法中的化学反应优化算法(Chemical Reaction Optimization,CRO)同时具有遗传算法和模拟退火算法的优点:快速的收敛性和有效性,但该算法目前仅被应用于二维装箱问题。本文综合化学反应优化算法的局限性及优势提出可求解三维装箱问题的混合启发式算法,该算法主要包括混合化学反应优化算法和混合递归算法。本文的主要贡献如下:1.针对最小化装箱数量问题,本文提出混合化学反应优化算法,在实现化学反应优化算法(Chemical Reaction Optimization,CRO)算法整体框架的同时,对适应性参数势能PE、种群数与数据集数量配比、合成率synth Thrs和分解率decomp Thrs等参数经实验数据运行调整后应用于三维装箱问题。基于公开提供的随机算法生成实际测试数据(8类320实例),将给定测试数据的所有可能结果抽象为未知可能的势能面,对本文算法进行实验找到势能最低的势能点,即适应性最佳的组合。通过比较与现有论文的数据结果,证明了本文的算法的有效性。2.针对同尺寸装箱问题,本文提出混合递归算法,一方面进行组合块的自然组合和拼接,另一方面对空间进行有效切割和递归实现用于求解该类问题。为了验证算法的有效性,基于现有论文的数据进行对比实验发现,本文算法能够进一步提高单位装箱的填充率,也在一定程度上解决CRO出现的局部搜索能力不强的问题。综上所述,本文针对三维装箱的具体问题,提出混合反应优化算法和混合递归算法。其中混合化学反应优化算法进一步优化最小化装箱数量,基于公开的数据集(Martello提出的8类320实例数据),通过仿真实验发现,本文算法优于现有的同类算法。其次,受组合块思想和空间切割思想启发,实现了混合递归算法,在现有的数据集I和数据集II上进行实验。通过结果分析可知,混合递归算法在同尺寸装箱问题上,具有较大的竞争优势。