柴佳祺，李 鋒，宓為建，楊小明，沈一帆

（上海振華重工（集團(tuán)）股份有限公司，上海 200125；上海海事大學(xué) 物流工程學(xué)院 上海 201306）

在港口碼頭的各類系統(tǒng)中，通常將礦石、煤炭、散糧、散裝水泥等專業(yè)化泊位稱為散貨碼頭.散貨碼頭的核心資源有泊位、裝卸機(jī)械、裝卸堆場(chǎng)等，其中泊位是指在港內(nèi)為了進(jìn)行裝卸給船舶停泊靠岸并有一定長(zhǎng)度岸壁的地方.船舶在靠、離泊時(shí)，所需的岸壁線長(zhǎng)度要大于船舶長(zhǎng)度.泊位屬于碼頭的稀缺資源，近年來(lái)不斷增長(zhǎng)的散貨流量給碼頭提出了更高的要求，而排船計(jì)劃的質(zhì)量是關(guān)系到碼頭生產(chǎn)作業(yè)質(zhì)量的重要因素，因此如何更好地利用有限的岸線空間、提高煤炭運(yùn)輸量和運(yùn)輸效率、減少船舶的在港時(shí)間一直都是研究的熱點(diǎn)與難點(diǎn).

針對(duì)碼頭泊位分配問(wèn)題很多國(guó)內(nèi)外學(xué)者進(jìn)行了相關(guān)研究.KIM等［1］運(yùn)用混合整數(shù)模型來(lái)描述泊位分配問(wèn)題，以船舶延遲離港和船舶偏離最優(yōu)位置產(chǎn)生的額外費(fèi)用最小化為目標(biāo)，并應(yīng)用模擬退火算法（SA）求得該模型的近似最優(yōu)解.IMAI等［2］為解決集裝箱船舶大型化和碼頭岸線資源有限的問(wèn)題，建立了鋸齒形岸線的泊位調(diào)度模型，提高了泊位的利用率.LEE等［3］建立了混合整數(shù)規(guī)劃模型，利用遺傳算法獲取最優(yōu)解.BIERWIRTH等［4］針對(duì)泊位安排和岸橋調(diào)度的聯(lián)合問(wèn)題進(jìn)行了研究.EDUARDO等［5］提出了禁忌搜索方法，并結(jié)合混合啟發(fā)式算法討論了動(dòng)態(tài)泊位的分配問(wèn)題.LIM等［6］以任意時(shí)刻下岸線空閑長(zhǎng)度的最小化為目標(biāo)，提出了連續(xù)型泊位的調(diào)度問(wèn)題.假設(shè)到港船舶無(wú)須等待，可立即靠泊作業(yè)，并且在離港之前不存在移泊現(xiàn)象.PARK等［7－8］綜合計(jì)算了船舶延遲離港和未停泊在最優(yōu)位置所產(chǎn)生的額外費(fèi)用.IMAI等［9］對(duì)于離散型的泊位調(diào)度問(wèn)題，按最大靠泊船舶的長(zhǎng)度對(duì)岸壁線進(jìn)行了劃分，運(yùn)用啟發(fā)式算法求解模型.國(guó)內(nèi)學(xué)者張煜等［10］將岸線連續(xù)化，建立了泊位動(dòng)態(tài)調(diào)度模型，通過(guò)仿真將連續(xù)型泊位調(diào)度與離散化泊位調(diào)度進(jìn)行了分析和比較.王紅湘等［11］按照岸線有限的泊位分配原則，建立了動(dòng)態(tài)泊位分配的數(shù)學(xué)模型，并采用啟發(fā)式算法對(duì)該策略進(jìn)行了模擬和優(yōu)化.何軍良等［12］按照滾動(dòng)式計(jì)劃模式，建立了基于整數(shù)規(guī)劃的動(dòng)態(tài)泊位調(diào)度模型，并采用分布式遺傳算法和啟發(fā)式算法相結(jié)合的分布式混合算法求解了泊位調(diào)度問(wèn)題.CHANG Daofang等［13］采用滾動(dòng)式計(jì)劃模式建立了泊位－岸橋聯(lián)合調(diào)度模型，然后利用遺傳算法和啟發(fā)式算法相結(jié)合的混合算法求解模型.

