多品種物資碼垛方案生成算法設計及編程實現

劉振興，吳兆東，張大鵬

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

1 引言

物資集裝化運輸是目前物流運輸的主要形式之一，常見的集裝容器有托盤、航空板、集裝箱等。對托盤以及航空板而言，物資的碼盤方式多數是依賴操作經驗進行，這種方式對同一類物資或少品類近似物資比較適用，但對多品類物資，這種方法的不確定性增加，會產生重心不穩、空間利用率低等問題，進而影響了物流效率。

碼盤優化算法一直都是集裝化研究的熱點問題。一個適用的算法，能夠得到一個相對優化的組盤方案，節省時間，提高效率，為后續的物流環節做好鋪墊。本文以航空板組板為例，研究多品種物資的組板問題，設計組板優化算法并通過java編程實現，得到自動堆碼模型，為自動組板系統的研發提供思路。

2 航空板組板問題描述

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

2.1 問題的數學抽象

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

空間利用率函數：

載重利用率函數：

重心偏移程度函數：

分別給予上述評價指標α、β、θ的權重系數，取值在（0,1）之間，依據實際情況對碼垛的要求進行取值。最后的考察函數為：

2.2 方案約束

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

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

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

2.3 空間分割組合思想

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

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

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

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

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

3 遺傳算法設計及編程實現

遺傳算法是一種基于達爾文生物進化論的自然選擇和遺傳學機理的生物進化過程的計算模擬，是一種通過模擬生物界自然進化過程尋找最優解的方法。

3.1 方案的編碼與解碼

圖2 空間淺組合示意圖

圖3 空間深組合示意圖

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

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

圖4 物資碼放流程圖

（1）待裝物資編號：i=1,2,…,n；

（2）待用航空板編號：j=1,2,…,m；

（3）待裝物資編號體現了堆碼順序，編號小的物資優先碼放；

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

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

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

（1）Si，Si+n，Si+2n表示一個物資以排序號Si，擺放方向為Si+n擺放在航空板編號為Si+2n的航空板上；

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

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

（4）碼放過程嚴格按照圖4所示的流程進行。

3.2 遺傳算法計算流程

遺傳算法的計算過程基本上是不涉及到外部信息，只需要關注評價函數。在第二節中已經給出了評價函數，即式（4），作為遺傳算法的適用度函數。

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

個體基因遺傳中，隨機選擇兩個基因位置，其索引分別為a和b，將a和b之間的基因進行交換。基因突變，設置每次基因突變的位置個數，每個位置以概率p發生基因突變，對應的基因位置根據代表的編碼意義，在對應的區間內隨機變化。

為了確保算法收斂，將每一代產生的最優個體保存在下一代的種群中。

計算流程如圖5所示。

圖5 遺傳算法流程圖

3.3 編程及案例分析

3.3.1 編程實現。本文主要使用java語言，利用開發工具eclipseVE開發，根據上述算法，實現模擬航空組板的方案。在java編程中，將組板方案和遺傳算法單獨編程。待放物資用Good類表示，航空板用Plate類表示，空間用Space類表示。通過解碼和編碼將兩者聯系，并寫一個工具類來計算組板方案和計算適應度。相關程序界面如圖6所示。

圖6 程序界面示意圖

基于面向對象的設計思想，每個需要擺放的貨物用Good類表示，集裝板用Plate類表示，擺放貨物的空間用Space類表示，最后生成的方案用PlanConcrete類表示，PGUtils類為遺傳算法和具體擺放方案進行轉換的工具類。

3.3.2 案例分析

（1）單一貨物的堆碼情況分析。利用單一貨物，可以實現基本的堆碼模擬生成。對于正方體形狀的物資，碼放的方式單一不用做多余工作。對于長方體物資，本文算法會考慮到物資的碼放方向，進而優化前文所提到的規劃目標，達到相對最優的情況。

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

（2）多種貨物、單一航空板堆碼情況分析。對多種貨物進行碼放時，存在兩種貨物混合碼放的情況。這里以寬和高相同、長度相差一倍的兩種貨物為例，具體如圖8所示。可以看出，貨物之間以相對規律的方式進行碼放，并且存在混合的情況，基于遺傳算法的特定，貨物的碼放方向存在一定的隨機性。

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

圖7 單一貨物的堆碼模擬及數據示意圖

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

表1 多航空板、多物資部分組板數據

模擬結果與數據如圖9所示。

因考慮整個組板方案的綜合適應度，存在部分航空板空間利用率不夠的情況。當存在此問題時，可以適當減少航空板的數量，再進行方案模擬。

圖9 多航空板、多物資堆碼模擬及數據示意圖

在計算中，可根據實際情況調整重心、空間利用率和載重利用率的偏好，如對重心要求比較高時，可將計算適應度的公式中的重心部分的權重提高。該程序提供了數據輸出功能，將計算結果，即每個物資對應的航空板及航空板上的坐標輸出，向外提供接口。

4 總結與展望

本文基于遺傳算法，探討了多品種物資的碼放問題，給出了3個評判指標和1個綜合的適應度，并基于java語言編程實現，得出相對較優方案，為高適應的自動組板系統的操作提供數據支撐。但本文僅給出最后組盤方案，未考慮自動組盤系統中的物資輸送順序，也是下一步研究需要重點考慮的方向。