考慮減載移泊的散貨港口泊位與船舶集成調(diào)度①

鄭紅星 姜 雪 段 爽

(大連海事大學(xué)交通運(yùn)輸工程學(xué)院 大連 116026)

0 引 言

近年來船舶大型化的趨勢愈發(fā)明顯，港口深水大泊位的利用越來越重要。同時，鑒于大型船舶在一些港口需乘潮進(jìn)出港口，合理地調(diào)度船舶進(jìn)出港逐漸引起了各方的關(guān)注。另考慮到港口中深水大泊位的稀少，一般散貨港口均采用減載移泊的方式來發(fā)揮該類泊位的效能。同時，鑒于船舶進(jìn)出港次序和泊位分配之間交互影響，考慮減載移泊的港口泊位分配和船舶調(diào)度的集成優(yōu)化問題，是提高港口服務(wù)水平的關(guān)鍵問題之一，也是港口效率提升的熱點問題。

現(xiàn)有的研究中，在船舶調(diào)度方面，江振峰等人[1]研究了不定期船舶運(yùn)輸?shù)恼{(diào)度優(yōu)化問題，考慮運(yùn)輸需求的時空分布特征，以最大化承運(yùn)人利益為目標(biāo)建立優(yōu)化模型，求解規(guī)劃期內(nèi)船舶的運(yùn)營調(diào)度方案，并采用遺傳算法求解模型。許歡等人[2]討論了低碳經(jīng)濟(jì)下的港口泊位分配模型及其算法實現(xiàn)，建立了船舶油耗量最小和船舶離港延遲時間最短的雙目標(biāo)優(yōu)化模型，設(shè)計了多目標(biāo)遺傳算法對該模型進(jìn)行求解。柴佳祺等人[3]研究了散貨碼頭排船問題，根據(jù)船舶載重多少以及延遲靠泊時間2個指標(biāo)對船舶進(jìn)行排序，考慮單位岸線長度、單船延遲靠泊時間，構(gòu)建連續(xù)性泊位分配優(yōu)化模型，設(shè)計了啟發(fā)式算法求解。Ernest等人[4]主要根據(jù)干散貨碼頭現(xiàn)有情況，考慮潮汐和船長等因素對在錨地的船舶進(jìn)行了時間與空間的排序，建立數(shù)學(xué)模型，設(shè)計了兩階段法，對模型進(jìn)行分段化簡，最后使用CPLEX進(jìn)行求解。張新宇等人[5]對雙向通航港口船舶調(diào)度優(yōu)化問題進(jìn)行了研究，考慮船舶屬性和船舶交通狀況等因素，在航道與泊位協(xié)調(diào)性以及船舶調(diào)度安全性的約束下，建立雙向通航港口船舶調(diào)度多目標(biāo)優(yōu)化模型，設(shè)計了改進(jìn)遺傳算法進(jìn)行求解。鄭紅星等人[6]研究了考慮減載移泊的散貨港口船舶調(diào)度優(yōu)化問題，采用減載移泊策略對船舶進(jìn)行調(diào)度優(yōu)化，建立最小船舶等待時間的混合整數(shù)規(guī)劃模型，設(shè)計了混合算法求解。朱云龍等人[7]等對港口業(yè)船舶進(jìn)行調(diào)度優(yōu)化研究，建立了船舶拖期懲罰費(fèi)用最小的調(diào)度模型，自行設(shè)計啟發(fā)式優(yōu)化算法求解。禹鑫燚等人[8]對自動化停車場調(diào)度問題進(jìn)行了研究，與船舶調(diào)度問題相似，在停車場調(diào)度問題中，為了降低自動化停車場中產(chǎn)生的能耗、車輛等待時間，提出基于啟發(fā)式動態(tài)規(guī)劃的自動化停車場調(diào)度方法，設(shè)計貪心算法求解。針對船舶調(diào)度問題，現(xiàn)有的研究較深入，但是研究過程中均將泊位分配方案默認(rèn)為已知，未將其與船舶調(diào)度集成考慮，也沒有考慮依據(jù)泊位實時情況對船舶進(jìn)出港次序進(jìn)行相應(yīng)調(diào)整，調(diào)度方案不靈活。

在泊位分配方面，Nishimura等人[9]研究了關(guān)于公共泊位系統(tǒng)泊位調(diào)度規(guī)劃的問題，考慮不同集裝箱船對港口泊位的操作能力要求不同等因素，建立以船舶服務(wù)時間最小的目標(biāo)規(guī)劃模型，設(shè)計了抑郁遺傳算法求解。劉杰[10]對集裝箱碼頭泊位分配問題進(jìn)行了研究，分析了集裝箱碼頭泊位分配流程，為降低船舶總在港時間，建立動態(tài)泊位分配模型，設(shè)計了改進(jìn)多層編碼遺傳算法解決問題。曾慶成等人[11]研究了集裝箱碼頭中干擾事件發(fā)生后泊位分配計劃的調(diào)整問題，建立了泊位分配干擾管理模型，設(shè)計了基于局部重調(diào)度與禁忌算法的仿真優(yōu)化算法進(jìn)行求解。張新宇等人[12]研究了基于粒子群優(yōu)化算法的船舶調(diào)度優(yōu)化問題，對船舶進(jìn)行了合理化的泊位分配，考慮航道限制及安全航距等問題，建立模型，設(shè)計了粒子群啟發(fā)式算法求解。唐偉祎[13]對船廠碼頭泊位調(diào)度優(yōu)化問題進(jìn)行了研究，對船廠碼頭進(jìn)行了多層級泊位分配，綜合考慮各調(diào)度優(yōu)化目標(biāo)，建立泊位調(diào)整決策模型，設(shè)計了改進(jìn)遺傳算法求解。童珊[14]在研究集裝箱港口泊位分配問題時，考慮了船舶優(yōu)先權(quán)的限制，根據(jù)船舶到達(dá)情況以及船舶所需靠泊作業(yè)時間等因素，建立了以船舶在港時間最小為目標(biāo)的連續(xù)布置泊位分配模型，設(shè)計了遺傳算法進(jìn)行求解。王軍等人[15]對動態(tài)情況下的泊位調(diào)度方案進(jìn)行了研究，考慮船舶在泊時間受水文氣象等多種復(fù)雜因素的影響，采用動態(tài)學(xué)習(xí)方法對在泊時間計算函數(shù)進(jìn)行更新，對泊位調(diào)度方案進(jìn)行優(yōu)化，設(shè)計包含船舶在泊時間動態(tài)學(xué)習(xí)及泊位調(diào)度方案優(yōu)化的并行算法求解。針對泊位分配問題，參考文獻(xiàn)中大多僅考慮泊位利用率，忽略了實際作業(yè)過程中船舶進(jìn)出港時的各種(船舶會遇和潮汐等)現(xiàn)實約束，這可能導(dǎo)致實際作業(yè)過程中某些船舶無法按時抵達(dá)分配好的泊位；且文獻(xiàn)大多忽略了航道通行限制和船舶進(jìn)出港規(guī)則的約束，這將導(dǎo)致實際作業(yè)過程中因作業(yè)完畢的船舶不能及時出港而造成船舶在港滯留時間過長，或因目標(biāo)泊位可用但船舶無法及時入港而造成泊位大段時間空閑等情況的發(fā)生。

上述國內(nèi)外關(guān)于泊位分配問題的研究在提高港口效率、減少船舶在港滯留時間方面都有不同著重，旨在降低船舶在港滯留時間，給出合理的船舶調(diào)度或者泊位分配方案。但是現(xiàn)有研究主要集中在單方面的船舶調(diào)度或是泊位分配，罕有將兩者集成考慮的文獻(xiàn)。然而在現(xiàn)實情況中，在單向航道的港口中，船舶調(diào)度與泊位分配交錯影響著船舶在港滯留時間，為最小化船舶在港滯留時間，需將泊位分配及船舶調(diào)度進(jìn)行集成優(yōu)化。例如單獨考慮船舶進(jìn)出港，可能出現(xiàn)船舶進(jìn)到港池而泊位不能使用，只考慮泊位分配，而船舶卻不能按期進(jìn)港等。除上述研究外，經(jīng)唐山港、曹妃甸港等港口調(diào)研發(fā)現(xiàn)，大型散貨船滿載時吃水較深，需在特定的深水大泊位進(jìn)行卸載，此時大多數(shù)港口現(xiàn)有深水大泊位數(shù)量不能及時滿足所有抵港大型散貨船的作業(yè)需求。

綜上，不同于以往的研究，本文研究固定計劃期內(nèi)考慮潮汐影響的泊位分配與船舶調(diào)度集成優(yōu)化方案，并在船舶調(diào)度過程中重點關(guān)注減載移泊過程，通過合理地減載移泊過程，為后續(xù)抵港大型散貨船適時提供可用泊位。在減載作業(yè)過程中，兼顧緊后船舶到達(dá)時刻來擇優(yōu)選取減載方案，最終給出最佳的泊位分配方案、船舶進(jìn)出港次序以及減載移泊方案。

1 問題描述

離散型泊位散貨港口海側(cè)的主要組成部分包括錨地、航道以及若干港池，根據(jù)泊位的水深以及泊位上配備裝卸設(shè)備的不同，泊位又分為可服務(wù)大型船舶的深水大泊位和普通泊位，港口的港池以及泊位分布情況示意圖如圖1所示。

港口包括的若干港池中，都擁有上述2種泊位，根據(jù)服務(wù)船型的不同，對泊位進(jìn)行了編號。由于不同船舶所需作業(yè)時間的不同、潮汐以及單向航道等影響因素，不同的船舶進(jìn)出港需滿足一些約束，例如大型散貨船吃水較深，需乘潮進(jìn)出港，為了安全，大型散貨船的緊后進(jìn)港船舶不為大型船。船舶卸載作業(yè)時，針對大型散貨船在深水大泊位減載至滿足普通泊位作業(yè)要求后，才可將其進(jìn)行移泊。據(jù)實際調(diào)查可知，大多數(shù)散貨港口中大型散貨船的比重在20%左右，且均需乘潮進(jìn)出港，而大型深水泊位非常有限。

圖1 港池以及泊位分布情況示意圖

本文的問題可描述為：根據(jù)數(shù)據(jù)分析以及船舶到達(dá)情況可獲知以下信息，包括一個散貨港口48 h內(nèi)的各類散貨船的到達(dá)情況和到達(dá)時刻，不同裝載量的船舶所需要的卸載作業(yè)時間，移泊船舶的耗時情況等信息，考慮潮汐對于大型散貨船進(jìn)出港的影響，船舶的進(jìn)出港規(guī)則(大型散貨船的緊前、緊后進(jìn)出港船舶不為大型散貨船)等限制約束，以48 h內(nèi)所有船舶的總在港時間最小為目標(biāo)，研究考慮減載移泊的散貨港口泊位分配與船舶調(diào)度集成優(yōu)化問題，最終給出船舶進(jìn)出港的最佳次序和船舶的合理泊位分配方案，以及抵港大型散貨船包括減載方案、移泊時刻和移泊位置的最優(yōu)減載移泊方案。

2 減載移泊調(diào)度模型

本文中的泊位分配和船舶調(diào)度問題可看作是一種二層級泊位分配問題。不同屬性的船根據(jù)其預(yù)計達(dá)到時間以及泊位現(xiàn)狀進(jìn)行初級泊位分配，在此基礎(chǔ)上，對個別船舶進(jìn)行減載移泊操作，根據(jù)實時泊位狀態(tài)進(jìn)行二級泊位分配，為移泊船舶提供泊位分配方案。

2.1 符號說明

2.1.1 已知變量

M為足夠大的正整數(shù)；TAi為船i到達(dá)港口的時刻；Qi為i船的載貨量；N為潮汐時段的總段數(shù)；an為第n個潮汐時段的開始時刻；bn為第n個潮汐時段的結(jié)束時刻；Lbb′為泊位b到b′的距離(針對移泊船舶參數(shù)，b為船舶初始作業(yè)泊位，b′為減載后的移泊位置)；vi為i船在港口的航速；Di為i船的吃水；D0為大型散貨船小型散貨船的吃水界限；Db為泊位b的水深；Db′為移泊泊位b′ 的水深；Dbb′為泊位b到移泊泊位b′的距離(針對移泊船舶參數(shù)，b為船舶初始作業(yè)泊位，b′為減載后的移泊位)；Lsij為i船與j船之間航行的安全航距(針對船舶編號參數(shù)，i、j皆為本周期到達(dá)船舶)；tmi,b為船i從錨地到港池b泊位所需時段；tmi,bb′為船i從港池b泊位移動到b′泊位所需時段(針對移泊船舶參數(shù)，b為船舶初始作業(yè)泊位，b′為減載后的移泊位)；ti,b為船i在b泊位作業(yè)的時段；ti, bb′(tj, bb′)為船i(j)在b泊位作業(yè)后在b′泊位作業(yè)的時段(針對移泊船舶參數(shù)，b為船舶初始作業(yè)泊位，b′為減載后的移泊位，針對船舶編號參數(shù)，i、j皆為本周期到達(dá)船舶)；tmi為船舶i從錨地到港池入口的時段；pi為船舶i的卸載效率；Hi為船舶i為大船即為1，否則為0；S為船舶數(shù)集合；B為泊位數(shù)集合。

2.1.2 中間變量

TLi(TLj)為船舶i(j)的離港時刻(針對船舶編號參數(shù)，i、j皆為本周期到達(dá)船舶)；γi,b為船舶i從最后作業(yè)的b泊位離開到港池出口所用的時段；Qi,b(Qi, b′)為船舶i在泊位b(b′)的減載量(針對移泊船舶參數(shù)，b為船舶初始作業(yè)泊位，b′為減載后的移泊位)；tdi為船舶出港等待潮汐時間；T1為泊位可用開始時刻；T2為泊位可用結(jié)束時刻。

2.1.3 決策變量

Pi為i船的減載率Tsi,b(Tsj,b)為船舶i(j)開始在泊位b作業(yè)的時刻(針對船舶編號參數(shù)，i、j皆為本周期到達(dá)船舶)。

(1)

Tsi,b-tmi,b≥TAi,?i∈S,?b∈B

(2)

Tsi,b-an≥M(3-Zi,n-xi,b-Hi),

?i∈S, ?b∈B(3)

bn-Tsi,b≥M(3-Zi,n-xi,b-Hi),

?i∈S, ?b∈B(4)

(5)

bn-(TLi,b-γi,b)≥M(3-Ui,n-xi,b-Hi),

?i∈S, ?b∈B(6)

TLi,b-γi,b-an≥M(3-Ui,n-xi,b-Hi),

?i∈S, ?b∈B(7)

(8)

Db-Di≥M(1-xi,b), ?i∈S, ?b∈B

(9)

Db′-Di(1-Pi)≥M(3-Ni-Hi-xi,b′),

?i∈S, ?b′∈B(10)

?i,j∈S, ?b∈B(11)

Qi-Qi,b=M(1-xi,b+Ni),?i∈S,?b∈B

(12)

Qi-Qi,b-Qi,b′=M(3-xi,b-xi,b′-Ni),

?i∈S, ?b,b′∈B(13)

?i∈S, ?b∈B(14)

T1-Tsi,b≥M(2-AT1,b-xi,b),

?i∈S, ?b∈B(15)

Tsi,b-T2≥M(2-AT2,b-xi,b),

?i∈S, ?b∈B(16)

≥M(5-Ni-Hi-AT1,b-AT2,b-xi,b),

?i∈S, ?b∈B(17)

≥M(5-Ni-Hi-xi,b′-AT2,b-xi,b),

?i∈S, ?b,b′∈B(18)

≥M(5-Ni-Hi-xi,b′-AT2,b-xi,b),

?i∈S, ?b,b′∈B(19)

TLj-γj,b-tj,bb′-tmj,bb′-tj,b-(TLi-γi,b-ti,bb′

-tmi,bb′-ti,b)≥M(5-Ni-Hi-Nj-Hj-xij),

?i,j∈S, ?b,b′∈B(20)

TLj-TLi≥M(1-xij), ?i,j∈S

(21)

(22)

TLj-γj,b-tmj,bb′-(TLi-γi,b-tmi,bb′)≥M(1-xij),

?i,j∈S, ?b,b′∈B(23)

TLj-γj,b-tmj-(TLi-γi,b-tmi)≥M(1-xij),

?i,j∈S,?b∈B(24)

?i,j∈S(25)

+γi,bxi,b+tdiHi, ?i,j∈S, ?b,b′∈S

(26)

AT1,b,AT2,b,Ni,Yij,b,xij,Zi,n,Ui,n,xi,b∈{0,1}

Tsi,b,Qi,b,Pi,γi,b,TLi≥0 (27)

上述模型中，目標(biāo)函數(shù)為一固定周期內(nèi)船舶總在港時間最小(其中每艘船的在港滯留時間為船舶入港時刻開始加上等待進(jìn)港潮汐時段、錨地入口行駛時段、入口泊位行駛時段、在初始泊位作業(yè)時段、移泊時段、移泊后作業(yè)時段、等待出港潮汐時段、泊位到出口作業(yè)時段、安全行距等在港時間，最后減去船舶的抵港時刻)。約束條件中，式(2)為開始操作時間晚于到達(dá)港口時間。式(3)～(8)為潮汐進(jìn)出港規(guī)則，大型散貨船的進(jìn)出港都要在潮汐時段結(jié)束并且每艘大型船舶只能選擇一個潮汐時段進(jìn)出港。式(9)～(10)為港池水深與船舶吃水限制，船舶的作業(yè)泊位滿足該船的吃水要求，減載后的船舶移泊泊位的水深滿足此時該船的吃水。式(11)表示同泊位作業(yè)的緊后船舶開始作業(yè)時刻晚于緊前船舶結(jié)束時間，即為緊前操作限制。式(12)～(13)保證船舶在作業(yè)泊位的卸載量與其裝載量相等，且有減載移泊操作的船舶在前后2個泊位的卸載量滿足船舶在此港的卸載要求。式(14)～(16)表示船舶i在選擇泊位作業(yè)時要保證泊位處于可用狀態(tài)并且在可用時段內(nèi)，船舶可以完成卸載操作。式(17)～(19)表示移泊船舶i在移泊時選擇的移泊泊位是可用的，且保證在泊位可用時間段內(nèi)能將剩余貨卸載完成。式(20)～(24)為安全航距，緊前緊后兩艘船進(jìn)出港或在港池內(nèi)移動時保持安全航距，在同一泊位作業(yè)的2艘船需保持安全航距，且當(dāng)其抵達(dá)泊位時，緊前作業(yè)船舶已作業(yè)完畢移出。式(25)為根據(jù)港口的一般作業(yè)規(guī)則，大型散貨船緊前緊后船舶不為大船。式(26)表示船舶離港時刻是其開始操作時刻、操作時段、移泊時段、進(jìn)出港移動時段以及出港時刻等待潮汐時段的加和。

3 求解算法

綜合已有文獻(xiàn)，關(guān)于船舶調(diào)度問題大多采用啟發(fā)式算法求解(如文獻(xiàn)[1-3，5，6，8])，在泊位分配問題的研究中大都采用遺傳算法(如文獻(xiàn)[9，10，13，14])求解，但考慮船舶調(diào)度和泊位分配集成問題的復(fù)雜性，且該問題屬于NP Hard問題，此時單純的采用遺傳算法解決問題的效率較低，受文獻(xiàn)[6，11]等文獻(xiàn)的啟發(fā)，本文設(shè)計了融入禁忌搜索思想的改進(jìn)遺傳算法，即在遺傳算法中引入禁忌表來提高求解效率。

本文的改進(jìn)遺傳算法主要包括5大部分，分別是：根據(jù)初始種群生成策略生成初始種群；解的排序與選擇，組成配對組；配對組進(jìn)行交叉、變異等操作產(chǎn)生新種群；對不可行解以及較差解進(jìn)行基因修復(fù)；引入禁忌表避免算法陷入局部最優(yōu)。5個部分的具體流程分別在3.1～3.5節(jié)中進(jìn)行了詳細(xì)解釋。除此之外，算法中對最優(yōu)解進(jìn)行了2次篩選操作，通過邏輯梳理對最優(yōu)解進(jìn)行記錄與選擇，得到更全面更優(yōu)化解的集群并為禁忌表的更新提供便利。綜上，運(yùn)用此改進(jìn)遺傳算法，對模型進(jìn)行求解得到優(yōu)化結(jié)果。算法流程為首先根據(jù)港口船舶泊位的現(xiàn)實情況生成初始種群，其次對初始種群中的解進(jìn)行排序選擇形成配對組，之后對配對組進(jìn)行交叉變異等操作生成新種群，然后對新種群進(jìn)行基因修復(fù)，對修復(fù)后的解進(jìn)行篩選得到較為全面的解，接著基于禁忌搜索思想對新種群進(jìn)行篩選(若新種群的最優(yōu)解曾在之前的迭代中存在，則選擇次一級最優(yōu)解)，不斷更新禁忌表。以此框架進(jìn)行多次迭代，算法流程如圖2所示。

圖2 算法流程圖

3.1 染色體編碼與初始種群生成策略

根據(jù)船舶抵港時刻先后進(jìn)行編號，考慮船舶初始作業(yè)位置，船舶減載量以及船舶移泊位置等信息進(jìn)行多層編碼，編碼情況如圖3所示。

圖3 5層染色體編碼

例如①抵港船舶6預(yù)計在泊位3作業(yè)減載量選擇1，移泊位置為12；②抵港船舶8預(yù)計在泊位6作業(yè)減載量選擇0，此時不移泊，所以移泊位置為0；③與①選擇的預(yù)計作業(yè)泊位相同，此時為了保證不沖突，選擇其中之一在錨地等待。對預(yù)計抵港散貨船分別編碼，將船舶與泊位進(jìn)行匹配。

根據(jù)多層染色體編碼設(shè)計，由于船舶預(yù)計作業(yè)位置、船舶移泊與否以及移泊船舶減載量等因素協(xié)同影響著船舶的總在港滯留時間，制定如下生成策略。

步驟1初始化相關(guān)參數(shù)，P表示第1層編碼船舶數(shù)量，Q表示第2層編碼可選擇泊位數(shù)量，t表示種群內(nèi)個體序號，t=1；

步驟2隨機(jī)在P中選擇一個隨機(jī)整數(shù)，從而生成t的第1行，根據(jù)第1行P的船舶基礎(chǔ)信息，根據(jù)其吃水要求，在Q中隨機(jī)選擇一個滿足作業(yè)要求的整數(shù)，生成為t的第2行；

步驟3根據(jù)第1行P的船舶基礎(chǔ)信息，當(dāng)其為大型散貨船時，隨機(jī)生成[0,1]整數(shù)，0表示不進(jìn)行移泊操作，1表示進(jìn)行移泊操作，從而生成t的第3行；

步驟4當(dāng)t的第3行為0時，t的第4行為0，表示其不進(jìn)行減載移泊操作；當(dāng)t的第3行為1時，隨機(jī)生成(0，1)區(qū)間內(nèi)的隨機(jī)數(shù)a，a≤0.5時，a的第4行取值為1，表示其減載量為第1種情況；a>0.5時，t的第4行取值為2，表示其減載量為其他情況；

步驟5當(dāng)t的第3行與第4行為0時，其第5行為0；當(dāng)t的第3行與第4行不為0時，隨機(jī)在Q中選擇一個整數(shù)，生成為t的第5行；

步驟6令t=t+1，當(dāng)t大于種群規(guī)模T時，則結(jié)束，否則令i=1執(zhí)行步驟2。

3.2 解的排序與選擇

本文采用輪盤賭選擇優(yōu)勝個體，對其進(jìn)行交叉變異等操作生成下一代，具體步驟如下。

步驟1根據(jù)個體的適應(yīng)度值在整個群體的適應(yīng)度總和中所占的比例，按從小到大進(jìn)行排序；

步驟2按排序?qū)⒈戎抵鹨化B加，如排位第2的值變?yōu)槠浔旧淼闹蹬c排位第1的值之和，以此類推更新排序數(shù)組；

