胡碧琴， 江 偉 （上海海事大學(xué)，上海 200135）

基于限制條件的港口集裝箱碼頭出口集裝箱堆存定位研究

胡碧琴， 江 偉 （上海海事大學(xué)，上海 200135）

采用限制條件滿(mǎn)足的方式，對(duì)出口集裝箱的堆存空間進(jìn)行配置。出口集裝箱堆場(chǎng)空間位置預(yù)分配可以提高集裝箱裝船效率。以?xún)?nèi)集卡和場(chǎng)吊效率最大化為目標(biāo)，根據(jù)實(shí)際集裝箱碼頭的堆存操作，提出相關(guān)限制條件。最后用實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證該方法的效果。

CPS；出口集裝箱；空間配置

0 引 言

集裝箱碼頭操作主要由卸箱操作 （進(jìn)口集裝箱從到港船卸下）、裝箱操作 （出口集裝箱裝上離港船）、發(fā)箱操作 （從堆場(chǎng)提取進(jìn)口集裝箱）、收箱操作 （出口集裝箱進(jìn)入堆場(chǎng)）。裝箱操作和卸箱操作被統(tǒng)一稱(chēng)作 “ship operation”，以?xún)?yōu)化服務(wù)水平為目標(biāo)，通過(guò)加快 “ship operation”速度以減少集裝箱船舶在港逗留時(shí)間和外集卡逗留時(shí)間。圖1是集裝箱堆場(chǎng)圖，集裝箱碼頭的出口集裝箱裝箱操作由裝箱計(jì)劃員在船舶到港前安排就緒。船公司在裝船前幾天告知碼頭公司船舶記載圖，在記載圖上，每個(gè)slot根據(jù)重量、目的地、集裝箱型號(hào)安排同類(lèi)集裝箱。由于船舶中的每個(gè)位置區(qū)域都會(huì)被指定堆放一類(lèi)集裝箱，堆場(chǎng)以滿(mǎn)足最快裝船為目標(biāo)合理安排集裝箱堆存區(qū)域和位置，形成最優(yōu)裝箱順序表。裝船計(jì)劃者在對(duì)集裝箱進(jìn)行排序時(shí)，通常試圖最小化橋吊和場(chǎng)吊時(shí)間。決策制定的過(guò)程被稱(chēng)為堆場(chǎng)順序圖，出口集裝箱在堆場(chǎng)中的位置是否合理直接決定著裝箱順序是否有效。本文主要的是以最大化裝船效率為目標(biāo)提出有效地出口集裝箱堆場(chǎng)空間提前合理配置的方法。

為得到有效地裝箱順序，在堆場(chǎng)空間配置計(jì)劃過(guò)程中必須通過(guò)考慮以下內(nèi)容。圖2展示的是集裝箱船的平面積載圖，也被稱(chēng)為BAY位圖，圖中顯示集裝箱根據(jù)重量和目的地兩因素分類(lèi)。集裝箱堆場(chǎng)空間計(jì)劃操作中一條普遍原則就是：集裝箱船對(duì)應(yīng)的出口集裝箱被堆放在靠近該船泊位的堆場(chǎng)區(qū)域。此外，另一條堆場(chǎng)空間計(jì)劃的普遍原則是基于堆場(chǎng)操作機(jī)械提出的：舉例來(lái)說(shuō)，不同類(lèi)別的出口集裝箱不應(yīng)該同時(shí)堆放在同一個(gè)yard-bay中。這條原則僅適用非直接轉(zhuǎn)運(yùn)堆場(chǎng)系統(tǒng)，即堆場(chǎng)的主要操作機(jī)械為場(chǎng)吊、跨車(chē)。出口集裝箱的裝船作業(yè)過(guò)程中，同一類(lèi)別的集裝箱應(yīng)就近堆放 （如圖2所示），這樣便于持續(xù)性的裝船作業(yè)。對(duì)于非直接轉(zhuǎn)運(yùn)堆場(chǎng)系統(tǒng)來(lái)講，同一類(lèi)別集裝箱集中堆放，可以減少場(chǎng)吊等機(jī)械的移動(dòng)距離，提高裝卸效率。其他一些堆場(chǎng)計(jì)劃遵循的原則將在下面幾部分進(jìn)行論述。

1 國(guó)內(nèi)外研究現(xiàn)狀

