A NOVEL WORK FOR BIN PACKING PROBLEM BY ANT COLONY OPTIMIZATION

Nishant Kumar Singh, Susobhan Baidya

Abstract: This paper presents Ant colony optimization metaheuristic solution for Bin packing problem (BPP). In the BPP, the aim is to combine a set of items into bins of a certain capacity so as to minimize the total number of bins. The bin packing is a well-known NP-hard combinatorial optimization problem. Only very little instances can be solved exactly, so for real-world problems we have to rely on heuristic solution methods. We are proposing an ant based optimization which was introduced by Dorigo in 1992, which in the past proved appropriate to solve many optimization problems. This ACO is inspired by the path-finding abilities of real ant colonies.It combines an artificial pheromone trail with simple heuristic information to stochastically build new solutions. This paper explores the ability of the ACO algorithm to balance between bins and objects in its decision making process. The solution quality and time to solution make ACO competitive as an optimization technique for NP-hard problems in which various factors such as cost and length are involved.[1][2]

Keywords: ACO, bin packing problem, NP- Problem

DOI: https://doi.org/10.15623/ijret.2013.0214014