大型港口集裝箱船舶智能配載的集成算法研究＊

楊杰敏，丁香乾，郭保琪，陳 林

（1.中國海洋大學(xué)，山東青島266100；2.青島港集團信息中心，山東青島266000）

大型港口集裝箱船舶智能配載的集成算法研究＊

楊杰敏1，2，丁香乾1，郭保琪2，陳 林2

（1.中國海洋大學(xué)，山東青島266100；2.青島港集團信息中心，山東青島266000）

為解決集裝箱碼頭智能化配載多業(yè)務(wù)規(guī)則集成優(yōu)化問題，提出3層規(guī)劃框架，重點研究第2層規(guī)劃方法。該方法對資源分配規(guī)則，建立數(shù)學(xué)模型；對質(zhì)量匹配規(guī)則和胎吊沖突規(guī)則，建立邏輯學(xué)模型；這些模型均以剪枝條件的形式融入到分支限界搜索中，而剪枝條件的正確性和有效性均有嚴(yán)格的證明保證。對于其它的業(yè)務(wù)規(guī)則，在生成和壓縮解空間的過程中就已經(jīng)充分考慮。同時并不忽略卸貨港、尺寸、箱型等重要屬性及其對配船位置的限制，實驗結(jié)果驗證算法的有效性。

集裝箱碼頭；配載；多業(yè)務(wù)規(guī)則集成；3層規(guī)劃；分支限界搜索

集裝箱船舶在各個港口間周轉(zhuǎn)，要保證船期，必須保障各個港口的順暢作業(yè)。廣義的配載是指船公司在其航線上各個港口的裝載計劃。狹義的配載是指集裝箱碼頭公司依據(jù)船公司的預(yù)配，確定每個集裝箱在船上的位置安排的業(yè)務(wù)過程。本文研究的重點是狹義的配載。配載作為集裝箱碼頭的核心業(yè)務(wù)，配載方案直接決定碼頭生產(chǎn)的運營效率和質(zhì)量，提高配載的水平會顯著提高港口作業(yè)的效率，優(yōu)化作業(yè)流程，降低生產(chǎn)能耗。目前配載業(yè)務(wù)雖然有可視化軟件的支持，但在集裝箱船舶大型化的發(fā)展形勢下，作業(yè)量和復(fù)雜度日趨增加，要高效組織碼頭生產(chǎn)，配載人員面臨很大挑戰(zhàn)，往往力不從心，迫切需要提高軟件的智能化和自動化水平。研究配載相關(guān)算法及計算機實現(xiàn)技術(shù)，是建設(shè)智慧碼頭的關(guān)鍵問題。

目前國內(nèi)外關(guān)于配載自動化的研究，大體上可分為4類。第1類是生成多種配載方案，通過仿真的手段來對方案進行篩選，評估［1］；第2類是將人工配載中的經(jīng)驗轉(zhuǎn)化成一種啟發(fā)策略，通過啟發(fā)式搜索得到配載方案［2－3］；第3類是采用人工智能中的技術(shù)，建立基于規(guī)則的專家系統(tǒng)，通過推理找到合適的配載方案［4］；第4類是建立各種各樣的數(shù)學(xué)規(guī)劃模型，通過求解模型生成配載方案［5－8］，而分支限界搜索是比較有效的求解方法［9－10］。

以上研究為實現(xiàn)配載自動化提供了多種途徑，但仍存在一些問題。最主要的是：研究廣義配載多，而集裝箱碼頭配載較少；配載業(yè)務(wù)規(guī)則眾多，目前的研究只是考慮其中的一小部分（比如船舶穩(wěn)性等），對于其它的一大部分規(guī)則（比如作業(yè)資源的分配和調(diào)度等），考慮得卻很少，所以導(dǎo)致生成的方案在實際中無法采用。

本文正是針對以上問題，深入一線配載實際，提出配載自動化的3層規(guī)劃方法，該方法關(guān)注多業(yè)務(wù)規(guī)則的集成，力求最大限度地逼近完整的真實的配載過程。

