邰世文， 商劍平， 饒衛(wèi)振

(1.中交水運規(guī)劃設計院有限公司,北京 100007; 2.山東科技大學 經(jīng)濟管理學院,山東 青島 266590)

0 引言

我國煤炭運輸形成了“北煤南運”、“西煤東運”的基本格局[1]，輸出型煤炭碼頭是我國煤運輸體系的關鍵樞紐。輸出型煤炭碼頭的運營模式是：列車運輸煤炭到港口，翻堆作業(yè)系統(tǒng)卸車并將煤炭堆存到堆場；船舶靠泊后，取裝作業(yè)系統(tǒng)從堆場取煤并傳送到泊位裝船，裝船完成后離港。輸出型煤炭碼頭輸入(卸車)的目的是輸出(裝船)，泊位分配是碼頭煤炭輸出調(diào)度計劃的起點，其重要性不言而喻。輸出型煤炭碼頭泊位分配問題不僅僅是單純考慮泊位規(guī)格和裝船設備下的船舶匹配泊位，還應考慮船舶票貨及裝船方案、煤種在堆場中的垛位分布及堆存量、取裝作業(yè)系統(tǒng)、裝船作業(yè)過程以及靠離泊規(guī)則等，即船貨匹配下的泊位分配問題。較優(yōu)的泊位分配，可以最大限度的避免泊位資源浪費，提高堆場煤源的利用情況，減少設備沖突，縮短船舶在港時間。

當前，關于碼頭泊位分配問題研究越來越多的與船舶靠泊后的實際生產(chǎn)掛鉤，并考慮其關聯(lián)的影響因素，如泊位分配與岸橋調(diào)度相互影響方面的研究[2～5]，泊位分配與堆場相互影響的研究[6,7]，泊位分配與燃油消耗相互影響的研究[8]。大規(guī)模泊位分配問題求解方面，流行的算法主要有遺傳算法[2,4,9,10]、粒子群算法[11]、模擬退火算法[12]等。煤炭碼頭卸車調(diào)度方面，劉文遠等[13]著重研究了煤炭碼頭列車等待和作業(yè)總時間最短的列車-翻車機-堆場聯(lián)合調(diào)度優(yōu)化問題；邰世文[14]研究了煤炭碼頭考慮列車-翻堆線-堆場的卸車生產(chǎn)調(diào)度問題多約束多目標優(yōu)化模型及其遺傳算法。目前關于煤炭碼頭泊位分配問題的研究文獻非常有限：有Robenek等[15]從戰(zhàn)術層面上研究了散貨港口的泊位分配和堆場分配問題，但其前提假設是所有船舶都是單一貨種，優(yōu)化目標單一；宓為建等[16]針對出口型煤碼頭泊位分配問題，以岸線、機械利用率最大和船舶總在港時間最短為目標建立泊位與機械聯(lián)合調(diào)度模型并用遺傳算法求解，但僅區(qū)分塊煤和末煤，而且未考慮場存、工藝可達等邊界條件，船舶在泊時間估算粗略。實際應用層面，國內(nèi)煤炭碼頭泊位分配嚴重依賴于人腦經(jīng)驗，由于影響因素眾多，工作人員很難站在全局角度分配泊位。

綜上，輸出型煤炭碼頭泊位分配問題不僅僅是單純的船舶匹配泊位，然而當前大多研究僅單一考慮堆場或設備因素且過于理想化，實用性較低。因此，本文針對輸出型煤炭碼頭船貨匹配下的泊位分配問題，考慮船舶票貨及裝船方案、煤種在堆場中的垛位分布及堆存量、垛位與取料機的可達性、取裝線、裝船機與泊位的可達性、泊位規(guī)格限制、航道開放時間和裝船作業(yè)規(guī)則等邊界條件，建立了多約束多目標數(shù)學模型，并設計了采用仿真推演策略解碼的遺傳算法求解。本研究旨在為解決具有船貨匹配、動態(tài)調(diào)度、多約束、多目標等特點的復雜、大型輸出型煤炭碼頭泊位分配問題提供新的解決途徑。

1 問題的描述