以上研究大多是針對(duì)集裝箱碼頭的泊位分配問(wèn)題，構(gòu)建數(shù)學(xué)模型并通過(guò)合理的算法解決相關(guān)問(wèn)題的.然而對(duì)于散貨碼頭的連續(xù)性泊位分配問(wèn)題，很少有人通過(guò)相應(yīng)算法進(jìn)行求解，也未給出詳細(xì)的計(jì)劃編制表供調(diào)度人員參考.因此本文采用啟發(fā)式算法求解連續(xù)性泊位的船舶靠泊計(jì)劃問(wèn)題，計(jì)算并驗(yàn)證該算法應(yīng)用于實(shí)際生產(chǎn)作業(yè)的效果，以提高碼頭的生產(chǎn)效率及服務(wù)水平.

1 排船問(wèn)題描述

國(guó)內(nèi)大部分散貨碼頭在做船舶靠泊計(jì)劃時(shí)，首先考慮船舶吃水和碼頭水深的關(guān)系，在確保安全靠離的前提下遵循“先外貿(mào)再內(nèi)貿(mào)”、“先干線后支線”、“先到錨地先靠”的原則，同時(shí)兼顧堆場(chǎng)、靠泊位置和各裝卸機(jī)械的所在位置，對(duì)船舶的靠泊位置與離泊時(shí)間做統(tǒng)籌安排.隨著船舶大型化的發(fā)展，越來(lái)越多的散貨碼頭開(kāi)始關(guān)注優(yōu)化散貨船的可裝載量以及在港時(shí)間，以求獲得更大的經(jīng)濟(jì)收益.

目前港口碼頭按照實(shí)際作業(yè)情況，將整個(gè)碼頭岸線均勻地分為若干個(gè)小單位.在考慮安全距離的前提下，根據(jù)到港船的船長(zhǎng)，?？吭谙鄳?yīng)若干個(gè)小單位組成的泊位區(qū)段上，這樣可以有效增加泊位岸線的利用率.

散貨碼頭的泊位沿線有一定數(shù)量的纜繩樁，每當(dāng)船舶靠泊時(shí)，船舶上的纜繩將會(huì)被固定于纜樁，以完成靠泊作業(yè).船舶占用的泊位長(zhǎng)度可以通過(guò)該船映射的纜繩樁頭尾之間的距離來(lái)確定，并將此長(zhǎng)度反映為纜繩樁間距的整數(shù)倍.在實(shí)際操作中，一個(gè)樁位只可作用于一艘船，即使相鄰樁位間留有一定距離，甚至可以容納一條船，也不能將相鄰船舶系在同一根纜樁上.實(shí)際排船的二維圖形如圖1所示.

圖1 排船分配的二維示意圖Fig.1 Two－dimensional diagram of berth allocation for vessels

圖1中橫坐標(biāo)表示碼頭泊位岸線，最右端的數(shù)值代表岸線總長(zhǎng)度，所有船舶的停靠位置都不能超過(guò)橫坐標(biāo)的范圍；縱坐標(biāo)表示碼頭生產(chǎn)管理的時(shí)間維度.所有船舶的靠泊作業(yè)都可用一個(gè)矩形框表示.其中，矩形的橫邊（Ei－Si）表示所占用的泊位岸線長(zhǎng)度（其中包含了為避免船體碰撞所預(yù)留的安全距離），矩形的縱邊（Eti－Bti）表示在泊作業(yè)時(shí)間.矩形左下角坐標(biāo)（Si，Bti）和（Sj，Btj）分別為靠泊船頭位置和靠泊時(shí)間，同理：（Ei，Eti）和（Ej，Etj）分別為靠泊船尾位置和離泊時(shí)間.

這樣，排船問(wèn)題就轉(zhuǎn)化成了上述約束條件下的矩形排列問(wèn)題，所有矩形框的集合就是調(diào)度人員排船的規(guī)劃方案.在實(shí)際的生產(chǎn)實(shí)踐中，有經(jīng)驗(yàn)的調(diào)度人員在絕大多數(shù)情況下會(huì)針對(duì)性地選擇多種排位順序作為輔助參考，以優(yōu)化作業(yè)總量和船舶在泊時(shí)間為前提，做出有效合理的安排與調(diào)整，提升散貨碼頭的整體生產(chǎn)作業(yè)質(zhì)量.

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

