多品種物資碼垛方案生成算法設(shè)計(jì)及編程實(shí)現(xiàn)

劉振興，吳兆東，張大鵬

（1.陸軍軍事交通學(xué)院 學(xué)員三大隊(duì)，天津 300161；2.陸軍軍事交通學(xué)院 學(xué)員五大隊(duì)，天津 300161；3.陸軍軍事交通學(xué)院 投送裝備保障系，天津 300161）

1 引言

物資集裝化運(yùn)輸是目前物流運(yùn)輸?shù)闹饕问街?，常見的集裝容器有托盤、航空板、集裝箱等。對(duì)托盤以及航空板而言，物資的碼盤方式多數(shù)是依賴操作經(jīng)驗(yàn)進(jìn)行，這種方式對(duì)同一類物資或少品類近似物資比較適用，但對(duì)多品類物資，這種方法的不確定性增加，會(huì)產(chǎn)生重心不穩(wěn)、空間利用率低等問題，進(jìn)而影響了物流效率。

碼盤優(yōu)化算法一直都是集裝化研究的熱點(diǎn)問題。一個(gè)適用的算法，能夠得到一個(gè)相對(duì)優(yōu)化的組盤方案，節(jié)省時(shí)間，提高效率，為后續(xù)的物流環(huán)節(jié)做好鋪墊。本文以航空板組板為例，研究多品種物資的組板問題，設(shè)計(jì)組板優(yōu)化算法并通過java編程實(shí)現(xiàn)，得到自動(dòng)堆碼模型，為自動(dòng)組板系統(tǒng)的研發(fā)提供思路。

2 航空板組板問題描述

多品種物資的航空組板問題可簡化為以下描述：在一定大小的容器中，如何科學(xué)合理地碼放物資，實(shí)現(xiàn)容器的空間利用率、載重利用率以及整體穩(wěn)定性的最優(yōu)化。

2.1 問題的數(shù)學(xué)抽象

將航空板視為具有一定載重量的立方體容器，其長、寬、高分別表示為Li，Wi，Hi（i=1,2,…），最大載重用Gi表示。待裝物資視為立方體，長、寬、高、質(zhì)量分別用lj，wj，hj，gj（j=1,2,3…）表示。以航空板的左上角為坐標(biāo)原點(diǎn)，右方向和下方向?yàn)樽鴺?biāo)軸正方向，表示物資的坐標(biāo)。方案評(píng)價(jià)指標(biāo)主要有空間利用率、載重利用率和重心偏移程度。

空間利用率函數(shù)：

載重利用率函數(shù)：

重心偏移程度函數(shù)：

分別給予上述評(píng)價(jià)指標(biāo)α、β、θ的權(quán)重系數(shù)，取值在（0,1）之間，依據(jù)實(shí)際情況對(duì)碼垛的要求進(jìn)行取值。最后的考察函數(shù)為：

2.2 方案約束

其主要分為航空板約束和物資約束：

在航空板約束中，主要有以下約束：（1）空間約束，即一個(gè)航空板所裝載的物資體積不得超過航空板的容量；（2）載重約束，一個(gè)航空板上所放物資的總質(zhì)量不得超過航空板的承載能力。

在物資約束中，主要有以下約束：（1）碼放位置，碼放不得超出航空板的邊緣；（2）碼放方向，物資不得隨意碼放，僅考慮正確碼放情況；（3）碼放順序約束，遵循大不壓小，重不壓輕的約束條件。

2.3 空間分割組合思想

2.3.1 空間分割。航空集裝板作為容器，可視為一個(gè)空間。物資存放采用“占角原則”，放置在空間的左上角，并且可以形成3個(gè)獨(dú)立的子空間，即右空間(R)、前空間(L)和上空間(M)。后續(xù)的物資均放入產(chǎn)生的子空間之中，并形成一個(gè)空間隊(duì)列，如圖1所示。

空間隊(duì)列的排列順序按照從下到上，從左到右進(jìn)行排序，即擺放物資順序是從下至上，從左至右，按層進(jìn)行擺放。每放入一個(gè)新的物資時(shí)，則從空間隊(duì)列中移出擺放物資的空間，并在空間隊(duì)列中增加因加入新物資產(chǎn)生的新的空間。在碼放下一個(gè)物資之前，先將隊(duì)列空間按上述擺放物資的要求進(jìn)行排序。

圖1 航空板空間分割示意圖

