李曉玲

（北京交通大學(xué)海濱學(xué)院 基礎(chǔ)教學(xué)部，河北 黃驊 061199）

1 引言

煤炭作為我國的主要能源，是我國經(jīng)濟飛速發(fā)展的重要支撐[1]。在我國“西煤東運，北煤南下”的戰(zhàn)略下，煤炭港口發(fā)揮了重要作用。近年來，隨著經(jīng)濟的發(fā)展，港口的吞吐量不斷提升，給港口帶來巨大經(jīng)濟效益的同時也帶來了很多挑戰(zhàn)。畢竟港口資源是有限的，如何合理有效的利用港口資源實現(xiàn)更大的吞吐量，成為了港口所面臨的重大問題。泊位資源作為煤炭港口的稀缺資源，其合理分配不僅能夠提升裝船效率，從而減少船舶在港時間，還能夠為后續(xù)生產(chǎn)計劃環(huán)節(jié)的實施和優(yōu)化奠定基礎(chǔ)。但是，由于煤炭種類繁多，煤炭港口不同于集裝箱港口，目前的調(diào)度主要還是人工調(diào)度，因此對煤炭港口的智能調(diào)度研究對提高港口的資源利用率，緩解疏港壓力，增加港口效益有著重要的理論和現(xiàn)實意義。

目前，國內(nèi)外專家都對港口的資源調(diào)度問題做了大量深入的研究。Imai 等[2]以最小化船舶等待時間為目標(biāo)，模擬了靜、動態(tài)分配模型，采用拉格朗日松弛法對模型進(jìn)行求解。Henesey 等[3]采用Agent 技術(shù)對集裝箱港口的船舶運輸策略進(jìn)行了仿真實驗，并對不同的策略進(jìn)行了比較和評價。Wang 和Lim[4]將NP泊位分配問題轉(zhuǎn)化成了一個多階段決策程序，利用隨機定向搜索算法，提出了改善定向搜索計劃、兩階段節(jié)點質(zhì)量評估、隨機節(jié)點選擇標(biāo)準(zhǔn)。韓駿等[5]提出了集裝箱碼頭的泊位與岸橋聯(lián)合調(diào)度問題的協(xié)調(diào)調(diào)度優(yōu)化模型。王軍等[6]采用動態(tài)學(xué)習(xí)方法對在泊時間計算函數(shù)進(jìn)行更新，再基于所得函數(shù)對泊位調(diào)度方案進(jìn)行優(yōu)化，設(shè)計了并行算法。劉強等[7]對基于線性規(guī)劃的煤炭碼頭泊位調(diào)度問題進(jìn)行研究，建立了以船舶整體缺煤量最少和整體在泊時間最短為目標(biāo)的逐級線性規(guī)劃模型。綜合國內(nèi)外對港口泊位調(diào)度問題的研究發(fā)現(xiàn)，大部分的泊位調(diào)度問題研究主要集中在集裝箱碼頭，對于煤炭碼頭的泊位調(diào)度問題研究很少。

本文以某大型輸出型煤炭港口系統(tǒng)為背景，充分研究了輸出型煤炭港口的服務(wù)系統(tǒng)特征，在考慮場存能力的前提下，以船舶在港總時間最短及整體裝煤量最大為目標(biāo)建立數(shù)學(xué)模型，并利用改進(jìn)的遺傳算法對模型進(jìn)行求解。

2 問題模型

2.1 問題描述

泊位調(diào)度問題就是研究一個計劃周期內(nèi)的到港船舶在什么時候進(jìn)入到什么位置的泊位問題。在煤炭港口物流系統(tǒng)中，船舶作業(yè)流程如圖1 所示，當(dāng)船舶到達(dá)錨地時，工作人員根據(jù)貨量需求信息和堆場存儲信息，結(jié)合碼頭正在進(jìn)行的工作信息，為船舶指定合適的堆場位置及泊位，發(fā)送作業(yè)指令給各工作單元和裝卸設(shè)備，進(jìn)行裝貨作業(yè)。裝貨完成后，船舶離港。

