楊 輝

摘要:貨物配裝問題是NP—難問題,對這類問題如何求解,學(xué)術(shù)界提出了多種算法,這些算法可歸結(jié)為2大類:精確算法和啟發(fā)式算法。通過對這2類算法中最具代表性的幾種算法的分析、比較和總結(jié),指出了各種算法的優(yōu)缺點(diǎn)、適用范圍和場合、存在的問題以及改進(jìn)的方案,為貨物配裝問題求解過程中算法的選擇提供了依據(jù)和參考。

關(guān)鍵詞:貨物配裝;精確算法;啟發(fā)式算法

中圖分類號:U294文獻(xiàn)標(biāo)識碼:A

Abstract: Loading of goods problem is an NP—hard problem, how to resolve this problem, academia have put forward many algorithms. These algorithms can be clarified as accurate algorithm and heuristic algorithm. By analyzing, comparing, summarizing some representative algorithms, points out advantages, dis—advantages, application scope and situation, problems, as well as improving project, this paper provides the reference for selecting algorithm when resolving loading of goods problem.

Key words: loading of goods; accurate algorithm; heuristic algorithm

1貨物配裝問題概述

貨物配裝問題的研究始于國外,自1939年(Kantorovich)、1940年(Brook等)以來,由于行業(yè)的需要,國外開始出現(xiàn)相關(guān)問題的研究。貨物配裝問題是指在配送中心,有若干需要送給不同客戶且有不同裝載要求的貨物,有若干臺車輛,要求合理安排貨物的裝車順序、合理安排貨物在車輛空間的裝載位置,從而在給定的約束條件下(如車輛的容積、車輛的載重等限制下),研究如何把所需配送的貨物合理裝入車輛中,并使目標(biāo)函數(shù)取得優(yōu)化(如使用車輛少、車輛載重和容積的利用率高等)的方法。

配裝問題在學(xué)術(shù)上屬于相當(dāng)復(fù)雜約束條件的組合優(yōu)化問題,屬于NP—難問題。國內(nèi)外許多學(xué)者對此進(jìn)行了研究,研究的內(nèi)容主要從車輛和貨物兩方面考慮,大致分為四種配裝情形,相同體積貨物與不同體積貨物的配裝、單車型和多車型的配裝。在有的貨物配裝問題中,還要考慮到客戶對貨物需求的優(yōu)先等級或貨物的不相容(某兩種貨物不能在統(tǒng)一輛車內(nèi)配裝)問題,這需要在原模型中增加新的約束條件。對于考慮客戶需求優(yōu)先級的問題,按客戶需求的急迫程度給定相應(yīng)貨物一個優(yōu)先等級,然后按優(yōu)先等級裝配;對于貨物不相容問題,則利用二部分圖的最大匹配問題思想來尋找能夠混裝的最大貨物子集。

另外,按貨物在裝載空間的裝載維數(shù)考慮,貨物配裝問題有二維貨物配裝問題(即因貨物為密度很大的重質(zhì)貨物或易碎怕壓貨物,在車輛內(nèi)只能單層裝載)和三維貨物配裝問題(貨物在車輛內(nèi)可以多層裝載)之分。

一般情況下,貨物配裝問題可以這樣描述:設(shè)配送中心有m輛可選車輛(車輛編號為j,j=1,2,3,…,m)對n件貨物(貨物編號為i,i=1,2,3,…,n)實施裝載配送,每輛車的容積限制為V ,載質(zhì)量限制為G ,每件貨物的體積為v ,質(zhì)量為g ;x 為貨物i和車輛j的關(guān)系變量,如果貨物i裝入貨車j中,x 為1,否則x 為0;y 為貨車j的狀態(tài)變量,如果貨車j被選中用于貨物裝載,y 為1,否則y 為0。

根據(jù)貨物和車輛的數(shù)量,裝載問題可以分為兩大類。一是待裝的貨物相對有限,要求使用的車輛數(shù)目最少。其數(shù)學(xué)模型如下:

minZ= y (1)

s.t.x ≤1 (2)

g x ≤G y (3)

v x ≤V y (4)

二是裝載車輛相對有限,要求充分利用現(xiàn)有車輛的容積和載質(zhì)量,盡可能多載貨物,使車輛的利用率最高。在這種情況下,由于所有的車輛都被選中用于貨物裝載,因此y 為1。決策目標(biāo)為:使得所有車輛裝載貨物的總體積Z 和總質(zhì)量Z 最大。建立該類問題的數(shù)學(xué)模型如下:

