模擬退火算法在裝箱問(wèn)題中的應(yīng)用

摘要:裝箱問(wèn)題是個(gè)NPC問(wèn)題[1]，該文采用了模擬退火算法解決這一問(wèn)題。文中給出了數(shù)學(xué)模型，模擬退火算法的步驟并結(jié)合實(shí)例進(jìn)行了收斂性分析，算法理想能迅速得出配裝方案。

關(guān)鍵詞:模擬退火;收斂性

中圖分類(lèi)號(hào):U169文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1009-3044(2010)05-1179-01

在貨物的運(yùn)輸中配裝是關(guān)鍵[6]，貨物的裝配問(wèn)題是個(gè)NPC問(wèn)題[1]，當(dāng)大規(guī)模地進(jìn)行貨物選擇裝箱就會(huì)使得搜索空間以2n的指數(shù)倍規(guī)模擴(kuò)大，計(jì)算時(shí)間也不斷增加，模擬退火算法是局部搜索算法的擴(kuò)展，它不同于局部搜索之處是以一定的概率選擇鄰域中費(fèi)用值大的狀態(tài)。從理論上來(lái)說(shuō)，它是一個(gè)全局最優(yōu)算法[5]。利用模擬退火算法來(lái)解決裝箱問(wèn)題是個(gè)有效辦法，算法收斂迅速，用時(shí)少，解的質(zhì)量高，能滿(mǎn)足現(xiàn)實(shí)要求。

1 裝箱問(wèn)題的數(shù)學(xué)模型[3-4]

設(shè)有n批待裝配的貨物Bi(i=1，2，3…n)，其重為pi，體積為vi，需要將其配裝的集裝箱內(nèi)，集裝箱的靜載重為P，容積為V，則如何裝配貨物使集裝箱載重最大。

以靜載重量最大為優(yōu)化目標(biāo)建立模型

其中變量含意如下

pi表示第i件貨物的重量;vi表示第i件貨物的體積;P表示允許裝貨的總重量;V表示允許裝貨的總體積。

2 算法的實(shí)現(xiàn)

2.1 關(guān)鍵技術(shù)與參數(shù)

目標(biāo)函數(shù):f(x)=p1x1 + p2x2 + p3x3 + p4x4 + p5x5 + p6x6

降溫方法:t=t*0.999。

新解產(chǎn)生方法:隨機(jī)選一個(gè)貨物，若此貨物已裝車(chē)則將其去除，若沒(méi)裝車(chē)則將其裝車(chē)。

內(nèi)循環(huán)終止準(zhǔn)則:在指定溫度下當(dāng)循環(huán)次數(shù)達(dá)到k=1000次時(shí)終止。

算法終止規(guī)則:

零度法[2]:模擬退火算法的最終溫度為零，因而最為簡(jiǎn)單的原則是:給出一個(gè)較小的正數(shù)(本算例取0.001)，當(dāng)溫度小于這個(gè)數(shù)時(shí)，算法停止，表示已經(jīng)達(dá)到最低溫度。

2.2 算法流程[5]

STEP1 初始解x=(0，0，0，0，0，0)沒(méi)有任何貨物裝車(chē)，t=100(初始溫度)

STEP2 內(nèi)循環(huán)是否執(zhí)行了1000次，若執(zhí)行了1000次則轉(zhuǎn)STEP 3;否則從臨域N(x)隨機(jī)生成一個(gè)解x0，計(jì)算df=f(x0)-f(x);若df>=0，則x=x0，否則若exp(df/t)>random(0，1)時(shí)，則x=x0;重復(fù)STEP 2。

STEP 3t=t*0.999;若t<0.001，終止計(jì)算;否則，回到STEP 2。

3 算例分析

3.1 算例[3]

有6件貨物，質(zhì)量分別為8t，11t，7t，13t，15t，8t體積分別為10m3，12m3，8m3，15m3，16m3，9m3集裝箱的標(biāo)記體積為52 m3，靜載重為45t，應(yīng)怎樣進(jìn)行拼箱配裝才能使集裝箱的靜載重得到最大利用。

算例模型:

經(jīng)計(jì)算x1=x4=x5=x6=1，x2=x3=0，Z=44結(jié)果令人滿(mǎn)意。

3.2 算法收斂性

從圖1可以看出隨著跌倒次數(shù)的增加貨車(chē)載貨總重迅速向最大值收斂，最后停留在44t處不再波動(dòng)。因此算法收斂迅速，令人滿(mǎn)意。

4 結(jié)論

實(shí)例數(shù)據(jù)結(jié)果表明，此算法收斂速度快，用時(shí)少。充分體現(xiàn)了模擬退火算法的優(yōu)點(diǎn)，以一定的概率接受質(zhì)量差的解，即可以跳出局部最優(yōu)解。因此，此模擬退火算法能有效的解決裝箱問(wèn)題。

參考文獻(xiàn):

[1] 卜雷，蒲云，劉海旭，等.集裝箱中零擔(dān)貨物合理混載的遺傳退火進(jìn)化算法[J].世界科技研究與發(fā)展，2002，24(6):88-91.

[2] 馮玉蓉， 模擬退火算法的研究及其應(yīng)用[D].昆明:昆明理工大學(xué)，2005.

[3] 付永軍，安晨.改進(jìn)有序組合樹(shù)法在鐵路普通零擔(dān)貨物拼箱配裝中的應(yīng)用[J].鐵道貨運(yùn)，2007(9):12-14，52.

[4] 張?zhí)靷?基于登山法的鐵路零擔(dān)貨物輕重配裝的研究[J].哈爾濱鐵道科技，2006(03):02.

[5] 邢文訓(xùn)，謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社，2009.

[6] 周穎，零擔(dān)貨物配裝模與算法研究[J].鐵道運(yùn)輸與經(jīng)濟(jì)，2006，28(7):32.