鄭紅星 姜 雪 段 爽

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

0 引 言

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

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

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

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

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

1 問(wèn)題描述

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

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

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

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

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

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

2.1 符號(hào)說(shuō)明

2.1.1 已知變量

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

2.1.2 中間變量

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

2.1.3 決策變量

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

3 求解算法

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

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

圖2 算法流程圖

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

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

圖3 5層染色體編碼

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

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

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

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

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

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

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

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

3.2 解的排序與選擇

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

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

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

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

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

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

3.3 新個(gè)體生成策略

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

步驟1產(chǎn)生一個(gè)[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)個(gè)體的第2層至第5層的部分染色體片段，與交配對(duì)另一染色體對(duì)應(yīng)部分進(jìn)行交叉，形成新的染色體；

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

3.4 基因修復(fù)

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

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

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

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

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

步驟5輸出新生成的個(gè)體。

3.5 禁忌表

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

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

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

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

4 算例分析

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

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

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

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

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

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

4.1 解決方案

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

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

優(yōu)化方案結(jié)果為此情況60艘船總在港時(shí)間為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 對(duì)比方案

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

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

4.3 算法有效性驗(yàn)證

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

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

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

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

5 結(jié) 論

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

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

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