步驟3產(chǎn)生一個[0,1]之間均勻隨機(jī)數(shù)，根據(jù)該隨機(jī)數(shù)在排序中的位置確定對應(yīng)的個體，將其作為父代個體；

步驟4個體被選后，重復(fù)步驟2選擇新的父代個體，將2個個體組成交配對，以供后面的交叉操作；

步驟5重復(fù)步驟2～4操作，直至操作次數(shù)等于種群規(guī)模。

3.3 新個體生成策略

每次迭代，對根據(jù)適應(yīng)度評估選擇出的每對交配對進(jìn)行如下操作，生成新個體。

步驟1產(chǎn)生一個[0,1]之間均勻隨機(jī)數(shù)，若該隨機(jī)數(shù)小于交叉概率，則進(jìn)行步驟2，否則進(jìn)行步驟3；

步驟2若該隨機(jī)數(shù)小于變異概率，則進(jìn)行步驟5，否則進(jìn)行步驟4；

步驟3保持原染色體，直接遺傳到下一代；

步驟4交叉為選取最優(yōu)個體的第2層至第5層的部分染色體片段，與交配對另一染色體對應(yīng)部分進(jìn)行交叉，形成新的染色體；

步驟5變異為任選一染色體，針對其第2層船舶預(yù)計作業(yè)泊位或第5層移泊船舶移泊位置進(jìn)行變異操作，替換為其他泊位編號。

