考慮網(wǎng)絡(luò)脆弱性的灣區(qū)港口泊位調(diào)度研究

朱益輝 賀紅燕 李彥蒼

1(長(zhǎng)安大學(xué)信息工程學(xué)院 陜西 西安 710000)2(河北政法職業(yè)學(xué)院 河北 石家莊 050000)3(河北工程大學(xué)水利水電學(xué)院 河北 邯鄲 056002)

0 引 言

灣區(qū)是指由一個(gè)或多個(gè)相連的海灣及臨近島嶼共同組成的區(qū)域，具有特點(diǎn)鮮明的經(jīng)濟(jì)形態(tài)，是濱海城市進(jìn)入下一個(gè)發(fā)展階段的顯著標(biāo)志。2017年起，我國(guó)提出粵港澳大灣區(qū)發(fā)展方略，灣區(qū)建設(shè)勢(shì)必成為經(jīng)濟(jì)增長(zhǎng)新風(fēng)口。灣區(qū)港口數(shù)目充足、位置鄰近，具備統(tǒng)一規(guī)劃、綜合利用的前提與基礎(chǔ)。研究灣區(qū)港口調(diào)度相關(guān)理論，實(shí)施科學(xué)有效的調(diào)度方案，可充分發(fā)揮其得天獨(dú)厚的地緣優(yōu)勢(shì)，提高整個(gè)灣區(qū)水路運(yùn)輸網(wǎng)絡(luò)的強(qiáng)健性與高效性，一方面增強(qiáng)對(duì)個(gè)別港口關(guān)閉導(dǎo)致商貿(mào)停擺的抵御能力，另一方面使物流效率大幅提高。

港口調(diào)度問(wèn)題涵蓋泊位調(diào)度、岸橋調(diào)度以及貨物堆場(chǎng)、運(yùn)載小車(chē)調(diào)度等多個(gè)子問(wèn)題，符合流水車(chē)間調(diào)度策略(Hybrid flow shop scheduling，HFSS)模式，具有NP-Hard屬性，無(wú)法明確得到全局最優(yōu)形式解。為簡(jiǎn)化該復(fù)雜問(wèn)題，前人研究主要在單一港口調(diào)度規(guī)劃場(chǎng)景下展開(kāi)，針對(duì)不同需求及約束環(huán)境，對(duì)模型升級(jí)改進(jìn)，并采用智能算法在規(guī)定時(shí)間內(nèi)求得可接受的帕累托最優(yōu)解。孫麒等[1]以運(yùn)營(yíng)成本最小為優(yōu)化目標(biāo)，考慮艦船錨海等待、艦船延期離崗、接卸任務(wù)作業(yè)三部分對(duì)整體目標(biāo)帶來(lái)的影響，構(gòu)造了經(jīng)典泊位調(diào)度求解模型，創(chuàng)新地以基于熵的Topsis方法計(jì)算船只優(yōu)先度，提高了求解效率。王軍等[2]提出船只停泊時(shí)間受水文氣象等諸多因素影響，為時(shí)變型復(fù)雜變量，由此引入動(dòng)態(tài)學(xué)習(xí)方法，在實(shí)際數(shù)據(jù)測(cè)試中可達(dá)10%以上的成本削減。鄭紅星等[3]考慮潮汐對(duì)船舶停靠的限制，設(shè)計(jì)了三階段混合遺傳求解算法。胡鴻韜等[4]考慮了岸橋維護(hù)情況，以船舶停泊的時(shí)間和最小化為優(yōu)化目標(biāo)，采用粒子群算法進(jìn)行求解。王寧寧等[5]則針對(duì)散雜貨港口特有的隨機(jī)性和不確定性，提出了場(chǎng)存平衡指標(biāo)，在實(shí)際數(shù)據(jù)測(cè)試中優(yōu)于人工調(diào)度。謝晨等[6]綜合泊位、岸橋、集卡、場(chǎng)橋等場(chǎng)景，提出了HFSS下的三階段調(diào)度模型，設(shè)計(jì)了改進(jìn)Johnson規(guī)則的啟發(fā)式算法。陳寧等[7]在HFSS模式上針對(duì)雙小車(chē)岸橋問(wèn)題進(jìn)行深入探討，以作業(yè)完工時(shí)間最小化為目標(biāo)，設(shè)計(jì)的改進(jìn)遺傳算法比傳統(tǒng)粒子群算法具有更高的求解效率。綜上，雖然針對(duì)港口泊位已有大量研究，但主要針對(duì)單一港口場(chǎng)景，未涉及多港口交互情況，因此，如何通過(guò)合理調(diào)度規(guī)劃，有效利用灣區(qū)內(nèi)多港口的協(xié)調(diào)互補(bǔ)關(guān)系，充分發(fā)揮水運(yùn)網(wǎng)絡(luò)的強(qiáng)健性和高效性，仍存在較大研究空間，具有重要研究意義。