1 3層規(guī)劃方法和人工配載分析

1.1 3層規(guī)劃方法

第1層 作業(yè)路分配優(yōu)化。即確定合理的橋吊作業(yè)計劃及每個船貝的作業(yè)時間表，目標(biāo)是最短的裝卸船完工時間。

第2層 堆場動態(tài)取箱優(yōu)化。即確定船貝內(nèi)分塊從堆場上哪些貝取箱，目標(biāo)是最佳的堆場作業(yè)計劃（包括最少的胎吊走位沖突，最合理的胎吊資源分配等）。

第3層 貝位派箱優(yōu)化。即確定取箱方式及每個箱子在船上的具體位置，目標(biāo)是符合船舶穩(wěn)性要求的質(zhì)量分布及符合機械作業(yè)方式的取放箱定序。

配載業(yè)務(wù)規(guī)則眾多，而且不在1個層面上；分層處理使得業(yè)務(wù)規(guī)則清晰化，問題邊界明朗化，有益于配載數(shù)據(jù)的融合，問題求解規(guī)模的控制，本文重點研究的是第2層規(guī)劃。

1.2 人工配載分析

目前，港口配載主要由計劃人員在可視化軟件的輔助下完成。圖1為某一船貝的實配船圖，每一方框代表一個箱位。要根據(jù)預(yù)配，按照箱位上要求的卸貨港、尺寸、箱型到堆場上選取箱子（例如：SE1 40HC表示這里要放1個卸貨港為SE1箱型為HC尺寸為12.19 m的箱子）。方框的最后一行標(biāo)識了所選箱子在堆場上的位置，而第3行左標(biāo)識了它的質(zhì)量。從圖中不難發(fā)現(xiàn)，同一卸貨港、尺寸、箱型的箱位占據(jù)一片連續(xù)的區(qū)域，稱作1個船貝分塊，1個船貝內(nèi)會有多個這樣的分塊，每個分塊是進行第2層規(guī)劃的基本單位。

圖1 實配船圖Fig.1 Real stowage ship chait

圖2為H05場區(qū)的取箱量統(tǒng)計圖。最左邊的1列為時間，第2列是H05場區(qū)的各個場貝，最上面的1行Q02X表示作業(yè)路。本例中有4個作業(yè)路并行作業(yè)。表中的每1個數(shù)據(jù)表示1個堆場貝在某時段某個作業(yè)路的取箱量。

圖2 取箱量統(tǒng)計圖Fig.2 Total of fetching container number

第2層規(guī)劃主要涉及以下業(yè)務(wù)規(guī)則：數(shù)量規(guī)則；質(zhì)量規(guī)則，包括質(zhì)量限定規(guī)則、質(zhì)量匹配規(guī)則；資源分配規(guī)則，包括輪胎吊場區(qū)部署規(guī)則，作業(yè)路均衡分配規(guī)則；取放箱規(guī)則，包括取箱無沖突規(guī)則、取箱完整性規(guī)則、同場區(qū)取箱規(guī)則、特種箱放置規(guī)則。

并不是所有的業(yè)務(wù)規(guī)則都適合構(gòu)建數(shù)學(xué)模型，對于數(shù)量特征明顯的規(guī)則本文給出其數(shù)學(xué)表達(dá)式；對于邏輯特征明顯的規(guī)則本文給出其邏輯表達(dá)式；其它的規(guī)則采用其它合適的方法處理，這些規(guī)則都集成在分支限界搜索框架中。

2 自動化配載的解空間

2.1 解空間生成

由圖1可知，（卸貨港，尺寸箱型）可以標(biāo)識1個船貝內(nèi)分塊的類型，而堆場貝也有同樣的類型表示。只有當(dāng)堆場貝的類型和船貝內(nèi)分塊的類型相同時，堆場貝的集裝箱才能運往該船貝分塊。

