基于图着色模型的冲突装箱问题启发式算法

带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下,使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型,提出了基于图着色模型的启发式算法进行求解。首先,使用冲突图来描述货物之间的冲突关系;其次,基于冲突图,采取图着色的方式将货物进行分组,并且组内的货物之间不存在冲突关系;最后,采取改进FFD算法对每组的货物进行装箱操作。实验表明,本文提出的启发式算法能够快速有效地找到问题的可行解,为此类装箱问题的求解提供了新思路。

Heuristic Algorithm for Bin Packing Problem with Conflicts Based on Graph Coloring Model

The objection of bin packing problem with conflicts(BPPC)is to minimize the number of bins used to accommodate all the items, and also has to satisfy the conflict constraints among the items. This paper summaries the mathematical model of BPPC, and proposes a heuristic algorithm based on graph coloring model to solve it. Firstly, a conflict graph structure is used to represent the conflict relationship among the items, and then, based on the conflict graph, the algorithm will finish a coloring procedure to group all the items and ensure that there is no items with conflict relationship in each group, and lastly, an improved FFD algorithm is used to complete the packing operation for the items in each group. The experiments show that the algorithm of this paper could find a feasible solution of BPPC quickly and efficiently, and provide a new approach for this kind of bin packing problems.