2.1 模型假設(shè)

數(shù)學(xué)模型的建立基于下列假設(shè)：① 每艘船根據(jù)自身?xiàng)l件、貨物配載量及到港時(shí)間配置以較優(yōu)的靠泊位置，考慮船舶都在計(jì)劃好的靠泊時(shí)間準(zhǔn)時(shí)到港，并且都是空船到達(dá)碼頭，等待靠泊并進(jìn)行裝船作業(yè).② 裝卸機(jī)械足夠，且船舶裝卸效率沿碼頭岸線固定.③ 船舶之間預(yù)留安全凈距離，可互不影響地進(jìn)行作業(yè).④ 靠泊位置始末決定了所占用的岸線長(zhǎng)度，靠泊時(shí)間始末決定了在港作業(yè)的總時(shí)間.⑤考慮在計(jì)劃開(kāi)始時(shí)刻泊位岸線皆為空閑狀態(tài).⑥ 在港作業(yè)時(shí)間包含從錨地到泊位的行駛時(shí)間與從泊位駛離港口的時(shí)間，即船舶到港時(shí)泊位岸線上若有空閑位置，認(rèn)定該船到港時(shí)刻為船舶靠泊時(shí)間，亦即無(wú)延遲靠泊，靠泊結(jié)束時(shí)刻為離港時(shí)間.⑦散貨船舶按計(jì)劃次序沿著岸壁線從左至右編排.

2.2 模型描述

2.2.1 目標(biāo)函數(shù)

目標(biāo)函數(shù)1：?jiǎn)挝话毒€長(zhǎng)度裝船容量最大化.

式中：L為岸線長(zhǎng)度，即泊位總長(zhǎng)度；s為規(guī)定排船周期（如日泊位計(jì)劃24h）到港船集合（i＝1，2，3…s）；i，j指任意船舶，i，j∈（1，2，3…s）；Xi為決策變量，若船舶i靠泊，則Xi＝1，否則Xi＝0；Ci為船舶i的載重量，i∈s（i＝1，2，3…s）.

目標(biāo)函數(shù)2：?jiǎn)未舆t靠泊時(shí)間最小化.

式中：Bti為船舶i的靠泊時(shí)間；Ati為船舶i的到港時(shí)間.

總目標(biāo)函數(shù)：

式中：w1，w2為權(quán)重.由于兩個(gè)子目標(biāo)的計(jì)算量綱不同，因此要對(duì)目標(biāo)函數(shù)做出轉(zhuǎn)換，如式（4）—（6）所示.

式中：Ti為船舶i的裝卸作業(yè)時(shí)間.

2.2.2 約束條件

（1）保證船舶的靠泊位置在岸線范圍以內(nèi)

式中：Pi為船舶i的中心位置，i∈s（i＝1，2，3，…，s）；Li為船舶i長(zhǎng)度，i∈s（i＝1，2，3，…，s）.

（2）船舶i靠泊后裝卸作業(yè)的開(kāi)始時(shí)間不能早于船舶的到港時(shí)間.

（3）在港船舶i接受裝卸處理的結(jié)束時(shí)間要早于船舶i的離港時(shí)間.

（4）要求泊位的空閑長(zhǎng)度要大于船舶的自身長(zhǎng)度.

（5）對(duì)于停靠在泊位上的所有船只，占用的裝卸設(shè)備不能超過(guò)碼頭所能提供的機(jī)械總量.

式中：Qi為分配給船舶i的機(jī)械數(shù)量，i∈s（i＝1，2，3…s）；q為機(jī)械設(shè)備數(shù)量.

（6）要求靠泊船舶在時(shí)間維度交叉沖突的情況下空間位置不重疊.

式中：Ei，Ej為船舶i，j的靠泊止位置，即船尾位置；Si，Sj為船舶i，j的靠泊始位置，即船頭位置.Sij為決策變量，若船舶i和j到港時(shí)間交叉，則Sij＝1，否則Sij＝0.

（7）要求靠泊船舶空間維度不交叉沖突（此約束下，無(wú)論時(shí)間維度是否重疊，都不會(huì)發(fā)生船舶碰撞）.

