CAJ | 학술논문

现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题（ BPPC），其优化目标是在满足货物间冲突限制的前提下完成装箱操作，并最小化使用货箱的数量。本文从实际需求出发，基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型；随后设计了求解BPPC问题的启发式算法，算法通过迭代求解最大团结构实现货物间冲突关系的消去，根据当前货物最大团采用改进降序首次适应算法（ FFD）完成货物装箱操作，并通过“洗牌”策略对已有装箱方案进行局部优化；最后，针对Iori算例数据，将以上算法与基于图着色的启发式算法进行比较分析，结果表明，本文算法是求解BPPC问题更为有效的方法。
현실물류활동중대량존재적식품、약품화위험품등화물적분조포장문제속우대충돌관계적장상문제（ BPPC），기우화목표시재만족화물간충돌한제적전제하완성장상조작，병최소화사용화상적수량。본문종실제수구출발，기우화물지간적충돌관계、장상순서화화상용량등약속건립상응적수학규화모형；수후설계료구해BPPC문제적계발식산법，산법통과질대구해최대단결구실현화물간충돌관계적소거，근거당전화물최대단채용개진강서수차괄응산법（ FFD）완성화물장상조작，병통과“세패”책략대이유장상방안진행국부우화；최후，침대Iori산례수거，장이상산법여기우도착색적계발식산법진행비교분석，결과표명，본문산법시구해BPPC문제경위유효적방법。
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 struc-ture 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 .