3.4 基因修復(fù)

在新個體生成的過程中可能存在下述情況：(1)大型散貨船初始分配泊位為淺水區(qū)泊位，船舶無法靠泊操作；(2)小型散貨船進(jìn)行移泊操作。針對這2種情況要進(jìn)行基因修復(fù)，使不可行解或較劣解變?yōu)榭尚薪猓唧w步驟如下。

步驟1針對任意個體，當(dāng)針對第1層編碼船舶狀態(tài)為大型船時，當(dāng)?shù)?層編號對應(yīng)的泊位水深滿足船舶吃水時，則轉(zhuǎn)到步驟2，否則轉(zhuǎn)到步驟3；

步驟2針對任意個體，當(dāng)針對第1層編碼船舶狀態(tài)為小型船時，當(dāng)?shù)?層編碼為0，則轉(zhuǎn)到步驟5，否則轉(zhuǎn)到步驟4；

步驟3在深水泊位編號中任選其一替換第2層編碼原編號，轉(zhuǎn)到步驟2;

步驟4將此個體第3層編碼至第5層編碼都設(shè)置為0，轉(zhuǎn)到步驟5；

步驟5輸出新生成的個體。

3.5 禁忌表

為避免同一個體多次出現(xiàn)，把個體的適應(yīng)度值設(shè)為禁忌對象，設(shè)置短禁忌表和禁忌表，分別為Ta×1與TA×1的矩陣，TA為禁忌表長度，Ta為短禁忌表長度，每次迭代完成重復(fù)下述步驟。

