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