式中：Eti，Etj為船舶i，j的離泊時(shí)間；Pij為決策變量，若船舶i和j靠泊位置交叉，則Pij＝1，否則Pij＝0.

（8）保證岸線上任意位置及任意時(shí)刻最多被1條船占用.

3 排船算法

港務(wù)碼頭公司對(duì)排船的實(shí)施控制具有主動(dòng)性，事先通過(guò)船代公司獲得每艘船的數(shù)據(jù)信息，并根據(jù)這些信息制定船舶的靠泊、裝卸等作業(yè)計(jì)劃［14］.船舶在泊生產(chǎn)作業(yè)的時(shí)間和單船作業(yè)量對(duì)港口的經(jīng)濟(jì)收益有重要影響，是排船問(wèn)題中的關(guān)鍵因素.

本文運(yùn)用啟發(fā)式排船算法，在保證求解速度的前提下能獲取最優(yōu)解.該算法的流程如圖2所示.

圖2 啟發(fā)式算法流程示意圖Fig.2 Flowchart of the proposed heuristic algorithm

步驟1 選擇符合計(jì)劃期的船舶初始信息，根據(jù)配載量從大到小進(jìn)行排序，總量為s.

步驟2 從i＝1開(kāi)始循環(huán)，給到港船舶進(jìn)行泊位分配.

步驟3 根據(jù)船舶i的進(jìn)港時(shí)間及配載量計(jì)算船舶的裝卸作業(yè)時(shí)間，由此得到靠泊的時(shí)間范圍.

步驟4 安排船舶靠泊位置的規(guī)則是沿著岸線從左向右排列，即第1艘船的靠泊始位置為碼頭最左端，依據(jù)占用的泊位長(zhǎng)度計(jì)算出靠泊末位置.根據(jù)靠泊始末位置計(jì)算得出對(duì)應(yīng)的纜樁始末位置.

步驟5 預(yù)先做出該時(shí)刻碼頭岸線有無(wú)空閑泊位的判斷.若有空閑泊位，繼續(xù)分析當(dāng)前計(jì)劃的船舶p與已排船舶t在作業(yè)時(shí)間上有無(wú)沖突.若沖突，進(jìn)入（1）；若不沖突，則進(jìn)入（2）.若船舶p到港時(shí)無(wú)空閑泊位，則進(jìn)入（3）.

（1）把船p的矩形框排放在t的右邊（遵循從左往右排的規(guī)則，直到超出長(zhǎng)度范圍為止），即纜樁的起始位置緊鄰船t所在纜樁的末端位置.

（2）將當(dāng)前船p排放在碼頭最左端.

（3）對(duì)該船進(jìn)行延時(shí)裝卸作業(yè)，相應(yīng)的靠泊時(shí)間段要做延后調(diào)整，同時(shí)排船規(guī)則依舊遵從（1），（2）.

步驟6i＝i＋1，若出現(xiàn)下述兩種情況，計(jì)算終止.

（1）如果i大于總船舶數(shù)s；

（2）現(xiàn)有的時(shí)間、空間范圍已無(wú)空閑區(qū)域可供船舶靠泊.

否則，重復(fù)算法步驟3—5.

上述過(guò)程中，在完成一艘船的配載任務(wù)后，隨即對(duì)現(xiàn)有船信息進(jìn)行更新，表示該船已做好排船計(jì)劃，同時(shí)進(jìn)入安排下一條船的預(yù)備狀態(tài).此算法保證了碼頭的裝船總量最大，根據(jù)到港時(shí)間、配載量和所占用的泊位長(zhǎng)度，盡量多地往二維圖中排放矩形框，直到無(wú)可放空間為止.

4 案例分析

各類散貨在碼頭的裝卸作業(yè)具有一定的共性，本文以出口型散貨煤碼頭為研究對(duì)象，碼頭的基本配置以出口為前提條件，所構(gòu)建的模型和算法求解同樣適用于其他類型的散貨碼頭.

