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

朱益輝 賀紅燕 李彥蒼

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

0 引 言

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

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

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

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

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

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

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

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

(1)

1.1 網(wǎng)絡脆弱性

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

(2)

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

(3)

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

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

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

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

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

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

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

(4)

1.2 耗時成本

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

本文計算耗時成本C時考慮了不同船只的貨物運載量情況，其定義如下：

(5)

式中：Tm為m號船的逗留時間，計算如下：

(6)

1.3 約束條件與模型設計

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

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

(12)

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

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

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

(13)

當X長度為M時，函數(shù)Confit(X)需要完成M(M-1)/2次加法運算。

2 基于約束適應的改進遺傳算法

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

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

交叉算子：

變異算子：

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

自我交叉算子：

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

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

重排序處理算法

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

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

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

Step4對θleft、θright集合，分別任意選擇數(shù)b、數(shù)c作為基準元素，對集合進行劃分，構成四個集合θleft-left、θleft-right、θright-left、θright-right。

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

(14)

顯然，有：

(15)

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

3 仿真實驗及結果分析

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

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

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

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

表2 各船只運貨量及排水量

假設深水泊位可匹配所有類型船只，中型泊位可匹配中型及小型船只，而淺水泊位僅能匹配小型船只?；诒疚奶岢龅木邆浼s束適應能力的改進遺傳算法，僅考慮耗時成本以及綜合考慮網(wǎng)絡脆弱性和耗時成本(權值系數(shù)w1=w2=0.5)的兩類優(yōu)化曲線分別如圖3、圖4所示。為使兩類優(yōu)化目標參數(shù)在畫圖上可比，本文采用歸一化方法使參數(shù)相對值來描述，其中：相對值=絕對值/迭代中的最大值。

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

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

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

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

可以看出，調度方案更為均勻時，網(wǎng)絡可以更靈活地應對其中個別節(jié)點的突發(fā)問題。

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

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

圖7 耗時成本變化情況

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

4 結 語

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