摘 要： 在考慮集裝箱裝載" title="集裝箱裝載">集裝箱裝載貨物底置等級、側放方式、堆碼層數等一些實際應用的約束條件下，根據同類型貨物一次性裝載的思想，提出了一種新的基于空間劃分的啟發式算法" title="啟發式算法">啟發式算法，并以此為基礎構造了一種混合遺傳算法" title="遺傳算法">遺傳算法。
關鍵詞： 集裝箱裝載 啟發式 混合遺傳算法 多約束
在運輸中如何進行貨物的有效裝載，即怎樣將一批矩形貨物布入一個或多個集裝箱中，使集裝箱的空間利用率達到最高，這屬于NP完全問題。集裝箱裝載問題根據集裝箱數量的有限和無限劃分成兩類：一是集裝箱數量無限，盒子必須全部裝完，要使所用的集裝箱數量最少；二是集裝箱數量有限，盒子數量超過了集裝箱的裝載能力，要求被裝載盒子的總體積達到最大，使空間利用率最高。在實際中第二類問題更為常見，所以在此只分析第二類問題。
目前常用的布局優化方法多為不帶約束的簡化布局問題，而現實生活中存在著大量的約束條件。
針對具有貨物底置位置、允許側放方式、最大堆碼層數等多約束條件下的集裝箱裝載問題和目前集裝箱容積有效利用率普遍較低的情況，本文將這些約束考慮到啟發式規則中，根據裝載中單種貨物數量一般較多的實際情況，提出了一種新的基于空間劃分的啟發式算法，并將其與遺傳算法結合，進一步提出了混合遺傳算法求解多約束裝箱問題。該算法已用于企業的實際裝箱中，結果表明，本文提出的方法可行且有效。
1 多約束集裝箱裝載的啟發式策略
實際裝載中單種貨物數量一般較多，采用現有針對單個物品的基于三維空間的啟發式算法存在裝載效率和空間利用率低的問題。因此，本文采用同類型貨物一次性裝載的思想，提出了一種新的基于空間劃分的啟發式策略。該策略根據待布局空間塊中貨物裝載方式的不同將剩余空間最多劃分為五種空間塊。實際應用中，對算法中的約束條件處理方法是引入不同變量分別表示貨物的側放方式、貨物的堆碼層數、底置等級等屬性。
1.1 基于空間劃分的啟發式算法流程
算法流程的步驟如下：
(1)初始化空間塊序列為集裝箱箱體。
(2)依次按底置等級遞增、體積遞減對貨物類型排序。
(3)從貨物類型序列中按順序取某類型貨物，從空間塊列表中取第一個" title="第一個">第一個可用空間塊。
(4)將所取類型的貨物一次性裝載到所取空間塊中。根據貨物可取側放方式、最大堆碼層數的不同，計算空間塊的最大裝載數量(本文稱為標準裝車)，同時產生標準裝車的擺放方式。當貨物數量小于標準裝車時(稱為非標準裝車)，根據貨物數量、允許側放方式、最大堆碼層數產生非標準裝車的擺放方式。
(5)分割空間塊，將其添加到空間塊序列，按體積對空間塊重新排序。
(6)如(4)為標準裝車，求所取類型貨物的剩余數量，從空間塊列表中取第一個可用空間塊，轉(4)；否則轉(3)。
1.2 定序" title="定序">定序規則
定序規則用來確定物體布入的先后順序，對最終布局結果的優劣有重要影響。由于貨物底置等級越低，要求放置的位置越低，所以采用依次按底置等級遞增、體積遞減的定序規則對貨物類型排序。
1.3 定位規則
1.3.1 標準裝車
裝車規則：對箱體的某種側放方式，X-Y平面的擺放次序為先橫后縱。如圖1所示，Nxhorz，Nyhorz，Nyvert，Nxbert分別表示整的橫箱、縱箱在X軸和Y軸的數目；Nrem_x，Nrem_y表示零頭在X軸和Y軸方向的數目；wid表示待布局立方體的寬。確定Nyhorz和Nyvert滿足：
min{wid-Nyhorz×boxwid-Nyvert×boxlen} (1)
零頭應置于最外側。零頭的擺放應考慮空間完整程度, 再決定橫放還是縱放。如果程度一致，則橫放。在Z軸方向，根據貨物可取側放方式、最大堆碼層數遍歷得到最優的箱子層數lay_num和各層的側放方式。最優判定準則是可裝的箱子數目最多。
1.3.2 非標準裝車
裝車規則：當裝載不滿時：(1)應避免中間突出的情況，以免使空間過于破碎。如有中間突出的情況，應把突出的擺放換到邊上，這樣可以利用最外邊的一段空間。(2)如有小于最小尺寸的邊，應盡量把此類情況轉換為其他方式。(3)在寬度方向上求最優，是為了維護空間完整度。
非標準裝車有以下幾種情況，如圖2所示。
設待布局箱子數目為num_all，如空間塊的標準裝車方式所確定的各層側放方式不同，則首先根據標準裝車擺放各層，對不滿的一層，令lay_num=1，刷新num_all，轉(1)。
如標準裝車方式所確定的各層側放方式相同，則：
(1)由標準裝車確定的各參數計算箱體在所布空間塊的理論長度La，其中：
La=Va/(Nyhorz×boxwid+Nyvert×boxlen) (2)
Va=boxwid×boxlen×num_all/lay_num (3)
(2)計算縱放排數：Nxvert1=La/boxwid (4)
橫放排數：Nxhorz1=La/boxlen (5)
(3)計算余箱數
num_r=num_all-Nxvert1×Nyvert-Nxhorz1×Nyhorz (6)
(4)余箱放置的種類有以下幾種：V0表示豎放；H0表示橫放；V1表示豎放1列或幾列，其余按橫放；H1表示橫放1列或幾列，其余按豎放。
這4種方式對應的共同約束為：所有情況的最長行不能超過長度界限；優先級應考慮空間的完整性和較短的總長度。具體流程如圖3所示。圖3中各公式如下：
①Lv=trunc(La/boxwid)
Lh=trunc(La/boxlen)
?、贜h=num_r/Nyhorz
Nh1=(Lv+boxwid-Lh)/boxlen
?、跱v=num_r/Nyvert
Nv1=(Lh+boxlen-Lv)/boxwid
?、芡?/P>
1.4 空間劃分
空間塊的劃分如圖4(a)、(b)所示。根據零頭所在位置的不同，空間塊可最多分割為A-B-C1-D-E-F或A-B-C2-D-E-F五種，各空間塊可視化時的遮擋順序為D-E-C-F-B-A。
2 約束集裝箱裝載問題的混合遺傳算法
采用以上基于空間劃分的啟發式算法的效率較高，但仍然難以保證獲得全局最優解或次優解。遺傳算法[4]作為一種模擬自然進化過程的隨機性全局優化概率搜索算法，在求解優化問題中顯示了優越的性能。因此本文將啟發式算法與遺傳算法結合，進一步提出了求解多約束裝箱問題的混合遺傳算法。
2.1 染色體的編碼方法
編碼是GA應用成功與否的關鍵。本文采用Grefen-
stette等針對TSP提出的基于順序表示的遺傳基因編碼方式[4]，把待裝物品的類型編號按排放順序排的串作為一個解的編碼，即p={p1，p2……pn}。其中n表示裝物品的類型；p1為整數，其值代表物品類型的編號。
2.2 目標函數和適應度
在集裝箱裝載過程中不僅要求容器空間利用率達到最高，同時要考慮多種約束。由于在啟發式裝載過程中引入了不同變量(暫不考慮重心約束)，因此適應度函數為：
其中BVi表示布入的第i個箱子體積，CV為集裝箱體積，m為布入箱子總個數。
2.3 選擇和交叉操作
采用類似于輪盤賭選擇法和跨世代精英選擇策略。對于本文這種類似于TSP問題的以符號編碼的基因串p，采用Goldberg等針對TSP提出的部分匹配交叉操作(Partially Matched Crossover)[5]策略。這種交叉操作的主要思想是：隨機選取二個交叉點，以便確定一個匹配段，根據二個父個體中二個交叉點之間的中間段給出的映射關系生成二個子個體。
2.4 變異操作
變異運算是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他等位基因來替換，從而形成一個新的個體。對于變異操作，采用逆位遺傳算子，在父個體的底置等級相同的染色體段內隨機選擇二個變異點，二點間的基因按相反順序重新排列。
2.5 混合遺傳算法流程
混合遺傳算法流程的步驟為：
(1)初始化種群。由啟發式算法的定序規則獲得初始種群的第一個染色體，對該染色體進行隨機變異，產生其余染色體。
(2)根據啟發式算法的定位規則和空間劃分方式計算個體適應度，并判斷是否符優化準則。若符合，輸出最佳個體及其代表的最優解，并結束計算；否則轉向(3)。
(3)按輪盤賭選擇法選擇再生的個體。
(4)按部分匹配交叉操作生成新的個體。
(5)由交叉和變異產生新一代的種群，新一代種群和上一代種群混合，按適應度選擇優良個體組成新一代的個體，返回到(2)。
遺傳算法的優化準則一般是依據問題的差異有不同的確定方式。本文采用的優化準則是：世代數超過預先設定的值。
本文針對多約束集裝箱貨物裝載問題，根據同類型貨物一次性裝載的思想，提出了一種新的基于空間劃分的啟發式策略，將剩余空間最多劃分為五種空間塊，并將其與遺傳算法結合，進一步提出了混合遺傳算法求解多約束裝箱問題。此算法為解決多目標、多約束的復雜集裝箱貨物裝載問題提供了一條新的思路。
參考文獻
1 Li K Q，Cheng K H.A heuristic algorithms for On Line Packing in Three Dimensions.Journal of Algorithms，1992；(13)
2 何大勇，查建中，姜義東.遺傳算法求解復雜集裝箱裝載問題方法研究.軟件學報，2001；12(9)
3 王濤，魏鳳.求解復雜集裝箱裝載問題的新方法.中國工程科學，2004；6(12)
4 周明，孫樹棟.遺傳算法原理及應用.北京：國防工業出版社，2000
5 Davis L.Handbook of genetic algorithms.Van Nostrand Rein-hold，new York，1991