基于禁忌搜索算法求解集装箱装载问题  

Solving containerloading based on tabu search algorithm

作　　者：刘嘉敏[1] 董宗然[2] 马广焜[1] 

机构地区：[1]沈阳工业大学信息科学与工程学院,沈阳110178 [2]大连东软信息学院计算机科学与技术系,辽宁大连116023

出　　处：《沈阳工业大学学报》2009年第2期212-216,共5页Journal of Shenyang University of Technology

基　　金：辽宁省教育厅基金资助项目(2004F043)

摘　　要：针对具有广泛应用背景、多约束条件和求解困难的集装箱装载问题,引入具有人工智能记忆机制、基于邻域搜索而避免局部最优的禁忌搜索算法,探讨了在求解集装箱装载问题中禁忌搜索的编码、解码和邻域解生成等关键技术,给出了基于物体数量的编码过程与剩余空间处理方法相结合的解码过程和邻域解生成的实现过程,并为对空间利用率影响较大的剩余空间设计了合理的划分与合并规则.通过实例测试和比较,显示出很好的效果,表明该算法是行之有效的.A tabu search algorithm was applied in order to solve the containerloading problem with the wide application background, multiple constraint and difficult solution. The tabu search algorithm based on the neighbourhood search can avoid the local optimization avoidance and has the artificial intelligence memory mechanism. Such key techniques as encoding, decoding and generation of neighbourhood solution for the tabu search in solving the containerloading problem were discussed. The implementation of the encoding process based on the box quantity and decoding process combined with the remaining space handling method as well as the neighbourhood solution generation was presented. The partitioning and merging principles of the remaining space were designed. The effectivity of the proposed method has been proved by test and comparison.

关 键 词：禁忌搜索 集装箱装载 组合优化 布局 启发式 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]