本文基于灣區(qū)港口水運(yùn)實(shí)際情況，引入網(wǎng)絡(luò)脆弱性定義，度量網(wǎng)絡(luò)在突發(fā)情況下的抗干擾能力，與耗時(shí)成本加權(quán)線性組合，構(gòu)成目標(biāo)函數(shù)，使優(yōu)化方向達(dá)到網(wǎng)絡(luò)強(qiáng)健性與高效性的理想權(quán)衡。此外，本文設(shè)計(jì)了有關(guān)泊位水深與船只排水量匹配關(guān)系、泊位數(shù)目、裝卸任務(wù)量等條件的約束集合，并模擬了突發(fā)情況下特定港口封閉引起的船只轉(zhuǎn)移，驗(yàn)證了該方法可在保持較高運(yùn)輸效率的前提下有效提高網(wǎng)絡(luò)魯棒性。

1 灣區(qū)港口泊位調(diào)度模型

基于灣區(qū)港口實(shí)際運(yùn)輸場(chǎng)景，本文構(gòu)造模型時(shí)遵循以下假設(shè)：(1) 船只卸貨任務(wù)必須全部完成；(2) 無(wú)突發(fā)情況下泊位及岸橋可供船只一直使用；(3) 深水泊位可供排水量小的船只使用；(4) 泊位與岸橋相對(duì)固定，岸橋不能在泊位間移動(dòng)；(5) 船只在被分配的泊位附近水域錨停等待卸貨；(6) 執(zhí)行卸貨任務(wù)的前后船只緊密貼合，流水作業(yè)，忽略切換時(shí)間；(7) 船只在泊位間轉(zhuǎn)移的距離按所屬港口間距離計(jì)算；(8) 某一港口發(fā)生突發(fā)事件時(shí)，該港口內(nèi)所有泊位均被關(guān)閉，且在任務(wù)期內(nèi)不可恢復(fù)開(kāi)放；(9) 船只卸貨速率均勻；(10) 原分配泊位被關(guān)閉的船只向?yàn)硡^(qū)內(nèi)可用泊位轉(zhuǎn)移。

港口調(diào)度問(wèn)題涉及泊位、岸橋、堆場(chǎng)、運(yùn)載小車(chē)多個(gè)媒介，模型復(fù)雜繁瑣。為突出研究灣區(qū)場(chǎng)景下多港口綜合利用帶來(lái)的性能提升，本文僅針對(duì)泊位調(diào)度問(wèn)題進(jìn)行討論，把問(wèn)題抽象為高維域下的組合優(yōu)化問(wèn)題。

顯然，一次分配指派行為可以用三維特征組(船號(hào)，泊位號(hào)，序號(hào))進(jìn)行唯一表示，即自變量屬于三維自變量，可以用柱狀圖表征，如圖1所示。

因此，將優(yōu)化決策自變量表示為矩陣XN×M。其中N為可供使用的泊位數(shù)，M為船只總數(shù)，N、M均為正整數(shù)，xn,m為自然數(shù)，表示m號(hào)船只分配在n號(hào)泊位的第xn,m位序列中，且1≤n≤N,1≤m≤M。

(1)

1.1 網(wǎng)絡(luò)脆弱性

