元 野， 李一軍

(1.哈爾濱工業(yè)大學(xué) 管理學(xué)院，哈爾濱 150001； 2. 國家自然科學(xué)基金委員會 管理科學(xué)部，北京 100085)

?

帶沖突關(guān)系裝箱問題的啟發(fā)式求解算法

元 野1， 李一軍2

(1.哈爾濱工業(yè)大學(xué) 管理學(xué)院，哈爾濱 150001； 2. 國家自然科學(xué)基金委員會 管理科學(xué)部，北京 100085)

現(xiàn)實(shí)物流活動中大量存在的食品、藥品和危險(xiǎn)品等貨物的分組包裝問題屬于帶沖突關(guān)系的裝箱問題(BPPC)，其優(yōu)化目標(biāo)是在滿足貨物間沖突限制的前提下完成裝箱操作，并最小化使用貨箱的數(shù)量。本文從實(shí)際需求出發(fā)，基于貨物之間的沖突關(guān)系、裝箱順序和貨箱容量等約束建立相應(yīng)的數(shù)學(xué)規(guī)劃模型；隨后設(shè)計(jì)了求解BPPC問題的啟發(fā)式算法，算法通過迭代求解最大團(tuán)結(jié)構(gòu)實(shí)現(xiàn)貨物間沖突關(guān)系的消去，根據(jù)當(dāng)前貨物最大團(tuán)采用改進(jìn)降序首次適應(yīng)算法(FFD)完成貨物裝箱操作，并通過“洗牌”策略對已有裝箱方案進(jìn)行局部優(yōu)化；最后，針對Iori算例數(shù)據(jù)，將以上算法與基于圖著色的啟發(fā)式算法進(jìn)行比較分析，結(jié)果表明，本文算法是求解BPPC問題更為有效的方法。

運(yùn)籌學(xué)與控制論；沖突裝箱問題；最大團(tuán)；啟發(fā)式算法

0 引言

裝箱問題(bin packing problem, BPP)是一個(gè)經(jīng)典的組合優(yōu)化難題，在切割加工與物流運(yùn)輸?shù)阮I(lǐng)域有著廣泛應(yīng)用，并已被證明屬于NP完全問題[1,2]。在對食品、藥品以及某些危險(xiǎn)品貨物的包裝過程中，由于不同的物理、化學(xué)或生物性質(zhì)，導(dǎo)致某些貨物不允許被裝入到同一個(gè)貨箱當(dāng)中，由此便產(chǎn)生了帶有沖突關(guān)系的裝箱問題(bin packing problem with conflicts, BPPC)。BPPC模型是在經(jīng)典裝箱模型的基礎(chǔ)上，加入了貨物沖突限制，是裝箱模型與圖著色模型的結(jié)合形式，求解時(shí)需要兼顧“密集裝箱”與“沖突化解”兩方面的內(nèi)容，才能實(shí)現(xiàn)問題的全局優(yōu)化[3]。

BPPC模型源于經(jīng)典裝箱問題模型，但其求解難度更大，目前國內(nèi)外針對這一問題的研究內(nèi)容甚少。Jansen[4]首次將BPPC模型中的沖突關(guān)系表示成圖結(jié)構(gòu)形式，通過迭代的求解最大導(dǎo)出子圖，設(shè)計(jì)了漸近式近似求解算法框架；Gendreau等[5]首次提出了BPPC問題的整數(shù)規(guī)劃模型，并分別從裝箱模型和圖著色模型兩個(gè)角度探討了問題下界；Muritiba等[6]采用集合覆蓋的方式對BPPC問題進(jìn)行了重新建模，在對問題下界進(jìn)行近似討論的基礎(chǔ)上，提出了分支定界算法進(jìn)行精確求解；Khanafer等[7]基于樹結(jié)構(gòu)分解的方式設(shè)計(jì)了求解BPPC問題的通用算法框架；Elhedhli等[8]通過定義分支規(guī)則來消除沖突約束，基于此采用動態(tài)規(guī)劃的方式進(jìn)行計(jì)算。從模型求解角度，作為NP-hard問題，傳統(tǒng)數(shù)學(xué)規(guī)劃方法和精確算法在求解能力和效率上有所不足，針對BPPC模型的特征，需要設(shè)計(jì)包含沖突化解和貨物裝箱的兩階段啟發(fā)式算法。沖突關(guān)系的定義和消去可以基于沖突圖結(jié)構(gòu)來實(shí)現(xiàn)，其思想源于圖著色模型中的最小色數(shù)問題[9,10]；而裝箱問題的啟發(fā)式算法在文獻(xiàn)[11]當(dāng)中進(jìn)行了系統(tǒng)總結(jié)。此外，BPPC模型及其求解算法還可以應(yīng)用于特定的調(diào)度問題和資源分配問題，例如排考問題的建模和求解[12]。