maxZ =g x (5)

maxZ =v x (6)

s.t.x ≤1 (7)

g x ≤G (8)

v x ≤V (9)

上述模型中,目標(biāo)函數(shù)(1)為使使用的車輛數(shù)達(dá)到最少,目標(biāo)函數(shù)(5)和(6)為使所有車輛的載重和體積利用率達(dá)到最高;(2)式和(7)式保證了每件貨物只裝一輛車的約束;(3)式和(4)式分別實現(xiàn)了配裝貨物的總質(zhì)量和總體積不超過選擇配裝的車輛的質(zhì)量和體積限制;(8)式為每輛車的裝載重量約束,(9)式為每輛車的裝載體積約束。

2貨物配裝問題的求解算法

由于求解貨物配裝問題的方法很多,而且根據(jù)優(yōu)化目標(biāo)的不同可選擇的算法也有區(qū)別,但究其實質(zhì),可以分為精確算法和啟發(fā)式算法兩大類。

2.1精確算法

精確算法是指可求出其最優(yōu)解的算法,主要有:分枝定界法、割平面法、動態(tài)規(guī)劃法等。

(1)分支定界法。分枝定界法是以廣度優(yōu)先遍歷或以最小耗費(fèi)(最大效益)優(yōu)先的方式搜索問題的解空間樹。在分枝定界法中,當(dāng)搜索到一個結(jié)點(diǎn)時,如果該結(jié)點(diǎn)可以繼續(xù)搜索下去,則稱其為活結(jié)點(diǎn),并加入到活結(jié)點(diǎn)隊列中。利用不同的分枝定界法在活結(jié)點(diǎn)隊列中選擇結(jié)點(diǎn)成為下一層搜索的擴(kuò)展結(jié)點(diǎn),通過該擴(kuò)展結(jié)點(diǎn)搜索其產(chǎn)生的所有子結(jié)點(diǎn),將能繼續(xù)搜索的子結(jié)點(diǎn)加入下一層搜索的貨結(jié)點(diǎn)隊列中,重復(fù)上述結(jié)點(diǎn)擴(kuò)展過程,這個過程一直持續(xù)到找到問題的最優(yōu)解。由于其計算量關(guān)于貨物數(shù)增長較快,所以這種方法只適于求解貨物數(shù)不多的貨物配裝問題。

(2)割平面法。割平面法求解貨物配裝問題(A)的基本思想是,在求解相應(yīng)的不含整數(shù)約束的貨物配裝問題(B)上,增加線性約束條件(幾何術(shù)語稱為割平面),以將B的可行域切割掉一部分,使其切割掉的部分只包含非整數(shù)解,沒有切割掉任何整數(shù)可行解,直到切割后得到的可行域有一個整數(shù)坐標(biāo)的極點(diǎn)恰好是A的最優(yōu)解為止。由于割平面法求解時間過長,故也不適用于大規(guī)模問題。

(3)動態(tài)規(guī)劃法。動態(tài)規(guī)劃法常常用來求解帶客戶需求優(yōu)先級的貨物配裝問題。動態(tài)規(guī)劃法求解貨物配裝問題的基本思路是,將貨物配裝問題視為一個n階段的決策問題,進(jìn)而將其轉(zhuǎn)化為依次求解n個具有遞推關(guān)系的單階段的決策問題,從而簡化計算過程。用這種方法可求得貨物配裝的最優(yōu)解,但僅適用于較小規(guī)模的尋優(yōu)問題。

2.2啟發(fā)式算法

由于精確算法的計算量一般隨問題規(guī)模的增大呈指數(shù)增長,在實際中其應(yīng)用范圍很有限。因此,專家研究出一些更實用、易操作的啟發(fā)式算法。啟發(fā)式算法又分為傳統(tǒng)啟發(fā)式算法和現(xiàn)代啟發(fā)式算法。

2.2.1傳統(tǒng)啟發(fā)式算法

傳統(tǒng)啟發(fā)式算法采用逐步構(gòu)解策略,算法擬從以下幾個方面來考察裝配結(jié)果。①著眼于提高裝載單元的載重力利用率,每次挑選重量最大的物品裝入裝載單元;②著眼于節(jié)省裝載單元的空間容積,每次挑選所占空間最小的物品裝入;③著眼于充分利用裝載單元的容積利用率,每次挑選所占空間最大的物品裝入;④著眼于優(yōu)先運(yùn)送輕浮貨物,每次選取單位比容最大的物品進(jìn)行配裝;⑤著眼于優(yōu)先運(yùn)送重質(zhì)貨物,每次選取單位比容最小的物品進(jìn)行配裝。