數(shù)量規(guī)則是指：同一類型的堆場貝的箱子總數(shù)和船貝內(nèi)分塊的箱位總數(shù)相等。例如：（VA3，40GP）共有2塊，分布在船貝10B和26B上，10B那塊可裝14個，26B那塊可裝50個，共64個箱子；堆場上共有5個同類型貝的箱子，也為64個。分別是

H05.48（25個）K07.24（9個）K07.12（3個）

H05.16（1個）H05.04（26個）

取箱完整性規(guī)則是指：胎吊到堆場某個貝取箱時要盡量1次性取完。這樣以避免胎吊往復(fù)運動，減少胎吊移動距離，這就要求配載時1個堆場貝的箱子要盡量全部配給某個船貝，減少拆分。實際中做配載一般把H05.04取14個放在船10B，剩下的那些配給26B，這樣只拆開了1個H05.04，其余的保持完整。比較嚴(yán)格取箱完整性規(guī)則限制性，可使得能夠接受的解空間的變動范圍不大。本例中如果限定只能拆1個，只有不多的候選解可供選擇：

候選解①﹕H05.04－＞10B（14個）；其余－＞26B

候選解②﹕K07.24（9個），K07.12（3個），H05.16（1個），H05.04（1個）－＞10B；其余－＞26B

候選解③﹕K07.24（9個），H05.04（5個）－＞10B；其余－＞26B

…………

現(xiàn)在記H05.04－＞10B（14個）為ak，lii，其中i∈堆場貝集合YB，編號Ii＝H 05.04，場區(qū)Hi＝H 05，j∈船貝內(nèi)分塊集合VB，分塊所在船貝Ej＝10 B。k指分塊類型，本例中是（VA3，40GP），l指l第個候選解。把所有分塊類型的候選解集合在一起，就構(gòu)成配載問題的解空間。如圖3所示：a（k.l）代表1個候選解，ak，lij代表該候選解的1個分配。

圖3 配載問題的解空間（候選解陣列）Fig.3 The solution space of stowage

每列元素構(gòu)成1組，每組有r個元素，只需從每組中選取一個a（k，l），就構(gòu)成配載問題的解。這樣求解形式就由通常的整數(shù)規(guī)劃變成1個多階段決策（每組為1個階段），從左至右依次決策。

求解給定拆開量的所有候選解的算法并不難，本文這里暫不詳述。

2.2 解空間壓縮

在生成解空間以后，應(yīng)用質(zhì)量限定規(guī)則、特種箱放置規(guī)則和同場區(qū)取箱規(guī)則壓縮解空間。

質(zhì)量限定規(guī)則是指：按照集裝箱的質(zhì)量等級，由重到輕。甲板上要求相對嚴(yán)格，一般分布1、2層20 t以上，3層15 t左右，4層13 t，5層10 t左右，6層10 t以下等。按照常規(guī)的收箱計劃，1個場貝上的箱子質(zhì)量很接近，可以取平均值作為該場貝的質(zhì)量標(biāo)簽，而船貝內(nèi)分塊的坐標(biāo)及所在層數(shù)是已知的，所以可以應(yīng)用質(zhì)量限定規(guī)則去掉不符合該規(guī)則的候選解；特種箱放置規(guī)則也類似，對于不符合特殊位置擺放要求的候選解也要去掉。同場區(qū)取箱規(guī)則是指：1個船貝內(nèi)分塊要盡量取相同場區(qū)的箱子，以減少胎吊轉(zhuǎn)場次數(shù)，該規(guī)則可以通過對每個候選解中的不同場區(qū)進行計數(shù)的方法體現(xiàn)出來，進而可用于候選解的篩選和過濾。

解空間r值由配載人員輸入，選出符合上述規(guī)則的前r個候選解構(gòu)建解空間。解空間實際上限定了配載問題的考慮范圍，可根據(jù)實際情況靈活調(diào)整其大小。

解空間確定以后，就要根據(jù)a（k，l）ij的函數(shù)來確定a（k，l）的選取。

下面的每1種業(yè)務(wù)規(guī)則都對應(yīng)了這樣1個函數(shù)，而選取則采用分枝限界搜索實現(xiàn)分階段決策。

