混堆模式下集裝箱堆場箱區(qū)指派優(yōu)化方法＊

鄭紅星 王曉薇 董 鍵 周汀洋

（大連海事大學(xué)交通運(yùn)輸管理學(xué)院 大連 116026）

集裝箱堆場空間資源的調(diào)度直接影響碼頭前沿和堆場內(nèi)裝卸資源的作業(yè)效率，以及裝卸設(shè)備的作業(yè)成本.P.Peter等［1］以船舶停港時間最短為目標(biāo)，建立了集裝箱堆場最優(yōu)堆存方案的混合整數(shù)線性規(guī)劃模型.Chen等［2］對集裝箱堆場空間分配問題進(jìn)行研究，提出一種混合算法進(jìn)行求解.Zhang［3］通過建立線性整數(shù)規(guī)劃模型對堆場空間進(jìn)行分配，得到分配到各箱區(qū)的集裝箱數(shù)量.徐德磊［4］等根據(jù)箱區(qū)容量建立了集裝箱運(yùn)輸最短路徑的集裝箱堆存分派模型.王斌［5－6］研究了混堆模式下堆場空間分配問題，并分別以平衡箱區(qū)箱量和最小化集卡行駛距離為目標(biāo)，建立了兩階段決策模型；陶經(jīng)輝等［7］提出了兩階段模型，并運(yùn)用啟發(fā)式算法進(jìn)行求解；徐亞等［8］建立了多目標(biāo)規(guī)劃模型，并提出了一種改進(jìn)的線性功效系數(shù)法進(jìn)行求解.本文考慮到作業(yè)效率與堆存策略之間的聯(lián)系，以及堆場作業(yè)的連續(xù)性和動態(tài)變化性，建立堆場箱區(qū)資源均衡調(diào)度模型，合理分配各箱區(qū)的作業(yè)量.

1 箱區(qū)間資源均衡優(yōu)化模型

1.1 問題描述

堆場中的集裝箱按其狀態(tài)，可分為5種類型：進(jìn)口箱（discharge），簡稱D型箱，指尚在船上等待卸船的進(jìn)口箱，被內(nèi)部集卡運(yùn)到堆場堆存；出口箱（loading），簡稱L型箱，指已在堆場上等待裝船的出口箱，被內(nèi)部集卡運(yùn)到岸橋邊裝船；中轉(zhuǎn)箱（transhipment），簡稱T型箱，指尚在某船上等待卸船被內(nèi)部集卡運(yùn)進(jìn)堆場后，或者已經(jīng)被運(yùn)進(jìn)堆場，等待內(nèi)部集卡運(yùn)到另一船出口的集裝箱；提箱（pickup），簡稱P型箱，指已經(jīng)在堆場，等待外部集卡提走的進(jìn)口箱；進(jìn)箱（sending），簡稱S型箱，指尚未分配到堆場的出口箱，等待被外部集卡運(yùn)進(jìn)堆場堆存.當(dāng)D型箱堆存到堆場后就變?yōu)镻型箱，S型箱進(jìn)入堆場后就變?yōu)長型箱.其中，T型箱在進(jìn)出口碼頭作業(yè)中，其所占的比例較低，而且一般將該箱型單獨(dú)存放在一個箱區(qū)，文中對此種箱型不作考慮.因此，堆場箱型可簡化分成上述4種類型，基于這4種類型的集裝箱數(shù)量來對堆場空間資源進(jìn)行分配.

由于集裝箱碼頭通常是24h連續(xù)作業(yè)，一般采用滾動模式安排作業(yè)調(diào)度計劃.運(yùn)用滾動計劃模式需要一個固定時段作為計劃期，在計劃期內(nèi)按照更新信息進(jìn)行計劃安排，考慮到大多數(shù)碼頭的作業(yè)情況，本文以3d為一個計劃期，以12h為一個計劃時段，每天分為2個時段，則3d劃分為6個時段.每次決策一個計劃期內(nèi)堆場空間資源調(diào)度情況，在這3d的計劃期中，初始時，只實(shí)施第1d的調(diào)度計劃，后2d的調(diào)度計劃編入到下一個計劃期，在下一個計劃期內(nèi)重新制定計劃，以此類推.集裝箱碼頭滾動計劃模式見圖1.

圖1 集裝箱碼頭滾動計劃模式圖