目前對(duì)于集裝箱碼頭的研究較多。Kim[1]提出以翻箱次數(shù)最小為目標(biāo)，決定出口集裝箱的堆存位置。Cao and Uebe[2]提出基于非線性限制條件的運(yùn)輸模型以得到安排堆場(chǎng)空間位置。然而，這些研究都沒(méi)有考慮時(shí)間軸的集裝箱流動(dòng)態(tài)變化因素。Kozan[3]提出用網(wǎng)絡(luò)模型來(lái)描述集裝箱流在集裝箱碼頭的動(dòng)態(tài)情況，這個(gè)模型試圖對(duì)集裝箱流進(jìn)行分類(lèi)，以減小操作成本。Roll and Rosenblatt[4]提出分類(lèi)堆存策略的概念類(lèi)似于集裝箱空間配置問(wèn)題，他們采取的堆存策略類(lèi)似于倉(cāng)庫(kù)的堆存策略。Tsang[5]詳細(xì)描述堆存問(wèn)題中的限制條件。Zhang[6]探討了集裝箱堆場(chǎng)的空間配置問(wèn)題，將空間配置問(wèn)題拆分成兩個(gè)層次，第一層次試圖平衡各BLOCK間的箱量，第二個(gè)層次最小化bay位到船舶的距離。Kim and Park[7]提出多貨物最小成本流程模型來(lái)解決空間配置問(wèn)題，用次級(jí)梯度優(yōu)化技術(shù)解決該問(wèn)題。

目前有關(guān)空間配置問(wèn)題的研究，目標(biāo)函數(shù)定義明確，容易得到可行解，然而在實(shí)際的碼頭操作過(guò)程中，很多復(fù)雜的限制條件需要滿(mǎn)足。因此，找到一個(gè)可行解是十分困難的問(wèn)題。這就是為什么需要將CSP技術(shù)應(yīng)用到集裝箱碼頭空間資源配置的原因。

2 出口集裝箱空間資源配置問(wèn)題

這個(gè)問(wèn)題的前提是空間配置按期進(jìn)行。配置的時(shí)期根據(jù)不確定性和計(jì)算時(shí)間，可能是一天、24小時(shí)，6小時(shí)，由于時(shí)期不一致，我們統(tǒng)一將進(jìn)行空間資源配置的一個(gè)決策期間稱(chēng)為一個(gè) “stage”。對(duì)到達(dá)的出口集裝箱根據(jù)尺寸、船、目的港進(jìn)行分類(lèi)。假設(shè)不同類(lèi)型的集裝箱不堆放在相同的yard-bay中。下一時(shí)期的集裝箱到達(dá)之前堆存空間已經(jīng)被預(yù)先安排。然而，如果下一階段的決策沒(méi)有考慮到堆場(chǎng)未來(lái)會(huì)發(fā)生的變化，將導(dǎo)致很難找到持續(xù)階段的可行解。研究考慮下一階段決策對(duì)未來(lái)階段的影響。在本文中，CPS技術(shù)將應(yīng)用于空間配置研究。

通過(guò)預(yù)測(cè)集裝箱的到達(dá)情況，估計(jì)下一階段和未來(lái)階段的每類(lèi)集裝箱空間需求，一類(lèi)集裝箱的空間需求被稱(chēng)作一個(gè)SDU （Space Demand Unit）。一個(gè)SDU的空間需求量以20英寸一個(gè)BAY或40英寸兩個(gè)BAY為需求單位?；陬A(yù)計(jì)的集裝箱到達(dá)情況，下一階段與未來(lái)階段的SDU數(shù)的空間需求量必須被指定。

其次，空間的供應(yīng)位置必須確定。一個(gè)堆放出口集裝箱的集裝箱堆場(chǎng)通?？煞譃槿舾蓚€(gè)yard-bay。每個(gè)yard-bay包含20～30個(gè)堆放位在跨車(chē)堆場(chǎng)系統(tǒng)或6～7個(gè)堆放位在場(chǎng)吊堆場(chǎng)系統(tǒng)。在本文研究中，一個(gè)yard-bay被認(rèn)為是一個(gè)空間配置單位SAU。圖3說(shuō)明本文空間配置問(wèn)題的概念表示，空間配置為一個(gè)SDU指定1～2個(gè)可用SAU。但是一個(gè)SAU不能指定給多個(gè)SDU。