堆場是用來儲存煤炭的場所，由于地理空間及設(shè)備的限制，每個垛位堆放的基礎(chǔ)原煤只能被運輸?shù)娇傻竭_(dá)的若干泊位上?？蛻粜枨蟮拿悍N稱為合同煤種，合同煤種可以由不同種類的基礎(chǔ)原煤按照一定的比例混合而成，這個過程稱為配煤，配煤過程中需要的基礎(chǔ)原煤種類和比例稱為配煤方案，對于一艘船舶的一種合同煤種,可以有多個配煤方案供其選擇。

正是因為煤炭港口的這個特性，所以在為船舶指泊時，不僅要考慮船泊匹配約束、時間約束、設(shè)備約束等，還要考慮船貨匹配約束。由于合同煤種可能有多個配煤方案供其選擇，所以待排船中有可能存在某些船舶共享幾種原煤的情況，若煤量場存不足，就有可能出現(xiàn)排在前面的船取走煤后，后面的船舶就只能等貨的情況，這不僅造成對泊位資源的浪費，也降低了港口的吞吐量。

為此，在煤量場存不足的條件下，本文建立了以港口總輸出煤量最大及船舶總在港時間最小為目標(biāo)的多目標(biāo)線性規(guī)劃模型，并給出基于遺傳算法的求解方法。

圖1 船舶作業(yè)流程圖

2.2 模型假設(shè)

為便于模型建立，首先做如下假設(shè)：

（1）不考慮機械故障、天氣因素等干擾。

（2）假設(shè)堆場在該規(guī)劃期內(nèi)不會補充庫存。

（3）假設(shè)船舶一旦停泊不允許移泊。

（4）假設(shè)船舶進(jìn)港后先在錨地等候，一旦被安排進(jìn)泊便開始作業(yè)。

（5）假設(shè)每條船舶符合其船型約束的可?？坎次惶崆耙阎?/p>

（6）假設(shè)機械的作業(yè)效率是一個固定值d。

（7）假設(shè)船舶在航道上行駛的時間忽略不計，船舶在每個泊位上的工作時間，即在泊時間窗可以提前計算得出。

2.3 符號說明

b：泊位編號，b ∈B。

v：一個計劃周期內(nèi)的在港船舶編號,v ∈V。

Vb：符合泊位b船型約束的船舶集合，Vb?V。

Av：船舶v的計劃到港時間。

Gvbk：船舶v?？吭诓次籦上作為第k條船被服務(wù)時泊位b可到達(dá)的堆場可以為其提供的煤量。

Lv：船舶v所要求的配載煤量。

η:船舶要求的最小匹配度。

xvbk=1 表示船舶v停靠在泊位b上作為第k條船被服務(wù)，否則，取0。

Cvbk：船舶v?？吭诓次籦上作為第k條船被服務(wù)時對應(yīng)的裝載量。

2.4 模型建立

港口企業(yè)的利潤取決于港口的整體輸出量，由于存在爭煤現(xiàn)象，整體輸出量一方面取決于港口的效率，主要表現(xiàn)在船舶的總在港時間，一方面取決于船舶的整體裝載量，故本文以整體裝載量最大和總在港時間最小為目標(biāo)函數(shù)，考慮船舶與泊位的一次性服務(wù)約束、船舶的裝載量約束以及時間窗約束，建立如下模型。

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

式（1）表示所有船舶的整體裝載量最大，式（2）表示所有船舶的總在港時間最小。

約束條件：

一次性服務(wù)約束：

式（3）表示一艘船只能?？吭谝粋€泊位上，b表示泊位編號，B表示所有泊位的集合；式（4）表示一個泊位一次性最多只能服務(wù)于一條船，Vb表示符合泊位b船型約束的船舶集合；式（5）表示在整個計劃周期內(nèi)一條船最多被服務(wù)一次。