步驟1當(dāng)?shù)螖?shù)小于Ta，在短禁忌表依次前1行替換后1行，根據(jù)適應(yīng)度值排序，將在短禁忌表中未出現(xiàn)過的適應(yīng)度值置于第1行，更新短禁忌表，并把此適應(yīng)度值對應(yīng)的個體作為下次迭代的初始最優(yōu)個體；

步驟2當(dāng)?shù)螖?shù)大于Ta，根據(jù)適應(yīng)度值從小到大的順序選擇對應(yīng)個體，若此適應(yīng)度值在短禁忌表中存在，即被標(biāo)記時，選擇次一級最優(yōu)適應(yīng)度值，直至該適應(yīng)度值未被標(biāo)記。根據(jù)此適應(yīng)度值在長禁忌表中出現(xiàn)的次數(shù)，記錄m=m+1，當(dāng)m>M，即容忍的最多出現(xiàn)次數(shù)時，重新選取個體；

步驟3以短禁忌表的最后一行作為長禁忌表的第1行，從第2行開始前一行替換后一行，不斷更新禁忌表，并把第1行的適應(yīng)度值對應(yīng)的個體作為下次迭代的初始最優(yōu)個體。

4 算例分析

設(shè)定某單向航道散貨港口擁有4大港池，各港池內(nèi)分別擁有9、8、7、8個離散型泊位，依次編號為B= {1,2, … ,32}，其中1、24、32泊位為大型泊位，水深為20～30 m，為大型散貨船提供減載移泊服務(wù)，其余為小型泊位水深為12～20 m。根據(jù)離航道入口距離，分別編號港池為1、2、3、4，其中1～9號泊位位于1號港池，10～17號在2號港池，18～24在3號港池，25～32在4號港池。