Bhatta-charya等提出的深度優(yōu)先搜索算法[1],在求解的過程中,優(yōu)先考慮問題的一個維度。該方法對求解小規(guī)模貨物裝載問題相當(dāng)有效,但是由于該算法的計算量隨裝入貨物數(shù)目的增加呈指數(shù)式增長,不太適合大規(guī)模貨物的裝載。

Scheithauer等在Smith四分區(qū)算法和Bischff五分區(qū)算法基礎(chǔ)上,將該方法擴(kuò)展到大批量單一品種物品的擺放問題[2],但分區(qū)算法需對大量的可能模式進(jìn)行檢驗,尤其是對剩余空間和載質(zhì)量難以妥善處理。

Berghammer等對裝載問題采用線性逐漸逼近的方法進(jìn)行優(yōu)化,不過該方法對逼近的收斂條件較難確定[3]。

孫焰為單車裝載和多車裝載分別設(shè)計了A 算法和First Fit算法。A 算法考慮每個至多有K個元素的子集S,若 g ≤G,及 v ≤V,則從余下來體積以非遞增次序排列的貨物列中逐個取出貨物加入車箱中直至裝滿,該算法被證明是多項式算法具有可行性。同時裝配m輛車的First Fit算法對于各車箱已裝載的貨物集合s ,s ,…,s ,每次為剩余容積最大或剩余載重力最大的車箱尋找一批最合適的貨物裝車,直至所有車箱裝滿為止[4]。

高紅建等的實用啟發(fā)式算法給出了貨物合理比容的數(shù)值定義為“裝載單元的實際比容”(“合理比容”是指裝載單元內(nèi)部的幾何容積與其載重力之比),算法著眼于提高裝載單元的裝載能力利用率,每次選取松弛比容的偏差量最小的物品配裝構(gòu)成了貨物合理配裝的最優(yōu)策略,實現(xiàn)了貨物配裝時的巧裝滿載[5]。

劉小群等對First Fit算法進(jìn)行優(yōu)化,在以容重比為基準(zhǔn)對多品種的貨物進(jìn)行配裝的基礎(chǔ)上,將問題進(jìn)一步深化到各種不同類型的貨物[6]。根據(jù)貨物相對貨車輕重屬性的不同,同類型的貨物,將貨物劃分為不同的類型,采取不同的標(biāo)桿,構(gòu)建基于標(biāo)桿的啟發(fā)式算法。算法通過將貨物的容重比值與裝載單位的容重比值比較分類出輕質(zhì)貨物、重質(zhì)貨物和勻質(zhì)貨物。對于輕質(zhì)貨物,相比而言,貨物的體積較大,因此在算法設(shè)計中,應(yīng)該以貨車的載質(zhì)量為標(biāo)桿,在保證貨車容積能充分利用的前提下,盡可能地提高貨車的載質(zhì)量利用率。對于重質(zhì)貨物而言,則以貨車的容積為標(biāo)桿,在充分利用貨車載質(zhì)量的前提下,盡可能地提高貨車的容積利用率。對于勻質(zhì)貨物,由于貨物的體積和質(zhì)量相對貨車都比較均衡,則應(yīng)以貨車的體積質(zhì)量比為標(biāo)桿,對貨車的容積和載質(zhì)量利用率同時優(yōu)化。

2.2.2現(xiàn)代啟發(fā)式算法

20世紀(jì)90年代以來,由于人工智能方法在解決組合優(yōu)化問題中的強(qiáng)大功能,不少學(xué)者開始將人工智能引入貨物配裝問題的求解中,并構(gòu)造了基于人工智能的啟發(fā)式算法(現(xiàn)代啟發(fā)式算法),現(xiàn)代啟發(fā)式算法包括:

(1)遺傳算法。遺傳算法是進(jìn)行局部搜索改進(jìn)的一類算法。遺傳算法求解貨物配裝問題時,主要利用生物進(jìn)化世代性與最優(yōu)貨物配裝方案的迭代共性,在全局范圍內(nèi)搜索貨物配裝方案的最優(yōu)解。如遇同一級配送結(jié)點(diǎn)分支對優(yōu)化目標(biāo)的相同利用率情況,則均予以考慮,分別參與下一步驟迭代,并由后續(xù)步驟逐漸淘汰,最終確定最優(yōu)貨物配裝方案;如遇同一級配送結(jié)點(diǎn)分支的對優(yōu)化目標(biāo)不同利用率情況,則“適者幸存”,由耗費(fèi)少的配送分支獲得繼續(xù)迭代的權(quán)利,但并不能確定其最優(yōu)資格,必須參與后續(xù)淘汰步驟,直至迭代結(jié)束,得到最優(yōu)貨物配裝方案。卜雷等對零擔(dān)貨物的裝箱方式采用遺傳算法進(jìn)行了模擬[7],結(jié)果表明遺傳算法具有良好的魯棒性、靈活性、通用性,特別適合于大規(guī)模貨物配裝問題的求解。但由于算法本身還存在的一些缺陷,如易出現(xiàn)早熟收斂,局部搜索能力差,因此,不能保證最大概率收斂到全局最優(yōu)解。并且當(dāng)配裝貨物的配裝號較多,配裝關(guān)系十分復(fù)雜時,交叉和變異操作會以一個較大概率產(chǎn)生違背配裝約束的子代染色體, 如果加入懲罰因子則在進(jìn)化過程中會使不符合配裝約束的染色體逐漸增多,從而出現(xiàn)提前成熟的現(xiàn)象,找不到最優(yōu)解。如果改變交叉和變異規(guī)則, 調(diào)整子代染色體代表的配裝方案,使之滿足配裝約束,則父代染色體的大多屬性會丟失,子代失去父代大多數(shù)遺傳信息,遺傳算法變得不可靠。張麗萍等人于2002年通過引入新穎交叉算子,構(gòu)造了一種改進(jìn)遺傳算法。此算法擺脫了對群體多樣性的要求,不存在傳統(tǒng)遺傳算法常見的“早熟收斂”問題,可以有效求得貨物配裝問題的優(yōu)化解。

(2)蟻群算法。蟻群算法是Dorigo提出的一種基于群體仿生的智能優(yōu)化算法。該算法的基本原理是模擬蟻群搜索食物的行為:螞蟻群找到食物時,它們總能找到一條從食物到巢穴之間的最優(yōu)路徑。這是因為螞蟻在尋找路徑時,會在路徑上釋放出一種特殊的信息素。當(dāng)它們碰到一個還沒有走過的路口時,就隨機(jī)地挑選一條路徑前行,并釋放出與路徑長度有關(guān)的信息素。路徑越長,釋放的激素濃度越低,當(dāng)后來的螞蟻再次碰到這個路口的時候,選擇激素濃度較高路徑概率就會相對較大。這樣就形成了一個正反饋,最優(yōu)路徑上的激素濃度越來越大,而其他的路徑上激素濃度卻會隨著時間的流逝而消減,最終整個蟻群會找出最優(yōu)路徑。曹宏美等結(jié)合具體問題,充分利用蟻群算法可以有效解決無法用數(shù)學(xué)表達(dá)式描述問題的優(yōu)勢,構(gòu)造了多約束條件下多品種貨物配裝問題的螞蟻算法[8]。該算法在求解貨物配裝問題方面有良好效果,但存在如計算時間較長、容易陷入局部最優(yōu)等問題。

(3)模擬退火算法。模擬退火法是由Metropolis于1953年提出的,是一種基于熱力學(xué)原理的隨機(jī)搜索算法。賀國先等對貨物配裝問題的模擬退火算法進(jìn)行了研究,提出模擬退火方法適合于解決危險貨物配裝問題[9]。用模擬退火法求解貨物裝配問題時,把物理退火中原子獲得能量相當(dāng)于將貨物配裝到裝載單元中,將原子振動模擬為裝載方案尋優(yōu)空間的隨機(jī)搜索。搜索過程由執(zhí)行分配的成對交換完成,搜索初始解為轉(zhuǎn)載單元的容積或載重量的利用率。對現(xiàn)有配裝情況用任意成對交換產(chǎn)生新的分配,從而對配裝方案不斷進(jìn)行改進(jìn),直至找到最優(yōu)貨物配裝案。模擬退火算法適合大規(guī)模的考慮配裝約束時的貨物配裝問題。從理論上講,用這種方法求解貨物配裝問題,可以求得全局最優(yōu)解,但在實際應(yīng)用中,由于受計算時間的限制,往往只能給出一個近似的最優(yōu)解。為了使模擬退火算法求出的近似解更準(zhǔn)確,一般重復(fù)執(zhí)行模擬退火法多次,從中選取最好的解作為最終的近似最優(yōu)解。