本文重點(diǎn)闡述BPPC問題的數(shù)學(xué)模型，并基于該模型設(shè)計(jì)包含沖突化解和貨物裝箱過程的求解算法。主要包括三方面的工作：首先，引入沖突圖結(jié)構(gòu)來對貨物之間的沖突關(guān)系進(jìn)行描述，將貨物集合定義為圖結(jié)構(gòu)上的沖突因子；其次，針對圖著色過程中貨物劃分易陷入局部最優(yōu)的缺點(diǎn)，從沖突圖的補(bǔ)圖——兼容圖入手，迭代求解其最大團(tuán)結(jié)構(gòu)，獲取當(dāng)前相互之間不存在沖突關(guān)系的最大貨物子集；第三，基于數(shù)學(xué)模型和當(dāng)前獲取的最大團(tuán)結(jié)構(gòu)，采用改進(jìn)降序首次適應(yīng)啟發(fā)式求解算法實(shí)現(xiàn)裝箱操作。最后選取國際標(biāo)準(zhǔn)算例進(jìn)行仿真驗(yàn)證，實(shí)驗(yàn)結(jié)果表明，上述算法是求解BPPC模型的有效方法。

1 BPPC問題的數(shù)學(xué)規(guī)劃模型

BPPC模型的基本定義可以描述為：給定由n件重量分別為w1,w2,…,wn的貨物組成的貨物列表I和由m個(gè)最大容量均為c的貨箱組成的貨箱列表H；I中的任意一件貨物i對應(yīng)一個(gè)沖突貨物列表Li，其中的每件貨物均與i之間存在沖突關(guān)系，即不允許與i裝入到同一貨箱當(dāng)中；模型的求解目標(biāo)是在滿足貨箱容量和貨物間沖突約束的前提下，將I中的所有貨物裝入貨箱當(dāng)中，并最小化所使用貨箱的數(shù)量[5]。為具體描述貨物之間的沖突關(guān)系，引入沖突圖的定義如下。

定義1 沖突圖CG=(CV,CE)為一個(gè)無向圖，代表I內(nèi)所有貨物之間的沖突關(guān)系。其中，頂點(diǎn)集合CV對應(yīng)I中的每件貨物，邊集CE對應(yīng)貨物之間的沖突關(guān)系。

為方便沖突關(guān)系消去和后續(xù)裝箱操作，需要對沖突圖中的邊集CE進(jìn)行如下擴(kuò)展：首先，對任意貨物i∈I，在i與其對應(yīng)的沖突貨物列表Li內(nèi)的每件貨物之間添加一條邊；其次，對任意兩件貨物i,j∈I，如果wi+wj>c，則在i和j之間添加一條邊。

BPPC數(shù)學(xué)模型需要用到的決策變量包括：

數(shù)學(xué)規(guī)劃模型表示如下[7]：

(1)

(2)

(3)

xih+xjh≤yh,(i,j)∈CE,h∈H

(4)

yh∈{0,1},h∈H

(5)

xih∈{0,1},i∈I,h∈H

(6)

以上模型當(dāng)中，(1)式表示BPPC模型的目標(biāo)函數(shù)；(2)式表示任意一件貨物只能裝入到一個(gè)貨箱當(dāng)中；(3)式表示任意一個(gè)貨箱中裝入所有貨物的重量之和不允許超過貨箱的最大容量；(4)～(6)式表明任意一個(gè)貨箱當(dāng)中裝入的所有貨物都必需滿足沖突約束限制。