空間配置問(wèn)題的難點(diǎn)在于空間配置決策的效果評(píng)價(jià)只有當(dāng)裝船操作實(shí)際進(jìn)行時(shí)才可以得知。然而，裝船操作的效率依靠于空間配置和裝船順序。由于出口集裝箱裝船順序也是一個(gè)復(fù)雜的決策問(wèn)題，因此空間配置面臨有較多復(fù)雜的限制條件。

本文探討如何將CSP（constraint satisfaction problem）技術(shù)應(yīng)用于空間配置問(wèn)題。下面將解釋實(shí)際集裝箱港口中采集來(lái)的限制條件，大部分限制條件與制定有效裝船的堆存計(jì)劃所采用的原則有關(guān)。

限制1 出口集裝箱的堆放位置與將對(duì)于船停靠的泊位的距離小于指定的最大限制要求。這個(gè)約束對(duì)減少集裝箱在堆場(chǎng)與碼頭前沿的運(yùn)輸距離是必要的。

限制2 同船集裝箱在不同BLOCK間的最大距離小于制定值。這個(gè)限制條件對(duì)減少場(chǎng)吊的行駛距離是有效的。

限制3 同船集裝箱應(yīng)堆放同一箱區(qū)的同一排位置。這個(gè)限制的提出在于場(chǎng)吊在箱區(qū)的長(zhǎng)度方向容易移動(dòng)，在寬度方向不容易移動(dòng)。限制4 不同船對(duì)應(yīng)的出口集裝箱不能同時(shí)同箱區(qū)進(jìn)行收箱操作。這個(gè)限制條件是防止場(chǎng)吊在同一箱區(qū)堵塞。限制5 箱區(qū)內(nèi)集裝箱對(duì)應(yīng)的不同船總數(shù)不能超過(guò)規(guī)定限制 （NVmax）。這一限制同時(shí)約束了一艘船對(duì)應(yīng)的最大箱區(qū)數(shù)和一個(gè)箱區(qū)內(nèi)堆放的一艘船最小集裝箱數(shù)。

限制6 裝上同一艘船的集裝箱被堆放的箱位總數(shù)不超過(guò)規(guī)定限制 （NBmax）。如果一艘船的集裝箱被堆放在多個(gè)箱區(qū)，堆場(chǎng)機(jī)械的移動(dòng)距離將增加。

限制7 一個(gè)40英尺集裝箱所需要的堆存空間相當(dāng)于兩個(gè)20英尺集裝箱所需要的堆存空間。除了上述限制條件，在不大幅度修改搜索算法的基礎(chǔ)上，研究將考慮其他限制因素。

3 堆存空間配置中CSP技術(shù)的應(yīng)用

圖4說(shuō)明空間配置問(wèn)題的開(kāi)發(fā)程序結(jié)構(gòu)。如圖所示，這個(gè)系統(tǒng)由中間層、限制說(shuō)明層、搜索層。在中間層，將對(duì)變量進(jìn)行定義。對(duì)于堆場(chǎng)空間配置問(wèn)題，SDU對(duì)應(yīng)的變量，為每個(gè)SDU安排的SAU也適用于這些變量。限制說(shuō)明層，限制條件將以等式的形式在程序中體現(xiàn)。變量模型，在指定函數(shù)值的情況下可以被應(yīng)用于解決堆場(chǎng)空間配置模型。

Fig.4 The structure of the program developed for the space allocation

以下將說(shuō)明空間配置研究的搜索程序：

第1步 定義變量和變量范圍，每個(gè)變量的設(shè)定值范圍。

第2步 如果不存在任何變量就停止執(zhí)行程序。否則，選擇下一個(gè)變量執(zhí)行。

第3步 選擇下一個(gè)值，將指定值賦值給變量。如果所有變量都被賦值，那么停止執(zhí)行。否則，進(jìn)入第4步。

第4步 減少問(wèn)題。在這一步，剩余變量所賦予的值沒(méi)有滿(mǎn)足至少一個(gè)限制條件，將會(huì)從變量集合中移除。確定是否變量集合已經(jīng)為空集合。如果是，繼續(xù)執(zhí)行第5步，如果不是，執(zhí)行第2步。

第5步 確定是否還有剩余值4賦給當(dāng)前變量，如果有，繼續(xù)執(zhí)行第3步，如果不是，將當(dāng)前變量轉(zhuǎn)為過(guò)去變量，再繼續(xù)執(zhí)行第3步。