選取國(guó)內(nèi)某港煤碼頭2011年10月11日16∶00至12日16∶00所有的到港船舶作為實(shí)際研究案例，共30艘船.其主要內(nèi)容包括：船舶代碼、占用的泊位長(zhǎng)度、配載量和到港時(shí)間，如表1所示.案例所討論的是日泊位計(jì)劃，目的是將足夠多的船舶編制排入24小時(shí)的排船計(jì)劃中.需要說(shuō)明的是，這些船舶都是空船到港，靠泊后進(jìn)行裝船作業(yè)，而且不管任務(wù)是否做完，都算入當(dāng)日裝船總量.

采用Power Builder11.5構(gòu)建排船輔助系統(tǒng)，其中啟發(fā)式算法的計(jì)算模塊如圖3所示.

計(jì)算說(shuō)明：劃分樁位，設(shè)定25m為一個(gè)小單位的泊位長(zhǎng)度，煤碼頭岸線總長(zhǎng)度為1 000m，則纜樁數(shù)為1 000／25＋1＝41個(gè).從“占用的泊位長(zhǎng)度”一欄，可以用對(duì)應(yīng)的數(shù)值除以25，向上取整后得到纜樁與纜樁間共占用幾小段.例如，若長(zhǎng)度為168m，則占用7小段，即從B1至B7，是該船的?？课恢?，其他船在此時(shí)刻就不予?？吭谂c其有交叉的位置上.為方便計(jì)算，假設(shè)單位為1 000t的作業(yè)時(shí)間需要20min.如一艘船的裝載量為4 000t，其靠泊時(shí)間就是80min.因此船舶i的靠泊時(shí)間段為［進(jìn)錨地時(shí)間，進(jìn)錨地時(shí)間目標(biāo)函數(shù)中的權(quán)重w1和w2都設(shè)為1（可根據(jù)實(shí)際作業(yè)情況作相應(yīng)調(diào)整），求解結(jié)果如圖4和表2所示.

表1 煤碼頭初始數(shù)據(jù)表（30條船）Tab.1 Initial datasheet for the coal terminal

圖3 啟發(fā)式算法模塊Fig.3 Heuristic algorithm module

圖4 啟發(fā)式算法二維效果圖Fig.4 Two－dimensional result by heuristic algorithm

表2 煤碼頭排船計(jì)劃編制表Tab.2 Table showing the vessel scheduling at coal terminal

續(xù)表2

煤碼頭的常規(guī)排船策略是運(yùn)用“先到錨地，先安排泊位”的方法，即FCFS.在此綜合比較兩組求解結(jié)果，如表3所示.

表3 排船結(jié)果比較Tab.3 Comparison of scheduling results

從表3可以發(fā)現(xiàn)：在裝船量和延遲靠泊時(shí)間這兩個(gè)評(píng)價(jià)指標(biāo)上，啟發(fā)式算法有一定的優(yōu)勢(shì)，能多排入一艘船，裝船量相比多了9 000t.比較后面兩個(gè)指標(biāo)，發(fā)現(xiàn)傳統(tǒng)排船方法的延遲情況比較嚴(yán)重，單船平均延遲靠泊時(shí)間大于30min，采用啟發(fā)式排船策略則可將單船延遲靠泊時(shí)間降低到22.06min.

上述分析表明，啟發(fā)式算法對(duì)于求解現(xiàn)有散貨碼頭的排船問(wèn)題有現(xiàn)實(shí)意義，對(duì)于提高碼頭的經(jīng)濟(jì)效益有積極作用.碼頭調(diào)度人員也能很直觀地參考二維圖制定規(guī)劃，針對(duì)碼頭的實(shí)際作業(yè)情況進(jìn)行調(diào)整，得到較為科學(xué)可靠的結(jié)果.

另外，從船舶的初始數(shù)據(jù)信息可以看出，配載量較大的船舶有時(shí)會(huì)集中進(jìn)港.如果不及時(shí)對(duì)裝載量較大的船舶進(jìn)行靠泊，則會(huì)在船舶數(shù)量很多、來(lái)不及作業(yè)的情況下，無(wú)法排入當(dāng)天的排船計(jì)劃，出現(xiàn)壓港或者延遲靠泊的現(xiàn)象.所以啟發(fā)式算法的好處在于為配載量大的船舶先安排靠泊，與之相比，“先到先靠”的傳統(tǒng)方法，沒(méi)有考慮船舶配載量，只按照進(jìn)港秩序進(jìn)行編排，這樣的運(yùn)行模式缺乏一定的經(jīng)濟(jì)合理性.