船舶在碼頭接受服務的整個過程是：船舶抵錨→在航道開放進港時間進港靠泊→第一輪裝船作業(yè)并同時排壓艙水→第二輪裝船作業(yè)→第三輪裝船作業(yè)(調(diào)水尺)→在航道開放出港時間離泊，裝船作業(yè)過程需要按照船方配載步驟依次進行取裝作業(yè)。煤炭流經(jīng)取裝線的關鍵節(jié)點是：堆垛→取料機(或給料機)及其相連的皮帶→轉(zhuǎn)接皮帶→裝船機→船艙，取裝線設備節(jié)點會存在交叉的情況。一般來說，船舶裝船需求可能是多票貨，每票貨可以是多個裝船方案，每個裝船方案可以是單個煤種(如神混1單裝)或者兩個煤種按一定比例配煤(如神混1:神優(yōu)1=2:1)，多條船舶可能存在共用一個裝船方案或裝船煤種情況。

輸出型煤炭碼頭典型布局如圖1所示，整個堆場由露天堆場和封閉筒倉構成(取料機移動到相應垛位取料，給料機固定在筒倉底端供料)，受取裝線限制，不同的堆場可達不同的泊位，如筒倉排A和B均可達泊位201和202。

圖1 輸出型煤炭碼頭典型布局

本研究問題可以描述為：有s個不同的垛位(垛位位置、類型、堆存煤種等不同)、e條取料線(包括取料機或給料機及其相連的傳送皮帶，取料線與垛位的可達性關系為一對多)、l臺裝船機(受取裝工藝限制，取料線與裝船機的可達性關系為多對多)、m個不同規(guī)格的泊位(裝船機與泊位的可達性關系為多對多)；有n條抵錨或預到船舶，每條船舶可以配載1～3票貨(票貨量固定)，每票貨對應裝船方案為1～3個，每個裝船方案可以是一個堆存煤種單裝或由兩個堆存煤種按一定比例配煤(同一取裝線上的垛位才能配煤)；按照船舶具備排船條件的時間順序，將n條船分配到m個泊位上，并給出裝船方案計劃裝載量、垛位和船舶的計劃靠離泊時間，使得碼頭作業(yè)效率最大和船舶在港時間最短。

為便于建模及求解，在符合其實用性的前提下，本文設定以下前提條件：

①待排船舶包括抵錨和預到船舶(動態(tài)調(diào)度)，船舶具備排船條件時間滾動變化。

②一條船舶只能?？恳粋€泊位，不考慮移泊。

③航道開放進港、離港時間點固定，船舶從錨地到泊位以及從泊位離港的時長固定。

④船舶裝船作業(yè)分三輪，靠泊后開始排水和第一輪作業(yè)，排水和第一輪作業(yè)均完成后方可進行第二輪作業(yè)，第一、二輪作業(yè)效率取歷史平均值，第三輪(調(diào)水尺)作業(yè)時長取歷史平均值。

⑤轉(zhuǎn)接皮帶充足，一條取裝線由取料線(取料機或給料機及其相連的傳送皮帶)和裝船機唯一確定。

⑥取裝線一次裝船作業(yè)準備時長取平均值。

⑦泊位、垛位及取裝設備等抽象為中心點。

⑧煤源充足，忽略設備故障、天氣等情況導致的延遲。

本文使用的符號說明如表1所示。

表1 符號說明表

2 模型的構建

2.1 目標函數(shù)

本文問題模型的目標函數(shù)為港口生產(chǎn)效率最大和船舶在港時間最短，表示如下:

(1)

(2)

(3)

(4)

(5)

(6)

2.2 約束條件

本模型的約束條件主要包括泊位規(guī)格限制、作業(yè)唯一性約束、進出港時間限制、裝船煤種場存充足及取值范圍限制等約束條件，表示如下:

(7)

(8)

(9)

(10)

(11)

(12)

(13)

?j∈B,?i∈V,?i′∈V,i≠i′,xij=1,xi′j=1

(14)

(15)

(16)

(17)

(18)

(19)

3 遺傳算法設計

泊位分配問題是已經(jīng)被證明了的NP-Hard問題，遺傳算法是應用最廣泛的智能求解算法之一[2,4,9,10,16]，而仿真能夠用一個虛擬的系統(tǒng)描述真實系統(tǒng)的運行、演變及其發(fā)展過程[14,17]。為更好地接近煤炭碼頭船舶系統(tǒng)運行情況，提高結(jié)果精確性，本文將遺傳算法與仿真推演結(jié)合求解本研究問題。

3.1 編碼設計