2 基于最大團(tuán)的BPPC問題啟發(fā)式算法

BPPC模型較為直觀的解法是基于沖突圖結(jié)構(gòu)上的獨(dú)立集來消去沖突關(guān)系，通常采用圖著色的方式實(shí)現(xiàn)，即對沖突圖CG中可以裝入到同一貨箱中的貨物著以相同的顏色，求得貨物列表I的一個(gè)劃分，并基于每一劃分進(jìn)行裝箱。然而，圖著色過程不僅時(shí)間復(fù)雜度較高，并且由于強(qiáng)制將貨物列表I進(jìn)行劃分，容易陷入局部最優(yōu)的狀態(tài)，很難取得質(zhì)量很高的裝箱方案。針對這一缺陷，本文將沖突圖的補(bǔ)圖定義為兼容圖，迭代求解兼容圖上的最大團(tuán)結(jié)構(gòu)，每次根據(jù)當(dāng)前獲取的最大團(tuán)采用改進(jìn)降序首次適應(yīng)的方法進(jìn)行裝箱操作，并通過“洗牌”策略對獲取的裝箱方案進(jìn)行局部再優(yōu)化，以期獲取質(zhì)量更高的裝箱方案。

2.1 基于最大團(tuán)結(jié)構(gòu)的沖突關(guān)系消去方法

2.1.1 最大團(tuán)的定義

定義2[13]給定簡單無向圖G=(V,E)，其中的完全子圖Q稱為圖G中的一個(gè)團(tuán)結(jié)構(gòu)，即Q中任意兩個(gè)頂點(diǎn)之間都有E中的一條邊相連接，如圖1所示。

圖1 團(tuán)結(jié)構(gòu)示意圖

定義3 對于給定圖G中的一個(gè)團(tuán)結(jié)構(gòu)Q和頂點(diǎn)υ(v∈G且υQ)，如果頂點(diǎn)集合Q∪{υ}仍為圖G中的一個(gè)團(tuán)結(jié)構(gòu)，則記υ為團(tuán)Q的鄰接頂點(diǎn)，且將Q在G中的所有鄰接頂點(diǎn)數(shù)目記為ρ(Q)。

定義4[13]對于圖G中的團(tuán)結(jié)構(gòu)Q來說，如果ρ(Q)=0，則稱Q為圖G的一個(gè)極大團(tuán)；頂點(diǎn)數(shù)量最多的極大團(tuán)稱為圖G的最大團(tuán)。

顯然，圖G的最大團(tuán)一定是它的極大團(tuán)，反之不成立。最大團(tuán)問題(maximum clique problem, MCP)的求解也是NP難的，隨著圖中頂點(diǎn)數(shù)量的增多和邊密度的增大，求解問題的時(shí)間復(fù)雜度越來越高。因此，通常采用啟發(fā)式算法或智能算法進(jìn)行求解。

2.1.2 基于最大團(tuán)的沖突消去總體策略

兼容圖是沖突圖的轉(zhuǎn)換形式，沖突圖上的獨(dú)立集等價(jià)于兼容圖上的團(tuán)結(jié)構(gòu)，都對應(yīng)不含沖突關(guān)系的貨物子集。因此，求解沖突圖上的獨(dú)立集和兼容圖上的團(tuán)結(jié)構(gòu)是兩種消去貨物間沖突關(guān)系的有效方法，二者基于不同的數(shù)據(jù)結(jié)構(gòu)得以實(shí)現(xiàn)。根據(jù)BPPC模型定義，沖突消去的目的是在貨物列表I中尋找可相互兼容的貨物子集I’，并基于I’進(jìn)行裝箱操作。本文通過求解兼容圖上的最大團(tuán)結(jié)構(gòu)來搜索可相互兼容的貨物子集，設(shè)計(jì)了基于最大團(tuán)結(jié)構(gòu)的沖突消去方法，其具體步驟如下[5]：

