在運(yùn)輸中如何進(jìn)行貨物的有效裝載，即怎樣將一批矩形貨物布入一個(gè)或多個(gè)集裝箱中，使集裝箱的空間利用率達(dá)到最高，這屬于NP完全問題。集裝箱裝載問題根據(jù)集裝箱數(shù)量的有限和無限劃分成兩類：一是集裝箱數(shù)量無限，盒子必須全部裝完，要使所用的集裝箱數(shù)量最少；二是集裝箱數(shù)量有限，盒子數(shù)量超過了集裝箱的裝載能力，要求被裝載盒子的總體積達(dá)到最大，使空間利用率最高。在實(shí)際中第二類問題更為常見，所以在此只分析第二類問題。
　　目前常用的布局優(yōu)化方法多為不帶約束的簡(jiǎn)化布局問題，而現(xiàn)實(shí)生活中存在著大量的約束條件。
　　針對(duì)具有貨物底置位置、允許側(cè)放方式、最大堆碼層數(shù)等多約束條件下的集裝箱裝載問題和目前集裝箱容積有效利用率普遍較低的情況，本文將這些約束考慮到啟發(fā)式規(guī)則中，根據(jù)裝載中單種貨物數(shù)量一般較多的實(shí)際情況，提出了一種新的基于空間劃分的啟發(fā)式算法，并將其與遺傳算法結(jié)合，進(jìn)一步提出了混合遺傳算法求解多約束裝箱問題。該算法已用于企業(yè)的實(shí)際裝箱中，結(jié)果表明，本文提出的方法可行且有效。
1 多約束集裝箱裝載的啟發(fā)式策略
　　實(shí)際裝載中單種貨物數(shù)量一般較多，采用現(xiàn)有針對(duì)單個(gè)物品的基于三維空間的啟發(fā)式算法存在裝載效率和空間利用率低的問題。因此，本文采用同類型貨物一次性裝載的思想，提出了一種新的基于空間劃分的啟發(fā)式策略。該策略根據(jù)待布局空間塊中貨物裝載方式的不同將剩余空間最多劃分為五種空間塊。實(shí)際應(yīng)用中，對(duì)算法中的約束條件處理方法是引入不同變量分別表示貨物的側(cè)放方式、貨物的堆碼層數(shù)、底置等級(jí)等屬性。
1.1 基于空間劃分的啟發(fā)式算法流程
　　算法流程的步驟如下：
　　(1)初始化空間塊序列為集裝箱箱體。
　　(2)依次按底置等級(jí)遞增、體積遞減對(duì)貨物類型排序。
　　(3)從貨物類型序列中按順序取某類型貨物，從空間塊列表中取第一個(gè)" title="第一個(gè)">第一個(gè)可用空間塊。
　　(4)將所取類型的貨物一次性裝載到所取空間塊中。根據(jù)貨物可取側(cè)放方式、最大堆碼層數(shù)的不同，計(jì)算空間塊的最大裝載數(shù)量(本文稱為標(biāo)準(zhǔn)裝車)，同時(shí)產(chǎn)生標(biāo)準(zhǔn)裝車的擺放方式。當(dāng)貨物數(shù)量小于標(biāo)準(zhǔn)裝車時(shí)(稱為非標(biāo)準(zhǔn)裝車)，根據(jù)貨物數(shù)量、允許側(cè)放方式、最大堆碼層數(shù)產(chǎn)生非標(biāo)準(zhǔn)裝車的擺放方式。
　　(5)分割空間塊，將其添加到空間塊序列，按體積對(duì)空間塊重新排序。
　　(6)如(4)為標(biāo)準(zhǔn)裝車，求所取類型貨物的剩余數(shù)量，從空間塊列表中取第一個(gè)可用空間塊，轉(zhuǎn)(4)；否則轉(zhuǎn)(3)。
1.2 定序" title="定序">定序規(guī)則
　　定序規(guī)則用來確定物體布入的先后順序，對(duì)最終布局結(jié)果的優(yōu)劣有重要影響。由于貨物底置等級(jí)越低，要求放置的位置越低，所以采用依次按底置等級(jí)遞增、體積遞減的定序規(guī)則對(duì)貨物類型排序。