2.3.2 空間組合。在空間分割中存在部分相鄰空間，如果僅僅考慮空間隊(duì)列，則可能存在物資只有在跨空間的情況下才能夠放得下。因此，在考慮隊(duì)列空間的同時(shí)，在放不下物資的情況下，考慮空間的組合。主要分為空間淺組合和空間深組合?？臻g淺組合，就是將2個(gè)相鄰且在同一水平面上的空間進(jìn)行合并，如圖2所示?？臻g深組合，是指多個(gè)相鄰空間進(jìn)行組合，組合出一個(gè)長條狀的空間，如圖3所示。

在進(jìn)行空間組合之后，判斷是否可以放得下物資，如果放得下，則更新隊(duì)列空間，如果放不下，則取消更新，退出碼放。因此，物資的碼放流程如圖4所示。

3 遺傳算法設(shè)計(jì)及編程實(shí)現(xiàn)

遺傳算法是一種基于達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模擬，是一種通過模擬生物界自然進(jìn)化過程尋找最優(yōu)解的方法。

3.1 方案的編碼與解碼

圖2 空間淺組合示意圖

圖3 空間深組合示意圖

個(gè)體的編碼解碼是將解空間和遺傳算法能夠處理的搜索空間相互轉(zhuǎn)化的過程。這里將一組航空板和一批物資的組裝方案視為一個(gè)個(gè)體。

3.1.1 編碼。一個(gè)組裝方案涉及待裝物資編碼、待用航空板編碼、物資的擺放方向編碼。編碼預(yù)處理如下：

圖4 物資碼放流程圖

（1）待裝物資編號(hào)：i=1,2,…,n；

（2）待用航空板編號(hào)：j=1,2,…,m；

（3）待裝物資編號(hào)體現(xiàn)了堆碼順序，編號(hào)小的物資優(yōu)先碼放；

（4）物資碼放方向編碼采用1和2表示，1表示物資橫向碼放，即物資較長邊平行于y軸，較短邊平行于x軸。

依據(jù)方案設(shè)計(jì)可以得到一個(gè)編碼長度為3×n的基因個(gè)體（S1，S2，S3，...Sn|Sn+1，Sn+2，...S2n|S2n+1，S2n+2，...，S3n），其中，前n個(gè)編碼表示物資的碼放順序，取值在（1，n）之間，中間n個(gè)編碼表示物資的擺放方向，取值為1或者2，后n個(gè)編碼表示物資擺放在哪一個(gè)航空板上，取值在（1，m）之間。

3.1.2 解碼。解碼是將問題的可行解從遺傳算法所能處理的搜索空間轉(zhuǎn)化為實(shí)際方案，按照編碼的逆操作進(jìn)行。

（1）Si，Si+n，Si+2n表示一個(gè)物資以排序號(hào)Si，擺放方向?yàn)镾i+n擺放在航空板編號(hào)為Si+2n的航空板上；

（2）物資i和物資j的Si+2n和Sj+2n相同時(shí)，表示兩者在同一個(gè)航空板上，此時(shí)，比較基因Si和Sj來確定碼放順序；

（3）基因Si+n解碼成物資在航空板上的碼放方向；

（4）碼放過程嚴(yán)格按照?qǐng)D4所示的流程進(jìn)行。

3.2 遺傳算法計(jì)算流程

遺傳算法的計(jì)算過程基本上是不涉及到外部信息，只需要關(guān)注評(píng)價(jià)函數(shù)。在第二節(jié)中已經(jīng)給出了評(píng)價(jià)函數(shù)，即式（4），作為遺傳算法的適用度函數(shù)。

在解碼過程中可能出現(xiàn)的不符合實(shí)際的情況增加適用度“懲罰”系數(shù)。一種情況是，當(dāng)出現(xiàn)航空板所裝物資超過了航空板的容積時(shí)，適用度函數(shù)z=z-10 000，通過這種方式剔除不合格的基因個(gè)體；另一種情況是所裝物資超過航空板載重，適用度函數(shù)z=z-10 000。通過這樣的方式在遺傳算法中過濾掉不符合實(shí)際的情況。

個(gè)體基因遺傳中，隨機(jī)選擇兩個(gè)基因位置，其索引分別為a和b，將a和b之間的基因進(jìn)行交換?；蛲蛔儯O(shè)置每次基因突變的位置個(gè)數(shù)，每個(gè)位置以概率p發(fā)生基因突變，對(duì)應(yīng)的基因位置根據(jù)代表的編碼意義，在對(duì)應(yīng)的區(qū)間內(nèi)隨機(jī)變化。