Step 1 從還未裝箱的貨物列表當(dāng)中挑選出與所有貨物間均不存在沖突關(guān)系的貨物集合，即從沖突圖CG=(CV,CE)中挑選出所有度數(shù)為零的頂點(diǎn)集合CV0，并令沖突圖CG=(CV-CV0,CE)；若CV=?，則轉(zhuǎn)至Step 4；

Step 2 采用2.1.3小節(jié)部分中介紹啟發(fā)式策略計(jì)算當(dāng)前沖突圖CG=(CV-CV0,CE)中的一個(gè)最大團(tuán)D，并隨機(jī)選取貨物i∈D；

Step 4 令DI=Di∪CV0，DI則為貨物列表的一個(gè)沖突消去結(jié)果；

Step 5 輸出DI，當(dāng)前沖突消去過程結(jié)束。

圖2 沖突消去過程示例

2.1.3 最大團(tuán)的計(jì)算

沖突消去過程中，針對沖突圖和兼容圖的最大團(tuán)計(jì)算是核心內(nèi)容，并且后續(xù)的裝箱操作也是基于當(dāng)前兼容圖上的貨物最大團(tuán)進(jìn)行。因此，最大團(tuán)的求解質(zhì)量決定了可同時(shí)執(zhí)行裝箱操作的貨物規(guī)模，是獲得較優(yōu)裝箱方案的基礎(chǔ)。此外，目前計(jì)算最大團(tuán)的啟發(fā)式算法通常是基于當(dāng)前已獲得的極大團(tuán)列表，從中挑選出頂點(diǎn)數(shù)最多的一個(gè)極大團(tuán)作為結(jié)果輸出，因此，算法還需要充分考慮給定圖結(jié)構(gòu)上極大團(tuán)的搜索能力[14]。綜合以上分析內(nèi)容，本文基于給定圖結(jié)構(gòu)的鄰接矩陣和當(dāng)前最大團(tuán)，采用頂點(diǎn)插入過程和頂點(diǎn)取代過程進(jìn)行優(yōu)化，設(shè)計(jì)了迭代求解最大團(tuán)的啟發(fā)式搜索算法。

(1)頂點(diǎn)插入過程

(2)頂點(diǎn)取代過程

(3)啟發(fā)式搜索策略

Step 2 基于極大團(tuán)Qi，調(diào)用頂點(diǎn)插入過程對Qi進(jìn)行擴(kuò)展；

Step 3 基于擴(kuò)展后的極大團(tuán)Qi，遍歷其中全部可取代的頂點(diǎn)，調(diào)用頂點(diǎn)取代過程對Qi進(jìn)行再擴(kuò)充，并從頂點(diǎn)取代結(jié)果中選取頂點(diǎn)數(shù)最多的Qi插入到極大團(tuán)列表List中；

Step 4 若不存在還未遍歷的頂點(diǎn)i，則選取頂點(diǎn)數(shù)最多的Qi，令Qmax=Qi，并轉(zhuǎn)至Step5；否則令i=i+1，并轉(zhuǎn)至Step 1；

Step 5 從List中隨機(jī)選取兩個(gè)極大團(tuán)Qx和Qy，令Qx,y=Qx∩Qy，并依次調(diào)用頂點(diǎn)插入過程和頂點(diǎn)取代過程對Qx,y進(jìn)行擴(kuò)展；

Step 6 若Qx,y中頂點(diǎn)數(shù)量多于Qmax，則令Qmax=Qx,y；否則，若不滿足算法終止條件(執(zhí)行Step 5的最大次數(shù)，此處設(shè)定為100次)，轉(zhuǎn)至Step 5；

Step 7 輸出Qmax，一個(gè)最大團(tuán)的計(jì)算過程結(jié)束。

2.2 改進(jìn)FFD啟發(fā)式裝箱算法

