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

《带冲突关系装箱问题的启发式求解算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

2、法进行比较分析，结果表明，本文算法是求解BPPC问题更为有效的方法。关键词：运筹学与控制论；冲突装箱问题；最大团；启发式算法中图分类号：F224.31文章标识码：A文章编号：1007-322102-0051-07引言装箱问题是一个经典的组合优化难题，在切割加工与物流运输等领域有着广泛应用，并已被证明属于NP完全问题。在对食品，药品以及某些危险品货物的包装过程中，由于不同的物理、化学或生物性质，导致某些货物不允许被装入到同一个货箱当中，由此便产生了带有冲突关系的装箱问题。BPPC模型是在经典装箱模型的基础上，加入了货物冲突限制，是装箱模型与图着色模型的

3、结合形式，求解时需要兼顾“密集装箱”与“冲突化解”两方面的内容，才能实现问题的全局优化。BPPC模型源于经典装箱问题模型，但其求解难度更大，目前国内外针对这一问题的研究内容甚少。Jansen首次将BPPC模型中的冲突关系表示成图结构形式，通过迭代的求解最大导出子图，设计了渐近式近似求解算法框架；Gendreau等首次提出了BPPC问题的整数规划模型，并分别从装箱模型和图着色模型两个角度探讨了问题下界；Muritiba等采用集合覆盖的方式对BPPC问题进行了重新建模，在对问题下界进行近似讨论的基础上，提出了分支定界算法进行精确求解；Khanafer等基

4、于树结构分解的方式设计了求解BPPC问题的通用算法框架；Elhedhli等通过定义分支规则来消除冲突约束，基于此采用动态规划的方式进行计从模型求解角度，作为NP-hard问题，传统数学规划方法和精确算法在求解能力和效率上有所不足，针对BPPC模型的特征，需要设计包含冲突化解和货物装箱的两阶段启发式算法。冲突关系的定义和消去可以基于冲突图结构来实现，其思想源于图着色模型中的最小色数问题；而装箱问题的启发式算法在文献当中进行了系统总结。此外，BPPC模型及其求解算法还可以应用于特定的调度问题和资源分配问题，例如排考问题的建模和求解。本文重点阐述BPPC问

5、题的数学模型，并基于该模型设计包含冲突化解和货物装箱过程的求解算法。主要包括三方面的工作：首先，引入冲突图结构来对货物之间的冲突关系进行描述，将货物集合定义为图结构上的冲突因子；其次，针对图着色过程中货物划分易陷入局部最优的缺点，从冲突图的补图一一兼容图人手，迭代求解其最大团结构，获取当前相互之间不存在冲突关系的最大货物子集；第三，基于数学模型和当前获取的最大团结构，采用改进降序首次适应启发式求解算法实现装箱操作。最后选取国际标准算例进行仿真验证，实验结果表明，上述算法是求解BPPC模型的有效方法。1BPPC问题的数学规划模型BPPC模型的基本定义可

6、以描述为：给定由n件重量分别为wl，w2，...，wn的货物组成的货物列表，和由m个最大容量均为c的货箱组成的货箱列表H;I中的任意一件货物i对应一个冲突货物列表Li，其中的每件货物均与i之间存在冲突关系，即不允许与i装入到同一货箱当中；模型的求解目标是在满足货箱容量和货物间冲突约束的前提下，中的所有货物装入货箱当中，并最小化所使用货箱的数量。为具体描述货物之间的冲突关系，引入冲突图的定义如下。定义1冲突图CG=*—个无向图，代表，内所有货物之间的冲突关系。其中，顶点集合cv对应，中的每件货物，边集CE对应货物之间的冲突关系。为方便冲突关系消去和后续

7、装箱操作，需要对冲突图中的边集CE进行如下扩展：首先，对任意货物iei，在i与其对应的冲突货物列表Li内的每件货物之间添加一条边;其次，对任意两件货物i，j^I，如果wi+wj>c,则在i和j之间添加一条边。BPPC数学模型需要用到的决策变量包括：数学规划模型表示如下：以上模型当中，式表示BPPC模型的目标函数；式表示任意一件货物只能装入到一个货箱当中；式表示任意一个货箱中装入所有货物的重量之和不允许超过货箱的最大容量；〜式表明任意一个货箱当中装入的所有货物都必需满足冲突约束限制。2基于最大团的BPPC问题启发式算法BPPC模型较为直观的解法是基于冲

8、突图结构上的独立集来消去冲突关系，通常采用图着色的方式实现，即对冲突图CG中可以装入到同一货箱中的货物着以相