由于船舶大小不同，船舶卸載時，提供的卸載艙口不同，此時會產(chǎn)生不同的卸載率，綜合來看大型散貨船卸載率為0.83萬噸/h，中小型船舶減載率為0.5萬噸/h；大型散貨船的減載量可選擇70%或者85%。

從錨地區(qū)域開始計算，船舶由錨地航行至航道口入口的時間為1 h；船舶從港池入口到泊位，泊位到航道出口；泊位到泊位等各個航行時間在0.2～0.5 h區(qū)間內(nèi)。

據(jù)唐山港、曹妃甸港等地的調(diào)研數(shù)據(jù)可知，船舶的卸載周期一般在24～48 h之間，本文以48 h作為1個調(diào)度周期，周期內(nèi)共有4個潮汐時段，乘潮船舶所占比重為13%，船舶間的安全航行距離為50 min，整個周期中船舶的到達(dá)時刻以及船舶的基礎(chǔ)信息、乘潮情況如表1所示。

表1 船舶的基礎(chǔ)信息表

注:1表示乘潮，0表示不乘潮

4.1 解決方案

應(yīng)用本文模型與算法，運(yùn)用Matlab R2014a軟件進(jìn)行本文算法的編程實現(xiàn)，設(shè)定遺傳算法相關(guān)參數(shù)：種群規(guī)模為50，迭代次數(shù)為1 500次，P1和P2分別取值0.9和0.1，文中實驗都運(yùn)行在3.1 GHz Intel Core 2 CPU和4 GB內(nèi)存的雙核計算機(jī)上。運(yùn)行收斂圖如圖4所示。

