基于啟發(fā)式算法的散貨碼頭排船問題研究

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

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

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

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

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

1 排船問題描述

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

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

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

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

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

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

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

2.1 模型假設(shè)

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

2.2 模型描述

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

目標(biāo)函數(shù)1：單位岸線長度裝船容量最大化.

式中：L為岸線長度，即泊位總長度；s為規(guī)定排船周期（如日泊位計劃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：單船延遲靠泊時間最小化.

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

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

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

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

2.2.2 約束條件

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

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

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

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

（4）要求泊位的空閑長度要大于船舶的自身長度.

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

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

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

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

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

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

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

3 排船算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 案例分析

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

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

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

計算說明：劃分樁位，設(shè)定25m為一個小單位的泊位長度，煤碼頭岸線總長度為1 000m，則纜樁數(shù)為1 000／25＋1＝41個.從“占用的泊位長度”一欄，可以用對應(yīng)的數(shù)值除以25，向上取整后得到纜樁與纜樁間共占用幾小段.例如，若長度為168m，則占用7小段，即從B1至B7，是該船的?？课恢?，其他船在此時刻就不予?？吭谂c其有交叉的位置上.為方便計算，假設(shè)單位為1 000t的作業(yè)時間需要20min.如一艘船的裝載量為4 000t，其靠泊時間就是80min.因此船舶i的靠泊時間段為［進(jìn)錨地時間，進(jìn)錨地時間目標(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 煤碼頭排船計劃編制表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)：在裝船量和延遲靠泊時間這兩個評價指標(biāo)上，啟發(fā)式算法有一定的優(yōu)勢，能多排入一艘船，裝船量相比多了9 000t.比較后面兩個指標(biāo)，發(fā)現(xiàn)傳統(tǒng)排船方法的延遲情況比較嚴(yán)重，單船平均延遲靠泊時間大于30min，采用啟發(fā)式排船策略則可將單船延遲靠泊時間降低到22.06min.

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

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

5 結(jié)語

本文針對散貨碼頭泊位分配的具體現(xiàn)狀，深入研究排船策略.根據(jù)碼頭生產(chǎn)管理的相應(yīng)原則，構(gòu)建綜合考慮裝船容量和延遲靠泊時間的優(yōu)化數(shù)學(xué)模型，在模型基礎(chǔ)上利用啟發(fā)式算法進(jìn)行求解.實(shí)例驗(yàn)證表明，該模型和算法能在一定程度上增加配載總量及降低船舶延遲靠泊時間，對提高散貨碼頭的生產(chǎn)作業(yè)效率和服務(wù)水平有一定的指導(dǎo)意義，證明該排船計劃模型和啟發(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ù)化動態(tài)調(diào)度研究［J］.系統(tǒng)仿真學(xué)報，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)化的岸壁線長度泊位分配策略 ［J］.上海海事大學(xué)學(xué)報.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］何軍良，宓為建，謝塵，等.基于分布式混合遺傳算法的動態(tài)泊位分配策略與仿真 ［J］.上海海事大學(xué)學(xué)報，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］.商場現(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.