網(wǎng)絡(luò)脆弱性用于衡量在港口自然布局與船只調(diào)度方案給定的條件下，灣區(qū)水運(yùn)網(wǎng)絡(luò)的強(qiáng)健性。強(qiáng)健性可具體描述為對(duì)突發(fā)情況具備較好的抗干擾能力，即當(dāng)部分港口關(guān)閉時(shí)，整個(gè)網(wǎng)絡(luò)的貨物流轉(zhuǎn)依然穩(wěn)定維持的能力。網(wǎng)絡(luò)脆弱性的計(jì)算借鑒了文獻(xiàn)[8-9]提出的網(wǎng)絡(luò)效能及節(jié)點(diǎn)重要性定義。水運(yùn)網(wǎng)絡(luò)各港口構(gòu)成圖為G(K,H)，其中K為港口集合，H為港口間兩兩構(gòu)造的航線集合，則任一港口i的重要性Ii可通過(guò)刪除該港口對(duì)整個(gè)網(wǎng)絡(luò)效率的影響程度進(jìn)行衡量。計(jì)算公式為：

(2)

式中：E為網(wǎng)絡(luò)整體效率，Ei為網(wǎng)絡(luò)刪除點(diǎn)i后的效率。計(jì)算方法為：

(3)

式中：dij表示從港口i到j(luò)的最短路徑長(zhǎng)度，P為灣區(qū)內(nèi)港口個(gè)數(shù)。網(wǎng)絡(luò)整體效率的定義為：網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間最短路徑長(zhǎng)度的倒數(shù)和的平均值。

根據(jù)文獻(xiàn)[9]，有：

結(jié)論1網(wǎng)絡(luò)效率越高，表示物流在各節(jié)點(diǎn)間傳輸越方便；反之，效率越低，表示物流傳輸越慢。

綜合結(jié)論1及式(2)、式(3)，有推論1、推論2。

推論1網(wǎng)絡(luò)節(jié)點(diǎn)的重要性越高，對(duì)整個(gè)網(wǎng)絡(luò)效率的影響程度越大，可以理解為該網(wǎng)絡(luò)節(jié)點(diǎn)在網(wǎng)絡(luò)中的可替代性較差。

推論2要降低網(wǎng)絡(luò)脆弱性，顯然應(yīng)該合理規(guī)劃船只與港口的匹配關(guān)系，使得任意港口出現(xiàn)緊急情況時(shí)，都能找到充足的替代性資源為后續(xù)船只服務(wù)。

基于推論1和推論2，在各網(wǎng)絡(luò)節(jié)點(diǎn)重要性Ii已知的基礎(chǔ)上，對(duì)網(wǎng)絡(luò)脆弱性有如下定義：

(4)

1.2 耗時(shí)成本

船只在港逗留時(shí)間是泊位調(diào)度模型的核心優(yōu)化指標(biāo)，逗留時(shí)間越長(zhǎng)，一方面意味著油料、人工等成本耗費(fèi)越大，另一方面意味著港口的吞吐量越小，單位時(shí)間產(chǎn)出利潤(rùn)越低。因此，壓縮船只在港逗留時(shí)間對(duì)提升港口的效率具有重要意義。

本文計(jì)算耗時(shí)成本C時(shí)考慮了不同船只的貨物運(yùn)載量情況，其定義如下：

(5)

式中：Tm為m號(hào)船的逗留時(shí)間，計(jì)算如下：

(6)

1.3 約束條件與模型設(shè)計(jì)

為綜合考慮網(wǎng)絡(luò)脆弱性與耗時(shí)成本，本文采用加權(quán)線性和的形式將兩項(xiàng)優(yōu)化目標(biāo)結(jié)合，構(gòu)成目標(biāo)函數(shù)，另外，結(jié)合實(shí)際場(chǎng)景，設(shè)計(jì)了涵蓋港口水深承載能力、任務(wù)必須全部完成、泊位一個(gè)時(shí)刻只能停一艘船三方面的約束條件，構(gòu)成如下模型表示式：

minf(XN×M)=w1·D+w2·C

(7)

s.t.

xn,m=0,?n∈MidBerth,?m∈HeavyShip

