一種基于啟發(fā)式算法的貨物裝載問題的研究

鄭煒, 劉文興, 楊喜兵, 袁緒龍, 王文鵬

(1.西北工業(yè)大學(xué) 軟件與微電子學(xué)院, 陜西 西安　710072; 2.西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安　710072)

?

一種基于啟發(fā)式算法的貨物裝載問題的研究

鄭煒1, 劉文興1, 楊喜兵1, 袁緒龍2, 王文鵬1

(1.西北工業(yè)大學(xué) 軟件與微電子學(xué)院, 陜西 西安710072; 2.西北工業(yè)大學(xué) 航海學(xué)院, 陜西 西安710072)

摘要：文章旨在解決多車輛車廂合理、高效裝載問題,即給定一批大小不同的貨物和一批車廂大小不同的車輛,在滿足貨物裝載約束條件下實(shí)現(xiàn)自動化裝載。文章首先分析借助計(jì)算機(jī)實(shí)現(xiàn)自動化裝載存在的難點(diǎn),在此基礎(chǔ)上提出一種基于平面分割理論的啟發(fā)式搜索算法,以解決自動化裝載問題,并給出算法優(yōu)化方法以提高算法的效率與實(shí)用價(jià)值。最后,為了得到滿足貨物裝載約束條件的最優(yōu)裝載方案,文章也提出了結(jié)合遺傳算法解決貨物裝載問題的改進(jìn)思路。

關(guān)鍵詞：成本降低;三維貨物裝載;多車輛;多貨物;平面劃分;遺傳算法;啟發(fā)式算法

在貨物的流通運(yùn)輸環(huán)節(jié)中,貨物裝載工作是最費(fèi)時(shí)費(fèi)力的部分,直接影響著運(yùn)輸部門的運(yùn)輸效率與成本。隨著信息技術(shù)的不斷發(fā)展,貨物的裝載方案完全可以通過計(jì)算機(jī)模擬來自動生成,并以此指導(dǎo)裝載人員的裝載活動,以提高貨物運(yùn)輸環(huán)節(jié)的效率并降低成本。

本文試圖構(gòu)建一種能自動生成裝載方案的算法,該算法可以將貨物合理有效地裝入車輛車廂中,并在滿足給定車輛車廂與貨物約束條件的情況下裝完所有的貨物。為了驗(yàn)證算法生成的裝載方案的可行性,本文利用SharpGL圖形包對生成的方案進(jìn)行了驗(yàn)證,實(shí)驗(yàn)結(jié)果表明,該算法可以合理、高效地完成自動化裝載。

1貨物自動化裝載問題

1.1貨物自動化裝載概述

貨物自動化裝載問題,簡言之就是利用計(jì)算機(jī)自動生成把不同大小、不同形狀的一些貨物合理地裝到車廂中的方案。

貨物裝載問題不是一類簡單的問題,而是由許多不同種類裝載問題所組成的裝載問題家族。根據(jù)不同的目標(biāo)和不同的約束條件,可以將其細(xì)分為不同的分支。貨物裝載還是一類多目標(biāo)組合優(yōu)化問題,其已被證明為NP-HARD問題[1-2],而解決NP完全問題的一般方法就是利用元啟發(fā)式搜索算法,不斷在解空間中搜索最優(yōu)解,使得到的最終解盡量達(dá)到最優(yōu)解或者接近最優(yōu)解。

1.2貨物自動化裝載問題的分類

貨物自動化裝載是一個三維空間裝載問題,有多種分類方法。目前比較流行的分類方法是由德國人Dyckhoff[3]提出的,他根據(jù)貨物裝載所需要車輛車廂的數(shù)量,將裝載問題劃分為以下2類：

1) 多車輛車廂問題:給定一批貨物和一定數(shù)量的車輛車廂,要求所有的貨物都能裝入到車輛車廂內(nèi),并且盡可能使所需的車輛車廂最少,本文的主要研究工作是解決此類問題,即滿足貨物的約束條件下,使得所需要的車輛車廂最少。

2) 單車輛車廂問題:給定一批規(guī)格不同的貨物并且只給定一個車輛車廂,要求將盡量多的貨物裝載到給定的單個車廂內(nèi),使給定的單個車輛車廂的空間利用率達(dá)到最大。

