计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (22): 237-240.DOI: 10.3778/j.issn.1002-8331.2008.22.071

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

集装箱装载问题的一种DNA遗传算法

许光泞,俞金寿   

  1. 华东理工大学 信息科学与工程学院,上海 200237
  • 收稿日期:2007-10-15 修回日期:2008-01-16 出版日期:2008-07-11 发布日期:2008-07-11
  • 通讯作者: 许光泞

DNA genetic algorithm for solving container loading problem

XU Guang-ning,YU Jin-shou   

  1. College of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China
  • Received:2007-10-15 Revised:2008-01-16 Online:2008-07-11 Published:2008-07-11
  • Contact: XU Guang-ning

摘要: 三维集装箱装载是一个复杂的组合优化问题,约束条件多,属于NP完全问题,求解难度大.在考虑方向性约束和稳定性约束的情况下,提出了一种DNA遗传算法(DNA-GA),给出了有效的编码和解码方法。实例计算结果表明,利用DNA-GA解决装箱问题是行之有效的一种方法,对推广DNA计算在求解NP难解问题中的应用具有一定的意义。

关键词: 集装箱装载, DNA遗传算法, 空间分解, 优化

Abstract: Container loading problem with multi-constraints is a complicated combinatorial optimization problem.It’s a NP-hard problem and difficult to obtain an optimal solution.Considering orientation and stability constraint,a DNA-based genetic algorithm for the three-dimension container loading problem is presented in this paper.In the algorithm,the authors take into account the direction in which goods are placed and the loading capacity,and propose an effective encoding algorithm.Simulation results show that the proposed algorithm is feasible and effective,and can be directly used in practical applications.It is of some significance to promote DNA computation application in NP-complete problem.

Key words: container loading, DNA-based genetic algorithm, space decomposition, optimization