圖4 算法運(yùn)行收斂圖

優(yōu)化方案結(jié)果為此情況60艘船總在港時間為1 549 h，船舶進(jìn)出安排如下。

1-2-4-5-6-7-8-11-12-14-15-16-18-17-20-22-27-28-3-32-33-21-34-26-30-13-35-38-9-23-29-41-43-45-39-36-42-46-24-19-47-48-49-50-25-51-53-52-55-56-10-54-57-59-37-60-44-31-58-40。分配方案如圖5所示。

圖5 船舶作業(yè)分配方案

4.2 對比方案

分別設(shè)計不考慮移泊以及不考慮變換減載量的解決方案，驗證方案的可行性。除了本文的減載移泊分配方案(方案1)外，設(shè)計方案2為1次移泊，船舶卸載至70%選擇移泊與否；方案3為先到先服務(wù)，船舶不移泊。方案對比結(jié)果如表2所示。

由表2可知，本文方案相較于方案2的平均優(yōu)化率為0.060832，相較方案3的平均優(yōu)化率為0.130110，表明了減載移泊的重要性。另相較于固定減載量，靈活地對減載量進(jìn)行不同的選擇，可更有效地降低船舶在港滯留時間。綜上，本文方案可在較大程度上減少船舶在港滯留時間，優(yōu)化效果較好。