3 業(yè)務(wù)規(guī)則模型與搜索剪枝定理

3.1 資源分配規(guī)則

①每個時間段內(nèi)每個場區(qū)的取箱量不超過3個RTG發(fā)箱率（輪胎吊場區(qū)部署規(guī)則）。

②每個時間段內(nèi)每個場區(qū)每個作業(yè)路的取箱量不超過RTG發(fā)箱率（作業(yè)路均衡）RTG發(fā)箱率：1個輪胎吊每小時的裝載集裝箱的數(shù)量，通常為20～25。

資源分配規(guī)則是配載人員最為關(guān)心的規(guī)則，直接影響到港口生產(chǎn)作業(yè)順暢。規(guī)則①是要限定每個時間段內(nèi)每個場區(qū)的所使用的輪胎吊數(shù)量不能超過3個；規(guī)則②是因為每條作業(yè)路是串行作業(yè)，如果被違背，就意味著該作業(yè)路在此時段的取箱任務(wù)不可能完成。上述規(guī)則直觀上是對取箱量的規(guī)劃，實質(zhì)上是對胎吊資源使用的規(guī)劃。其數(shù)量關(guān)系較為復(fù)雜，需要借助矩陣來表達(dá)。

3.1.1 數(shù)學(xué)模型 Q（k，l）ivt是第k組第l個候選解中堆場貝i分配到作業(yè)路v時段t的取值量，對應(yīng)圖2中的每一個元素，其值由候選解a（k，l）經(jīng)公式（1）計算得到，排成矩陣Q（k，l）。

設(shè)Hi表示堆場貝i所在的場區(qū)，Wj表示船貝內(nèi)分塊j被安排的作業(yè)路，Tj表示分塊j被安排作業(yè)的時間（時段），E表示單位矩陣。其計算公式為：

于是資源分配規(guī)則可表示為公式（4）（5）。

3.1.2 分枝限界函數(shù) 根據(jù)公式（2）、（3），對每個候選解a（k，l）計算其相應(yīng)的矩陣M（k，l）、N（k，l），依據(jù)矩陣來決定候選解的選取，為此首先要研究矩陣M（k，l）、N（k，l）的性質(zhì)。

對于同一組的各個候選解而言，所涉及的場區(qū)和時段都是一樣的，分別記作Uk、Ek并記該組的取箱總量為TCk，根據(jù)公式（2）（3）有：

其它位置的元素均為0，l＝1，2，…r

性質(zhì)1說明不管怎樣分配，總箱量一定。性質(zhì)2說明同一組的候選矩陣M的非零元素都分布在相同的位置，可以將每個相應(yīng)位置取最小元素，構(gòu)成最小矩陣。

于是定義最小矩陣

和限界矩陣B（k）可作為分支限界搜索的限界函數(shù)。

松馳變量是當(dāng)前搜索到的解與所允許的最大箱量之間的差值矩陣。

定理1 設(shè)當(dāng)前決策到階段k，候選解a（k，l）滿足資源分配規(guī)則①必須有：

證明 根據(jù)公式（4）（10）可知滿足資源分配規(guī)則①必須有

根據(jù)公式（8），；而根據(jù)公式（9），

定理2 設(shè)當(dāng)前決策到階段k，候選解滿足a（k，l）資源分配規(guī)則②必須有：

證明類似，其限界函數(shù)為D（k）。

3.2 沖突規(guī)則

在實際生產(chǎn)中，胎吊調(diào)度經(jīng)常是由中控人員根據(jù)配載方案完成的。人工配載時雖然無法對場上胎吊的運動走位情況作精確計算，但可以依據(jù)以下規(guī)則來判定是否存在胎吊沖突：

如果a、b兩取箱點（堆場貝）位于同1個場區(qū)同1個時段內(nèi)，并且a、b相鄰，并且a、b分屬2個不同的作業(yè)路，并且a、b兩點取箱量之和大于RTG發(fā)箱率，那么a、b兩取箱點沖突。根據(jù)規(guī)則分析，定義沖突函數(shù)為：