另外,在做配裝方案時,若待配裝貨物的種類比較多,且配裝號也較多時,配裝關(guān)系十分復(fù)雜,此時可以先將貨物依據(jù)配裝號分類,之后將具有同一配裝號的貨物視為一批(或一件)貨物,按照配裝號的順序進(jìn)行解的編碼,這樣編碼長度最多為所有貨物包含的配裝號的數(shù)量,節(jié)省計算機(jī)存儲空間,大大降低計算復(fù)雜度,提高計算效率;但是在進(jìn)行單車配載時該編碼方法產(chǎn)生的最優(yōu)解不利于充分利用貨車載重量。在確定請求車時,需要多次使用該算法,直到確定的配裝方案中的貨物總重量和總體積小于裝載單位的標(biāo)記載重為止。

3結(jié)束語

貨物配裝問題是NP—難問題,如果用精確算法來求解,只能解決規(guī)模較小的問題,而且求解過程需要的運(yùn)行時間較長。因此,目前啟發(fā)式算法,特別是智能化啟發(fā)式算法,仍是求解貨物配裝問題的主要方法。需要說明的是,啟發(fā)式算法雖然能夠比較快地解決有關(guān)問題,但算法的各項初始參數(shù)的適當(dāng)選取均會影響算法的收斂性、收斂速度和計算時間,因此啟發(fā)式算法的優(yōu)劣往往取決于算法設(shè)計者的實際經(jīng)驗以及處理的樣本空間的大小。在求解過程中,應(yīng)根據(jù)各類算法的適用范圍,并針對配裝優(yōu)化問題的具體情況,尋找最適合的求解方法,搜索最優(yōu)配裝方案。對于貨物號比較多的配裝優(yōu)化問題、多約束的復(fù)雜貨物配裝問題或者是多優(yōu)化目標(biāo)的貨物配裝優(yōu)化問題,可以考慮利用多種算法相結(jié)合的辦法來解決。

參考文獻(xiàn):

[1]Bhattacharya S, Roy R. An exact depth-first algorithm for the pallet loading problem[J]. European Journal of Opera-tional Research, 1998,110(3):610-625.

[2]Scheithauer G, Sommerweib U. 4-block heuristic for the rec-tangle packing problem[J]. European Journal of OperationalResearch, 1998,108(3):509-526.

[3]Berghammer R, Reuter F. A linear approximation algorithmfor bin packing with absolute approximation factor[J]. Sci-ence of Computer Programming, 2003,48(1):67-80.

[4] 孫焰,李致中. 求雙目標(biāo)配裝方案的多項式近似算法[J]. 長沙鐵道學(xué)院學(xué)報,1997,15(2):33-39.

[5] 高紅建,等. 貨物合理配裝的實用啟發(fā)式算法[J]. 交通科學(xué)與經(jīng)濟(jì),2004(1):59-61.

[6] 劉小群,馬士華. 基于標(biāo)桿的多車多品種貨物裝載優(yōu)化算法[J]. 交通運(yùn)輸工程學(xué)報,2007,7(1):99-105.

[7] 卜雷,等. 遺傳算法確定零擔(dān)貨物的選擇裝箱方式[J]. 交通運(yùn)輸工程學(xué)報,2002,2(3):93-96.

[8] 曹宏美,等. 優(yōu)化多品種貨物配裝的螞蟻算法[J]. 交通與計算機(jī),2008,26(2):11-15.

[9] 賀國先,劉凱. 模擬退火算法在鐵路貨運(yùn)站危險貨物配裝中的應(yīng)用[J]. 鐵道學(xué)報,2003,25(1):9-14.

[10] 王玲玲,等. 單車多品種貨物配裝問題模型與算法研究[J]. 物流科技,2007(8):118-122.

[11] 孫黎宏,許恒勤. 多包裝形式下貨物配裝問題的研究[J]. 森林工程,2006,22(5):69-70.

[12] 王玲玲,等. 多車多品種貨物配裝問題模型與算法研究[J]. 物流科技,2007,26(7):58-60.

[13] 曹明蘭,等. 考慮客戶需求優(yōu)先級的貨物配裝問題的模型與算法研究[J]. 物流科技,2007,29(10):69-72.

[14] 史亞貝,等. 零擔(dān)貨物配裝問題的算法和系統(tǒng)設(shè)計[J]. 工藝與裝備,2008(3):86-90.

[15] 吳穎,程賜勝. 基于分枝定界法的車輛配載問題[J]. 長沙理工大學(xué)學(xué)報,2008,5(4):23-27.

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文