編碼的目的是將問題的可行解從其解空間轉(zhuǎn)換為求解算法的搜索空間中，其設計質(zhì)量對求解效果有較大影響。基于本問題模型的特點，本文提出了一種組合式編碼方法，介紹如下：

(1)編碼

在本研究問題中，編碼需要描述的解空間包括船舶?？康牟次弧⒃诓次簧系淖鳂I(yè)順序、采用的裝船方案垛位及裝船量、接受服務的時間點。其中，一條船舶僅且僅能對應一個泊位，船舶在泊位上的服務順序按照船舶具備排船條件時間排序，采用的裝船方案可以通過設定裝船方案優(yōu)先級的方式來解決，實際采用的裝船方案的垛位、裝船量和作業(yè)時間可以根據(jù)船舶作業(yè)時選擇啟用的取裝線、票貨量、垛位實時堆存量以及作業(yè)效率等計算得到。為了減少編碼長度，縮小解空間的規(guī)模，本文染色體編碼僅考慮船舶作業(yè)泊位和裝船方案優(yōu)先級，而裝船方案垛位、裝船量和作業(yè)時間在仿真推演裝船作業(yè)過程中計算。因此，本文設計的染色體由泊位序列和裝船方案優(yōu)先級序列構成，如圖2所示。

圖2 染色體編碼示意圖

①泊位序列Berth={b1,b2,…,bn-1,bn}。如bi=j，表示第i條船作業(yè)的泊位為j。

于是，本模型的任意一種方案可由(Berth，Order)唯一表示。所有船舶根據(jù)Berth序列分配到相應泊位上，根據(jù)船舶具備排船條件時間確定船舶在泊位上的靠泊順序；然后根據(jù)Order序列確定方案的優(yōu)先級，綜合航道開放時間、裝船工藝可達性、場存量、票貨量、船舶輪次配載量、作業(yè)效率以及裝船作業(yè)啟發(fā)式優(yōu)化規(guī)則等進行仿真推演計算，可以得到裝船方案仿真裝載量、取料垛位、裝船作業(yè)時間和船舶的計劃靠離泊時間。

(2)初始種群生成

由于船舶可分配的泊位除了需要滿足船舶與泊位的噸級、長度、寬度和吃水深度匹配情況外，還應考慮裝船方案煤種的堆存位置與泊位的可達性以及堆存量與配載量關系等約束。因此，在生成染色體時需要確保染色體的合法性，本文設計的染色體生成規(guī)則如下：

①從船舶隊列取出i船，根據(jù)公式(7)～(10)初步篩選符合限制的可用泊位集合Bi；

②根據(jù)公式(15)(19)計算貨源情況，刪除掉集合Bi中不滿足約束的泊位；

③從集合Bi中隨機選擇一個泊位賦值基因位bi，生成Berth序列；

⑤返回到①生成下一染色體。

3.2 仿真推演解碼設計

由于本問題牽扯到的變量較多、船舶作業(yè)過程順序嚴格、作業(yè)工藝約束較多，僅僅通過簡單的編碼和解碼較難反應作業(yè)的真實情況。這就需要染色體解碼時，利用仿真技術來推演各調(diào)度方案的運行情況，并統(tǒng)計分析相應的目標函數(shù)值作為各染色體的適應值，最終求得較優(yōu)的解。首先，介紹仿真推演過程中船舶作業(yè)各個節(jié)點的開始和結(jié)束時間的計算方法，如下：

令i′和i船是先后靠j泊位作業(yè)的兩條船，i′船離開j泊位后，i船在第w個進港時間點到j泊位作業(yè)，則i船的進港靠泊各時間節(jié)點及泊位狀態(tài)如下:

(20)

(21)

(22)

(23)

(24)

其中，式(20)表示i船的進港靠泊開始時間為第w個進港時間點，該時間點要晚于i船到港時間和i′船的離泊時間；式(21)表示j泊位從i船開始進港靠泊的時刻起就為被占用狀態(tài)；式(22)表示i船的靠泊完成時間，該時間也是船舶開始排水時間，見式(23)，若i船靠泊完成后即裝船作業(yè)，則該時間也是船舶開始作業(yè)時間(第一輪裝船作業(yè)開始時間)；式(24)表示船舶排水完成時間。

令在t0時刻a取料線及相連的z裝船機開始空閑，在t1時刻i船舶具備進行第g輪裝船作業(yè)，且i船舶能使用該取裝線從u垛位取料進行裝船作業(yè)，則應滿足如下約束條件:

(25)

(26)

(27)

(28)

(29)

(30)

同時，在作業(yè)期間取裝線被占用，表示如下:

(31)

其次，令第一輪完成作業(yè)時間為t4，則i船舶具備第二輪開始作業(yè)的條件的時間t5為:

(32)

重復公式(25)～(32)過程可以計算i船舶第一、二輪裝船作業(yè)開始和結(jié)束過程中的裝船垛位、取裝量及時間節(jié)點。令第三輪裝船作業(yè)開始時間為t6，則第三輪裝船作業(yè)完成時間t7和船舶作業(yè)完成時間表示如下:

(33)

(34)

最后，完成裝船作業(yè)后船舶在航道開放船舶出港的第w個時間點離泊出港，離港時間為:

(35)

本文采用事件調(diào)度法進行仿真推演解碼，詳細步驟如下：

①初始化仿真時鐘以及泊位、設備、堆場和取裝線(取料線和裝船機)狀態(tài)。

②處理船舶：將未到港船舶的到港事件加入事件列表；將已抵錨未靠泊船舶放入到等待靠泊列表；對于正在裝船作業(yè)船舶，根據(jù)裝船進度(第幾輪作業(yè)、裝船作業(yè)記錄、已完成票貨量、正在裝船作業(yè)的取裝線和垛位信息)計算流本次裝船作業(yè)量及完成時間，將一次裝船作業(yè)完成事件加入事件列表；對于在泊等待作業(yè)的船舶，加入等待作業(yè)列表。

③推進仿真時鐘，處理事件列表直到空為止：船舶到港事件發(fā)生時，將船舶加入到等待靠泊列表；船舶具備靠泊條件或泊位空閑事件發(fā)生時執(zhí)行④；船舶具備作業(yè)條件或一次裝船作業(yè)完成時執(zhí)行⑤。

④針對空閑的泊位，從等待靠泊列表取出i船，若bi與該泊位相同，則根據(jù)船舶配載量、裝船方案、場存情況，按照公式(15)(19)計算船貨匹配情況，選擇第一艘船貨匹配的船舶，根據(jù)公式(20)～(24)更新船舶進港靠泊各時間節(jié)點及狀態(tài)。

⑤針對空閑的取裝流程，根據(jù)在泊船舶靠泊順序及裝船方案優(yōu)先級模擬裝船作業(yè)，根據(jù)公式(25)～(35)計算船舶的作業(yè)時間和垛位剩余堆存量、并更新船舶狀態(tài)和設備狀態(tài)，若完成作業(yè)則計算船舶離泊時間，將一次裝船作業(yè)完成事件或泊位空閑事件加入事件列表。

3.3 適應值函數(shù)設計

本算法適應值函數(shù)的設計是在式(4)的基礎上作如下變換:

(36)

3.4 遺傳操作設計

遺傳算法針對由多個可行染色體構成的種群，通過選擇、交叉和變異進行迭代尋優(yōu)。目前，常用的選擇方法有輪盤賭法、隨機遍歷抽樣法、局部選擇和錦標賽選擇等，常用的交叉方法有單點交叉、多點交叉、算術交叉、順序交叉、部分映射交叉和循環(huán)交叉等，常用的變異方法有實值變異、替換變異、互換式變異等?；谇笆鼍幋a方式，本算法的遺傳操作設計如下：

①選擇操作：采用最流行的輪盤賭法和保優(yōu)策略結(jié)合的方法。選擇時，首先采用輪盤賭法，從父代中選出一定比例的染色體，以進行后續(xù)的交叉和變異操作產(chǎn)生子代個體；然后采取保優(yōu)策略，從子代個體和父代個體中選擇適應值、目標1和目標2較大的個體進入下一輪的遺傳操作，使進化過程中的優(yōu)秀個體全部保留下來。

②交叉操作：交叉操作是遺傳造作中最重要的一環(huán)，本文為了增加交叉的多樣性，設計了三種交叉策略，以不同的概率進行相應的交叉操作。第一種是以船舶為單位同時分別兩點交叉染色體的兩個序列；第二種是保持Berth序列不變，對Order序列內(nèi)每條船以票貨為單位進行單點交叉；第三種是Berth序列保持不變，對Order序列內(nèi)的每條船舶的每票貨的基因片段進行部分映射交叉。

