資源描述：
《基于圖著色模型的沖突裝箱問題啟發(fā)式算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、第２２卷第５期運(yùn)籌與管理Ｖｏｌ．２２，Ｎｏ．５２０１３年１０月ＯＰＥＲＡＴＩＯＮＳＲＥＳＥＡＲＣＨＡＮＤＭＡＮＡＧＥＭＥＮＴＳＣＩＥＮＣＥＯｃｔ．２０１３基于圖著色模型的沖突裝箱問題啟發(fā)式算法１１１２元野，李一軍，王延青，王曉博（１．哈爾濱工業(yè)大學(xué)管理學(xué)院，黑龍江哈爾濱１５０００１；２．黑龍江大學(xué)信息管理學(xué)院，黑龍江哈爾濱１５００８０）摘要：帶有沖突關(guān)系裝箱問題的優(yōu)化目標(biāo)是在滿足貨物沖突關(guān)系的前提下，使用數(shù)量最少的貨箱完成貨物裝箱的目的。本文分析了沖突裝箱問題的數(shù)學(xué)模型，提出了基于圖著色模型的啟發(fā)式算法進(jìn)行求解。首先，使用沖突圖來描述貨物之間的
2、沖突關(guān)系；其次，基于沖突圖，采取圖著色的方式將貨物進(jìn)行分組，并且組內(nèi)的貨物之間不存在沖突關(guān)系；最后，采取改進(jìn)ＦＦＤ算法對每組的貨物進(jìn)行裝箱操作。實(shí)驗(yàn)表明，本文提出的啟發(fā)式算法能夠快速有效地找到問題的可行解，為此類裝箱問題的求解提供了新思路。關(guān)鍵詞：運(yùn)籌學(xué)與控制論；沖突裝箱問題；圖著色；啟發(fā)式算法中圖分類號：Ｆ２２４．３１文章標(biāo)識碼：Ａ文章編號：１００７-３２２１（２０１３）０５-００１２-０５HeuristicAlgorithmforBinPackingProblemwithConflictsBasedonGraphColoringModel１
3、１１２ＹＵＡＮＹｅ，ＬＩＹｉ-ｊｕｎ，ＷＡＮＧＹａｎ-ｑｉｎｇ，ＷＡＮＧＸｉａｏ-ｂｏ（１．SchoolofManagement，HarbinInstituteofTechnology，Harbin１５０００１，China；２．SchoolofInformationManagement，HeilongjiangUniversity，Harbin１５００８０，China）Abstract：Ｔｈｅｏｂｊｅｃｔｉｏｎｏｆｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｗｉｔｈｃｏｎｆｌｉｃｔｓ（ＢＰＰＣ）ｉｓｔｏｍｉｎｉｍｉｚｅｔｈｅｎｕｍｂｅｒｏｆｂｉｎｓｕｓｅ
4、ｄｔｏａｃｃｏｍｍｏｄａｔｅａｌｌｔｈｅｉｔｅｍｓ，ａｎｄａｌｓｏｈａｓｔｏｓａｔｉｓｆｙｔｈｅｃｏｎｆｌｉｃｔｃｏｎｓｔｒａｉｎｔｓａｍｏｎｇｔｈｅｉｔｅｍｓ．ＴｈｉｓｐａｐｅｒｓｕｍｍａｒｉｅｓｔｈｅｍａｔｈｅｍａｔｉｃａｌｍｏｄｅｌｏｆＢＰＰＣ，ａｎｄｐｒｏｐｏｓｅｓａｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍｂａｓｅｄｏｎｇｒａｐｈｃｏｌｏｒｉｎｇｍｏｄｅｌｔｏｓｏｌｖｅｉｔ．Ｆｉｒｓｔｌｙ，ａｃｏｎｆｌｉｃｔｇｒａｐｈｓｔｒｕｃｔｕｒｅｉｓｕｓｅｄｔｏｒｅｐｒｅｓｅｎｔｔｈｅｃｏｎｆｌｉｃｔｒｅｌａｔｉｏｎｓｈｉｐａｍｏｎｇｔｈｅｉｔｅｍｓ
5、，ａｎｄｔｈｅｎ，ｂａｓｅｄｏｎｔｈｅｃｏｎｆｌｉｃｔｇｒａｐｈ，ｔｈｅａｌｇｏｒｉｔｈｍｗｉｌｌｆｉｎｉｓｈａｃｏｌｏｒｉｎｇｐｒｏｃｅｄｕｒｅｔｏｇｒｏｕｐａｌｌｔｈｅｉｔｅｍｓａｎｄｅｎｓｕｒｅｔｈａｔｔｈｅｒｅｉｓｎｏｉｔｅｍｓｗｉｔｈｃｏｎｆｌｉｃｔｒｅｌａｔｉｏｎｓｈｉｐｉｎｅａｃｈｇｒｏｕｐ，ａｎｄｌａｓｔｌｙ，ａｎｉｍｐｒｏｖｅｄＦＦＤａｌｇｏｒｉｔｈｍｉｓｕｓｅｄｔｏｃｏｍｐｌｅｔｅｔｈｅｐａｃｋｉｎｇｏｐｅｒａｔｉｏｎｆｏｒｔｈｅｉｔｅｍｓｉｎｅａｃｈｇｒｏｕｐ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉ
6、ｔｈｍｏｆｔｈｉｓｐａｐｅｒｃｏｕｌｄｆｉｎｄａｆｅａｓｉｂｌｅｓｏｌｕｔｉｏｎｏｆＢＰＰＣｑｕｉｃｋｌｙａｎｄｅｆｆｉｃｉｅｎｔｌｙ，ａｎｄｐｒｏｖｉｄｅａｎｅｗａｐｐｒｏａｃｈｆｏｒｔｈｉｓｋｉｎｄｏｆｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｓ．Keywords：ｏｐｅｒａｔｉｏｎｓｒｅｓｅａｒｃｈａｎｄｃｙｂｅｒｎｅｔｉｃｓ；ｂｉｎｐａｃｋｉｎｇｐｒｏｂｌｅｍｗｉｔｈｃｏｎｆｌｉｃｔｓ；ｇｒａｐｈｃｏｌｏｒｉｎｇ；ｈｅｕｒｉｓｔｉｃａｌｇｏｒｉｔｈｍ０引言［１］裝箱問題在切割加工和物流運(yùn)輸?shù)刃袠I(yè)當(dāng)中有著廣泛的應(yīng)用背景。然而，在對食品、藥品以及某
7、些危險品貨物的包裝過程當(dāng)中，待裝箱的貨物往往由于其不同的物理、化學(xué)和生物性質(zhì)，導(dǎo)致某些貨物不［２］允許被裝入到同一個貨箱當(dāng)中。因此，便產(chǎn)生了帶有沖突關(guān)系的裝箱問題（ＢｉｎＰａｃｋｉｎｇＰｒｏｂｌｅｍｗｉｔｈＣｏｎｆｌｉｃｔｓ，ＢＰＰＣ）。ＢＰＰＣ問題是在經(jīng)典裝箱問題的基礎(chǔ)之上加入了貨物沖突限制，因此，它也是一個［３］ＮＰ-ｈａｒｄ問題。ＢＰＰＣ問題源于經(jīng)典裝箱問題，在ＢＰＰＣ模型當(dāng)中，如果忽略貨物間的沖突關(guān)系，便可以將其轉(zhuǎn)化成為一個普通的裝箱問題。因此，可以借鑒裝箱問題的求解算法解決ＢＰＰＣ問題。Ｌｏｄｉ等人對不同維度的裝收稿日期：２０１２-０
8、９-２１基金項(xiàng)目：國家社會科學(xué)基金項(xiàng)目資助項(xiàng)目（１０ＣＧＬ０７６）作者簡介：元野（１９８５-），男，朝鮮族，黑龍江雙鴨山人，博士研究生，研究方向：運(yùn)籌