Bortfeldt[4]提出了另外一種比較流行的分類方法,其思路是將裝載問題分為3類,即同類問題、弱異類問題、強(qiáng)異類問題。劃分依據(jù)是貨物規(guī)格差異的程度:當(dāng)待裝貨物規(guī)格完全一樣時(shí),為同類問題;當(dāng)待裝貨物只有少數(shù)幾種不同規(guī)格時(shí),為弱異類問題;當(dāng)待裝貨物有很多不同類型時(shí),為強(qiáng)異類問題。

另外,在工程領(lǐng)域中,還可以根據(jù)貨物約束條件進(jìn)行分類。例如考慮是否多目的地運(yùn)送。

1.3貨物自動化裝載問題的技術(shù)難點(diǎn)

通常在解決貨物自動裝載過程中,存在以下技術(shù)難點(diǎn):

1) NP-HARD問題本身就是一個比較難以解決的技術(shù)問題,通常是通過元啟發(fā)式算法求其比較理想的解,最優(yōu)解很難通過自動化求解得到。

2) 傳統(tǒng)的貨物自動化裝載大都規(guī)定貨物的形狀為長方體,但是在實(shí)際運(yùn)輸過程中,運(yùn)輸?shù)呢浳锖芸赡苁且环N不規(guī)則形狀的貨物,或者是一種規(guī)則的形狀,但不是規(guī)則的長方體。在貨物形狀很多并且車廂尺寸不確定的情況下,解決貨物的裝載,并且滿足裝載約束條件是一個技術(shù)難點(diǎn)。

3) 在實(shí)際擺放時(shí),貨物存在著不同的擺放狀態(tài),貨物的形狀即使是長方體情況下,如圖1所示,仍可以有6種不同裝載狀態(tài)。

圖1　長方體貨物的6種擺放狀態(tài)

4) 所設(shè)定的裝載約束條件使裝載過程變得更為復(fù)雜,如Bischoff和Ratchliff[5]總結(jié)的貨物承重約束、分類約束、穩(wěn)定性約束、卸載順序約束、方位約束等。

2一般求解方法

貨物自動化裝載問題的解決方法目前主要有啟發(fā)式搜索算法、數(shù)學(xué)規(guī)劃法、組合算法[6]。在一般求解貨物裝載問題用到的啟發(fā)式算法中,遺傳算法是最為廣泛使用的一種元啟發(fā)式搜索算法,屬于全局性的搜索算法,能自適應(yīng)地控制搜索過程,以求得最優(yōu)解[7]。在解決類似于貨物裝載這樣的NP問題中表現(xiàn)非常卓越,但是其算法時(shí)間復(fù)雜度很大,并且,搜索結(jié)果具有不確定性,使其在實(shí)際工程應(yīng)用中有一定的局限性。

3核心算法

3.1算法基本思想

本文在貨物裝載約束條件下,探索基于平面劃分理論求解貨物自動化裝載問題，如圖2所示。根據(jù)貨物裝載的誤差要求以及時(shí)間成本要求將車廂內(nèi)底面劃分為不同數(shù)量的等面積小格子,這里為了顯示方便，將車廂內(nèi)底面劃分為5*4=20個等面積小格子。如要提高裝載的精度,可以劃分為更多的小格子。

圖2　車廂底面分割圖

