基于遺傳算法的煤炭港口泊位分配優(yōu)化模型

李曉玲

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

1 引言

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

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

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

2 問題模型

2.1 問題描述

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

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

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

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

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

2.2 模型假設(shè)

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

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

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

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

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

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

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

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

2.3 符號(hào)說明

b：泊位編號(hào)，b ∈B。

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

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

Av：船舶v的計(jì)劃到港時(shí)間。

Gvbk：船舶v停靠在泊位b上作為第k條船被服務(wù)時(shí)泊位b可到達(dá)的堆場(chǎng)可以為其提供的煤量。

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

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

xvbk=1 表示船舶v?？吭诓次籦上作為第k條船被服務(wù)，否則，取0。

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

2.4 模型建立

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

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

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

約束條件：

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

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

裝載量約束：

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

時(shí)間約束：

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

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

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

3.1 染色體編碼

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

圖2 染色體舉例

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

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

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

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

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

3.3 初始種群

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

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

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

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

3.4 遺傳操作

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

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

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

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

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

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

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

①選擇一對(duì)個(gè)體作為父代個(gè)體1 和父代個(gè)體2，如圖3所示。

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

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

圖3 父個(gè)體舉例

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

圖4 新個(gè)體舉例

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

4 試驗(yàn)與仿真

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

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

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