分支限界裝載問題的算法分析與設(shè)計(jì)

孫瑞芳 焦曉君 施瑞娜 李雯璐

摘要：該文主要介紹用分支限界的方法解決裝載問題。首先給出對(duì)裝載問題的描述；接著著重優(yōu)先隊(duì)列式分支限界法的算法設(shè)計(jì)思想和算法分析展開談?wù)?；最后給出實(shí)驗(yàn)，用分支限界法來解決裝載問題，從而得到集裝箱裝載問題的裝載方案或者不存在合理的裝載方案。

關(guān)鍵詞：隊(duì)列式分支限界法；優(yōu)先隊(duì)列式分支限界法；裝載問題

中圖分類號(hào)：TP301 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2015）03-0105-01

在美國，運(yùn)輸費(fèi)占GDP的比重大約為6%，大于庫存費(fèi)用4%的比重[1]。在我國，自從加入WTO后，很多領(lǐng)域相繼對(duì)外開放，更多的跨國企業(yè)進(jìn)入我國參與競(jìng)爭(zhēng)，我們的物流配送也出現(xiàn)了一些新的變化和趨向[2]?？梢娔壳斑\(yùn)輸問題在實(shí)際操作中存在的效率和效益低下的現(xiàn)狀。本文解決裝載問題的理論依據(jù)就是分支限界法，即在滿足約束條件的前提下，通過限界條件來加快找到最佳方案的效率。

1 問題描述

有一批共[n]個(gè)集裝箱要裝上2艘載重量分別為[c1]和[c2]的兩艘輪船，其中集裝箱[i]的重量為[wi]，且[i=1nwi≤c1+c2]。裝載問題要求確定是否存在一個(gè)合理的裝載方案可將這[n]個(gè)集裝箱要裝上這2艘輪船。如果有，找出裝載方案[3]。

2 分支限界裝載問題算法設(shè)計(jì)

對(duì)于該問題容易證明，如果給定的裝載問題有解，則可以通過下面的方案得到可行的裝載方案[3]：

1）首先將第一艘輪船盡可能裝滿；

2）然后將剩余的集裝箱裝上第二艘輪船。

則裝載問題可以描述為：

[maxi=1nwixi] （1）

s.t.[i=1nwixi≤c1]，（[xi∈{0，1}，1≤i≤n]） （2）

分支限界法的求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解。裝載問題的要求是確定是否存在一個(gè)合理的裝載方案可將這個(gè)集裝箱要裝上這2艘輪船。如果有，找出裝載方案，即只需找出一種求解方案即可。根據(jù)公式1、公式2可知裝載問題可轉(zhuǎn)化為0-1背包問題，故只需將第一艘輪船盡可能裝滿，剩余的集裝箱全部裝入第一艘輪船中，則裝載問題等價(jià)于選取全體集裝箱的一個(gè)子集，使該子集中集裝箱的重量之和盡可能接近其中的一個(gè)輪船。解決裝載問題也就是在滿足約束條件公式2的解中找出使目標(biāo)函數(shù)公式1達(dá)到極大的解，故裝載問題適用于分支限界法。

用優(yōu)先隊(duì)列式分支限界法時(shí)，從第一個(gè)集裝箱[A]開始，分支、限界的方法也相同。優(yōu)先隊(duì)列式分支限界法用一個(gè)極大堆表示活結(jié)點(diǎn)表的優(yōu)先隊(duì)列?；罱Y(jié)點(diǎn)[x]在優(yōu)先隊(duì)列中的優(yōu)先級(jí)定義為從根節(jié)點(diǎn)到活結(jié)點(diǎn)[x]的路徑所相應(yīng)的載重量再加上剩余集裝箱的重量之和，即[Ew+w[i]+r[i]]（[Ew]為擴(kuò)展結(jié)點(diǎn)所相應(yīng)的載重量，[w[i]]為活結(jié)點(diǎn)所對(duì)應(yīng)集裝箱的重量，[r[i]]為剩余集裝箱的重量）。加入活結(jié)點(diǎn)表時(shí)根據(jù)該結(jié)點(diǎn)所代表集裝箱的重量加入到最大堆中，選取下一個(gè)擴(kuò)展結(jié)點(diǎn)時(shí)，總是選取堆頂元素進(jìn)行擴(kuò)展。容易知道，子集樹中葉子結(jié)點(diǎn)的載重量與其優(yōu)先級(jí)相同，所以一旦有葉子結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，則該葉子結(jié)點(diǎn)所相應(yīng)的解就是最優(yōu)解，此時(shí)便可終止算法。

