Abstract
Every day different companies in industry have to solve many optimization problems. One of them is cutting out of linear materials, like steel or aluminum profiles, steel or wood beams and so on. It is so called cutting stocks problem (CSP). It is well known NP-hard combinatorial optimization problem. The accurate and fast cutting out is very important element from the working process. The aim in CSP is to cut items from stocks of certain length, minimizing the total number of stocks (waste). The computational time increases exponentially when the number of items increase. Finding the optimal solution for large-sized problems for a reasonable time is impossible. Therefore, exact algorithms and traditional numerical methods can be apply of only on very small problems. Mostly appropriate methods for this kind of problems are methods based on stochastic search or so called metaheuristic methods. We propose a variant of Ant Colony Optimization (ACO) algorithm to solve linear cutting stocks problem.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Dorigo, M., Maniezzo, M., Colorni, A.: The ant system: optimization by a colony of cooperating agents. IEEE Trans. Syst. Man Cybern. B 26(1), 29–41 (1996)
Falkenauer, E.: A hybrid grouping genetic algorithm for bin packing. J. Heuristics 2, 5–30 (1996)
Fidanova, S.: Evolutionary algorithm for multiple Knapsack problem. In: International Conference Parallel Problems Solving from Nature, Real World Optimization Using Evolutionary Computing, Granada, Spain (2002). ISBN No 0-9543481-0-9
Gradisar, M., Resinovic, G., Kljajic, M.: Evaluation of algorithms for one-dimensional cutting. Comput. Oper. Res. 29(9), 1207–1220 (2002)
Hinterding, R., Khan, L.: Genetic algorithms for cutting stock problems: with and without contiguity. In: Yao, X. (ed.) Progress in Evolutionary Computation, pp. 166–186. Springer, Berlin, Germany (1995)
Jahromi, M.H., Tavakkoli-Moghaddam, R., Makui, A., Shamsi, A.: Solving an one-dimensional cutting stock problem by simulated annealing and Tabu search. J. Ind. Eng. Int. 8(1), paper 24 (2012)
Kantorovicc, L.: Mathematical methods of organizing and planing production. Manag. Sci. 6, 366–422 (1960)
Reeves, C.: Hybrid genetic algorithms for bin-packing and related problems. Ann. Oper. Res. 63, 371–396 (1996)
Reiman, M., Laumanns, M.: A hybrid ACO algorithm for the capacitate minimum spanning tree problem. In: Proceedings of First International Workshop on Hybrid Metaheuristics, pp. 1–10, Valencia, Spain (2004)
Scheithauer, G., Terno, J.: A branch&bound algorithm for solving one-dimensional cutting stock problem exactly. Appl. Math. 23(2), 151–167 (1995)
Stutzle, T., Dorigo, M.: ACO algorithm for the traveling salesman problem. In: Miettinen, K., Makela, M., Neittaanmaki, P., Periaux, J. (eds.) Evolutionary Algorithms in Engineering and Computer Science, pp. 163–183. Wiley (1999)
Vink, M.: Solving combinatorial problems using evolutionary algorithms (1997). http://citeseer.nj.nec.com/vink97solving.html
Zhang, T., Wang, S., Tian, W., Zhang, Y.: ACO-VRPTWRV: a new algorithm for the vehicle routing problems with time windows and re-used vehicles based on ant colony optimization. In: Sixth International Conference on Intelligent Systems Design and Applications, pp. 390–395. IEEE Press (2006)
Acknowledgements
Work presented here is partially supported by the Bulgarian National Scientific Fund under Grants DFNI I02/20 “Efficient Parallel Algorithms for Large Scale Computational Problems” and DN 02/10 “New Instruments for Data Mining and their Modeling”.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG
About this chapter
Cite this chapter
Evtimov, G., Fidanova, S. (2018). Ant Colony Optimization Algorithm for 1D Cutting Stock Problem. In: Georgiev, K., Todorov, M., Georgiev, I. (eds) Advanced Computing in Industrial Mathematics. Studies in Computational Intelligence, vol 728. Springer, Cham. https://doi.org/10.1007/978-3-319-65530-7_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-65530-7_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-65529-1
Online ISBN: 978-3-319-65530-7
eBook Packages: EngineeringEngineering (R0)