(8)

xn,m=0,?n∈ShallowBerth,?m∈MidShip∪HeavyShip

(9)

(10)

Confit(X1×m(n))=0 ?n∈[1,2,…,N]

(11)

其中：式(7)中D表示網(wǎng)絡(luò)脆弱性，如式(4)所示；C表示耗時(shí)成本，其計(jì)算如式(5)所示；w1、w2分別為網(wǎng)絡(luò)脆弱性與耗時(shí)成本的加權(quán)系數(shù)。式(8)、式(9)表示泊位與船只水深約束條件。其中，將泊位全集Berch={1,2,…,M}，劃分為三個(gè)不相交的子集：淺水深泊位集合ShallowBerth，中水深泊位MidBerth和深水泊位集合DeepBerth；將船只全集Ship={1,2,…,N}，劃分為三個(gè)不相交子集：小型船只集合SmallShip，中型船只集合MidShip和大型船只集合HeavyShip。匹配關(guān)系為：小型船只可停靠全部泊位；中型船只可停靠中、深水泊位；大型船只可停靠深水泊位。式(10)表示卸貨任務(wù)必須全部完成，其中Φ(·)為標(biāo)志函數(shù)，用于指示數(shù)值是否為零：

(12)

因此，式(10)保證了在列向量XN×m=[x1,m,x2,m,…,xN,m]T中，有且只有一個(gè)元素不等于0，保證了每艘船只必定被分配一個(gè)且只有一個(gè)泊位進(jìn)行卸載作業(yè)。

式(11)表示在同一個(gè)泊位上的卸貨船只不可出現(xiàn)排序沖突情況，其中，Xn×M為自變量矩陣中的任意行構(gòu)成的行向量Xn×M=[xn,1,xn,2,…,xn,M]T。

函數(shù)f(X)=Confit(X)為序列沖突指示函數(shù)，針對(duì)輸入向量中的所有元素作兩兩遍歷，檢查是否存在取值相同的沖突項(xiàng)。

(13)

當(dāng)X長(zhǎng)度為M時(shí)，函數(shù)Confit(X)需要完成M(M-1)/2次加法運(yùn)算。

2 基于約束適應(yīng)的改進(jìn)遺傳算法

為了充分考慮灣區(qū)港口運(yùn)輸網(wǎng)絡(luò)脆弱性和耗時(shí)成本，從而較好的應(yīng)用文中所提出的灣區(qū)港口泊位調(diào)度模型，在研究過(guò)程中，提出了一種基于約束適應(yīng)的改進(jìn)遺傳算法，一方面保證模型的有效性，另一方面也提高模型應(yīng)用的執(zhí)行效率。遺傳算法作為一種成熟的智能算法，具有設(shè)計(jì)簡(jiǎn)單、收斂較快、計(jì)算復(fù)雜度低等優(yōu)點(diǎn)，在調(diào)度問(wèn)題中廣泛應(yīng)用。本文在經(jīng)典遺傳算法的基礎(chǔ)上，結(jié)合模型實(shí)際對(duì)流程進(jìn)行改進(jìn)，在子代產(chǎn)生階段插入重排序階段，避免了約束校驗(yàn)中的繁瑣計(jì)算，提高了算法迭代速度。

算法以自變量矩陣為自然基因編碼，構(gòu)造的交叉、變異遺傳算子實(shí)施示意如下。

交叉算子：

變異算子：

為使遺傳變化更靈活，算法在基因編碼矩陣內(nèi)部引入行向量的自我交叉算子。

自我交叉算子：

顯然，上述變化過(guò)程難以保證產(chǎn)生子代符合模型約束條件，因此在對(duì)子代進(jìn)行適應(yīng)度函數(shù)計(jì)算及擇優(yōu)繁育前，需要先進(jìn)行約束條件校驗(yàn)。然而，由于式(11)計(jì)算量大，在迭代次數(shù)較大時(shí)將導(dǎo)致算法求解速度顯著降低。