假設(shè)貨物的裝載層數(shù)要求為NumLayer,并且貨物總是底面接地時(shí),即貨物只有如圖1所示的第一種和第二種放置狀態(tài)。當(dāng)NumLayer為1時(shí),這里優(yōu)先選擇圖1的第二種放置狀態(tài)(在具體的算法實(shí)驗(yàn)中,可以優(yōu)先選擇不同的貨物放置狀態(tài))。利用搜索算法選擇一個貨物,記當(dāng)前選擇的貨物長為Li,寬為Wi,高為Hi,從車廂內(nèi)底面原點(diǎn)出發(fā),開始順著X軸正方向依次查找,直到找到第一個空白小格子,開始依次累加小格子的長,當(dāng)?shù)竭_(dá)車廂內(nèi)底面邊緣或小格子已經(jīng)填上貨物編號,則停止累加。記小格子的累加長為Lsum,當(dāng)Lsum≥Wi,從找到的第一個空白小格子位置開始順著Y軸正方向依次累加小格子的寬,當(dāng)?shù)竭_(dá)車廂內(nèi)底面邊緣或小格子已經(jīng)填上貨物編號,則停止累加。記小格子的累加寬為Wsum,當(dāng)Wsum≥Li,判斷車廂的高是否大于等于貨物的高,如大于等于,則將以小格子向X軸正方向累加長為寬與小格子向Y軸正方向累加寬為長的長方形區(qū)域填寫上貨物的編號與貨物的擺放狀態(tài)(圖1中狀態(tài)2),表明當(dāng)前貨物已經(jīng)裝載到車輛車廂中。在累加過程中,如不能同時(shí)滿足Lsum≥Wi,Wsum≥Li條件,則變換到如圖1所示的第一種貨物放置的狀態(tài),重復(fù)操作,若滿足Lsum≥Li,Wsum≥Wi,并且貨物高小于等于車廂的高時(shí),則將以小格子向X軸正方向累加長為長與小格子向Y軸正方向累加寬為寬的長方形區(qū)域填寫上貨物的編號與貨物的擺放狀態(tài)(圖1中狀態(tài)1),表明當(dāng)前貨物已經(jīng)裝載到車廂中。當(dāng)以找到的第一個空白小格子為起點(diǎn)順著X軸與Y軸正方向累加不能搜索到上述長方形區(qū)域時(shí),則應(yīng)順著X軸正方向與Y軸正方向?qū)ふ蚁乱粋€空白小格子。

當(dāng)NumLayer≥2時(shí),可以在第二層或者第二層以上建立如圖2所示長方形底面,稱其為虛平面,并且按照第一層劃分小格子的方法劃分第二層及第二層以上建立的虛平面,并為貨物查找放置區(qū)域。在第二層及第二層以上放置貨物不同于第一層的是:要累加其下面幾層已裝載貨物的總高度并要判斷下層已填長方形區(qū)域是否滿足疊放條件。

當(dāng)NumLayer為1時(shí),對上述算法步驟用圖像化的方式給出說明。如圖3所示。

圖3　貨物裝載初始狀態(tài)

假設(shè)車廂底面內(nèi)長為5 m,內(nèi)寬為4 m,要求精度為1 m,則可以將車廂內(nèi)底面劃分為5*4=20個小格子。每個格子的長與寬都為1 m。圖3右邊是待裝貨物俯視圖。將貨物編號為1～3。貨物1的長度和寬度設(shè)為4 m和2 m,貨物2的長度和寬度設(shè)為3.5 m和1.5 m,貨物3的長度和寬度設(shè)為2.3 m和1 m。

開始選擇編號為1的貨物進(jìn)行裝載,從車廂內(nèi)底面原點(diǎn)開始順著X軸正方向開始尋找空白小格子,由于第一個為空格子,所以可以從這個位置向X軸正方向進(jìn)行累加,累加到第二個格子時(shí),累加長已經(jīng)大于貨物1的寬度,然后順著初始找到的第一個空格子向Y軸正方向累加,到車廂內(nèi)底面邊緣時(shí),車廂內(nèi)底面寬度恰好等于貨物長度,再比較貨物1

高度與車廂內(nèi)高,得出貨物高度小于車廂內(nèi)高,因此將貨物1的編號及放置狀態(tài)填入放置貨物1的長方形區(qū)域中,結(jié)果如圖4所示。其中貨物1覆蓋的小格子填寫的編號都是1和貨物擺放狀態(tài)(圖1中狀態(tài)2)。

圖4　裝入貨物1時(shí)貨物的狀態(tài)

接著,選擇編號為2的貨物進(jìn)行裝載,從車廂的內(nèi)底面原點(diǎn)出發(fā),順著X軸尋找第一個空白小格子,如圖4所示,黑色小格子為找到的第一空白小格子,從這個小格子開始順著X軸累加,當(dāng)累加長度大于等于貨物2寬度時(shí),從初始找到的空白小格子處順著Y軸累加,當(dāng)累加寬度大于等于貨物2的長度時(shí),并且貨物2高度小于等于車廂內(nèi)部高度時(shí),給以小空白格子累加寬與累加長組成的長方形域填寫貨物編號2與貨物2的擺放狀態(tài)。貨物3也以此方法填入車廂內(nèi)底面中。最終裝填狀態(tài)如圖5所示,從圖5可以看出貨物2與貨物3之間存在很大間隙,可以通過增加劃分的小格子個數(shù)解決。

圖5　最終貨物裝填狀態(tài)

