An improved ACO algorithm for the bin packing problem with conflicts based on graph coloring model

摘要

Bin packing problem with conflicts(BPPC) is a complex combinatorial optimization problem originated from logistics, whose objective is packing all the items with the least number of bins and satisfying the conflict constraints among the items. In this paper, we firstly give the description and 0–1 integer programming model of BPPC, and then transform the model into the representation of conflict graph structure. After that, an ant colony optimization(ACO) algorithm framework is proposed for solving the conflict elimination procedure of BPPC based on a graph coloring heuristic, according to the results of conflict elimination, an improved first-fit decreasing algorithm is used to finish the packing operations of the subsets of items without conflicts. The experiments show that the improve ACO algorithm in this paper is valid and could provide a feasible and high-quality solutions of BPPC efficiently.