集裝箱碼頭裝船順序和場(chǎng)橋行駛路徑聯(lián)合優(yōu)化

郭文文，計(jì)明軍，?；垤`，王清斌

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院，大連116026)

0 引言

集裝箱碼頭作為連接不同運(yùn)輸模式的樞紐節(jié)點(diǎn)，其作業(yè)效率的高低很大程度上取決于堆場(chǎng)的作業(yè)效率.在出口箱裝船作業(yè)過(guò)程中，不合理的場(chǎng)橋行駛路徑和裝船順序會(huì)導(dǎo)致堆場(chǎng)倒箱操作的產(chǎn)生，直接影響了堆場(chǎng)作業(yè)效率.因此，碼頭操作人員需要對(duì)裝船順序和場(chǎng)橋行駛路徑聯(lián)合優(yōu)化，提高堆場(chǎng)作業(yè)效率.

倒箱操作是影響堆場(chǎng)作業(yè)效率的重要因素，眾多學(xué)者研究了確定裝船順序下的堆場(chǎng)倒箱問(wèn)題.Kim等[1-2]考慮了重量因素對(duì)出口箱存儲(chǔ)位置的影響，建立了目標(biāo)為最小期望倒箱量的數(shù)學(xué)模型.Lee等[3]利用鄰域搜索啟發(fā)式方法優(yōu)化了堆場(chǎng)預(yù)翻箱方案.Zhu等[4]提出了更深層次迭代A*算法解決倒箱問(wèn)題.周鵬飛等[5]建立了基于Petri網(wǎng)的翻箱模擬仿真模型及二次翻箱量估計(jì)模型.Ting等[6]提出了定向搜索算法解決堆場(chǎng)倒箱問(wèn)題.此外，關(guān)于倒箱操作，多數(shù)專家從集裝箱所在堆場(chǎng)棧和層的二維角度進(jìn)行研究，比如Petering等[7]、Jin等[8-9]均研究了堆場(chǎng)單個(gè)貝位內(nèi)棧和層對(duì)倒箱量的影響.而場(chǎng)橋作為堆場(chǎng)作業(yè)的主要機(jī)械設(shè)備，部分學(xué)者對(duì)場(chǎng)橋調(diào)度問(wèn)題進(jìn)行研究，但多在確定裝船順序下實(shí)現(xiàn)場(chǎng)橋作業(yè)成本最小或運(yùn)行距離最短的路徑優(yōu)化，比如Vis等[10]研究了單個(gè)街區(qū)內(nèi)兩臺(tái)場(chǎng)橋的調(diào)度問(wèn)題.He等[11]建立了堆場(chǎng)調(diào)度問(wèn)題的動(dòng)態(tài)調(diào)度模型，設(shè)計(jì)混合算法對(duì)特定堆場(chǎng)算例進(jìn)行有效求解.樂(lè)美龍等[12]、Gharehgozli等[13]在已知裝船順序的前提下研究了場(chǎng)橋調(diào)度問(wèn)題.

綜上所述，關(guān)于堆場(chǎng)內(nèi)倒箱操作和場(chǎng)橋作業(yè)的成果，均在確定裝船順序下進(jìn)行研究，并沒(méi)有關(guān)注裝船順序和場(chǎng)橋行駛路徑的相互制約.然而，裝船順序和場(chǎng)橋行駛路徑相互影響且對(duì)倒箱操作影響較大，同時(shí)，集裝箱多堆存于多個(gè)堆場(chǎng)貝位內(nèi).因此，本文從堆場(chǎng)的貝、棧、層三維角度對(duì)裝船順序及場(chǎng)橋行駛路徑聯(lián)合優(yōu)化，對(duì)提高堆場(chǎng)作業(yè)效率具有重要的實(shí)際意義.

1 問(wèn)題描述

出口箱作業(yè)過(guò)程中，場(chǎng)橋根據(jù)船舶配載圖可確定多種裝船順序，如圖1所示，船舶貝位同一層中相同圖案代表的集裝箱可以交換順序完成裝船.圖2為堆場(chǎng)作業(yè)過(guò)程，定義待提集裝箱為目標(biāo)箱，在裝船過(guò)程中，存在多種目標(biāo)箱類型，有些目標(biāo)箱位于堆場(chǎng)貝位某一棧的最高層，場(chǎng)橋可直接將箱提走，有些目標(biāo)箱并未堆放在最高層，定義堆放于目標(biāo)箱之上的箱為阻礙箱，則場(chǎng)橋需將阻礙箱移至同一貝位的其他棧，稱之為倒箱；同時(shí)，如果目標(biāo)箱與上一個(gè)提取箱位于同一貝位內(nèi)，則場(chǎng)橋不必在貝位間移動(dòng)，否則場(chǎng)橋發(fā)生移動(dòng).由圖2可知，不同裝船順序的產(chǎn)生會(huì)導(dǎo)致不同目標(biāo)箱的選擇，進(jìn)而影響場(chǎng)橋行駛路徑，使得倒箱量及場(chǎng)橋作業(yè)時(shí)間不同，反之亦然，不同的場(chǎng)橋行駛路徑可以產(chǎn)生不同的裝船順序.因此，裝船順序和場(chǎng)橋行駛路徑相互影響，為提高碼頭作業(yè)效率，港口應(yīng)對(duì)裝船順序和場(chǎng)橋行駛路徑聯(lián)合優(yōu)化.

本文在已知船舶配載圖和堆場(chǎng)堆存狀態(tài)的前提下，研究出口箱裝船過(guò)程中的裝船順序和場(chǎng)橋行駛路徑問(wèn)題，聯(lián)合優(yōu)化裝船順序及場(chǎng)橋行駛路徑產(chǎn)生的倒箱量，將倒箱量用場(chǎng)橋作業(yè)時(shí)間衡量，建立以最短作業(yè)時(shí)間為目標(biāo)的聯(lián)合優(yōu)化模型，并設(shè)計(jì)均衡倒箱量及場(chǎng)橋作業(yè)時(shí)間的啟發(fā)式算法對(duì)其求解，尋求最短的作業(yè)時(shí)間從而提高堆場(chǎng)作業(yè)效率.

圖1 碼頭俯視圖Fig.1 Terminal planform

圖2 堆場(chǎng)作業(yè)過(guò)程Fig.2 Yard operation

2 數(shù)學(xué)模型

2.1 模型假設(shè)

(1)集裝箱堆存狀態(tài)和船舶配載圖已知；

(2)堆存貝位內(nèi)只允許堆存相同尺寸的集裝箱，倒箱僅發(fā)生在堆場(chǎng)同一貝位內(nèi)；

(3)場(chǎng)橋在堆場(chǎng)中的作業(yè)是勻速的；

(4)集卡的數(shù)量相對(duì)充足，滿足場(chǎng)橋的作業(yè)需求，不存在等待問(wèn)題，即集卡不是制約性因素.

2.2 模型符號(hào)與決策變量

(2)過(guò)程變量.

(3)決策變量.

2.3 模型建立

根據(jù)目標(biāo)箱位于堆場(chǎng)棧的位置，分為4類：目標(biāo)箱上無(wú)阻礙箱、目標(biāo)箱上存在1個(gè)阻礙箱、存在2個(gè)阻礙箱及3個(gè)阻礙箱.當(dāng)目標(biāo)箱上存在3個(gè)阻礙箱時(shí)，目標(biāo)箱的提取會(huì)極大地增加場(chǎng)橋的作業(yè)時(shí)間及堆場(chǎng)倒箱量，因此，本文避免了這一類目標(biāo)箱的提取，只考慮直提箱、存在1個(gè)阻礙箱及2個(gè)阻礙箱的3類目標(biāo)箱的提取，分別計(jì)算其提取過(guò)程中的場(chǎng)橋作業(yè)時(shí)間.

當(dāng)目標(biāo)箱ks上無(wú)阻礙箱時(shí)，提箱過(guò)程如圖3所示，場(chǎng)橋作業(yè)時(shí)間tks為

圖3 直提箱提取過(guò)程Fig.3 Loading process without rehandles

當(dāng)目標(biāo)箱ks上存在1個(gè)阻礙箱is時(shí)，場(chǎng)橋?qū)s翻倒至落箱位js上，提箱過(guò)程如圖4所示，場(chǎng)橋作業(yè)時(shí)間為

當(dāng)目標(biāo)箱ks上存在2個(gè)阻礙箱is和ps時(shí)，場(chǎng)橋先將ps翻倒至落箱位qs，將is翻倒至落箱位js，提箱過(guò)程如圖5所示，場(chǎng)橋作業(yè)時(shí)間為

綜上所述，本文建立以最短場(chǎng)橋總作業(yè)時(shí)間為目標(biāo)的數(shù)學(xué)模型.

圖4 存在1個(gè)阻礙箱的提箱過(guò)程Fig.4 Loading process with 1 rehandle

圖5 存在2個(gè)阻礙箱的提箱過(guò)程Fig.5 Loading process with 2 rehandles

所有的目標(biāo)箱都能被提取裝船的約束為

場(chǎng)橋每次提取1個(gè)集裝箱的約束為

集裝箱在船舶上不能懸空放置的約束為

堆場(chǎng)貝位每一棧的堆存高度要小于最高可堆存高度的約束為

提箱裝船和倒箱過(guò)程中目標(biāo)箱所在的棧和落箱位所在棧的高度變化約束為

倒箱僅發(fā)生在同一貝位不同棧中，其約束為

為了表示目標(biāo)箱和阻礙箱位于堆場(chǎng)貝、棧、層之間的關(guān)系，其約束為

決策變量均為0-1變量，即

3 算法設(shè)計(jì)

3.1 算法原理

已知船舶配載圖和堆場(chǎng)堆存狀態(tài)，可確定多種裝船順序.假設(shè)集裝箱的數(shù)量為N，則裝船順序的復(fù)雜度為N!，難以對(duì)問(wèn)題進(jìn)行求解.本文從船舶棧的最底層和堆場(chǎng)棧的最頂層進(jìn)行研究，避免了集裝箱在船舶上的翻倒，結(jié)合堆場(chǎng)堆存狀態(tài)剔除部分不合理的可行解.在求解過(guò)程中，比較與前一目標(biāo)箱位于相同堆場(chǎng)貝的箱及其他貝位直提箱的場(chǎng)橋作業(yè)時(shí)間，選擇最短作業(yè)時(shí)間的箱作為目標(biāo)箱，如果存在阻礙箱則將其翻倒至同一貝位的最矮棧中，直至所有目標(biāo)箱完成裝船作業(yè).基于上述思想的均衡倒箱量及場(chǎng)橋作業(yè)時(shí)間的啟發(fā)式算法，減少計(jì)算量，提高了計(jì)算效率.

3.2 算法步驟

基于上述算法原理，算法流程圖如圖6所示，具體步驟如下：

Step 1設(shè)定初始數(shù)據(jù).確定集裝箱數(shù)為N，場(chǎng)橋作業(yè)時(shí)間CT=0，倒箱量R=0，裝船順序集合LS.

Step 2確定初始裝船集合S.根據(jù)船舶配載圖，選擇船舶貝位各棧最底層箱，構(gòu)成集合S，確定S中箱所在堆場(chǎng)貝位棧的層數(shù)E及最高層數(shù)M，轉(zhuǎn)Step 3.

Step 3判斷是否存在直提箱.由S、E及M，計(jì)算L=M-E，判斷L中是否存在元素0，即直提箱，如果存在，轉(zhuǎn)Step 4；否則，轉(zhuǎn)Step 5.

Step 4直接提取直提箱n.選擇L中元素0中序號(hào)最小的箱作為目標(biāo)箱，并確定場(chǎng)橋作業(yè)時(shí)間CT和所在堆場(chǎng)貝位bay，倒箱量R不變，轉(zhuǎn)Step 8.

Step 5判斷是否存在阻礙箱為1的箱.判斷L中是否存在元素1，如果存在，轉(zhuǎn)Step 6；否則，轉(zhuǎn)Step 7.

Step 6提取阻礙箱為1的箱n1.選擇L中元素1中序號(hào)最小的箱作為目標(biāo)箱，確定場(chǎng)橋作業(yè)時(shí)間CT2、堆場(chǎng)貝位bay、倒箱量r，總場(chǎng)橋作業(yè)時(shí)間CT=CT+CT2，總倒箱量R=R+r，將箱n1記錄到集合LS中，轉(zhuǎn)Step 8.

Step 7提取S中最小序號(hào)的箱n1.選擇S中序號(hào)最小的箱作為目標(biāo)箱，確定場(chǎng)橋作業(yè)時(shí)間CT2、及堆場(chǎng)貝位bay、倒箱量r，總場(chǎng)橋作業(yè)時(shí)間CT=CT+CT2，總倒箱量R=R+r，將箱n1記錄到集合LS中，轉(zhuǎn)Step 8.

Step 8更新集合S、E及M，轉(zhuǎn)Step 9.

Step 9判斷S中是否存在位于bay堆場(chǎng)貝的集裝箱n3.如果存在，轉(zhuǎn)Step 10；否則，轉(zhuǎn)Step 11.

Step 10確定提取n3所用的場(chǎng)橋作業(yè)時(shí)間CT3及倒箱量r，轉(zhuǎn)Step 12.

Step 11判斷是否存在直提箱n4.根據(jù)更新的集合S、E及M，計(jì)算L=M-E，判斷L中是否存在元素0，如果存在，轉(zhuǎn)Step 17；否則，轉(zhuǎn)Step 18.

Step 12判斷是否存在直提箱n4.根據(jù)更新的集合S、E及M，計(jì)算L=M-E，判斷L中是否存在元素0，如果存在，轉(zhuǎn)Step 13；否則，轉(zhuǎn)Step 16.

Step 13確定提取n4所用的場(chǎng)橋作業(yè)時(shí)間CT4，轉(zhuǎn)Step 14.

Step 14判斷CT3是否大于CT4，如果是，轉(zhuǎn)Step 15；否則，轉(zhuǎn)Step 16.

Step 15將箱n4記錄到集合LS中，計(jì)算總場(chǎng)橋作業(yè)時(shí)間CT=CT+CT4，倒箱量R不變，bay為箱n4所在的堆場(chǎng)貝位，轉(zhuǎn)Step 19.

Step 16將箱n3記錄到集合LS中，計(jì)算總場(chǎng)橋作業(yè)時(shí)間CT=CT+CT3，倒箱量R=R+r，bay為箱n3所在的堆場(chǎng)貝位，轉(zhuǎn)Step 19.

Step 17確定提取n4所用的場(chǎng)橋作業(yè)時(shí)間CT4，轉(zhuǎn) Step 15.

Step 18確定S中最小序號(hào)的集裝箱n3及倒箱量r，轉(zhuǎn) Step 16.

Step 19判斷集合LS的集裝箱量是否為N.如果是，轉(zhuǎn)Step 20；否則，轉(zhuǎn)Step 8.

Step 20輸出提取N個(gè)集裝箱所用的總場(chǎng)橋作業(yè)時(shí)間CT及倒箱量R.

4 算例比較與分析

4.1 算例求解

本文基于上述算法，以14個(gè)集裝箱為例，圖7(a)表示船舶配載狀態(tài)，圖7(b)表示位于堆場(chǎng)不同貝位的堆存狀態(tài).利用Matlab對(duì)啟發(fā)式算法進(jìn)行求解，得到裝船順序及場(chǎng)橋行駛路徑，如圖8和表1所示.

圖8為裝船過(guò)程中的堆場(chǎng)變化，可以看出只需翻倒阻礙箱8，倒箱量為1.表1為啟發(fā)式算法下的裝船順序及場(chǎng)橋作業(yè)時(shí)間，可以看到最優(yōu)的裝船順序?yàn)?-2-6-4-8-13-5-10-11-3-7-12-9-14，場(chǎng)橋作業(yè)時(shí)間CT=1 744s.

4.2 下界分析

為了驗(yàn)證模型的有效性，計(jì)算理論上的下界至關(guān)重要，分析可知，場(chǎng)橋作業(yè)時(shí)間包括直接提箱產(chǎn)生的場(chǎng)橋作業(yè)時(shí)間及倒箱操作產(chǎn)生的場(chǎng)橋作業(yè)時(shí)間，裝船過(guò)程中倒箱操作是不可避免的，不同的裝船順序會(huì)產(chǎn)生不同的倒箱量，影響場(chǎng)橋作業(yè)時(shí)間.因此，為縮短場(chǎng)橋作業(yè)時(shí)間，必須減少倒箱量的產(chǎn)生，使其趨向于0，即所有的集裝箱直接裝船，得到最短場(chǎng)橋作業(yè)時(shí)間.因此，本文計(jì)算了所有集裝箱直接提箱裝船的場(chǎng)橋作業(yè)時(shí)間，以此作為下界，驗(yàn)證算例的準(zhǔn)確性.

具體的下界求解過(guò)程如下所示：

(1)根據(jù)船舶配載圖，選擇船舶貝位各棧最底層的集裝箱，構(gòu)成初始裝船集合S.

(2)提取S中集裝箱號(hào)最小的箱n，并計(jì)算直接提取箱n的場(chǎng)橋作業(yè)時(shí)間.更新S.

(3)直接提取與箱n同一貝位的集裝箱，計(jì)算場(chǎng)橋作業(yè)時(shí)間，如果不存在同一貝位的箱，則繼續(xù)提取集合S中箱號(hào)最小的，直至所有箱裝船.

圖6 算法流程圖Fig.6 Algorithm flow chart

圖7 船舶及堆場(chǎng)堆存狀態(tài)Fig.7 Stacking status for ship and yard

圖8 堆場(chǎng)狀態(tài)變化過(guò)程Fig.8 Changing process of yard state

(4)將所有箱直接提取裝船所需要的場(chǎng)橋作業(yè)時(shí)間作為該模型的下界LB，下界求解公式為

4.3 算法比較

本文利用Matlab編程語(yǔ)言開發(fā)，所得結(jié)果是在Intel Core 2 Duo3GHzCPU及2G內(nèi)存平臺(tái)下測(cè)得.為驗(yàn)證算法的可行性及通用性，本文對(duì)B×S×T(即堆場(chǎng)貝數(shù)×棧數(shù)×最高層數(shù))的不同組合，隨機(jī)生成集裝箱規(guī)模為N的不同算例，針對(duì)不同規(guī)模的算例，采用了啟發(fā)式算法求解，并進(jìn)行對(duì)比分析，結(jié)果如表2和圖9所示.

表1 裝船順序及場(chǎng)橋作業(yè)時(shí)間Table 1 Loading sequence and yard crane operation time

表2 啟發(fā)式算法和下界比較Table 2 Comparison for heuristic algorithm and lower bound

圖9 算法分析圖Fig.9 Algorithm analysis diagram

表2表示了啟發(fā)式算法下不同規(guī)模算例產(chǎn)生的倒箱量、場(chǎng)橋作業(yè)時(shí)間及算法下界，得到以下結(jié)論：

(1)本文提出的啟發(fā)式算法適用于不同規(guī)模下的集裝箱作業(yè)，且隨著集裝箱規(guī)模的增大，場(chǎng)橋作業(yè)時(shí)間增加，算法運(yùn)行時(shí)間變長(zhǎng)，但仍較快獲得計(jì)算結(jié)果，表明本文設(shè)計(jì)的模型及算法是有效的.

(2)裝船順序及場(chǎng)橋行駛路徑聯(lián)合優(yōu)化下的場(chǎng)橋作業(yè)時(shí)間與下界相比，場(chǎng)橋作業(yè)時(shí)間的增加程度約為20%～35%，這主要是由于裝船順序及場(chǎng)橋行駛路徑的不同導(dǎo)致不同倒箱量的產(chǎn)生，表明倒箱量對(duì)場(chǎng)橋作業(yè)效率影響較大.因此，碼頭操作人員可對(duì)裝船順序及場(chǎng)橋行駛路徑聯(lián)合優(yōu)化，提高堆場(chǎng)作業(yè)效率.

(3)場(chǎng)橋作業(yè)時(shí)間與下界差值呈指數(shù)增長(zhǎng)趨勢(shì)，擬合曲線的可決系數(shù)為0.960 8，表明倒箱量對(duì)場(chǎng)橋作業(yè)時(shí)間影響較大.因此，碼頭操作人員應(yīng)著重于降低倒箱量，降低場(chǎng)橋作業(yè)時(shí)間.

5 結(jié)論

集裝箱碼頭堆場(chǎng)運(yùn)作優(yōu)化的重要目標(biāo)之一是提高堆場(chǎng)作業(yè)效率.本文在已知船舶配載圖及堆場(chǎng)堆存狀態(tài)的前提下，研究出口箱裝船順序及場(chǎng)橋行駛路徑聯(lián)合優(yōu)化問(wèn)題，以作業(yè)時(shí)間衡量裝船順序產(chǎn)生的倒箱量及場(chǎng)橋行駛路徑，建立了以最短場(chǎng)橋作業(yè)時(shí)間為目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)啟發(fā)式算法對(duì)模型進(jìn)行求解，分析了該聯(lián)合優(yōu)化問(wèn)題的下界，并通過(guò)算例實(shí)驗(yàn)對(duì)問(wèn)題進(jìn)行討論.算例結(jié)果表明該聯(lián)合優(yōu)化問(wèn)題在啟發(fā)式算法下的場(chǎng)橋作業(yè)時(shí)間與下界相比增加的程度約為20%～35%，且場(chǎng)橋作業(yè)時(shí)間與下界差值呈指數(shù)增長(zhǎng)趨勢(shì)，同時(shí)，隨著集裝箱規(guī)模的增加，算法仍能較快得到最優(yōu)解，驗(yàn)證了算法和模型的有效性和合理性，為碼頭調(diào)度人員提供了理論上的依據(jù).