基于知識的集裝箱堆場箱位分配計劃研究

摘要：針對集裝箱堆場箱位分配問題中規(guī)則因素較強的特點，建立基于知識的箱位分配計劃方法。首先描述了該問題中知識構(gòu)成和表示方法；并提出了基于知識的箱位分配模型，包括分配區(qū)域劃分、作業(yè)模式及規(guī)則匹配、最優(yōu)箱位選擇三個部分。實例分析表明本方法可取得良好的箱位分配效果。

關(guān)鍵詞：知識； 箱位分配； 集裝箱堆場； 規(guī)則； 模板

中圖分類號：TP391

文獻標(biāo)志碼：A

文章編號：1001-3695（2007）09-0146-03

集裝箱港口堆場大門作業(yè)中，出口集裝箱的箱位分配優(yōu)化對提高集裝箱堆場作業(yè)效率、減少船舶在港停靠時間具有重要意義。在集裝箱班輪到達(dá)港口前的集裝箱載入期內(nèi)，港口作業(yè)方獲得船舶配載圖之前集裝箱已經(jīng)隨機到達(dá)堆場，在此期間產(chǎn)生完全符合配載圖要求的集裝箱堆垛較困難[1]。為此，要求堆場作業(yè)應(yīng)優(yōu)化箱位分配計劃使得后續(xù)按配載圖為基準(zhǔn)的裝卸作業(yè)成本最小。近年來，在箱位分配問題的研究方面，Kim和Park考慮貝中集裝箱的重量等級分布，建立以期望倒箱次數(shù)最少為目標(biāo)的動態(tài)規(guī)劃模型[2]；Kim和Bae研究了集裝箱堆垛的重新配置問題，提出一種變當(dāng)前貝堆垛為期望貝堆垛的方法，實現(xiàn)倒箱數(shù)量最少、設(shè)備移動距離最短的目標(biāo)[3]；郝聚民等人以圖搜索和模式識別技術(shù)為基礎(chǔ)建立了混合順序作業(yè)堆場貝優(yōu)化模型[4]。

上述研究主要針對獲得船舶配載圖后的堆垛優(yōu)化并且主要以集裝箱的貝堆垛為單位進行。本文則著眼于獲得船舶配載圖前的箱位分配作業(yè)，考慮在由若干個貝構(gòu)成的堆垛區(qū)域內(nèi)進行。箱位分配是一種以堆場管理原則為中心的計劃活動，其中存在較多的規(guī)則和制約因素。為此，本文提出并實現(xiàn)了一種基于知識的、方便后續(xù)作業(yè)的集裝箱箱位分配計劃方法。

1箱位分配作業(yè)知識構(gòu)成及其表示

1.1箱位分配作業(yè)知識構(gòu)成

在出口集裝箱的箱位分配問題中，根據(jù)堆場管理原則和作業(yè)設(shè)備的特點，可得到多種關(guān)于作業(yè)的知識[5]。按其作用可分為分配區(qū)域劃分規(guī)則、堆垛作業(yè)模式和設(shè)備作業(yè)規(guī)則。

1）分配區(qū)域劃分規(guī)則

堆場集裝箱的堆放一般遵循PSCW原則，即對同一目的港(port)、同一尺寸(size)、同一種類(category)的集裝箱，按重量級別(weight)堆放在堆場的同一貝上，滿足PSCW原則的集裝箱集合為同類箱組。按照這一原則，可以得到相應(yīng)的分配區(qū)域劃分規(guī)則，將同類箱組放在同一區(qū)域。

2)堆垛作業(yè)模式

堆垛作業(yè)模式（以下簡稱模式）指的是，對于街中的任意一個貝的各行，集裝箱堆垛作業(yè)的方向及先后次序。常見的堆垛作業(yè)模式有從小行到大行、從大行到小行、從中間到兩邊，如圖1所示。

3）設(shè)備作業(yè)規(guī)則