1.3 定位規(guī)則
1.3.1 標(biāo)準(zhǔn)裝車
　　裝車規(guī)則：對(duì)箱體的某種側(cè)放方式，X-Y平面的擺放次序?yàn)橄葯M后縱。如圖1所示，Nxhorz，Nyhorz，Nyvert，Nxbert分別表示整的橫箱、縱箱在X軸和Y軸的數(shù)目；Nrem_x，Nrem_y表示零頭在X軸和Y軸方向的數(shù)目；wid表示待布局立方體的寬。確定Nyhorz和Nyvert滿足：
　　min{wid-Nyhorz×boxwid-Nyvert×boxlen}　　　　　　(1)
　　零頭應(yīng)置于最外側(cè)。零頭的擺放應(yīng)考慮空間完整程度, 再?zèng)Q定橫放還是縱放。如果程度一致，則橫放。在Z軸方向，根據(jù)貨物可取側(cè)放方式、最大堆碼層數(shù)遍歷得到最優(yōu)的箱子層數(shù)lay_num和各層的側(cè)放方式。最優(yōu)判定準(zhǔn)則是可裝的箱子數(shù)目最多。
1.3.2 非標(biāo)準(zhǔn)裝車
　　裝車規(guī)則：當(dāng)裝載不滿時(shí)：(1)應(yīng)避免中間突出的情況，以免使空間過于破碎。如有中間突出的情況，應(yīng)把突出的擺放換到邊上，這樣可以利用最外邊的一段空間。(2)如有小于最小尺寸的邊，應(yīng)盡量把此類情況轉(zhuǎn)換為其他方式。(3)在寬度方向上求最優(yōu)，是為了維護(hù)空間完整度。
　　非標(biāo)準(zhǔn)裝車有以下幾種情況，如圖2所示。

　　設(shè)待布局箱子數(shù)目為num_all，如空間塊的標(biāo)準(zhǔn)裝車方式所確定的各層側(cè)放方式不同，則首先根據(jù)標(biāo)準(zhǔn)裝車擺放各層，對(duì)不滿的一層，令lay_num=1，刷新num_all，轉(zhuǎn)(1)。
　　如標(biāo)準(zhǔn)裝車方式所確定的各層側(cè)放方式相同，則：
　　(1)由標(biāo)準(zhǔn)裝車確定的各參數(shù)計(jì)算箱體在所布空間塊的理論長(zhǎng)度La，其中：
　　La=Va/(Nyhorz×boxwid+Nyvert×boxlen)　　　　　　(2)
　　Va=boxwid×boxlen×num_all/lay_num　　　　　　　(3)
　　(2)計(jì)算縱放排數(shù)：Nxvert1=La/boxwid　　　　　　　(4)
　　橫放排數(shù)：Nxhorz1=La/boxlen　　　　　　　　　　　(5)
　　(3)計(jì)算余箱數(shù)
　　num_r=num_all-Nxvert1×Nyvert-Nxhorz1×Nyhorz　　　(6)
　　(4)余箱放置的種類有以下幾種：V0表示豎放；H0表示橫放；V1表示豎放1列或幾列，其余按橫放；H1表示橫放1列或幾列，其余按豎放。

　　這4種方式對(duì)應(yīng)的共同約束為：所有情況的最長(zhǎng)行不能超過長(zhǎng)度界限；優(yōu)先級(jí)應(yīng)考慮空間的完整性和較短的總長(zhǎng)度。具體流程如圖3所示。圖3中各公式如下：
　?、貺v=trunc(La/boxwid)
　　　Lh=trunc(La/boxlen)
　　②Nh=num_r/Nyhorz
　　　Nh1=(Lv+boxwid-Lh)/boxlen
　?、跱v=num_r/Nyvert
　　　Nv1=(Lh+boxlen-Lv)/boxwid
　?、芡?/P>

1.4 空間劃分
　　空間塊的劃分如圖4(a)、(b)所示。根據(jù)零頭所在位置的不同，空間塊可最多分割為A-B-C1-D-E-F或A-B-C2-D-E-F五種，各空間塊可視化時(shí)的遮擋順序?yàn)镈-E-C-F-B-A。
2 約束集裝箱裝載問題的混合遺傳算法
　　采用以上基于空間劃分的啟發(fā)式算法的效率較高，但仍然難以保證獲得全局最優(yōu)解或次優(yōu)解。遺傳算法^[4]作為一種模擬自然進(jìn)化過程的隨機(jī)性全局優(yōu)化概率搜索算法，在求解優(yōu)化問題中顯示了優(yōu)越的性能。因此本文將啟發(fā)式算法與遺傳算法結(jié)合，進(jìn)一步提出了求解多約束裝箱問題的混合遺傳算法。
2.1 染色體的編碼方法
　　編碼是GA應(yīng)用成功與否的關(guān)鍵。本文采用Grefen-
　　stette等針對(duì)TSP提出的基于順序表示的遺傳基因編碼方式^[4]，把待裝物品的類型編號(hào)按排放順序排的串作為一個(gè)解的編碼，即p={p₁，p₂……p_n}。其中n表示裝物品的類型；p1為整數(shù)，其值代表物品類型的編號(hào)。
2.2 目標(biāo)函數(shù)和適應(yīng)度
　　在集裝箱裝載過程中不僅要求容器空間利用率達(dá)到最高，同時(shí)要考慮多種約束。由于在啟發(fā)式裝載過程中引入了不同變量(暫不考慮重心約束)，因此適應(yīng)度函數(shù)為：