基于图着色模型的冲突装箱问题启发式算法

《基于图着色模型的冲突装箱问题启发式算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第２２卷第５期运筹与管理Ｖｏｌ．２２，Ｎｏ．５２０１３年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１３基于图着色模型的冲突装箱问题启发式算法１１１２元野，李一军，王延青，王晓博（１．哈尔滨工业大学管理学院，黑龙江哈尔滨１５０００１；２．黑龙江大学信息管理学院，黑龙江哈尔滨１５００８０）摘要：带有冲突关系装箱问题的优化目标是在满足货物冲突关系的前提下，使用数量最少的货箱完成货物装箱的目的。本文分析了冲突装箱问题的数学模型，提出了基于图着色模型的启发式算法进行求解。首先，使用冲突图来描述货物之间的

2、冲突关系；其次，基于冲突图，采取图着色的方式将货物进行分组，并且组内的货物之间不存在冲突关系；最后，采取改进ＦＦＤ算法对每组的货物进行装箱操作。实验表明，本文提出的启发式算法能够快速有效地找到问题的可行解，为此类装箱问题的求解提供了新思路。关键词：运筹学与控制论；冲突装箱问题；图着色；启发式算法中图分类号：Ｆ２２４．３１文章标识码：Ａ文章编号：１００７-３２２１（２０１３）０５-００１２-０５HeuristicAlgorithmforBinPackingProblemwithConflictsBasedonGraphColoringModel１

3、１１２ＹＵＡＮＹｅ，ＬＩＹｉ-ｊｕｎ，ＷＡＮＧＹａｎ-ｑｉｎｇ，ＷＡＮＧＸｉａｏ-ｂｏ（１．SchoolofManagement，HarbinInstituteofTechnology，Harbin１５０００１，China；２．SchoolofInformationManagement，HeilongjiangUniversity，Harbin１５００８０，China）Abstract：Ｔｈｅｏｂｊｅｃｔｉｏｎｏｆｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｗｉｔｈｃｏｎｆｌｉｃｔｓ（ＢＰＰＣ）ｉｓｔｏｍｉｎｉｍｉｚｅｔｈｅｎｕｍｂｅｒｏｆｂｉｎｓｕｓｅ

4、ｄｔｏａｃｃｏｍｍｏｄａｔｅａｌｌｔｈｅｉｔｅｍｓ，ａｎｄａｌｓｏｈａｓｔｏｓａｔｉｓｆｙｔｈｅｃｏｎｆｌｉｃｔｃｏｎｓｔｒａｉｎｔｓａｍｏｎｇｔｈｅｉｔｅｍｓ．ＴｈｉｓｐａｐｅｒｓｕｍｍａｒｉｅｓｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆＢＰＰＣ，ａｎｄｐｒｏｐｏｓｅｓａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｇｒａｐｈｃｏｌｏｒｉｎｇｍｏｄｅｌｔｏｓｏｌｖｅｉｔ．Ｆｉｒｓｔｌｙ，ａｃｏｎｆｌｉｃｔｇｒａｐｈｓｔｒｕｃｔｕｒｅｉｓｕｓｅｄｔｏｒｅｐｒｅｓｅｎｔｔｈｅｃｏｎｆｌｉｃｔｒｅｌａｔｉｏｎｓｈｉｐａｍｏｎｇｔｈｅｉｔｅｍｓ

5、，ａｎｄｔｈｅｎ，ｂａｓｅｄｏｎｔｈｅｃｏｎｆｌｉｃｔｇｒａｐｈ，ｔｈｅａｌｇｏｒｉｔｈｍｗｉｌｌｆｉｎｉｓｈａｃｏｌｏｒｉｎｇｐｒｏｃｅｄｕｒｅｔｏｇｒｏｕｐａｌｌｔｈｅｉｔｅｍｓａｎｄｅｎｓｕｒｅｔｈａｔｔｈｅｒｅｉｓｎｏｉｔｅｍｓｗｉｔｈｃｏｎｆｌｉｃｔｒｅｌａｔｉｏｎｓｈｉｐｉｎｅａｃｈｇｒｏｕｐ，ａｎｄｌａｓｔｌｙ，ａｎｉｍｐｒｏｖｅｄＦＦＤａｌｇｏｒｉｔｈｍｉｓｕｓｅｄｔｏｃｏｍｐｌｅｔｅｔｈｅｐａｃｋｉｎｇｏｐｅｒａｔｉｏｎｆｏｒｔｈｅｉｔｅｍｓｉｎｅａｃｈｇｒｏｕｐ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉ

6、ｔｈｍｏｆｔｈｉｓｐａｐｅｒｃｏｕｌｄｆｉｎｄａｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｆＢＰＰＣｑｕｉｃｋｌｙａｎｄｅｆｆｉｃｉｅｎｔｌｙ，ａｎｄｐｒｏｖｉｄｅａｎｅｗａｐｐｒｏａｃｈｆｏｒｔｈｉｓｋｉｎｄｏｆｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈａｎｄｃｙｂｅｒｎｅｔｉｃｓ；ｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｗｉｔｈｃｏｎｆｌｉｃｔｓ；ｇｒａｐｈｃｏｌｏｒｉｎｇ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ０引言［１］装箱问题在切割加工和物流运输等行业当中有着广泛的应用背景。然而，在对食品、药品以及某

7、些危险品货物的包装过程当中，待装箱的货物往往由于其不同的物理、化学和生物性质，导致某些货物不［２］允许被装入到同一个货箱当中。因此，便产生了带有冲突关系的装箱问题（ＢｉｎＰａｃｋｉｎｇＰｒｏｂｌｅｍｗｉｔｈＣｏｎｆｌｉｃｔｓ，ＢＰＰＣ）。ＢＰＰＣ问题是在经典装箱问题的基础之上加入了货物冲突限制，因此，它也是一个［３］ＮＰ-ｈａｒｄ问题。ＢＰＰＣ问题源于经典装箱问题，在ＢＰＰＣ模型当中，如果忽略货物间的冲突关系，便可以将其转化成为一个普通的装箱问题。因此，可以借鉴装箱问题的求解算法解决ＢＰＰＣ问题。Ｌｏｄｉ等人对不同维度的装收稿日期：２０１２-０

8、９-２１基金项目：国家社会科学基金项目资助项目（１０ＣＧＬ０７６）作者简介：元野（１９８５-），男，朝鲜族，黑龙江双鸭山人，博士研究生，研究方向：运筹