Simulated Annealing applied to the problem of Bin Packing with Conflicts

- 325877
Complete Articles (CA)
Favorite this paper
How to cite this paper?
Abstract

This paper tackles the combinatorial optimization problem called the Bin Packing Problem with Conflicts (BPPC). The problem is variant of the classic Bin Packing Problem (BPP). In the original problem, a set of items is to be packed in the minimum number of same size containers, respecting its maximum weight capacity. The BPPC has the same objective but presents the case where items may have conflicts with each other and cannot be packed in the same bin together. A Simulated Annealing method with a random initial solution and four neighborhood moves is implemented. The proposed algorithm is tested on 2,160 instances from the literature and results show that high quality solutions were obtained. The average gap from the best known solutions was 4.81% and optimality was reached in 24.21% of cases. 

Share your ideas or questions with the authors!

Did you know that the greatest stimulus in scientific and cultural development is curiosity? Leave your questions or suggestions to the author!

Sign in to interact

Have a question or suggestion? Share your feedback with the authors!

Institutions
  • 1 Universidade Federal de Ouro Preto
Track
  • 12. MH – Metaheurístics
Keywords
Simulated Annealing
Bin Packing with Conflicts
Metaheuristics