基于知識(shí)的集裝箱堆場(chǎng)箱位分配計(jì)劃研究

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

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

中圖分類(lèi)號(hào)：TP391

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

文章編號(hào)：1001-3695（2007）09-0146-03

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2基于知識(shí)的箱位分配模型

2.1模型原理

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

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

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

b)模式及規(guī)則匹配。將堆垛作業(yè)模式、設(shè)備作業(yè)規(guī)則和堆場(chǎng)狀態(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ū)域的劃分過(guò)程如圖4所示。

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

A=f(C，R)(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3實(shí)例分析

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

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

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

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

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

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

b)用圖2(c)所示的混合作業(yè)模板匹配A01005貝和A02007貝，問(wèn)題的狀態(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)各個(gè)位置的評(píng)價(jià)結(jié)果如表2所示。

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

4結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［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è)堆場(chǎng)BAY優(yōu)化模型[J]. 大連理工大學(xué)學(xué)報(bào)， 2000，40(1):102-105.

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

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

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

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