③變異操作：變異操作包括兩種，染色體變異時，以一定的概率選擇一種或兩種策略進行相應的變異操作。第一種是僅對Berth序列的交換變異，合法范圍內(nèi)隨機選取2個基因位交換泊位；第二種是對Order序列變異，隨機選取一條船內(nèi)的任一票貨，隨機交換該票貨內(nèi)裝船方案的順序。

4 研究應用情況

4.1 實例概況

本文算法用JAVA編程實現(xiàn)，開發(fā)了黃驊港煤炭碼頭泊位計劃智能排產(chǎn)系統(tǒng)，以黃驊港煤炭碼頭實際數(shù)據(jù)為例驗證模型及算法的有效性。黃驊港煤炭碼頭是國內(nèi)煤炭出口大港，有17個煤炭泊位，3個露天堆場共計122個垛位，1個筒倉堆場共計48個筒倉，堆存煤種38個，取料線14條，裝船機13臺，取裝線46條，2018年煤炭量下水量超過2億噸。

4.2 算例分析

本文取黃驊港煤炭碼頭某一時點的實際數(shù)據(jù)(在泊船舶14條，正在進港船舶2條，錨地船舶29條，預到船舶1條)，在配置為CPU Intel 4核1.6GHz、內(nèi)存8G的計算機上測試。

經(jīng)統(tǒng)計，程序計算時長約257.39秒。適應值函數(shù)及目標函數(shù)收斂曲線如圖3所示，可以看出算法從約84代開始收斂，算法收斂性和執(zhí)行效率較高。

圖3 適應值函數(shù)及目標函數(shù)收斂曲線

泊位分配結(jié)果如圖4所示，30條待排船舶的總在港時間3775小時(單船平均在港5.2天)，計劃開始時間2019-01-07 13:00:00，船舶最晚離泊時間2019-01-10 10:00:00，計劃時長69小時。圖4主界面X軸為時間軸，Y軸為泊位號，2019-01-07 13:00:00處的豎線為計劃開始時間截線，與其相交的有14條在泊船舶和2條正在進港船舶，圖中一個圖形代表一條船，圖形內(nèi)數(shù)據(jù)分別表示船號、船名、配載噸和裝船進度，如泊位100后的第二個圖形表示：船舶號為19858，船名為長旺門，配載為17300噸，計劃在船舶中匯22離泊后靠泊，計劃靠泊時間是2019-01-07 20:00:00，計劃離泊時間是2019-01-08 14:00:00。

圖4 程序計算的泊位分配方案

有經(jīng)驗的計劃人員一次制定本實例30條船舶的泊位方案平均約耗時120分鐘，本文用計算機模擬人工方案的結(jié)果如圖5所示，30條待排船舶總在港時間4207小時(單船平均在港5.8天)，計劃開始時間2019-01-07 13:00:00，船舶最晚離泊時間2019-01-10 14:00:00，計劃時長73小時。

圖5 計劃人員制定的泊位分配方案

通過對比可知，人工制定的泊位分配方案在耗費工時、船舶總在港時間和計劃時長方面分別是系統(tǒng)計算結(jié)果的28倍、1.1倍和1.1倍。本文算法可以更加科學、迅速、精確地制定新的調(diào)度計劃，執(zhí)行效率高，優(yōu)化效果好，結(jié)果展示清晰。

5 結(jié)論

本文主要研究輸出型煤炭碼頭船貨匹配下泊位動態(tài)分配問題多目標優(yōu)化模型及遺傳算法。在模型方面，本文綜合船舶、泊位、堆場、取裝線、煤種、航道開放時間和裝船作業(yè)規(guī)則等要素，構建了堆場-取裝線-泊位-船舶聯(lián)合分配優(yōu)化數(shù)學模型；在算法方面，本文給出了遺傳算法的詳細設計，包括組合式編碼、采用仿真推演策略的解碼方法，追加了合法性檢查的染色體生成算法，適應值函數(shù)設計，以及采用多種策略的遺傳操作等。最后，針對黃驊港煤炭碼頭實例測試結(jié)果表明：模型實用性強，算法求解效率高，優(yōu)化效果好且適用。本研究成果為解決具有船貨匹配、動態(tài)調(diào)度、多約束、多目標等特點的復雜、大型輸出型煤炭碼頭泊位動態(tài)分配問題提供了新的解決途徑。