4.3 算法有效性驗證

為了驗證算法有效性，利用linGo求得精確解，并與本文的算法結(jié)果進(jìn)行對比，不同規(guī)模的算法實驗結(jié)果如表3所示。

表2 方案對比結(jié)果

表3 算法比較結(jié)果

由表3可知，當(dāng)船舶與泊位數(shù)量按比例增加時，相比于linGo解的目標(biāo)函數(shù)值，本文算法的優(yōu)化結(jié)果偏差都在10%以內(nèi)；且很多算例中l(wèi)inGo的運(yùn)行時間過長，甚至無法在有效的時間內(nèi)給出結(jié)果，而本文算法的運(yùn)行時間均在3 min左右。綜上，本文設(shè)計的算法可在較短時間內(nèi)得到較好的優(yōu)化解，尤其是適用于中大規(guī)模的算例求解。

5 結(jié) 論

針對散貨碼頭深水大泊位數(shù)量不足，大型散貨船的在港滯留時間過長等問題，本文對散貨港口泊位分配與船舶調(diào)度進(jìn)行集成優(yōu)化研究，并給出了優(yōu)化的減載移泊方案，有效地降低了所有船舶在港滯留時間。結(jié)果表明，在不增加大泊位數(shù)量的前提下，合理地設(shè)計減載移泊方案，并將泊位分配與船舶進(jìn)出港優(yōu)化集成為一體，可有效提高碼頭的服務(wù)水平。

考慮問題的特點，設(shè)計了可規(guī)避不可行解的編碼方案，并在遺傳算法中嵌入禁忌表來有效地跳出局部最優(yōu)解，為解決此類問題的算法提供思路。

考慮到船舶到港時間具有不確定性，進(jìn)一步的研究可考慮船舶動態(tài)到港的情況下港口泊位分配與船舶調(diào)度的集成優(yōu)化問題。