本文擬建立混堆模式下堆場箱區(qū)間作業(yè)量均衡優(yōu)化模型，合理調(diào)配各箱區(qū)中4種箱型的作業(yè)量，使各箱區(qū)的作業(yè)量處于均衡狀態(tài)，從一定程度上提高裝卸設(shè)備的作業(yè)效率.

1.2 模型的建立

1.2.1 模型的假設(shè)條件 根據(jù)碼頭實(shí)際作業(yè)狀況，對部分指標(biāo)或作業(yè)標(biāo)準(zhǔn)建立合理假設(shè)：（1）計劃期內(nèi)，按照班輪作業(yè)計劃，船舶靠離泊位的時間為已知；（2）計劃期內(nèi)，各船舶及港口出口集裝箱箱型、箱量、集裝箱重量等級為已知；（3）計劃期內(nèi)，堆場后方陸側(cè)系統(tǒng)作業(yè)的出口箱運(yùn)入堆場數(shù)量、進(jìn)口箱的提箱數(shù)量及其作業(yè)時間為已知（可根據(jù)歷史統(tǒng)計數(shù)據(jù)得到）；（4）為了簡化模型，設(shè)定集裝箱堆場集裝箱型都為TEU標(biāo)準(zhǔn).

1.2.2 模型的符號說明 M為堆場中的箱區(qū)總數(shù)；T為一個計劃期內(nèi)的總時段數(shù)；i為堆場中的箱區(qū)編號（i∈［1，M］）；t為一個計劃周期內(nèi)第t個計劃時段（t∈［1，T］）；Ci為箱區(qū)i的堆存容量；Dit為計劃時段t內(nèi)卸到箱區(qū)i中的D型箱量；為計劃時段t內(nèi)卸到箱區(qū)i中，在計劃期外被客戶提走的D型箱量；Dith為計劃時段t內(nèi)卸到箱區(qū)i中，在計劃期內(nèi)的h時段被客戶提走的D型箱量（h∈［t，T］）；Lit為計劃時段t內(nèi)從箱區(qū)i提上船的L型箱量；為計劃期開始時已經(jīng)在堆場的箱區(qū)i中，在計劃時段t內(nèi)提上船的L型箱量；Ligt為計劃時段g內(nèi)到港分配到箱區(qū)i中，在計劃時段t內(nèi)提上船的L型箱量（g∈［1，t］）；Sit為計劃時段t內(nèi)到港分配到箱區(qū)i中的S型箱量；~Sit為計劃時段t內(nèi)到港分配到箱區(qū)i中，在計劃期外提上船的S型箱量；Sitk為計劃時段t內(nèi)到港分配到箱區(qū)i中，在計劃時段k內(nèi)提上船的S型箱量（k∈［t，T］）；Pit為計劃時段t內(nèi)被客戶從箱區(qū)i中提走的P型箱量；為計劃期開始時已經(jīng)在堆場的箱區(qū)i中，在計劃時段t內(nèi)被客戶提走的P型箱量；Pilt為在計劃時段l內(nèi)卸到箱區(qū)i中，在計劃時段t被客戶提走的P型箱量（l∈［1，t］）；Vi0為計劃時段開始時堆存在箱區(qū)i中的箱量；Vit為計劃時段t結(jié)束時堆存在箱區(qū)i中箱量.

1.2.3 目標(biāo)函數(shù) 多目標(biāo)資源均衡優(yōu)化模型的目標(biāo)函數(shù)為：min［μ1·f1＋μ2·f2］.式中：μ1為船舶裝卸計劃在各箱區(qū)作業(yè)量的均衡權(quán)重系數(shù)；μ2為整個堆場箱區(qū)作業(yè)量均衡權(quán)重系數(shù)，μ1＋μ2＝1.

目標(biāo)函數(shù)1：船舶裝卸計劃在各箱區(qū)作業(yè)總量均衡.該目標(biāo)可轉(zhuǎn)化為在計劃期內(nèi)，船舶在各箱區(qū)i作業(yè)量的平均差為最小，即

目標(biāo)函數(shù)2：整個集裝箱堆場箱區(qū)作業(yè)總量均衡.該目標(biāo)可轉(zhuǎn)化為在計劃期內(nèi)，碼頭堆場的全部箱區(qū)中，各箱區(qū)作業(yè)量的平均差為最小，即

1.2.4 約束條件

式中：Dit，Lit，Pit，Sit，Vit，i，t，h，g，k，l均為非負(fù)整數(shù).

