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

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

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

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

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

1 問題描述

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

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

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

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

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

則裝載問題可以描述為：

[maxi=1nwixi] （1）

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

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

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

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

優(yōu)先隊(duì)列式分支限界法同樣需要存儲解空間樹，因此空間復(fù)雜度也是[O（2n）]。但該算法是以最小耗費(fèi)（最大效益）的方式搜索解空間樹，最小耗費(fèi)（最大效益）是用最小堆（最大堆）實(shí)現(xiàn)最?。ㄗ畲螅﹥?yōu)先隊(duì)列，故其時間復(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算法過程分析

先求出解空間樹各個層的剩余集裝箱的總重量，即[r[1..4]={17，15，9，4}]。當(dāng)前擴(kuò)展結(jié)點(diǎn)0（數(shù)字零，用以表示進(jìn)行擴(kuò)展的第一個結(jié)點(diǎn)，此時還沒有擴(kuò)展任何一個集裝箱）為載重量為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]加入最大堆。然后從最大堆中取出對頂元素，按照上述擴(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)解，從而降低時間復(fù)雜度和空間復(fù)雜度。分支限界法根據(jù)擴(kuò)展下一結(jié)點(diǎn)的不同可以有隊(duì)列式分支限界法和優(yōu)先隊(duì)列式分支限界法。優(yōu)先隊(duì)列式分支限界法采用最大堆或最小堆實(shí)現(xiàn)最大或最小優(yōu)先隊(duì)列，使搜索始終想著最優(yōu)的方向，相對隊(duì)列式分支限界可以更加快的搜索到最優(yōu)解。

參考文獻(xiàn)：

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

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

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