i1，i2：堆場貝Ii1，Ii2堆場貝編號t1，t2：時段v1，v2：作業(yè)路

而對于v1＝v2的情況雖然不屬于嚴(yán)格意義上的沖突，但由于違背資源分配規(guī)則也是不行的，因此沖突函數(shù)可簡化為：

現(xiàn)仍設(shè)決策到階段k，判定候選解a（k，l）會不會倒致沖突；為了降低計算量，采用函數(shù)映射方法直接定位到相鄰場貝的取箱信息。設(shè)Yi代表場貝i的相鄰貝；Pi代表場貝i所在的分組（分塊類型），是唯一的。對于a（k，l）的每個堆場貝i1，其相鄰貝i2＝Y(jié)i1所在的分組號b＝P（i2）＾b＜k，則可知；該相鄰貝所在的分組是唯一的，所以便可代入公式（12）判定。另外，由于Q（k，l）較大，并不直接計算此矩陣，而是根據(jù)式（1）在需要時臨時計算。

定義1 沖突計數(shù)函數(shù)

該函數(shù)計算由候選解a（k，l）引起的沖突增加量，是進行方案尋優(yōu)的指標(biāo)。

3.3 質(zhì)量匹配規(guī)則

為使重心保持在船舶中央，較輕的箱子分布在船貝內(nèi)外圍，較重的箱子分布在船貝內(nèi)部，碼頭配載人員并不嚴(yán)格去計算重心數(shù)值，而只是把握好船貝內(nèi)各分塊的質(zhì)量匹配，滿足預(yù)配即可。具體來說，甲板以上，船貝分塊所處的位置越高，分塊所裝載的箱子質(zhì)量應(yīng)越小；船貝分塊所處的位置越靠近兩側(cè)，分塊所裝載的箱子質(zhì)量應(yīng)越小（見圖1）。在船貝自然坐標(biāo)系下

圖4 船貝的自然坐標(biāo)系Fig.4 Natural coordinate system of a vessel bay

設(shè)船貝內(nèi)某分塊的箱位坐標(biāo)集合為Oi，箱位數(shù)目m；則該分塊的中心坐標(biāo)為：，該分塊所裝的箱子的質(zhì)量平均值為［W］i。則質(zhì)量匹配規(guī)則可表示為邏輯表達(dá)式：

對于甲板以上的2個分塊：

由逆否定律有：

即：

另外，分塊中心坐標(biāo)之間的大小關(guān)系要做模糊化：

則：

不難發(fā)現(xiàn)此關(guān)系具有反自反，反對稱，傳遞性質(zhì)，先計算其傳遞閉包：

于是可以得到：

定理3 船貝b各分塊之間是質(zhì)量匹配當(dāng)且僅當(dāng)其中任意2個分塊i，j均滿足：

為了減少比較運算次數(shù)，得到如下定理：

定理4 設(shè)已決策到階段k，對船貝b，已確定了s個分塊，其中心坐標(biāo)分別為：這s個分塊的裝箱質(zhì)量分別為，并且已經(jīng)是質(zhì)量匹配的。在階段k，候選解a（k，l）要將1個新的［W］k裝入到分塊Cs＋1中，設(shè)則船貝b仍是質(zhì)量匹配的，當(dāng)且僅當(dāng)

證明

充分性 已確定的S個分塊是質(zhì)量匹配的，則有

于是對于［W］k，如果有

同理，如果有

所以在新裝入分塊s＋1后，仍然滿足定理3的條件，保持質(zhì)量匹配。

必要性 根據(jù)定理3，保持質(zhì)量匹配則對任意2個分塊

同時成立，定理得證。

定義3 質(zhì)量匹配函數(shù)：

對a（k，l）中的每個分塊。

4 第2層規(guī)劃算法

4.1 完整的規(guī)劃算法

由以上定理，可得滿足所需業(yè)務(wù)規(guī)則，具有最少沖突量的配載方案的算法如下：