4 算例實(shí)驗(yàn)

算例實(shí)驗(yàn)的目的是驗(yàn)證搜索方法的可行性和有效性，同時(shí)找到最優(yōu)搜索決策。

4.1 算例實(shí)驗(yàn)輸入數(shù)據(jù)

本文采用的算法將應(yīng)用于解決一個(gè)實(shí)際大型集裝箱碼頭——釜山港的空間配置問(wèn)題 （PECT:Pusan Eastern Container Terminal）。對(duì)大量的搜索策略的速度和效果進(jìn)行驗(yàn)證。應(yīng)用的搜索策略所給予的原則是變量順序原則，賦值順序原則和限制條件順序原則。算例的問(wèn)題可分成2個(gè)階段，84個(gè)SDUs變量相當(dāng)于15（vessels）×2（sizes）×3（destination ports），對(duì)應(yīng)于箱區(qū)bay位數(shù)的600個(gè)SAUs值。數(shù)據(jù)來(lái)源于15 vessels and 24 blocks,and 4 berths的實(shí)際集裝箱操作數(shù)據(jù)。第二部分實(shí)驗(yàn)中將考慮所有上述7個(gè)限制條件。限制5和限制6的參數(shù)定義如下：NVmax=3 and NBmax=3。

4.2 驗(yàn)證變量順序策略的實(shí)驗(yàn)和結(jié)果分析

以下3個(gè)標(biāo)準(zhǔn)將用于指定變量：

（1）SDU的時(shí)期：SDU的早期階段優(yōu)于其后期階段； （2）SDU對(duì)應(yīng)集裝箱的尺寸大?。?0英尺集裝箱對(duì)應(yīng)SDU級(jí)別高于20英尺集裝箱對(duì)應(yīng)SDU級(jí)別； （3）SDU對(duì)應(yīng)船：SDU的順序是對(duì)應(yīng)船按時(shí)間順序進(jìn)行先后排列。

通過(guò)這3個(gè)標(biāo)準(zhǔn)的綜合分析，3個(gè)指定變量的規(guī)則設(shè)立如下：

（Rule 1）SDUs的順序根據(jù)計(jì)劃階段進(jìn)行安排； （Rule 2）SDUs的順序根據(jù)集裝箱尺寸進(jìn)行安排； （Rule 3）SDUs的順序首先根據(jù)計(jì)劃階段，其次根據(jù)船的先后順序； （Rule 4）SDUs的順序首先根據(jù)計(jì)劃階段，其次根據(jù)船的先后順序，最后根據(jù)集裝箱尺寸。

SDUs的順序在以上4條規(guī)則下仍無(wú)法區(qū)分的情況下，按隨機(jī)順序。值的排列順序是BAY ID的遞增次序?；?0個(gè)初始分布的集裝箱解決該問(wèn)題。Table1中結(jié)果顯示耗費(fèi)多少CPU時(shí)間找到10個(gè)問(wèn)題的可行解。通過(guò)數(shù)據(jù)測(cè)試，在3個(gè)零值假定下，規(guī)則4的計(jì)算時(shí)間沒(méi)有比由于因置信度為1%而被拒絕的其他3條規(guī)則長(zhǎng)。零值測(cè)試結(jié)果說(shuō)明，規(guī)則4相較于其他規(guī)則計(jì)算時(shí)間較短。

Table 1 The computational time for various variable-ordering rules （in seconds）

4.3 驗(yàn)證兩個(gè)賦值順序策略

按照不同的賦值順序進(jìn)行實(shí)驗(yàn)，規(guī)則3是變量順序策略。兩個(gè)賦值順序策略進(jìn)行相互比較。第一個(gè)規(guī)則是SAU的順序按bay ID的字母表順序，被稱(chēng)作 “bay ID rule”。第二個(gè)規(guī)則是SAU順序是靠近對(duì)應(yīng)船只泊位的bay ID具有優(yōu)先順序，被稱(chēng)作 “closest-to berth rule”。在第一個(gè)實(shí)驗(yàn)中，10個(gè)不同初始分布的集裝箱堆存問(wèn)題的解答結(jié)果如下Table 2所示。通過(guò)數(shù)據(jù)測(cè)試，得出結(jié)論在置信度為1%的情況下， “closest-to berth rule”的計(jì)算時(shí)間優(yōu)于 “bay ID rule”的計(jì)算時(shí)間。