經(jīng)過沖突關(guān)系消去后得到的貨物最大團(tuán)即為當(dāng)前可直接進(jìn)行裝箱操作的貨物集合。通常來說，為了獲取質(zhì)量較高的裝箱方案，需要基于“大件貨物優(yōu)先裝箱”和“密集裝箱”兩項(xiàng)原則進(jìn)行方案構(gòu)建。其中，“大件貨物優(yōu)先裝箱”原則是指優(yōu)先考慮將重量較大的貨物裝入到貨箱當(dāng)中；“密集裝箱”原則是指針對某一個(gè)已被使用的貨箱來說，盡可能向其中裝入更多的貨物。以上兩個(gè)原則的實(shí)質(zhì)是提高每個(gè)貨箱的空間利用率，即一個(gè)貨箱中已裝入的所有貨物重量之和與該貨箱最大容量之間的比值。算法可以通過提高所有貨箱的空間利用率來減少裝箱方案中所使用貨箱的數(shù)量。因此，針對一個(gè)不含沖突關(guān)系的貨物集合，本文基于著名的降序首次適應(yīng)算法[16](First Fit Decreasing, FFD)進(jìn)行改進(jìn)，設(shè)計(jì)了一種包含構(gòu)建過程和優(yōu)化過程的啟發(fā)式裝箱算法。

在初始狀態(tài)下，問題的啟發(fā)式信息只有各貨物的重量和貨箱的容量值，因此，需要依據(jù)“大件貨物優(yōu)先裝箱”原則構(gòu)建一個(gè)較優(yōu)的初始裝箱方案。具體過程為：首先，按照貨物列表中貨物重量由大到小的順序?qū)ω浳镞M(jìn)行重新排序；然后，順次遍歷排序后的貨物列表，如果當(dāng)前貨箱的剩余容量可以容納遍歷到的貨物，則對該貨物進(jìn)行裝箱操作，并將其從貨物列表中刪除；否則，跳過該貨物繼續(xù)遍歷余下貨物；最后，如果遍歷完成后，貨物列表仍不為空，則開啟一個(gè)新貨箱，重復(fù)以上裝箱過程，直到所有貨物均完成裝箱操作為止。

通過以上操作得到一個(gè)完整的裝箱方案之后，問題的啟發(fā)式信息變?yōu)楦髫浵涞目臻g利用率，因此，需要依據(jù)“密集裝箱”原則提高貨箱空間的利用情況，從而進(jìn)一步減少使用貨箱的數(shù)量。具體過程為：首先，從已有裝箱方案中選取空間利用率最低的一個(gè)貨箱，復(fù)制保存其中的所有貨物信息，并釋放該貨箱空間；其次，采用“洗牌”策略[2]對上述貨物進(jìn)行重新裝箱，即順次遍歷每件貨物，依據(jù)現(xiàn)有各貨箱的剩余容量，采用首次適應(yīng)算法[16](First Fit, FF)執(zhí)行裝箱操作。如果通過“洗牌”策略得到更優(yōu)的裝箱方案，則用新方案取代舊方案，否則繼續(xù)重復(fù)執(zhí)行上述操作，直到滿足算法終止條件為止(由于“洗牌”操作中不包含隨機(jī)過程，此處的算法終止條件為連續(xù)執(zhí)行10次“洗牌”操作仍無法得到有所改進(jìn)的裝箱方案)。

圖3 算法流程圖

2.3 算法總體流程

以上內(nèi)容詳細(xì)介紹了針對BPPC模型的沖突消去過程和貨物裝箱過程。沖突消去過程主要通過最大團(tuán)結(jié)構(gòu)的表示和求解來實(shí)現(xiàn)，貨物裝箱過程主要通過改進(jìn)FFD算法來實(shí)現(xiàn)，二者有序結(jié)合在基于迭代過程的算法框架當(dāng)中。流程圖如圖3所示。

3 實(shí)驗(yàn)與分析