約束（3）保證計劃時段t內(nèi)卸到箱區(qū)i中的D型箱總量等于計劃時段t內(nèi)卸到箱區(qū)i中，在計劃期外被客戶提走的D型箱量與在計劃期內(nèi)被客戶提走的D型箱總量之和；約束（4）保證計劃時段t內(nèi)從箱區(qū)i提上船的L型箱量，等于計劃期開始時已經(jīng)在堆場上的箱區(qū)i中t時段被提上船的L型箱量與計劃時段g內(nèi)到港分配到箱區(qū)i中，在計劃時段t被提上船的L型箱量之和；約束（5）保證計劃時段t內(nèi)到港分配到箱區(qū)i中的S型箱總量等于計劃時段t內(nèi)到港分配到箱區(qū)i中，在計劃期外被提上船的S型箱量與在計劃期內(nèi)被提上船的S型箱總量之和；約束（6）保證計劃時段t內(nèi)被客戶從箱區(qū)i中提走的P型箱量，等于計劃期開始時已經(jīng)在堆場上的箱區(qū)i中，在t時段被客戶提走的P型箱量與各船舶在計劃時段l內(nèi)卸到箱區(qū)i中，在t時段被港外客戶提走的P型箱量之和；約束（7）表示箱區(qū)前后時段堆存數(shù)量的關(guān)系；約束（8）保證計劃期內(nèi)各箱區(qū)集裝箱總量不能超過其堆存容量；約束（9）、（10）表示2箱型之間的關(guān)系；約束（11）保證各決策變量均為非負(fù)整數(shù).

2 模型的求解

2.1 解的形式

模型中的決策變量為：計劃時段t內(nèi)卸到箱區(qū)i中，計劃期外被提走的D型箱總量~Dit；計劃時段t內(nèi)卸到箱區(qū)i中，計劃時段內(nèi)被提走的D型箱總量；計劃時段t內(nèi)送到箱區(qū)i中，計劃期外被提上船的S型箱總量~Sit；計劃時段t內(nèi)送到箱區(qū)中，計劃時段內(nèi)被提上船的S型箱總量.以上述決策變量為行，以所有箱區(qū)編號i（i＝1，2，…，10）為列，構(gòu)造各個時段t（i＝1，2，…，6）對應(yīng)下的解矩陣 Ax（x 為矩陣的編號），矩陣Ax為解的表現(xiàn)形式.

2.2 初始解的產(chǎn)生步驟

步驟2 i＝1，轉(zhuǎn)步驟3.

步驟5 i＝i＋1，判斷i的值，如果i＞M 轉(zhuǎn)步驟6；否則轉(zhuǎn)步驟3.

步驟6 t＝t＋1，判斷t的值，如果t＞6解的生成結(jié)束；否則轉(zhuǎn)步驟2.

2.3 新解的產(chǎn)生步驟

步驟1 獲取當(dāng)前解Ax，轉(zhuǎn)步驟2.

步驟2 t＝1，轉(zhuǎn)步驟3.

步驟4 t＝t＋1，判斷t的值，如果t＞6，則新解生成結(jié)束；否則，轉(zhuǎn)步驟3，繼續(xù)循環(huán).

2.4 適應(yīng)度函數(shù)

以堆場箱區(qū)間空間資源調(diào)度模型的目標(biāo)函數(shù)，作為算法的適應(yīng)度函數(shù)：E（Ax）＝式中：μ1，μ2的值根據(jù)港口具體情況而定.

2.5 接受準(zhǔn)則

按照模擬退火算法的原理，新解被接受的概率Cx1x2為

2.6 終止條件

循環(huán)終止條件為達(dá)到預(yù)定溫度，當(dāng)算法達(dá)到預(yù)定的溫度時，當(dāng)前解即為模型的優(yōu)化解.

3 實(shí)例分析

3.1 初始數(shù)據(jù)

本案例來源于某港口實(shí)際運(yùn)營數(shù)據(jù)，經(jīng)簡化處理后有2個泊位，堆場箱區(qū)總數(shù)Z＝10，每個箱區(qū)共15個貝位，每個貝位分6排；最多堆垛層高為4層，其中第一排最大堆垛層高為2層，第二排最大堆垛層高為3層，每個箱區(qū)存儲容量Ci＝315TEU.