（1）配載人員輸入r值確定解空間大小，給定沖突上限值NC，生成并壓縮解空間。

（2）預(yù)先計算M（k，l），N（k，l），B（k），D（k）以及函數(shù)P。

（16）if（k＞n）記錄當(dāng)前可行解；并更新CC值；k＝k－1；轉(zhuǎn)（11）

（17）轉(zhuǎn)（4）

第（1）步由配載人員輸入r值來調(diào)整解空間，如果所獲解不滿意可增大該值，如果求解時間過長可減少該值。NC是沖突允許的上限值，該值作為沖突量CC的初始值，在搜索過程中，沖突逐漸減小，直至最優(yōu)。第（4）步獲得滿足輪胎吊場區(qū)部署規(guī)則的候選解；第（5）步獲得滿足作業(yè)量均衡規(guī)則的候選解；第（6）步獲得滿足沖突規(guī)則的候選解；第（7）步獲得滿足質(zhì)量匹配規(guī)則的候選解；每一步均在上一步的基礎(chǔ)上求得，其中任何一步為空都要回退，可見將業(yè)務(wù)規(guī)則作為截枝條件顯著增加了截枝效果，并且計算以少量矩陣的代數(shù)和及函數(shù)映射為主，負(fù)擔(dān)較輕。第（8）步Sk獲得第k階段滿足所有的業(yè)務(wù)規(guī)則的候選解集合，并計算其方向函數(shù)值，選取該值最大的候選解，前進至下一階段；其余的留下儲備待回溯時再取用。

在本算法中，最少的沖突量是顯式的求解目標(biāo)。另外，還有最少的堆場貝拆開量，最少的跨場區(qū)取箱量，作為隱式的優(yōu)化指標(biāo)在解空間的生成和壓縮中就得到了體現(xiàn)。

4.2 算例及實驗

本文采用實際的生產(chǎn)作業(yè)數(shù)據(jù)，對箱量為463的貨船進行了自動化配載。由于運算過程較為復(fù)雜，本文僅以矩陣M為例截取k＝5時的運行片斷。

1個候選解對應(yīng)1個矩陣M（k，l），于是相應(yīng)的就有矩陣M陣列，如圖5所示，共有9組，陣列第5組（VA3，40GP）的候選解在前面第2.1節(jié)中。本案例中只有H 05，K 07場的取箱總量超過3RTG（RTG設(shè)為25），所以矩陣M只涉及這2個場區(qū)，其它場區(qū)肯定不會違背資源分配規(guī)則①。

對每組矩陣預(yù)先計算其最小和限界矩陣如下：

圖5 候選解的矩陣M陣列Fig.5 Array of the matrix M of candidate solution

k＝1時起開始運行，當(dāng)前進至k＝5時，

……

運行結(jié)束，得到的場區(qū)取箱量分布見圖6，從圖中可知，每個時間段內(nèi)每個場區(qū)的取箱量均沒有超過3個RTG發(fā)箱率（75）；而每個時間段內(nèi)每個場區(qū)各個作業(yè)路的取箱量也未超過RTG發(fā)箱率，圖7展示了H05場的作業(yè)路分配情況。而各船貝也有良好的質(zhì)量分布，圖8展示了船貝18A的箱位配載狀況，每個箱位的最下面一行數(shù)字代表集裝箱質(zhì)量，沿著從中央向兩側(cè)，從下往上的方向排列，滿足中心較重，外圍較輕的配載要求。沖突量也控制在3次。總體而言，滿足第2層規(guī)劃的主要業(yè)務(wù)規(guī)則，是1個比較可行的配載方案。

圖7 作業(yè)路時段分布Fig.7 Distribution in queues and phases

圖8 箱位配載船圖Fig.8 Stowage chart of a vessel bay

5 結(jié)語

配載本身涉及很多業(yè)務(wù)規(guī)則，這些業(yè)務(wù)規(guī)則具有不同的類型分屬不同的層面，如何將它們有效集成是智能化配載要解決的核心問題。本文正是針對該問題，提出了1種集成優(yōu)化方案體系。