假設(shè)車廂內(nèi)長為Lcarriage,車廂內(nèi)寬為Wcarriage,車廂內(nèi)高為Hcarriage。公式(1)與公式(2)給出當(dāng)貨物放置狀態(tài)為圖1所示第一種和第二種放置狀態(tài)時(shí),單個貨物進(jìn)行裝載時(shí)的一般約束條件。

(1)

(2)

其中CurrentLayer為當(dāng)前裝載貨物層數(shù),公式(1)為如圖1所示的第二種貨物放置狀態(tài)的一般裝載約束條件,公式(2)為如圖1所示的第一種貨物放置狀態(tài)的一般裝載約束條件。

對基于平面分割理論的貨物裝載算法梳理為以下幾個步驟:

Step1對所有的待裝貨物及車輛車廂進(jìn)行編號,為所有待裝貨物設(shè)置一個裝載狀態(tài)標(biāo)志數(shù)組,表明當(dāng)前貨物是否已經(jīng)裝載到車廂中。

Step2按照預(yù)先設(shè)置的搜索條件從待裝貨物中選擇一個貨物,利用上述所提到算法裝填到車輛車廂中,若裝載不成功則裝填到下一個車廂中,如若成功,則在相應(yīng)小空白格子中填入貨物編號及貨物放置狀態(tài),并設(shè)置貨物對應(yīng)標(biāo)志數(shù)組狀態(tài)為已裝載。

Step3從當(dāng)前未裝載貨物中搜索條件選擇一個貨物,重復(fù)Step2步驟,直到標(biāo)志數(shù)組全部元素狀態(tài)變?yōu)橐蜒b載。

3.2改進(jìn)思想

上述提供了一種貨物裝載的基本思路,但是存在以下幾個缺陷:

1) 進(jìn)行貨物裝載時(shí),只考慮了如圖1所示的前2種貨物放置狀態(tài),當(dāng)考慮所有的貨物放置狀態(tài)時(shí),算法時(shí)間成本急劇上升。

2) 算法本身帶有貪婪算法的特征,致使得到的裝載方案往往很難達(dá)到最優(yōu)解或接近于最優(yōu)解。

3) 有時(shí)在給定車輛數(shù)量的情況下,要求每個車輛裝載的貨物數(shù)量、質(zhì)量、體積盡量達(dá)到均衡化,但通過上述算法得到的裝載方案很可能不能滿足此要求。

對于上述算法缺陷,提出2種改進(jìn)思路。

第一個改進(jìn)思路是對算法效率的改進(jìn),順著X軸正方向搜索第一個空白小格子過程中,當(dāng)開始發(fā)現(xiàn)不是空白小格子時(shí),不應(yīng)該繼續(xù)順序讀取已添編號與狀態(tài)的小格子,而是直接根據(jù)貨物放置狀態(tài)與貨物編號跳到貨物長或者貨物寬占有的全部小格子的下一個小格子。這樣做的好處是節(jié)省了搜索的時(shí)間,對算法效率的提高具有深遠(yuǎn)的意義。

設(shè)搜索到第一非空白小格子的時(shí)候,讀取的放置狀態(tài)為Status,可能取值為0或1。當(dāng)Status=0時(shí),表明貨物放置狀態(tài)為如圖1所示第一種狀態(tài),當(dāng)Status=1時(shí),表明貨物放置狀態(tài)為如圖1所示的第二種狀態(tài)。具體的跳格步數(shù)計(jì)算公式如公式(3)所示。

(3)

式中，Lgrid為X軸正方向上劃分的小格子長,X表示X軸正方向。

由于貪心算法本身具有局部搜索最優(yōu)解,很難得到全局最優(yōu)解的弊端,結(jié)合元啟發(fā)式搜索算法-遺傳算法提出第二個改進(jìn)思想。

遺傳算法把搜索最優(yōu)解的任務(wù)交給進(jìn)化過程,其關(guān)鍵操作包括:初始種群的設(shè)置、交叉操作,變異操作以及適應(yīng)度的確定。

本文實(shí)現(xiàn)的是多貨物多車輛車廂問題,并在車輛數(shù)量不確定的狀況下,要求裝載方式具有一定的伸縮性,以上述算法為基礎(chǔ),結(jié)合遺傳算法解決貨物裝載問題的具體操作如下:

·染色體編碼

