基于双层启发式遗传算法的三维装箱问题

发布时间：2020-12-22 07:55

　　三维装箱问题是一类组合优化问题,多用于物流运输业的货物装载,具有重要的实践意义。它的最优解受多种条件因素的影响,求解形式复杂且计算量较大,所以常用启发式算法来解决。以空间分割为原则的启发式算法融入遗传算法中并结合二层规划的思想,提出一种基于双层启发式遗传的三维装箱算法。通过双层启发式遗传策略分别对可行解进行广度和深度的搜索来提高寻优效率,从而得到最优的三维装箱方案。在此基础上利用具体算例进行运算和分析,证明该算法在空间利用率和稳定性上都有较好的效果,同时装箱方案可以依托计算机技术进行三维可视化,可为三维装箱问题的信息可视化提供理论依据。 

【文章来源】：科学技术与工程. 2020年05期 北大核心

【文章页数】：6 页

【部分图文】：

空间分割示意图

图2所示为基于双层启发式遗传算法流程。上层遗传使用选择、交叉、变异等不受限的遗传演化形式,这是为了加大可行解的搜索范围,找到一个足够优秀的可行解;下层遗传在上层遗传的基础上对这个可行解进行有目的的多层次变异,经过迭代进化得到最优解。从宏观上对算法进行分析,上层遗传是面向广度的搜索,而下层遗传是面向深度的搜索,结合两层遗传的特点综合使用可以找到最合适的装箱方案。2.3 下层遗传算法的设计

新的遗传演化方法的特殊性主要体现在变异算子上,如图3所示,在变异前要先确立有效装箱区和无效装箱区,选定一个可行解编码次序按照装箱算法依次放入,直到出现无法放入箱容器内的箱体则停止放入,该箱体之前的次序则为有效装箱区,其余的次序则都是无效装箱区。如图4所示,当变异开始时随机选取有效装箱区的一位基因A和无效装箱区的一位基因B,基因A放入无效装箱区基因B的位置,有效装箱区内基因A之后的基因依次向前移动一位,基因B放入有效装箱区的最后一位。此后对新的有效装箱区再运行一遍装箱算法并评估长度,如果与之前的有效装箱区长度一样,则再从无效装箱区中随机选取一位基因放入有效装箱区的尾部,重复上述步骤直至有效装箱区的长度无法再增加,则一次完整的变异过程结束。

【参考文献】：
期刊论文
[1]求解非标准货物货机群装载问题的启发式搜索算法[J]. 郑琰,李鹏.  科学技术与工程. 2018(23)
[2]有角件约束的集装箱配载问题优化算法[J]. 那日萨,崔雪莲,韩琪玮.  工业工程与管理. 2016(01)
[3]带平衡约束三维装箱问题的双层混合遗传算法[J]. 朱向,雷定猷.  交通运输系统工程与信息. 2015(02)
[4]求解三维装箱问题的多层启发式搜索算法[J]. 张德富,彭煜,张丽丽.  计算机学报. 2012(12)
[5]遗传算法选择策略比较[J]. 张琛,詹志辉.  计算机工程与设计. 2009(23)
[6]基于空间优化的三维装箱布局混合遗传算法[J]. 庄凤庭,宋淑娜,高尚.  科学技术与工程. 2009(03)
[7]求解矩形Packing问题的砌墙式启发式算法[J]. 张德富,韩水华,叶卫国.  计算机学报. 2008(03)
[8]三维装箱问题的组合启发式算法[J]. 张德富,魏丽军,陈青山,陈火旺.  软件学报. 2007(09)
[9]平衡装载问题的优化模型和算法[J]. 雷定猷,陈德良.  系统工程学报. 2004(03)

硕士论文
[1]三维装箱问题的混合遗传算法研究[D]. 翟钰.上海交通大学 2007
[2]装箱问题方法研究及其集成应用[D]. 韩运实.中国海洋大学 2004



本文编号：2931413