設(shè)備作業(yè)規(guī)則（以下簡稱規(guī)則）和設(shè)備的物理及空間作業(yè)特性有關(guān)，它影響到設(shè)備在物理及空間上的作業(yè)能力和對同一貝中不同箱位的作業(yè)順序。通過作業(yè)能力可判斷某種堆場狀態(tài)下設(shè)備能否將集裝箱放入某位置，通過作業(yè)順序則可判斷設(shè)備在當(dāng)前貝中應(yīng)當(dāng)優(yōu)先選擇的位置。堆場作業(yè)設(shè)備有堆場橋式起重機（場橋）、正面吊、叉車等多種，不同類型設(shè)備的作業(yè)能力和作業(yè)順序各不相同，均需對作業(yè)規(guī)則合理定義。

1.2箱位分配作業(yè)知識表示

在以上三類知識中，分配區(qū)域劃分規(guī)則和堆垛作業(yè)模式采用適合于表達(dá)判斷性知識的產(chǎn)生式規(guī)則表示，其形式為

if(前提1)(前提2)…(前提p)then(結(jié)論1)(結(jié)論2)…(結(jié)論q)

例如：if(目的港=天津)(尺寸=20)(箱型=普通干貨箱)then(分配區(qū)域=F01)；if(街代碼=A01)(貝號=1 ) then(作業(yè)模式=從小行到大行)。

設(shè)備作業(yè)規(guī)則可以由設(shè)備作業(yè)模板來表示。若設(shè)備作業(yè)能力最大跨度為m行，最高層為n層，則設(shè)備作業(yè)規(guī)則可由一個m×n的矩陣Omn來反映，這個矩陣就是作業(yè)模板。其中m和n定義了設(shè)備的作業(yè)能力。矩陣中存放1，2，…，m×n的自然數(shù)，它定義了設(shè)備對貝中各個箱位的作業(yè)順序。圖2列舉了m=3，n=4時，場橋的作業(yè)模板O34示意圖，包括垂直作業(yè)、水平作業(yè)和混合作業(yè)。

設(shè)備作業(yè)模板在形式上為一個矩陣，但本質(zhì)上表達(dá)的是設(shè)備作業(yè)所遵循的規(guī)則。若用產(chǎn)生式規(guī)則[6]來表示模板所表達(dá)的知識，相當(dāng)于如下語句：

2基于知識的箱位分配模型

2.1模型原理

對于任意一個集裝箱，其箱位分配的過程可看做按上述知識和規(guī)則運作的許多判斷活動的集合[7]，每經(jīng)過一個（或一組）判斷，可選擇箱位的范圍就相應(yīng)減少，將最終選出的集裝箱位置作為最優(yōu)位置分配給集裝箱。設(shè)問題的狀態(tài)空間為U〈S，F(xiàn)，P，C〉。其中：S為堆場狀態(tài)集合；F為作業(yè)設(shè)備集合；P為計劃分配的箱位集合；C為待分配的集裝箱。

設(shè)最初狀態(tài)空間為U0〈S0，F(xiàn)0，P0，C〉。其中：S0代表整個堆場的堆放狀態(tài)；F0代表不確定的作業(yè)設(shè)備；P0代表整個堆場中的箱位。箱位分配模型如圖3所示。

a)分配區(qū)域劃分。通過分配區(qū)域劃分規(guī)則判斷，將待分配集裝箱的箱位選擇范圍從整個堆場縮小至規(guī)則定義的某一區(qū)域。狀態(tài)空間更新為U1〈S1，F(xiàn)1，P1，C〉。其中：S1代表分配區(qū)域堆場狀態(tài)；F1代表分配區(qū)域的作業(yè)設(shè)備；P1代表分配區(qū)域中的箱位集合。

b)模式及規(guī)則匹配。將堆垛作業(yè)模式、設(shè)備作業(yè)規(guī)則和堆場狀態(tài)相匹配，排除不滿足堆垛作業(yè)模式和設(shè)備不可作業(yè)的位置，狀態(tài)空間更新為U2〈S1，F(xiàn)1，P2，C〉。其中：P2代表分配區(qū)域中符合分配條件的箱位集合。

c)最優(yōu)箱位選擇。從P2中選擇最優(yōu)箱位，狀態(tài)空間更新為U3〈S1，F(xiàn)1，P3，C〉。其中：P3代表最終選定的最優(yōu)箱位。

