计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (36): 222-225.DOI: 10.3778/j.issn.1002-8331.2010.36.062

• 工程与应用 • 上一篇    下一篇

混合二元蚁群算法求解集装箱装载问题

袁军良,熊伟清,江宝钏   

  1. 宁波大学 计算机科学与技术研究所,浙江 宁波 315211
  • 收稿日期:2010-06-28 修回日期:2010-09-02 出版日期:2010-12-21 发布日期:2010-12-21
  • 通讯作者: 袁军良

Hybrid binary ant colony algorithm for container loading problem

YUAN Jun-liang,XIONG Wei-qing,JIANG Bao-chuan   

  1. Institute of Computer Science and Technology,Ningbo University,Ningbo,Zhejiang 315211,China
  • Received:2010-06-28 Revised:2010-09-02 Online:2010-12-21 Published:2010-12-21
  • Contact: YUAN Jun-liang

摘要: 集装箱装载问题是一个具有复杂约束条件的组合优化问题,属于NP-hard问题。针对集装箱装载问题的特点,设计了空间三叉树,对可利用空间采用三叉树划分策略,利用二元蚁群算法结合启发式算法进行求解,即先利用二元蚁群算法确定预备装入货物集,再用启发式算法决定货物的装入优先级顺序,并给出了有效的装箱算法。实例结果表明该算法的有效性和实用性。

关键词: 集装箱装载, 二元蚁群算法, 启发式, 三叉树

Abstract: Container loading problem with multi-constraints is a complicated combinatorial optimization problem.It’s a NP-hard problem.A trifurcate tree of space is designed according to the trait of this problem and available space is divided by the strategy of trifurcate tree.Binary ant colony algorithm combining heuristics is proposed to solve the container loading problem.First,using binary ant colony algorithm determines the set of preparatory loading goods.Then,using heuristics determines the priority of the goods and an effective bin-packing algorithm is given.Results of the experiment show the feasibility and effectiveness of the proposed algorithm.

Key words: container loading, binary ant colony algorithm, heuristic, trifurcate tree

中图分类号: