Author(s)

Y.-B. Shin & E. Kita

Abstract

The item packing problem is a class of optimization problems which involve attempting to pack items together inside a container, as densely as possible without the item overlap. This research focuses on the application of Particle Swarm Optimization (PSO) to the item packing problem in the two-dimensional region. PSO has the potential solutions of the problem as particles. Particles in the swarm are updated according to the update rule with the velocity and position vectors. The position vectors of the item centers are taken as the design variables. The total number of items is maximized when all items are included inside a container without the item overlap. In the original PSO, the particle position vector is updated with the best position in all particles; i.e., global best position, and the local best position in previous positions of each particle; i.e., local best position. The present PSO algorithm utilizes, in addition to them, the second best position in all particles; i.e., global second-best position. In the numerical example, the present algorithm is applied to the item packing problem within the two-dimensional region. The region figure is not regular and the square items are packed in the region. The comparison of the original and the present PSOs show that the present algorithm can find a better solution than the original PSO. Keywords: particle swarm optimization, item packing problem, global best position, second global best position. 1 Introduction Evolutionary computations are techniques implementing mechanisms inspired by biological evolution such as reproduction, mutation, recombination, natural selection and survival of the fittest; Genetic Algorithms [1–3], Simulated Annealing [4], Evolutionary Programming [5], Genetic Programming [6, 7], Particle Swarm Optimization [8, 9] and so on.

Keywords

particle swarm optimization, item packing problem, global best position, second global best position.