先對貨物進(jìn)行順序編碼,編碼為a1,a2,a3…an,其中n為貨物的數(shù)量。隨機(jī)生成區(qū)間在[1,6]的n個整數(shù)b1,b2,b3…bn,作為貨物裝載時(shí)的擺放狀態(tài)。每種裝載方案對應(yīng)一個長度為2n的符號串,表示為P(a1,a2,a3,a4…an,b1,b2,b3…bn)?；蛭籥1,a2,a3…an表示貨物裝載的順序,b1,b2,b3…bn表示貨物裝載時(shí)擺放的狀態(tài),a1,a2,a3…an與b1,b2,b3…bn一一對應(yīng),當(dāng)進(jìn)行裝載時(shí),按照貨物編號順序選擇車廂按照平面劃分理論進(jìn)行填充。

·選擇

選擇時(shí)采用錦標(biāo)賽選擇算法進(jìn)行選擇。

·交叉

進(jìn)行交叉時(shí)對貨物編碼和擺放狀態(tài)編碼分別進(jìn)行交叉,由于貨物編碼的基因位的唯一性,貨物編碼交叉采用PMX部分匹配交叉法[4],擺放狀態(tài)采用普通交叉方式。

·變異

由于貨物編碼的唯一性,所以只對基因段b1,b2,b3…bn進(jìn)行隨機(jī)變異。

·適應(yīng)度計(jì)算

可以根據(jù)車廂承重、虛面積中空白格子占有率或者裝載的均衡化程度設(shè)置相應(yīng)的適應(yīng)度計(jì)算公式。

可以看出,當(dāng)車輛車廂變?yōu)橐粋€時(shí),多車廂多貨物裝載問題就變成了單車廂多貨物裝載優(yōu)化問題,上述提到的遺傳算法解決貨物裝載優(yōu)化問題是基于平面分割理論的。

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

4.1實(shí)驗(yàn)配置

本文選用C#語言下的OpenGL函數(shù)庫SharpGL對算法進(jìn)行驗(yàn)證,SharpGL可以在Windows Forms或WPF中輕松使用OpenGL開發(fā)圖形應(yīng)用,借助SharpGL使用地優(yōu)雅性,可以迅速建立其對裝載效果的模擬仿真。

4.2實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)對基于平面分割理論算法進(jìn)行了驗(yàn)證,實(shí)驗(yàn)中,設(shè)裝載時(shí)具有以下約束條件:

1) 給定一批貨物與一批車輛,貨物及車廂形狀全部是規(guī)則的長方體,車廂與貨物數(shù)量不固定,要求將給定貨物全部裝載到給定的車輛車廂中。

2) 貨物種類分為4類,第一、二、三類貨物不能互相混裝,第四類貨物可以與前3類貨物進(jìn)行混裝。

3) 要求貨物底面接地,即實(shí)際放置狀態(tài)只有如圖1所示的第一、二種放置狀態(tài)。

給定表1車輛車廂尺寸與表2貨物尺寸,當(dāng)NumLayer為1時(shí),即只要求貨物裝載1層時(shí),根據(jù)實(shí)驗(yàn)結(jié)果得出如表3所示的貨物坐標(biāo)以及放置狀態(tài),其中實(shí)驗(yàn)所用坐標(biāo)系如圖2所示。

表1　給定的車輛車廂尺寸/mm

表2　給定的貨物尺寸/mm

表3　生成的貨物放置狀態(tài)及坐標(biāo)/mm

其中，貨物編號、貨物坐標(biāo)及擺放狀態(tài)所組成的五元式表示為(貨物編號、貨物放置的X軸坐標(biāo)，貨物放置的Z軸坐標(biāo)，貨物放置的Y軸坐標(biāo)，貨物放置狀態(tài))。

從實(shí)驗(yàn)結(jié)果可以看出,要求裝載一層時(shí),算法生成的裝載方案充分利用了車廂底面空間，其中HY001車輛車廂底面空間的占有率達(dá)到90%以上,利用本算法求解自動化裝載方案，在時(shí)間成本方面有明顯優(yōu)勢。

5結(jié)論

