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

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

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

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

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

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

0 引 言

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

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

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

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

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

2 出口集裝箱空間資源配置問題

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

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

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

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

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

限制1 出口集裝箱的堆放位置與將對于船?？康牟次坏木嚯x小于指定的最大限制要求。這個約束對減少集裝箱在堆場與碼頭前沿的運輸距離是必要的。

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例實驗

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

4.1 算例實驗輸入數(shù)據(jù)

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

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

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

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

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

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

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

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

4.3 驗證兩個賦值順序策略

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

4.4 驗證多種限制條件的順序策略

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

5 結(jié) 論

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

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)新行動項目，項目編號：08170511300。

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