Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (22): 197-199.DOI: 10.3778/j.issn.1002-8331.2009.22.063

• 工程与应用 • Previous Articles     Next Articles

Research on three dimensional bin packing problem with multi-type bins based on tabu search algorithm

ZHONG Shi-quan1,WANG Xue-lian2   

  1. 1.School of Management,Tianjin University,Tianjin 300072,China
    2.School of Management,Hebei University of Technology,Tianjin 300130,China
  • Received:2008-04-23 Revised:2008-08-14 Online:2009-08-01 Published:2009-08-01
  • Contact: ZHONG Shi-quan1

多箱型三维装箱问题及其优化研究

钟石泉1,王雪莲2   

  1. 1.天津大学 管理学院,天津 300072
    2.河北工业大学 管理学院,天津 300130
  • 通讯作者: 钟石泉

Abstract: A three dimensional Bin Packing problem(3BP) with multi-type bins is presented in this paper.A Tabu Search algorithm(TS) is designed to solve this problem on nature number.Three kinds of neighborhood are proposed in this algorithm to extend the search space.The algorithm uses the operation of neighborhood to control the bin number limit.Weight limit and center of gravity limit are controlled with penalty function.The principium of the TS are introduced,two representative results and the analysis are given.The experiment indicates the validity of the TS to the three dimensional bin packing problem with multi-type bins.

Key words: bin packing problem, three dimensional, tabu search algorithm

摘要: 对多箱型三维装箱问题进行了描述,提出了求解该问题的禁忌算法。算法基于自然数编码,设计了货物的摆放规则和序列生成方式,采用三种邻域,利用邻域操作控制集装箱数量限制,采用惩罚函数处理集装箱重量约束和重心约束。介绍了算法的原理,给出了具有代表性算例实验结果并且进行了分析。实验结果表明了提出的禁忌算法对优化多箱型三维装箱问题的有效性。

关键词: 装箱问题, 三维, 禁忌算法