三維貨物裝載問題是一個難以有效解決的NP-HARD問題,當(dāng)貨物裝載約束條件很多時(shí),很難得到滿意的結(jié)果。本文所提出的基于平面分割的算法提供了一種貨物自動化裝載方案，但本算法還存在很多局限,如不能很好地利用車廂空間,對于異構(gòu)貨物的裝載,尚不能圓滿滿足車廂和貨物裝載的約束條件。結(jié)合本算法的遺傳算法解決三維貨物裝載問題,基于此問題，本文提出了改進(jìn)思想，結(jié)合遺傳算法全局搜索性可望得到最優(yōu)解。不過，結(jié)合本算法的遺傳算法解決三維貨物裝載問題，我們將會進(jìn)一步給出研究與驗(yàn)證。

參考文獻(xiàn)：

[1]Raymond Edward Miller, James W Thatcher. Complexity of Computer Computations[M]. New York: Plenum Press, 1972: 85-103

[2]雷定猷,陳德良. 平衡裝載問題的優(yōu)化模型與算法[J]. 系統(tǒng)工程學(xué)報(bào), 2004,19(3): 251-257

Lei Dingyou, Chen Deliang. Optimizing Model and Its Algorithm of Balanced Loading Problems[J]. Journal of System Engineering, 2004, 19(3): 251-257 (in Chinese)

[3]Dyckhoff H. A Typology of Cutting and Packing Problems[J]. European Journal of Operational Research, 1990, 44(2): 145-159

[4]Bortfeldt A. A Genetic Algorithm for the Container Loading Problem[C]∥Proceedings of the Conference on Adaptive Computing and Information Processing, London, 1994: 25-32

[5]Bischoff E E, Ratcliff M S W. Issues in the Development of Approaches to Container Loading[J]. Omega, 1995, 23(4): 377-390

[6]李鵬,湯勇. 三維貨物裝箱問題的研究進(jìn)展[J]. 南京林業(yè)大學(xué)學(xué)報(bào),2015, 12(5): 1235-1238

Li Peng, Tang Yong. Research Progress of Three Dimensional Packing of Goods[J]. Journal of Nanjing Forestry University, 2015, 12(5): 1235-1238 (in Chinese)

[7]Goldberg D E. Genetic Algorithms in Search,Optimization and Machine Learning[M]. Boston, Addison-Wesley Professional,

1989

[8]Dwmkerr.SharpGL[EB/OL](2014-3-31)[2016-6-27].http:∥sharpgl.codeplex.com

Research on the Problem of Cargo Loading Based on Heuristic Algorithm

Zheng Wei1, Liu Wenxing1, Yang Xibing1, Yuan Xulong2, Wang Wenpeng1

1.School of Software and Microelectronic Engineering, Northwestern Polytechnology, Xi′an 710072, China 2.School of Marine Science and Technolgoy University, Xi′an 710072, China

Abstract:Cargo loading is a key link in the process of cargo transportation. The effective realization of rational loading of cargoes can save enormous manpower and material resources cost. But in practical work, most of the loading is directed by experience, time-consuming and unsatisfactory loading scheme ultimately. With the development of information technology, rational loading scheme can be generated automatically by computer, which can guide the actual loading. But it has been proved that the automated loading is a NP-HARD problem, how to use computer to generate automated loading to meet the constraints and possible near-optimal loading solution is a hotspot of current research. The purpose of this paper is to solve the problem of rational and efficient loading of vehicle compartments, that is, given a number of different sizes of cargoes and a number of vehicles with different sizes of compartments, automatic loading will be realized under the condition of meeting the cargo loading constraints. This paper firstly analyzes the difficulties in the realization of automatic loading by computer, then, a heuristic search algorithm based on plane segmentation theory is proposed to solve the problem of automatic loading. In order to improve the efficiency and practical value of the algorithm. This paper also puts forward the method of improving the efficiency of the algorithm. Finally, in order to accomplish the optimal loading scheme under the condition of meeting the cargo loading constraints, such as achieving a balanced loading of cargoes in a fixed number of vehicle compartments, this paper also puts forward the improved idea of combining genetic algorithm to solve the problem of cargoes loading.

Keywords:cost reduction,dimensional cargo loading, multi-vehicle, multi-cargo, plane division, genetic algorithm, heuristic algorithm

收稿日期：2016-04-14

基金項(xiàng)目：國家自然科學(xué)基金(61402370)與中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助

作者簡介：鄭煒(1975—)，西北工業(yè)大學(xué)副教授，主要從事軟件工程及軟件測試的研究。

中圖分類號：TP311.5

文獻(xiàn)標(biāo)志碼：A

文章編號:1000-2758(2016)04-0708-06