為驗(yàn)證算法性能，選取文獻(xiàn)[6]中基于標(biāo)準(zhǔn)裝箱問題算例設(shè)計(jì)的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行測試，所有實(shí)驗(yàn)數(shù)據(jù)可以從網(wǎng)站http://www.or.deis.unibo.it/research_pages/ORinstances/BPPC.html上下載。算例分為三類，貨物數(shù)量分別為120、250和500，其中每件貨物的重量在20～100之間隨機(jī)選定，所有貨箱容量值固定為150。每一類算例按照沖突貨物數(shù)量的密度值δ(0.1≤δ≤0.9)不同進(jìn)一步劃分為九個(gè)小組，每個(gè)小組有十個(gè)具體算例。密度值δ的計(jì)算方式為：對某一貨物i賦予一個(gè)滿足[0,1]區(qū)間上均勻分布的特征值pi，那么，對于同組算例中的另外一件貨物j，如果滿足(pi+pj)/2≤δ，則在貨物i與貨物j之間添加一對沖突關(guān)系。為驗(yàn)證提出算法的有效性，選取文獻(xiàn)[17]中提出的基于圖著色的沖突消去方法與本文提出的基于最大團(tuán)的沖突消去方法分別實(shí)現(xiàn)并進(jìn)行比較，比較內(nèi)容主要包括針對每組算例計(jì)算得出的最優(yōu)值、最差值和均值，并通過均值來計(jì)算算法改進(jìn)效率。所有算法細(xì)節(jié)采用Java語言來實(shí)現(xiàn)，相應(yīng)的虛擬機(jī)版本為Java Development Kit 1.7.0，具體計(jì)算結(jié)果如表1所示。

表1 兩類啟發(fā)式算法計(jì)算結(jié)果對照表

(1)在貨物數(shù)量規(guī)模相同的一類算例內(nèi)部，當(dāng)沖突密度值較小的時(shí)候(0.1≤δ≤0.3)，由于兼容圖中的邊較為稠密，算法求解質(zhì)量主要取決于改進(jìn)FFD裝箱算法的性能，此時(shí)本文提出算法相比基于圖著色過程的啟發(fā)式算法改進(jìn)程度較小；隨著沖突密度值的增大(0.4≤δ≤0.6)，兼容圖中的頂點(diǎn)集合劃分?jǐn)?shù)量增多，此時(shí)基于最大團(tuán)的啟發(fā)式算法更為有效地將沖突消去過程和裝箱過程有機(jī)結(jié)合在一起，計(jì)算結(jié)果的改進(jìn)程度較大；在沖突密度值最大的情況下(0.7≤δ≤0.9)，兼容圖中的邊較為稀疏，算法求解質(zhì)量與沖突消去過程密切相關(guān)，此時(shí)本文提出算法具有更強(qiáng)的兼容貨物搜索能力，但計(jì)算結(jié)果的改進(jìn)能力有所下降。

(2)從整體角度來看，不同規(guī)模的三類算例在計(jì)算結(jié)果上均有所改進(jìn)。相比基于圖著色過程的啟發(fā)式算法，本文提出算法通過迭代方式搜索兼容圖上的貨物最大團(tuán)，更大限度的發(fā)揮改進(jìn)FFD裝箱算法的計(jì)算性能，有助于獲得質(zhì)量更優(yōu)的裝箱方案。

4 結(jié)論

帶沖突關(guān)系裝箱問題是圖著色問題與裝箱問題這兩個(gè)經(jīng)典NP難題融合之后的一個(gè)新問題。盡管該問題在實(shí)際物流系統(tǒng)中的應(yīng)用更為廣泛，但由于問題的復(fù)雜性，直至最近幾年才引起國內(nèi)外學(xué)者們的關(guān)注。本文根據(jù)問題的數(shù)學(xué)模型，采用最大團(tuán)計(jì)算取代圖著色方式實(shí)現(xiàn)貨物沖突關(guān)系的消去，并基于此設(shè)計(jì)了求解該問題的一個(gè)混合啟發(fā)式算法。實(shí)驗(yàn)表明，本文提出的算法有效地將“沖突化解”和“貨物裝箱”過程融為一體，根據(jù)問題蘊(yùn)含的啟發(fā)式知識引入局部搜索算子，在保證求解質(zhì)量的同時(shí)，確保了算法的穩(wěn)定性。但通過實(shí)驗(yàn)也發(fā)現(xiàn)，算法有時(shí)也容易陷入局部最優(yōu)，尤其問題規(guī)模較大時(shí)，其求解質(zhì)量會受到影響，下階段工作將側(cè)重解決這一方面的問題。

