The Particle Swarm Optimization Algorithm for Solving Rectangular Packing Problem

Abstract:

Based on extensive researches on various heuristic algorithms, the particle swarm optimization algorithm was developed to solve the rectangular packing problems. The algorithm optimizes the parameter of dynamic attractive factors by updating the position and the velocity of the particles, and applies perturbation strategy to solve the matter that it is easy to stick at local optima. The experimental result shows that the algorithm can get a better packing result by less time.

• Periodical: Advanced Materials Research (Volume 186)
• Pages: 479-483
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.186.479
• Online since: January 2011
• Authors: Yang Qi, Jin Min Wang
• Keywords: Dynamic Attractive Factors, Packing Problem, Particle Swarm Optimization Algorithm (PSO)

References

[1] Berkey J. O. and Wang P. Y: Two dimensional finite bin-packing algorithms, European Journal of Operation Research, vol. 38, No. 5 (1987), p.423~429.

DOI: 10.1057/jors.1987.70

[2] Dagli C: Cutting stock problem: Combined use of heuristics and optimization methods, in: Proceedings of the 9th International Conference on Production Research (1987), pp.843-849.

[3] Smith D: Bin-packing with adaptive search. in: Proceeding of an International Conference on Genetic Algorithms and their Applications, Lawrence Erlbaum (1985).

[4] S. Jakobs: On genetic algorithms for the packing of the polygons, European Journal of Operational Research, vol. 88, No. 1 (1996), pp.65-181.

DOI: 10.1016/0377-2217(94)00166-9

[5] Hopper. E and Turton. B. C. H: An empirical investigation of meta-heuristic and heuristic algorithm for a 2D packing problem, European Journal of Operational Research, vol. 128, No. 1 (2001), p.34~57.

DOI: 10.1016/s0377-2217(99)00357-4

[6] Wang Jinmin and Yang Weijia: Dynamic Attractive Factors Applied in Packing Problems, Journal of Computer-aided Design & Computer Graphics, vol. 17, No. 8 (2005), p.1725～1729.

[7] Kennedy J and Eberhart R: Particle swarm optimization. in: Proceedings of IEEE International Conference on Neural Networks, edited by Piscataway, IEEE Service Center (1995), p.1942~(1948).

[8] Engelbrechtr A. P: Fundaments of Computational Swarm Intelligence, edited by Tsinghua University Press, Beijing (2009), p.67.

[9] Silvano Martello, Michele Monaci and Daniele Vigo: An exact approach to the strip-packing problem, Journal on computing, vol. 15, No. 3 (2003), pp.310-319.

DOI: 10.1287/ijoc.15.3.310.16082