2.2分配區(qū)域劃分

分配區(qū)域的劃分過程如圖4所示。

a)進行出口箱區(qū)域劃分。分配區(qū)域的劃分通過匹配待分配集裝箱的PSCW屬性和分配區(qū)域劃分規(guī)則實現(xiàn)，規(guī)則匹配可由式（1）表示。

A=f(C，R)(1)

其中:f是規(guī)則匹配函數(shù);A是分配區(qū)域;R是規(guī)則集;C是集裝箱屬性集。

b)每個分配區(qū)域由若干個計劃貝組成，通過B=g(A)確定。其中:g是計劃貝的定義函數(shù)；B為計劃貝集合。計劃貝的堆垛作業(yè)模式、貝中的箱位是否放有集裝箱可由堆場狀態(tài)S1表示，區(qū)域中的所有箱位由箱位集合P1表示。

c)港口的堆場管理可根據(jù)現(xiàn)場情況，為區(qū)域調(diào)度作業(yè)設(shè)備，設(shè)調(diào)度函數(shù)為F=h(A)。其中：F是調(diào)度的作業(yè)設(shè)備；設(shè)備的作業(yè)模板和位置由F1確定。

經(jīng)過以上步驟之后，問題狀態(tài)空間表示為U1〈S1，F(xiàn)1，P1，C〉，模式及規(guī)則匹配的初始條件被確定下來。

2.3模式及規(guī)則匹配

模式及規(guī)則匹配過程在方向上遵循堆垛作業(yè)模式，在作業(yè)順序上按照設(shè)備作業(yè)模板執(zhí)行。本文以圖1(a)的“從小行到大行”的作業(yè)模式和圖2(c)的“混合作業(yè)”模板為例，說明匹配方法。

a)模板最小序號所在行和作業(yè)起始行對齊（圖5(a)）。若該行已放滿箱，模板右移一行(b)，直到模板最小序號所在行沒有放滿箱，匹配成功(c)。模板中的所有位置被賦予相應(yīng)的作業(yè)順序號，如(c)所示，模板區(qū)域內(nèi)的所有箱位均帶有1~12的作業(yè)順序號。

b)根據(jù)堆場狀態(tài)和設(shè)備作業(yè)能力，選出可以分配的箱位，如圖5(c)中順序號為4、6、8的箱位。

堆垛作業(yè)模式為“從大行到小行”下的模板匹配，則將模板對稱翻轉(zhuǎn)，從貝的最大行開始，按類似于“從小行到大行”的匹配方法進行。“從中間到兩邊”的模板匹配時，其原理相同，中間的作業(yè)起始行往小行方向一側(cè)按“從大行到小行”模式匹配；另一側(cè)按“從小行到大行”模式匹配。

2.4最優(yōu)箱位選擇

模式及規(guī)則匹配后，得到分配區(qū)域中符合分配條件的箱位集合P2，還需要從P2中挑選一個最優(yōu)箱位作為最終為集裝箱分配的箱位。最優(yōu)箱位選擇的依據(jù)有兩個：集裝箱的堆放盡量按設(shè)備作業(yè)模板順序進行；集裝箱的擺放滿足重量等級要求，即符合重箱壓輕箱，或者輕箱壓重箱的原則。

由此，最優(yōu)箱位的選擇按以下三個步驟執(zhí)行：

a)按作業(yè)模板序號排序。由模式和規(guī)則匹配可知：匹配得到的箱位，同一貝中每行至多一個（圖5(c)中序號為4、6、8的箱位分布在不同的行中）。對于一個m行的模板，可以將匹配得到的箱位分成m+1個等級。其中：1~m個等級在模板范圍之內(nèi)，按序號從小到大排列；第m+1個等級為模板范圍之外的符合分配條件的箱位。

b)重量等級判斷。出口箱的箱位分配需要按照重量等級要求進行，如重箱壓輕箱或者輕箱壓重箱的原則。設(shè)待分配箱位的集裝箱的重量等級為w0;位于P2中的箱位pij下方的集裝箱重量等級為wij;重量等級規(guī)則函數(shù)為f(w0， wij)。若f(w0， wij)值為true，則pij滿足重量等級要求，否則不滿足。