某計劃期內(nèi)到港船舶數(shù)J＝3（艘），每艘船載箱量為200TEU.船舶1在t＝1時段開始卸船，在t＝3時段開始裝船；船舶2在t＝2時段開始卸船，在t＝4時段開始裝船；船舶3在t＝4時段開始卸船，在t＝6時段開始裝船.根據(jù)港口實(shí)際情況，船舶作業(yè)箱量在各箱區(qū)作業(yè)量均衡權(quán)重系數(shù)μ1＝0.7.本模型計劃期為3d，時段總數(shù)T＝6.

表1 的值

表1 的值

?

表2 初始計劃時段各箱區(qū)箱量Vi0

表3 的值

表3 的值

?

3.2 優(yōu)化結(jié)果與分析

利用本研究建立的箱區(qū)間資源均衡優(yōu)化模型的模擬退火算法，采用MATLAB語言進(jìn)行編程，運(yùn)用 Window7操作系統(tǒng)的Pentium（R）T4200處理器的PC機(jī)進(jìn)行運(yùn)算.

主要參數(shù)設(shè)置：初始溫度t0＝97，預(yù)訂溫度tf＝3，馬爾科夫鏈長度為500，降溫系數(shù)為0.94；矩陣DS各行從上到下依次為的值；矩陣L0表示的值；矩陣L表示的值；矩陣P0表示的值；矩陣P表示的值；矩陣ini＿vol表示計劃初始時段各箱區(qū)的箱量.利用上述等參數(shù)來控制程序運(yùn)算，目標(biāo)函數(shù)值趨向收斂，目標(biāo)函數(shù)收斂圖見圖2，各箱型在各時段分配到各箱區(qū)的箱量見表4，得出總的均衡偏差目標(biāo)值為273.24TEU.

從求解結(jié)果可以看出，運(yùn)用本文建立模型來均衡堆場的箱區(qū)資源，優(yōu)化效果顯著.該模型不僅平衡了船舶在各箱區(qū)中的作業(yè)量，提高了堆場對船舶作業(yè)的服務(wù)效率，降低了船舶的在港時間，而且平衡了整個堆場箱區(qū)間的作業(yè)量，提高了裝卸設(shè)備的作業(yè)效率，進(jìn)而實(shí)現(xiàn)了集裝箱箱區(qū)內(nèi)空間資源的優(yōu)化.

圖2 標(biāo)函數(shù)收斂圖

4 結(jié)束語

在滾動計劃的基礎(chǔ)上，以提高堆場空間資源的利用率和裝卸設(shè)備資源的作業(yè)效率為目標(biāo)，建立了基于混堆模式的箱區(qū)間作業(yè)量均衡優(yōu)化模型，并采用模擬退火算法進(jìn)行求解.通過實(shí)際的案例分析，驗證了模型及算法的有效性，結(jié)果顯示該模型能夠提高堆場空間資源的利用率.隨著研究內(nèi)容的深入，仍需進(jìn)一步考慮如何確定每艘船舶分配到各個箱區(qū)貝位中的裝卸箱量，從而縮短船舶在港時間，提高集裝箱碼頭的服務(wù)效率.

表4 各箱型在各時段分配到各箱區(qū)的箱量

［1］PRESTON P，KOZAN E.An approach to determine storage location of containers at seaport terminals［J］.Computers ＆ Operations Research，2001，28：983－995.

［2］CHEN P，F(xiàn)U Zhaohui，LIM A.The yard allocation problem［C］.Eighteenth National Conference on Artificial Intelligence，2002：56－65.

［3］ZHANG Chuqian，LIU Jiyin，WAN Yatwah.Storage space allocation in container terminals［J］.Transportation Research Part B，2003，37：883－903.

［4］徐德磊，韓曉龍，梁成姬.基于堆存能力的集卡優(yōu)化分派研究［J］.武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版，2011，35（9）：77－81.

［5］王 斌.集裝箱堆場基于混堆的滾動式計劃堆存方法［J］.系統(tǒng)工程學(xué)報，2005，20（5）：466－471.

［6］王 斌.集裝箱碼頭堆場的一種動態(tài)隨機(jī)堆存方法［J］.系統(tǒng)工程理論與實(shí)踐，2007，27（4）：147－153.

［7］陶經(jīng)輝，汪 敏.基于混堆模式的集裝箱堆場區(qū)段分配［J］.系統(tǒng)工程理論與實(shí)踐，2009，29（8）：185－192.

［8］徐 亞，陳秋雙，龍 磊，等.基于多目標(biāo)規(guī)劃的堆場空間分配問題研究［J］.系統(tǒng)工程學(xué)報，2009，24（3）：365－369.