Improved ACO for Dimensional Cutting-Stock Problem


Article Preview

In order to find an effective method for solving the NP problem-dimensional cutting stock problem, the improved ACO based on entropy was introduced.After introducing the basic knowledge of the improved ACO, the dimensional cutting-stock problem’s mathematical model was set up.And the improved ACO was employed to optimize the problem.Computed results indicate that the ant colony algorithm can approach the theoretical optimal solution,and its astringency is good.This study provides a new approach for the optimization of the NP hard problems.



Edited by:

Zhenyu Du and Bin Liu




Y. C. Li et al., "Improved ACO for Dimensional Cutting-Stock Problem", Applied Mechanics and Materials, Vols. 26-28, pp. 277-280, 2010

Online since:

June 2010




[1] Dorigo M, Maniezzo V, and Colorni A.: Positive Feedback as a SearchStrategy. Technical Report Politecnicod Milano, Italy: Dipartimentodi Elettronica (1991), p.91.

[2] Maniezzo V, Colorni A, and Dorigo M.: The Ant System Applied to the Quadratic Assignment Problem. Tech. Rep. IRIDIA. Bruxelles, Belgium: Université Librede, (1994), p.94.

[3] Colorni A, Dorigo M, Maniezzo V. and et al.: Ant System for job-shopscheduling. Belgian Juarnal of Operations Research Statistics and Computer Science. Vol. 34(1994), pp.39-53.

[4] Tarasewich P, and McMullen P. R.: Swarm intelligence: power in numbers. Commun ACM. Vol. 45(2002), p.62.


[5] Dorigo M, D. Caro G, and Gambardella LM.: Ant algorithms for discreteoptimization. Artif Life. Vol. 5(1999), pp.137-72.

[6] Bland JA.: Space planning by ant colony optimization. Int J. Comput Appl. Tech. Vol. 6 (1999), p.320.

[7] Bauer A, Bullnheimer B, Hartl RF, and et al.: An ant colony optimization approach for the single machine tool tardiness problem. Proceedings of the 1999 Congress on Evolutionary Computation. (1999), p.1445.


[8] Mc Mullen PR.: An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives. Artif. Intell. Eng. Vol. 15 (2001), p.309.


[9] Lin S, and Kernighan BW.: An effective heuristic algorithm for the TSP. Oper. Res. Vol. 21(1973), p.498.

[10] Li Yancang, Li Wanqing: Adaptive Ant Colony Optimization Algorithm Based on Information Entropy: Foundation and Application. Fundamenta Informaticae. Vol. 77(2007), p.229.