3 算法復(fù)雜度分析

優(yōu)先隊(duì)列式分支限界法同樣需要存儲(chǔ)解空間樹，因此空間復(fù)雜度也是[O（2n）]。但該算法是以最小耗費(fèi)（最大效益）的方式搜索解空間樹，最小耗費(fèi)（最大效益）是用最小堆（最大堆）實(shí)現(xiàn)最小（最大）優(yōu)先隊(duì)列，故其時(shí)間復(fù)雜度為[（nlogn）]。算法執(zhí)行完畢后，可以用隊(duì)列式分支限界法中構(gòu)造最優(yōu)解的方法得出最優(yōu)解。

4 實(shí)驗(yàn)分析

4.1實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)的硬件環(huán)境為CPU：intel（R） Core（TM） i5-3210M CPU @2.50GHz，內(nèi)存4G。操作系統(tǒng)為WIN7旗艦版。軟件環(huán)境為VC++6.0，使用語言為C++語言。

4.2實(shí)驗(yàn)數(shù)據(jù)

5集裝箱要裝入兩艘輪船，集裝箱的重量[w[]={7，2，6，5，4}]，第一艘輪船的載重量[c=10]。

4.3算法過程分析

先求出解空間樹各個(gè)層的剩余集裝箱的總重量，即[r[1..4]={17，15，9，4}]。當(dāng)前擴(kuò)展結(jié)點(diǎn)0（數(shù)字零，用以表示進(jìn)行擴(kuò)展的第一個(gè)結(jié)點(diǎn)，此時(shí)還沒有擴(kuò)展任何一個(gè)集裝箱）為載重量為0，即[Ew=0]；所在層數(shù)為第一層，即[i=1]，故[Ew+w[i]=7]（<10）。由于[Ew+w[i]=7]，大于[bestw]的初始值0，所以更新[bestw]為7。又有[Ew+w[i]+r[i]=24>7]，所以將左兒子結(jié)點(diǎn)[A]加入最大堆。由于[Ew+r[i]=17>7]，故可能包含最優(yōu)解，所以將右兒子結(jié)點(diǎn)[B]加入最大堆。然后從最大堆中取出對(duì)頂元素，按照上述擴(kuò)展方法進(jìn)行擴(kuò)展，直到達(dá)到葉子結(jié)點(diǎn)。然后可以構(gòu)造出最優(yōu)解，最優(yōu)解為[bestx[]={0，0，1，0，1}]。

4.4實(shí)驗(yàn)結(jié)果

根據(jù)分支限界算法的基本原理，運(yùn)用C++程序設(shè)計(jì)語言實(shí)現(xiàn)該算法，可以得到這5只集裝箱的裝載方案，如圖1所示：

圖1 集裝箱裝載方案

5 結(jié)論

分支限界方法是在回溯法的基礎(chǔ)上加上了約束條件和限界條件，由此可以加速找到最優(yōu)解，從而降低時(shí)間復(fù)雜度和空間復(fù)雜度。分支限界法根據(jù)擴(kuò)展下一結(jié)點(diǎn)的不同可以有隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法。優(yōu)先隊(duì)列式分支限界法采用最大堆或最小堆實(shí)現(xiàn)最大或最小優(yōu)先隊(duì)列，使搜索始終想著最優(yōu)的方向，相對(duì)隊(duì)列式分支限界可以更加快的搜索到最優(yōu)解。

參考文獻(xiàn)：

[1] 吳志惠.美國的物流成本[J].中國儲(chǔ)運(yùn)，2002（5）.

[2] 張曉麗.物流配送中心貨物裝載問題研究[D].鄭州：鄭州大學(xué)，2012.

[3] 王曉東.計(jì)算機(jī)算法與技術(shù)分析[M].4版.北京：電子工業(yè)出版社，2012.