為了確保算法收斂，將每一代產(chǎn)生的最優(yōu)個(gè)體保存在下一代的種群中。

計(jì)算流程如圖5所示。

圖5 遺傳算法流程圖

3.3 編程及案例分析

3.3.1 編程實(shí)現(xiàn)。本文主要使用java語言，利用開發(fā)工具eclipseVE開發(fā)，根據(jù)上述算法，實(shí)現(xiàn)模擬航空組板的方案。在java編程中，將組板方案和遺傳算法單獨(dú)編程。待放物資用Good類表示，航空板用Plate類表示，空間用Space類表示。通過解碼和編碼將兩者聯(lián)系，并寫一個(gè)工具類來計(jì)算組板方案和計(jì)算適應(yīng)度。相關(guān)程序界面如圖6所示。

圖6 程序界面示意圖

基于面向?qū)ο蟮脑O(shè)計(jì)思想，每個(gè)需要擺放的貨物用Good類表示，集裝板用Plate類表示，擺放貨物的空間用Space類表示，最后生成的方案用PlanConcrete類表示，PGUtils類為遺傳算法和具體擺放方案進(jìn)行轉(zhuǎn)換的工具類。

3.3.2 案例分析

（1）單一貨物的堆碼情況分析。利用單一貨物，可以實(shí)現(xiàn)基本的堆碼模擬生成。對(duì)于正方體形狀的物資，碼放的方式單一不用做多余工作。對(duì)于長方體物資，本文算法會(huì)考慮到物資的碼放方向，進(jìn)而優(yōu)化前文所提到的規(guī)劃目標(biāo)，達(dá)到相對(duì)最優(yōu)的情況。

以長0.5m，寬0.5m，高0.5m，數(shù)量為40的貨物，航空板為PMC標(biāo)準(zhǔn)航空板為例，可以得到圖7所示的組板方案，該圖體現(xiàn)了算法的核心擺放順序和擺放方式，即將航空板視為一個(gè)長方體，從左→右→上的順序依次碼放。

（2）多種貨物、單一航空板堆碼情況分析。對(duì)多種貨物進(jìn)行碼放時(shí)，存在兩種貨物混合碼放的情況。這里以寬和高相同、長度相差一倍的兩種貨物為例，具體如圖8所示?？梢钥闯觯浳镏g以相對(duì)規(guī)律的方式進(jìn)行碼放，并且存在混合的情況，基于遺傳算法的特定，貨物的碼放方向存在一定的隨機(jī)性。

（3）多種貨物、多航空板情況。在本算法中，考慮了單個(gè)航空板容量不足，用多個(gè)航空板進(jìn)行組板操作。案例數(shù)據(jù)見表1。

圖7 單一貨物的堆碼模擬及數(shù)據(jù)示意圖

圖8 多種貨物單一航空板堆碼模擬及數(shù)據(jù)示意圖

表1 多航空板、多物資部分組板數(shù)據(jù)

模擬結(jié)果與數(shù)據(jù)如圖9所示。

因考慮整個(gè)組板方案的綜合適應(yīng)度，存在部分航空板空間利用率不夠的情況。當(dāng)存在此問題時(shí)，可以適當(dāng)減少航空板的數(shù)量，再進(jìn)行方案模擬。

圖9 多航空板、多物資堆碼模擬及數(shù)據(jù)示意圖

在計(jì)算中，可根據(jù)實(shí)際情況調(diào)整重心、空間利用率和載重利用率的偏好，如對(duì)重心要求比較高時(shí)，可將計(jì)算適應(yīng)度的公式中的重心部分的權(quán)重提高。該程序提供了數(shù)據(jù)輸出功能，將計(jì)算結(jié)果，即每個(gè)物資對(duì)應(yīng)的航空板及航空板上的坐標(biāo)輸出，向外提供接口。

4 總結(jié)與展望

本文基于遺傳算法，探討了多品種物資的碼放問題，給出了3個(gè)評(píng)判指標(biāo)和1個(gè)綜合的適應(yīng)度，并基于java語言編程實(shí)現(xiàn)，得出相對(duì)較優(yōu)方案，為高適應(yīng)的自動(dòng)組板系統(tǒng)的操作提供數(shù)據(jù)支撐。但本文僅給出最后組盤方案，未考慮自動(dòng)組盤系統(tǒng)中的物資輸送順序，也是下一步研究需要重點(diǎn)考慮的方向。