5 結(jié)語(yǔ)

本文針對(duì)散貨碼頭泊位分配的具體現(xiàn)狀，深入研究排船策略.根據(jù)碼頭生產(chǎn)管理的相應(yīng)原則，構(gòu)建綜合考慮裝船容量和延遲靠泊時(shí)間的優(yōu)化數(shù)學(xué)模型，在模型基礎(chǔ)上利用啟發(fā)式算法進(jìn)行求解.實(shí)例驗(yàn)證表明，該模型和算法能在一定程度上增加配載總量及降低船舶延遲靠泊時(shí)間，對(duì)提高散貨碼頭的生產(chǎn)作業(yè)效率和服務(wù)水平有一定的指導(dǎo)意義，證明該排船計(jì)劃模型和啟發(fā)式算法的有效性和實(shí)用性.

［1］KIM K H，KIM H B.The optimal determination of the space requirement and the number of transfercranes for import containers［J］.Computers and Industrial Engineering，1998，35（3）：427－430.

［2］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berth allocation at indented berths for mega－containerships ［J］.European Journal of Operational Research，2007，179（2）：579－593.

［3］LEE D H，HUI Q W.Integrated discrete berth allocation and quay crane scheduling in port container terminals ［J］.Engineering Optimization，2010，42（8）：747－761.

［4］BIERWIRTH C，MEISEL F.A survey of berth allocation and quay crane scheduling problems in container terminals［J］.European Journal of Operational Research，2010，202（3）：615－627.

［5］EDUARDO L R，BELEN M B，MARCOS M V.Artificial intelligence hybrid heuristic based on tabu search for the dynamic berth allocation problem ［J］.Engineering Applications of Artificial Intelligence，2012，25：1132－1141.

［6］LIM A.The berth planning problem ［J］.Operations Research Letters，1998，22：105－110.

［7］PARK K T，KIM K H.Berth scheduling for container terminals by using a sub－gradient optimization technique［J］.Journal of the Operational Research Society，2002，53：1054－1062.

［8］PARK Y M，KIM K H.A scheduling method for berth and quay cranes［J］.OR Spectrum，2003，25：1－23.

［9］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berth allocation in a container port：using a continuous location space approach ［J］.Transportation Research：Part B，2005，39：199－221.

［10］張煜，王少梅.基于遺傳算法的泊位連續(xù)化動(dòng)態(tài)調(diào)度研究［J］.系統(tǒng)仿真學(xué)報(bào)，2007，19（10）：2161－2164.ZHANG Yu，WANG Shaomei.Dynamic scheduling of continuous berth based on genetic algorithm ［J］.Journal of System Simulation，2007，19（10）：2161－2164.

［11］王紅湘，嚴(yán)偉.基于啟發(fā)式算法和仿真優(yōu)化的岸壁線長(zhǎng)度泊位分配策略 ［J］.上海海事大學(xué)學(xué)報(bào).2008，29（1）：19－22.WANG Hongxiang，YAN Wei.Quay－length－based berth allocation strategy on heuristic algorithm and simulation optimization［J］.Journal of Shanghai Maritime University，2008，29（1）：19－22.

［12］何軍良，宓為建，謝塵，等.基于分布式混合遺傳算法的動(dòng)態(tài)泊位分配策略與仿真 ［J］.上海海事大學(xué)學(xué)報(bào)，2008，29（2）：52－57.HE Junliang，MI Weijian，XIE Chen，et al.Strategy and simulation on dynamic berth allocation based on distributed hybrid genetic algorithm ［J］.Journal of Shanghai Maritime University，2008，29（2）：52－57.

［13］CHANG Daofang，JIANG Zuhua.Integratin berth allocation and quay crane assignments［J］.Transportation Research：Part E，2010，46：975－990.

［14］鄧恢華，歐凡.港口運(yùn)行機(jī)制與排船決策影響因素分析 ［J］.商場(chǎng)現(xiàn)代化，2008（4）：156－158.DENG Huihua，OU Fan.The analysis of port operational mechanism and influential factors for vessel scheduling［J］.Market Modernization，2008（4）：156－158.