該體系分成3層，對第2層中的資源分配規(guī)則，建立了數(shù)學(xué)模型；對于質(zhì)量規(guī)則和沖突規(guī)則，建立了邏輯學(xué)模型，這些模型均以剪枝條件的形式融入到分支限界搜索框架中。而對于其它的業(yè)務(wù)規(guī)則，在生成和壓縮解空間的過程中就已經(jīng)使用。本文并不拘泥于純數(shù)學(xué)模型，而是根據(jù)業(yè)務(wù)規(guī)則特點設(shè)計合適的算法，并且充分考慮到了卸貨港、尺寸、箱型等多生產(chǎn)要素及其對配船位置的限制。從實驗結(jié)果來看，所生成的配載方案已經(jīng)很貼近真實的配載業(yè)務(wù)要求。

［1］ Shields.Container－ship stowage：a computer－aided preplanning system［J］.Mar Technol，1984（4）：370－383.

［2］ Avriel M，Penn M，Shpirer N，Container ship stowage problem：complexity and connection to the coloring of circle graphs［J］.Discrete Applied Mathematics，2000，103（1－3）：271－279.

［3］ Avriel M，Penn M，Shpirer N，et al.Stowage planning for container ships to reduce the number of shifts［J］.Annals of Operations Research，1998，76：55－71.

［4］ Dillingham J T，Perakis A N.Application of artificial intelligence in the marine industry［M］.Boston：Presented at Fleet Management technology Conference，2000.

［5］ Haghani A，Kaisar E I.A model for designing container loading plans for containerships working paper［M］.Boston：University of Maryland，presented at Transportation Research Board Annual Meeting，2001.

［6］ Giemsch P，Jellinghaus A.Organization models for the containership stowage problem［M］.Heidel Berg：Paper presented at the annual international conference of the German Operations Research Society，2003.

［7］ Ambrosino D，Sciomachen A，Tanfani E.Stowing a containership：the master bay plan problem［J］.Transport Res A，2004，38：81－99.

［8］ 張維英，林焰，紀(jì)卓尚.集裝箱全航線Bay位排箱優(yōu)化模型［J］.上海交通大學(xué)學(xué)報，2007，41（2）：199－204.

［9］ Wilson I D，Roach P A.Container stowage planning：a methodology for generating computerised solutions［J］.Journal of the Operational Research Society，2000，51：1248－1255.

［10］ Wilson I D，Roach P A，Ware J A.Container stowage pre－planning：using search to generate solutions，a case study［J］.Knowledge－Based Systems，2001，14（3－4）：137－145.

Stowage Planning and Integrating Algorithm Research in Large Container Terminal

YANG Jie－Min1，2，DING Xiang－Qian1，GUO Bao－Qi2，CHEN Lin2（1.Ocean University of China，Qingdao 266100，China；2.EDI Center of Qingdao Port，Qingdao 266000，China）

Container stowage planning，a three－tiers planning framework for the automatic generation is proposed，focusing on the second level planning method.In this method，a mathematical model for the resource allocation rules is established，as well as the logic models for the weight matching rules and the crane conflict rule.These models are melt into the branch and bound search in the form of pruning conditions，and the correctness and effectiveness is proved strictly.The other business rules have been fully considered in the generation and compression of the solution space as well.At the same time the important container properties such as the port of discharge，size and the restrictions for the target positions are not ignored.The experimental results verify the validity of the algorithm.

container terminal；stowage planning；multi－business rules integrating；three－tiers planning；branch and bound search

TP301.6

A

1672－5174（2011）10－121－07

中國交通運輸部科技司攻關(guān)項目（2008－353－854－480）；青島市重點技術(shù)創(chuàng)新項目（200904 LX090107.0515）資助。

2010－07－02；

2011－03－28

楊杰敏（1971－），男，高級工程師。E－mail：yjm＠qdport.com

責(zé)任編輯 陳呈超