Abstract: In real distributions, there are a great many of packing problems with food, medicine and hazardous material named bin packing problem with conflicts, whose objective is to minimize the number of used bins and has to satisfy the conflict constraints among the items. To solve the problems, the mathematical model of BPPC is proposed based on the conflict relationship among the items, packing order and capacity constraints of the bins; and then a heuristic algorithm is designed for solving BPPC, the algorithm computes the maximum clique structure iterately to eliminate the conflict relationship among the items, runs the packing operation according to the items corresponding to the current maximum clique structure, and a local search methed named shuffling strategy is applied to further optimize the current packing results; lastly the simulation experiment is carried out on Iori’s strandard instances compared with the heuristic algorithm based on the graph coloring model, the computational results demonstrate that the heuristic algorithm in this paper is more feasible and effective.

Key words: operations research and cybernetics, bin packing problem with conflicts, maximum clique, heuristic algorithm

摘要： 现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题(BPPC),其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法(FFD)完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。

关键词: 运筹学与控制论, 冲突装箱问题, 最大团, 启发式算法