裝載量約束：

式（6）、（7）限制了船舶v?？吭诓次籦上作為第k條船被服務(wù)時對應(yīng)的裝載量不得小于船舶要求的最小匹配量，也不可能大于相應(yīng)堆場可以為其提供的煤量。

時間約束：

式（8）-（10）表示第k條船必須在前一條船離泊之后進(jìn)泊，且計劃進(jìn)泊時間必須大于計劃到港時間，小于計劃離泊時間。

3 基于改進(jìn)遺傳算法的模型求解方案

該問題是一個具有復(fù)雜的多約束條件、多目標(biāo)函數(shù)的優(yōu)化問題，很難找到精確的算法。遺傳算法是模擬自然界生物進(jìn)化機制的一種算法，具有很好的自組織性、自適應(yīng)性和自學(xué)習(xí)性，但傳統(tǒng)的遺傳算法在實際應(yīng)用中容易陷入局部最優(yōu)，或者求解結(jié)果與實際情況不一致，為本文在求解模型時加入人工干預(yù)的啟發(fā)式規(guī)則，以提高求解的高效性和有效性。

3.1 染色體編碼

遺傳算法最常用的編碼方式是二進(jìn)制編碼，但是泊位調(diào)度問題的特性決定了使用二進(jìn)制編碼計算機不易處理，因此本文采用泊位-次序的二維編碼方式。例如，一個周期內(nèi)的到港船舶有9 只，可用泊位有3個，則我們將橫軸劃分為9個區(qū)間，豎軸劃分為3個區(qū)間，得到一個3×9 的矩陣，矩陣中第i行第j列的值為船舶序號，記做vij，表示第vij號船在第i個泊位作為第j條船被服務(wù)。圖2則表示一個染色體，第2 行第4 列的元素3 表示3 號船舶?？吭? 號泊位上被第4 個服務(wù)，在它前面接受服務(wù)的船舶依次是7號、9號、2號船。

圖2 染色體舉例

這里的0表示不再排船，要求每一行的第一個零元素后不再出現(xiàn)非零元素。

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

本文所建立的模型為雙目標(biāo)函數(shù)模型，由于兩個目標(biāo)的量綱不同，根據(jù)問題本身特性，選擇排序方式[8]來計算個體的適應(yīng)度。

對每一個個體xi，分別計算其兩個目標(biāo)函數(shù)值，根據(jù)計算的值對所有個體進(jìn)行排序，得到排序序列S1={R1(xi)}；S2={R2(xi)}，其中，Rj(xi)(j=1,2)表示個體xi在目標(biāo)j中的優(yōu)劣排列序號，取值越小說明該個體對于該目標(biāo)越優(yōu)。設(shè)種群規(guī)模為N，定義以下公式作為個體的適應(yīng)度。

式（11）定義了個體對每個目標(biāo)的適應(yīng)度值，分段的意義在于使得最優(yōu)解的適應(yīng)度值足夠大。式（12）則表示個體的總適應(yīng)度值。

3.3 初始種群

種群初始化過程結(jié)合隨機生成和啟發(fā)式規(guī)則的混合方式。啟發(fā)式規(guī)則包括先到先服務(wù)（FCFS）原則、緊急船優(yōu)先、自有船優(yōu)先等原則，對產(chǎn)生的隨機個體驗證是否滿足約束條件，進(jìn)行初步篩選，這里涉及到的主要問題為泊位指定和順序指定（即時間指定）。具體操作過程為：

第一步：根據(jù)船貨匹配、船泊匹配條件及設(shè)備可達(dá)性等，確定可用泊位集，隨機選擇泊位；

第二步：計算可靠泊時間約束，如果該泊位已經(jīng)有船，隨機選擇排列順序，否則根據(jù)最早可靠泊時間窗，隨機選擇時間點，作為該泊位第一艘被服務(wù)船舶；若可靠泊時間約束無解，重新制定泊位，若所有泊位無解，則計入未排船集合。