3實例分析

本文提出的基于知識的集裝箱箱位分配方法，以C++為開發(fā)語言，采用基于COM組件的方法實現(xiàn)，嵌入在某集裝箱堆場大門作業(yè)管理系統(tǒng)中。

集裝箱隨機到達(dá)港口，限于篇幅，本例只對具有相同PSCW屬性的集裝箱進行分析。設(shè)到達(dá)集裝箱的數(shù)量為30，其重量等級服從均勻分布U(1，3)，具有屬性：目的港為天津、尺寸為20尺、箱型是普通干貨箱。設(shè)集裝箱箱號為Ti（i表示集裝箱的到達(dá)順序），并存在以下分配區(qū)域劃分規(guī)則：

if (目的港=天津)(尺寸=20) (箱型=普通干貨箱)then(分配區(qū)域=F01)

該批集裝箱分配區(qū)域在F01，假設(shè)該區(qū)域有A01005、A02007兩個貝，最初沒有放任何集裝箱。堆垛模式及貝定義如表1所示。

這里以最后一個箱T30為例說明按照箱位分配模型所述步驟的最優(yōu)箱位選取過程：

a)當(dāng)T30到達(dá)后，根據(jù)分配區(qū)域劃分規(guī)則，將T30 劃入F01區(qū)域；此時，問題的狀態(tài)空間為U1〈S1，F(xiàn)1，P1，C〉。它們的具體含義如下：S1為表1所列貝定義及堆垛模式，計劃貝中各個位置；F1為場橋，當(dāng)前位置為A02007，作業(yè)模板；P1為A01005貝、A02007貝中的所有箱位；C為T30。

b)用圖2(c)所示的混合作業(yè)模板匹配A01005貝和A02007貝，問題的狀態(tài)空間更新為U2〈S1，F(xiàn)1，P2，C〉。其中：S1、F1和C含義不變；P2={(A01005，5，1)， (A01005，3，4)， (A01005，4，3)，（A02007，1，1)，(A02007，2，3)，(A02007，3，3)}。

c)各個位置的評價結(jié)果如表2所示。

通過該方法將堆場的管理規(guī)則作為箱位分配的依據(jù)，充分利用箱位分配作業(yè)知識。所產(chǎn)生的堆垛符合重量等級要求，方便后續(xù)裝船作業(yè)，同時考慮了設(shè)備的移動距離，減少了作業(yè)成本。

4結(jié)束語

本文通過分析集裝箱箱位分配作業(yè)的規(guī)則，說明采用基于知識的方法的必要性，并構(gòu)建了基于知識的箱位分配模型。實例結(jié)果表明，用該方法進行的箱位分配計劃有利于堆場的后續(xù)作業(yè)，并可減少設(shè)備作業(yè)的移動距離。

參考文獻：

［1］DAVIES A. BISCHOFF P， EBERHARD E. Weight distribution considerations in container loading [J].European Journal of Operational Research， 1999，114 (3):509-528.

［2］KIMK H， PARK Y M，RYUK R. Deriving decision rules to locate export containers in container yards [J].European Journal of Operational Research， 2000， 124(1):89-101.

［3］KIM K H， BAE J W. Remarshaling export containers in port container terminals [J].Computers and Industrial Engineering， 1998， 35(3-4):655-658.

［4］郝聚民，紀(jì)卓尚，林焰.混合順序作業(yè)堆場BAY優(yōu)化模型[J]. 大連理工大學(xué)學(xué)報， 2000，40(1):102-105.

［5］趙莉香，殷國富，陳田.基于知識的平面組合體ＣＡＩ二求三系統(tǒng)研究與開發(fā)[J]. 計算機應(yīng)用研究， 2003，20(4):67-69.

［6］楊小獻，趙云娣，謝自美.基于規(guī)則的柔性綜合統(tǒng)計報表技術(shù)[J].計算機應(yīng)用研究， 2005，22(12):54-56.

［7］田鋒，李人厚.基于知識的協(xié)同設(shè)計工作過程建模[J].計算機應(yīng)用研究， 2003，20(7):10-12，48.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”