為了提高模型求解效率，在約束校驗(yàn)前加入基于快速排序算法的重排序處理，使子代中所有基因矩陣的行向量?jī)?nèi)元素實(shí)現(xiàn)不重復(fù)排序，從而避免沖突情況。該方法生成的子代必定滿足式(11)，因此可在計(jì)算流程中免除該約束的校驗(yàn)，從而降低了計(jì)算量。重排處理算法步驟如下。

重排序處理算法

Step1以子代基因矩陣中的行向量為待排序元素集合。

Step2在待排序元素集合中任意選擇數(shù)a作為基準(zhǔn)元素。

Step3對(duì)集合內(nèi)剩余元素，與a進(jìn)行比較，若元素小于a，則劃歸θleft左集合，置于a的左邊。若元素大于a，則劃歸θright右集合，置于a的右邊。

Step4對(duì)θleft、θright集合，分別任意選擇數(shù)b、數(shù)c作為基準(zhǔn)元素，對(duì)集合進(jìn)行劃分，構(gòu)成四個(gè)集合θleft-left、θleft-right、θright-left、θright-right。

Step5在上述四個(gè)集合中繼續(xù)重復(fù)上述操作，將集合不停切分直至所有元素規(guī)則固定，則實(shí)現(xiàn)對(duì)整個(gè)集合的排序。

(14)

顯然，有：

(15)

因此，改進(jìn)后的遺傳算法可顯著減少計(jì)算量，提高算法迭代求解速率。

3 仿真實(shí)驗(yàn)及結(jié)果分析

為驗(yàn)證本文所提出的模型與算法的正確與有效性，我們基于粵港澳大灣區(qū)情況設(shè)計(jì)了仿真實(shí)驗(yàn)。該灣區(qū)是一個(gè)典型的港口調(diào)度適用型案例，首先，灣區(qū)內(nèi)港口間隔適中(50～120 km)，當(dāng)自然因素(如龍卷風(fēng)、雷暴天氣)導(dǎo)致某一港口停運(yùn)時(shí)，對(duì)其他港口影響較小；其次，各港口所屬城市具有充足的應(yīng)急資源，當(dāng)發(fā)生蓄意襲擊時(shí)，可迅速封閉城市，防止襲擊傷害蔓延至整個(gè)灣區(qū)；這種緊密相連而又相對(duì)獨(dú)立的情況為港口調(diào)度提供了充分條件。因此，實(shí)驗(yàn)中設(shè)計(jì)的緊急情況都是針對(duì)單港口產(chǎn)生影響的。另外，由于廣(港口A)、深(港口B)、港(港口C)、澳(港口D)4個(gè)港口的實(shí)際泊位、岸橋數(shù)量繁多，將導(dǎo)致實(shí)驗(yàn)計(jì)算復(fù)雜度呈幾何級(jí)上升，故本文在不影響結(jié)果的前提下對(duì)其進(jìn)行了簡(jiǎn)化，依照實(shí)際比例以最小化數(shù)目設(shè)置各港口深、淺水泊位與岸橋數(shù)量。

港口間相互距離如圖2所示，其中不同港口間箭頭旁邊的標(biāo)注d表示對(duì)應(yīng)港口之間的實(shí)際距離。表1所示為不同港口下泊位的水深情況及配備岸橋數(shù)目，表2所示為不同規(guī)模船只的數(shù)目及運(yùn)貨量。

圖2 港口間相互距離(單位：10 km)

表1 泊位水深及岸橋數(shù)目配比

表2 各船只運(yùn)貨量及排水量

假設(shè)深水泊位可匹配所有類型船只，中型泊位可匹配中型及小型船只，而淺水泊位僅能匹配小型船只。基于本文提出的具備約束適應(yīng)能力的改進(jìn)遺傳算法，僅考慮耗時(shí)成本以及綜合考慮網(wǎng)絡(luò)脆弱性和耗時(shí)成本(權(quán)值系數(shù)w1=w2=0.5)的兩類優(yōu)化曲線分別如圖3、圖4所示。為使兩類優(yōu)化目標(biāo)參數(shù)在畫(huà)圖上可比，本文采用歸一化方法使參數(shù)相對(duì)值來(lái)描述，其中：相對(duì)值=絕對(duì)值/迭代中的最大值。