第三步：更新數(shù)據(jù)。將啟發(fā)式規(guī)則和隨機生成原則結(jié)合在一起，既保證了初始種群中基因的多樣性，又保證初始種群的優(yōu)良性和有效性。

3.4 遺傳操作

遺傳操作主要包括選擇、交叉和變異操作。

（1）選擇操作。選擇操作的目的是為了從群體中選擇優(yōu)良的個體，使他們有機會作為父代來繁殖子孫。根據(jù)適應(yīng)度函數(shù)的特性，這里選用輪盤賭方法。

第一步，根據(jù)適應(yīng)度函數(shù)的定義方式，計算出每一個個體的適應(yīng)度值；

第四步：若r ＜q1，則選擇個體1，否則選擇個體k，使得qk-1＜r ≤qk成立；

第五步：重復(fù)第三、四步N次。

（2）交叉操作與變異操作。由適應(yīng)度函數(shù)的特性，交叉概率和變異概率都由以下公式自適應(yīng)產(chǎn)生。

其中fmax為群體中所有個體的最大適應(yīng)度值，為平均適應(yīng)度值為要進(jìn)行交叉的個體的最大適應(yīng)度值（要進(jìn)行變異的個體的適應(yīng)度值），c,d為[ ]0,1之間的常數(shù)。由于采用二維編碼方式，這里舉例說明具體的交叉方式和變異方式。

①選擇一對個體作為父代個體1 和父代個體2，如圖3所示。

②生成隨機數(shù)P與交叉概率pc比較，如果P ＞pc，則不進(jìn)行交叉，直接將父代復(fù)制到子代中，否則轉(zhuǎn)③。

③隨機選擇一個位置，寫出對應(yīng)元素對。如果沒有零元素，如第2 行第3 列，對應(yīng)元素對為（2，4），找到個體2中該位置船號（4）在個體1中的位置（第3行第1列），交換這兩個位置上的船號；同時找到個體1 中該位置船號（2）在個體2 中的位置（第1 行第1列），交換這兩個位置上的船號，得到新一代個體（如圖4所示新個體1、新個體2），否則，轉(zhuǎn)④。

圖3 父個體舉例

④若有兩個零則不進(jìn)行交叉操作，否則若有一個零如第2行第4列（3,0），則從該非零數(shù)字所在的個體中任選一行的第一個零與之互換（若該非零數(shù)字為所在行最后一個非零數(shù)字，則與除了本行外的其他行的非零數(shù)字互換），從零元素所在的個體中找到該非零數(shù)字，二者交換。剔除非零行非零數(shù)字前面的零，產(chǎn)生新一代個體（如圖4所示新個體3、新個體4）。

圖4 新個體舉例

⑤對于通過選擇復(fù)制及交叉產(chǎn)生的新個體進(jìn)行變異操作，由于變異概率pm比較小，變異操作一般不發(fā)生，變異操作采取單點變異方式。對個體中的每一個基因，產(chǎn)生一個隨機數(shù)p，如果p ＞pm則不發(fā)生變異，否則隨機產(chǎn)生一個位置，將該位置的基因與此基因進(jìn)行交換，如果隨機產(chǎn)生的位置與該基因位置相同，則不交換。

4 試驗與仿真

算例以某港口實際數(shù)據(jù)庫為依據(jù)，計劃周期為48小時，計劃周期內(nèi)的到港船舶為26艘，最小匹配度設(shè)置為0.8。通過MatlabR2012a 實現(xiàn)，得到結(jié)果。與其人工調(diào)動數(shù)據(jù)做對比，見表1。

表1 人工調(diào)度與模型調(diào)度數(shù)據(jù)表

與人工調(diào)度相比，雖然本文所建模型調(diào)度使未排船量增加了，但是船舶的平均等待時間減少了34%，總裝載量提高了2.5%，達(dá)到了優(yōu)化的目的。