An Ant Colony Optimization Algorithm for the One-dimensional Cutting Stock Problem with Multiple Stock Lengths

作者：Lu Qiang^*; Wang Zhiguang; Chen Ming

来源：4th International Conference on Natural Computation (ICNC 2008), 2008-10-18 to 2008-10-20.

DOI：10.1109/ICNC.2008.208

The Cutting Stock Problem (CSP) with multiple stock lengths is the NP-hard combinatorial optimization problem. In recent years, the CSP is researched by applying evolutionary approaches which includes Genetic Algorithm, Evolutionary Programming, et al. In the paper, an ant colony optimiation (ACO) algorithm for one-dimensional cutting stock problems with muliple stock lengths(MCSP) is presented, and mutation operatation is imported into the ACO in order to avoid the phenomenon of precocity and stagnation emerging. Based on the analysis of the algorithm, the ACO for MCSP has the same time complexity as CSP. Throught exmperiments study, the outcome shows that, compared with other algorithm, the algorithm takes a great improvement in the convergent speed and result optimization.

• 出版日期2008
• 单位中国石油大学（北京）