圖3 考慮網(wǎng)絡(luò)脆弱性的優(yōu)化目標(biāo)迭代變化折線圖

圖4 不考慮網(wǎng)絡(luò)脆弱性的優(yōu)化目標(biāo)迭代變化折線圖

顯然，綜合考慮多個(gè)指標(biāo)變量時(shí)，取得的最優(yōu)解為兩類指標(biāo)值的權(quán)衡與折中：在單目標(biāo)優(yōu)化函數(shù)下，耗時(shí)成本略優(yōu)于考慮脆弱性的多目標(biāo)優(yōu)化函數(shù)模型，但后者的泊位調(diào)度方案對(duì)船只的分配更加均勻，因此網(wǎng)絡(luò)脆弱性更低，抗風(fēng)險(xiǎn)能力更強(qiáng)。兩類解的甘特圖如圖5所示，圖中豎直細(xì)條紋方格為小型船只，交叉紋方格為中型船只，斜紋方格為大型船只。

圖5 不同優(yōu)化目標(biāo)下的甘特圖

可以看出，調(diào)度方案更為均勻時(shí)，網(wǎng)絡(luò)可以更靈活地應(yīng)對(duì)其中個(gè)別節(jié)點(diǎn)的突發(fā)問(wèn)題。

為進(jìn)一步研究網(wǎng)絡(luò)脆弱性的引入對(duì)充分發(fā)揮灣區(qū)網(wǎng)絡(luò)協(xié)調(diào)互補(bǔ)機(jī)制的影響，模擬突發(fā)事件引起的港口臨時(shí)關(guān)閉場(chǎng)景，對(duì)比關(guān)閉前后任務(wù)完成耗時(shí)成本的差異。根據(jù)文獻(xiàn)[8]，蓄意攻擊事件將使重要程度最高的港口關(guān)閉；而龍卷風(fēng)等自然事件則使各港口關(guān)閉概率均等。在港口關(guān)閉時(shí)，正處于該港口卸載作業(yè)中的船只剩余貨物量按下式計(jì)算：Z′=Z-r·p·twork，港口內(nèi)各船只向距離最近的可用泊位轉(zhuǎn)移。船只在遭受蓄意攻擊事件下的甘特圖變化情況如圖6所示。本實(shí)驗(yàn)中考慮了轉(zhuǎn)移船只成本，因此每艘轉(zhuǎn)移船只的耗時(shí)不光為卸載貨物用時(shí)，還包括在轉(zhuǎn)移過(guò)程中需要付出的時(shí)間成本，在甘特圖上以白色色段表示。最終，不同優(yōu)化目標(biāo)下的耗時(shí)成本差異如圖7所示。

圖6 發(fā)生緊急狀況下不同優(yōu)化目標(biāo)的甘特圖

圖7 耗時(shí)成本變化情況

仿真結(jié)果表明，網(wǎng)絡(luò)脆弱性的引入增強(qiáng)了灣區(qū)整體水運(yùn)網(wǎng)絡(luò)的強(qiáng)健性與抗干擾性，在突發(fā)情況下維持穩(wěn)定的網(wǎng)絡(luò)貨運(yùn)性能，尤其在蓄意攻擊場(chǎng)景下作用顯著。

4 結(jié) 語(yǔ)

本文針對(duì)灣區(qū)內(nèi)多港口的泊位調(diào)度問(wèn)題，綜合考慮網(wǎng)絡(luò)脆弱性及耗時(shí)成本，構(gòu)造了多目標(biāo)組合優(yōu)化模型。提出了具備約束適應(yīng)能力的改進(jìn)遺傳算法，提高了模型求解速度。實(shí)驗(yàn)結(jié)果表明，模型對(duì)網(wǎng)絡(luò)高效性和強(qiáng)健性權(quán)衡合理，在突發(fā)情況(尤其是蓄意攻擊場(chǎng)景)下可保持穩(wěn)定的網(wǎng)絡(luò)性能，對(duì)于灣區(qū)多港口的泊位綜合利用提供了理論基礎(chǔ)。