4.4 驗(yàn)證多種限制條件的順序策略

集裝箱空間配置問(wèn)題的可行解必須滿(mǎn)足多種限制條件，搜索過(guò)程中限制條件的逐級(jí)遞推順序極大地影響了計(jì)算時(shí)間，考慮限制1、限制2、限制3、限制6、限制7。假設(shè)NVmax=3 and NBmax=3，變量順序規(guī)則遵循規(guī)則3，賦值順序規(guī)則遵循bay ID規(guī)則，每個(gè)限制條件的順序在10個(gè)不同初始分布的集裝箱問(wèn)題中進(jìn)行實(shí)驗(yàn)。Table 3說(shuō)明不同限制順序的10次不同問(wèn)題的計(jì)算平均時(shí)間，實(shí)驗(yàn)結(jié)果說(shuō)明限制條件的順序極大影響計(jì)算時(shí)間，限制5應(yīng)該在搜索過(guò)程中首先滿(mǎn)足。

5 結(jié) 論

將CSP技術(shù)應(yīng)用于出口集裝箱堆場(chǎng)空間資源配置問(wèn)題。開(kāi)發(fā)基于CSP概念的程序應(yīng)用于出口集裝箱堆場(chǎng)空間資源配置。介紹了出口集裝箱堆場(chǎng)空間資源配置問(wèn)題的限制條件。用來(lái)源于上海洋山港的數(shù)據(jù)，通過(guò)進(jìn)行算例實(shí)驗(yàn)驗(yàn)證所應(yīng)用算法的有效性，比較不同的變量順序規(guī)則的計(jì)算時(shí)間。實(shí)驗(yàn)結(jié)果顯示，空間需求安排的順序依次是階段原則、船舶原則、尺寸原則的情況下計(jì)算時(shí)間最少，同時(shí)也說(shuō)明賦值順序?qū)O大影響計(jì)算時(shí)間。最后，比較搜索過(guò)程不同限制順序，搜索過(guò)程中限制條件順序?qū)O大影響空間配置的計(jì)算時(shí)間。

Table 2 The computational time for two value-ordering rules （in seconds）

Table 3 The computational time for different sequences of constraints

[1] Kim,K.H.,Park,Y.M.,and Ryu,K.R..Deriving Decision Rules to Locate Export Containers in Container Yard[J].European Journal of Operational Research,2000,124:89-101.

[2] Cao,B.and Uebe,G..Solving Transportation Problems with Nonlinear Side Constraints with Tabu Search[J].Computers Ops Res,1995,22(6):593-603.

[3] Kozan,E..Optimizing Container Transfers at Multimodal Terminals[J].Mathematical and Computer Modelling,2000,31:235-243.

[4] Roll,Y.and Rosenblatt,M.J..Random versus Grouped Storage Policies and Their Effect on Warehouse Capacity[J].Material Flow,1983(1):199-205.

[5] Tsang,E..Foundations of Constraint Satisfaction[M].Academic Press Limited,UK,1993.

[6] Zhang,C.,Liu,J.,Wan,Y.-W.,Murty,K.G.and Linn,R.J..Storage Space Allocation in Container Terminals[J].Transportation Research,2003,37B:883-903.

[7] Kim,K.H.and Park,K.T..Dynamic Space Allocation for Temporary Storage[J].International Journal of Systems Science,2003,34:11-20.

Yard Space Allocation for Locating Export Container with Satisfying Constrains

HU Bi-qin,JIANG Wei (Shanghai Maritime University,Shanghai 200135,China)

With satisfying constraints,yard space for export containers is allocated.Yard space is preassigned to improve container loading efficiency.With maximize the efficiency of inter-truck and YC,the paper presents the related constraints according to container terminal yard operation.Finally,testify the effects of the CPS methods with experiment data.

CPS;export container;space allocation

U169.6

A

1002-3100(2010)12-0015-05

2010-10-12

上海市科委創(chuàng)新行動(dòng)項(xiàng)目，項(xiàng)目編號(hào)：08170511300。

胡碧琴（1986-），女，浙江寧波人，上海海事大學(xué)碩士研究生，研究方向：物流管理與工程；江 偉（1985-），男，四川遂寧人，上海海事大學(xué)碩士研究生，研究方向：采購(gòu)與供應(yīng)鏈管理。