[1] W?scher G, Hau?ner H, Schumann H. An improved typology of cutting and packing problems[J]. European Journal of Operational Research, 2007, 183(3): 1109-1130.

[2] Zhu W B, Zhang Z Y, Oon W C, Lim A. Space defragmentation for packing problems[J]. European Journal of Operational Research, 2012, 222(3): 452- 462.

[3] Lin Y H, Lin C, Lin B. On conflict and cooperation in a two-echelon inventory model for deteriorating items[J]. Computers & Industrial Engineering, 2010, 59(4): 703-711.

[4] Jansen K. An approximation scheme for bin packing with conflicts[J]. Journal of Combinational Optimization, 1999, 3(4): 363-377.

[5] Gendreau M, Laporte G, Semet F. Heuristics and lower bounds for the bin packing problem with conflicts[J]. Computers & Operations Research, 2004, 31(3): 347-358.

[6] Muritiba A E F, Iori M, Malaguti E, Toth P. Algorithms for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2010, 22(3): 401- 415.

[7] Khanafer A, Clautiaux F, Talbi E. New lower bounds for bin packing problems with conflicts[J]. European Journal of Operational Research, 2010, 206(2): 281-288.

[8] Elhedhli S, Li L Z, Gzara M, Naoum-sawaya J. A branch-and-price algorithm for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2011, 22(3): 404- 415.

[9] Galinier P, Hertz A. A survey of local search methods for graph coloring[J]. Computers & Operations Research, 2006, 33(9): 2547-2562.

[10] Balogh J, Butterfield J. Excluding induced subgraphs: critical graphs[J]. Random Structures & Algorithms, 2011, 38(1-2): 100-120.

[11] Balogh J, Békési J, Galambos G. New lower bounds for certain classes for bin packing algorithms[J]. Theoretical Computer Science, 2012, 440-441: 1-13.

[12] Gogos C, Alefragis P, Housos E. An improved multi-staged algorithmic process for the solution of the examination timetabling problem[J]. Annals of Operations Research, 2012, 194(1): 203-221.

[13] 潘全,郭鳴,林鵬.基于MapReduce的最大團(tuán)算法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(S2):150-153.

[14] Chen Q, Fadlullah Z M, Lin X D, Kato N. A clique-based secure admission control scheme for mobile adhoc networks(MANETs)[J]. Journal of Network and Computer Applications, 2011, 34(6): 1827-1835.

[15] Dang D C, Moukrim A. Subgraph extraction and metaheuristics for the maximum clique problem[J]. Journal of Heuristics, 2012, 18(5): 767-794.

[16] Elhedhli S. Ranking lower bounds for the bin-packing problem[J]. European Journal of Operational Research, 2005, 160(1): 34- 46.

[17] Galinier P, Hertz A. A survey of local search methods for graph coloring[J]. Computers and Operations Research, 2006, 33(9): 2547-2562.

A Heuristic Algorithm for Solving the Bin Packing Problem with Conflicts

YUAN Ye1, LI Yi-jun2

(1.SchoolofManagement,HarbinInstituteofTechnology,Harbin150001,China; 2.DepartmentofManagement,NationalNaturalScienceFoundationofChina,Beijing100085,China)

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 structure 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.

operations research and cybernetics; bin packing problem with conflicts; maximum clique; heuristic algorithm

2013- 07- 02

國家社會科學(xué)基金項(xiàng)目資助(10CGL076)；教育部人文社會科學(xué)研究青年項(xiàng)目資助(12YJC630160)；黑龍江省自然科學(xué)基金項(xiàng)目資助(G201020)；黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(11551332)

元野(1985-)，男，朝鮮族，博士研究生，主要研究方向：運(yùn)籌學(xué)、物流與車輛調(diào)度；李一軍(1957-)，男，教授，博士生導(dǎo)師，主要研究方向：管理信息系統(tǒng)、電子商務(wù)。

F224.31

A

1007-3221(2015)02- 0051- 07