带冲突关系装箱题的启发式求解算法.doc

带冲突关系装箱问题的启发式求解算法摘要:现实物流活动中大量存在的食品、药品和危险品等货物的分组包装问题属于带冲突关系的装箱问题,其优化目标是在满足货物间冲突限制的前提下完成装箱操作,并最小化使用货箱的数量。本文从实际需求出发,基于货物之间的冲突关系、装箱顺序和货箱容量等约束建立相应的数学规划模型;随后设计了求解BPPC问题的启发式算法,算法通过迭代求解最大团结构实现货物间冲突关系的消去,根据当前货物最大团采用改进降序首次适应算法完成货物装箱操作,并通过“洗牌”策略对已有装箱方案进行局部优化;最后,针对Iori算例数据,将以上算法与基于图着色的启发式算法进行比较分析,结果表明,本文算法是求解BPPC问题更为有效的方法。关键词:运筹学与控制论;冲突装箱问题;最大团;启发式算法中图分类号: 文章标识码:A 文章编号:1007-322102-0051-07 引言装箱问题是一个经典的组合优化难题,在切割加工与物流运输等领域有着广泛应用,并已被证明属于NP完全问题。在对食品,药品以及某些危险品货物的包装过程中,由于不同的物理、化学或生物性质,导致某些货物不允许被装入到同一个货箱当中,由此便产生了带有冲突关系的装箱问题。BPPC模型是在经典装箱模型的基础上,加入了货物冲突限制,是装箱模型与图着色模型的结合形式,求解时需要兼顾“密集装箱”与“冲突化解”两方面的内容,才能实现问题的全局优化。 BPPC模型源于经典装箱问题模型,但其求解难度更大,目前国内外针对这一问题的研究内容甚少。Jansen首次将BPPC模型中的冲突关系表示成图结构形式,通过迭代的求解最大导出子图,设计了渐近式近似求解算法框架;Gendreau等首次提出了BPPC问题的整数规划模型,并分别从装箱模型和图着色模型两个角度探讨了问题下界;Muritiba等采用集合覆盖的方式对BPPC问题进行了重新建模,在对问题下界进行近似讨论的基础上,提出了分支定界算法进行精确求解;Khanafer等基于树结构分解的方式设计了求解BPPC问题的通用算法框架;Elhedhli等通过定义分支规则来消除冲突约束,基于此采用动态规划的方式进行计算。从模型求解角度,作为NP-hard问题,传统数学规划方法和精确算法在求解能力和效率上有所不足,针对BPPC模型的特征,需要设计包含冲突化解和货物装箱的两阶段启发式算法。冲突关系的定义和消去可以基于冲突图结构来实现,其思想源于图着色模型中的最小色数问题;而装箱问题的启发式算法在文献当中进行了系统总结。此外,BPPC模型及其求解算法还可以应用于特定的调度问题和资源分配问题,例如排考问题的建模和求解。本文重点阐述BPPC问题的数学模型,并基于该模型设计包含冲突化解和货物装箱过程的求解算法。主要包括三方面的工作:首先,引入冲突图结构来对货物之间的冲突关系进行描述,将货物集合定义为图结构上的冲突因子;其次,针对图着色过程中货物划分易陷入局部最优的缺点,从冲突图的补图――兼容图人手,迭代求解其最大团结构,获取当前相互之间不存在冲突关系的最大货物子集;第三,基于数学模型和当前获取的最大团结构,采用改进降序首次适应启发式求解算法实现装箱操作。最后选取国际标准算例进行仿真验证,实验结果表明,上述算法是求解BPPC模型的有效方法。lBPPC问题的数学规划模型 BPPC模型的基本定义可以描述