基于改進樽海鞘群算法的卸車調度優化

李長安，趙德隆，王國勇，吳忠強，張立杰

(1. 燕山大學 先進鍛壓成形技術與科學教育部重點實驗室，河北 秦皇島 066004; 2 .燕山大學 電氣工程學院， 河北 秦皇島 066004； 3.燕山大學 河北省重型機械流體動力傳輸與控制重點實驗室，河北 秦皇島 066004； 4. 神華天津煤炭碼頭有限責任公司，天津300457)

0 引 言

以往的港口作業調度多為人為決定，調度模式缺乏科學性，調度效率低，應變能力不足，經常造成火車長期滯留和煤炭積壓等問題，削弱了港口的市場競爭力，是亟待解決的關鍵問題。

港口調度問題具有復雜、隨機、多約束和多目標等特點，許多經典優化算法已被成功的應用到港口調度問題中。B. SKINNER等[1]以遺傳算法為基礎，結合使用了路徑規劃的方法將港口集成調度作業分組進行優化；張新宇等[2]建立雙向通航港口調度優化模型，用多目標遺傳算法尋找最優解；曾建智等[3]在對分段堆場調度的研究中，應用雙層遺傳算法優化分段出場時間和停放位置，并使用啟發式規則搜索分段調度路徑；陳文[4]構建了泊位岸橋聯合調度模型，使用螢火蟲算法求解調度方案；王諾等[5]將改進模擬植物生長算法應用于優化港口調度問題；陳紅梅等[6]建立M/M/S排隊模型研究卸車調度，并用實際港口實驗驗證了模型的有效性；劉文遠等[7]構建了關聯堆場作業動態卸車聯合調度優化模型，使用禁忌搜索算法實現最優卸車調度；邰世文等[8]以卸車效率最大和列車在港時間最短為目標，設計了采用仿真推演策略解碼的遺傳算法求解此多約束多目標優化模型。

以港口的卸車作業為研究對象，以載煤列車在港滯留總時間最短為研究目標，構建了考慮多煤種、火車調度時間、工作機械可用性、作業流程可達性及其相互約束關系等因素的卸車作業模型。采用基于改進樽海鞘群算法(improved seyedali seyed andrew，ISSA)求解。改進的樽海鞘群算法引入自適應慣性權重，提高了算法收斂速度；引入柯西變異策略，提高了算法尋優能力，得到了到港列車的優化翻卸調度順序，減少了列車在港等待時間，達到了提高港口工作效率，節省列車等待成本的目的。

1 卸車調度數學模型

以優化火車總在港時間為目標，卸車調度的數學模型為：①火車集P={p1,p2,…,pn}，pi表示第i列火車，i=1,2,…,n；②翻車機集C={c1,c2,…,cm}，cj表示第j臺翻車機，j=1,2,…,m；③堆垛集S={s1,s2,…,sq}，sk為第k個堆場垛位，k=1,2,…,q。

火車pi開始被翻車機cj作業的時間為：

Sij=ai+wi+dij

(1)

式中：ai為火車pi的到港時間；wi為火車pi的等待時間；dij為火車pi與翻車機cj的對接所用時間。

第i列火車的牽空離港時間為：

li=Sij+Fij+Bij

(2)

式中：Fij為翻卸作業所消耗時間；Bij為火車pi與翻車機cj的拆離所用時間。

火車pi的等待時間為：

(3)

式中：Xij為火車pi是否在翻車機cj上作業；lα為火車pi在對應翻車機上開始作業的時間(等同于前一列火車完成作業的牽空時間)。

目標函數為列車總在港時間最少[7]：

(4)

約束條件為：

(5)

2 樽海鞘群搜索算法

樽海鞘群搜索(seyedali seyed andrew，SSA)算法是2017年由S. SEYEDALI等[9]提出的一種新型智能優化算法，是受到樽海鞘群體行為特征啟發而開發的算法。SSA算法中樽海鞘以“鏈”的方式分布，群體中含有兩種角色：領導者和跟隨者，領導者是處于群鏈最前端的背囊生物，而剩下的生物為跟隨者，領導者負責帶領跟隨者進行協調運動，在搜索空間中尋找更好的食物源作為群體運動目標[10]，兩者在搜索過程中不斷更新自己位置，不斷向最優食物源移動。相比其他生物種群來說，樽海鞘群體中領導者對群體的影響力不高，領導者只直接影響緊挨著自己的第2個跟隨者的位置更新，第2個影響第3個，由此類推，領導者對后面跟隨者的影響力逐層遞減，可以使得排在后面的跟隨者在更新過程中保持多樣性。

算法步驟如下：

1)初始化種群

xn=rand(N,D)×(u-l)+l

(6)

式中：xn=[xn1,xn2,…,xn1]T,n=1,2,…,N為第n只樽海鞘在搜索空間中的位置，N為樽海鞘群的規模；D為搜索空間維度，u=[u1,u2,…,uD]T為搜索空間的上限；l=[l1,l2,…,lD]T為搜索空間的下限。

2)領導者位置更新

(7)

式中:x1j(j=1,2,…,D)為領導者每一維的狀態；Fj為食物所在位置；c2,c3為[0,1]內的隨機數，作用是增強領導者位置更新的隨機性，增強個體的多樣性和加強全局搜索能力；c1為收斂因子，起到權衡種群勘探和開發食物源的作用，當其大于1時，算法進行全局搜索，當其小于1時，算法進行局部開發，得到精確的估計值，c1的取值通常是一個2～0的遞減函數，表達式如式(8)：

(8)

式中：t為當前迭代次數；tmax為最大迭代次數。

3)追隨者位置更新

(9)

式中：xmj(m=2,3,…,N)為第m個追隨者第j維的位置。

3 ACSSA算法

針對SSA算法在函數尋優過程中存在的估計精度不高、收斂速度慢、容易陷入局部最優等問題，提出兩點改進：①自適應慣性權重；②柯西變異策略，新算法記為ACSSA (adaptive cauchy SSA) 算法。

3.1 自適應慣性權重

張永等[11]提出了慣性權重線性下降策略并應用到WOA(whale optimization algorithm )算法中, 實驗證明, 較大的慣性權重有利于粒子全局尋優，反之, 則利于局部開發、加快收斂速度。因此, 慣性權重對算法收斂速度和全局尋優能力都有重要影響，由于SSA在優化過程中是非線性變化的, 慣性權重線性下降策略無法體現實際的優化搜索過程, 又考慮到各搜索個體間的狀態差異性, 為此筆者提出基于搜索個體當前狀態的非線性自適應權重策略，將領導者位置更新表達式加入自適應權重，表達式為：

(10)

式中：g, h為常數；t為當前迭代次數。

將(10)式代入式(7)，得出領導者位置更新表達式為：

(11)

追隨者位置更新表達式(9)加入反向非線性自適應權重，表達式為：

(12)

3.2 柯西變異策略

王永驥等[12]引入柯西變異策略并應用到PSO (particle swarm optimization) 算法中，有利于增加種群多樣性以減小陷入局部最優的概率。為了提高SSA算法的尋優能力，筆者提出一種以當前最優樽海鞘位置為中心的隨機柯西變異策略，協調全局搜索和局部開發能力，進而提高算法尋優能力，表達式為：

(13)

式中：xbestj為當前迭代過程中領導者第j位置，Cauchy(0,1)是服從標準柯西分布的隨機數。

4 算法測試與分析

為了驗證筆者所提出算法的優越性，選取5個標準測試函數將ACSSA與ASSA (adaptive SSA)、SSA算法性能進行比較。5個標準測試函數分別為：Ackley函數、Sphere函數、Quartic函數、Schwefel’s problem 22函數以及Griewank函數等，具體表達式和搜索空間如表1。種群規模n、迭代次數Tmax、粒子空間維數D統一設定為30、1 000、10。3種算法分別獨立運行10次，并對運行所得的最優值、均值及方差進行比較，結果如表2。

表1 標準測試函數Table 1 Standard test functions

表2 3種算法估計精度Table 2 Estimation accuracy of three kinds of algorithms

從表2的最優值對比結果可以看出， SSA算法的最優值達到10-10， ASSA算法的最優值達到0，估計精度提高。從經典測試函數的均值和方差可以看出，SSA算法的均值和方差分別在10-5和10-11左右， ASSA算法的均值和方差分別在10-46和10-92左右，因此，ASSA算法具有較強的尋優能力和穩定性。從ASSA算法和ACSSA算法的對比結果可以看出，提出的自適應柯西變異策略對ASSA算法的估計精度略有提高。

下面對3種算法的收斂速度進行比較，將運行10次的適應度值取平均值，結果如圖1～圖5。

圖1 Ackley函數Fig. 1 Ackley function

圖2 Sphere函數Fig. 2 Sphere function

圖3 Quartic函數Fig. 3 Quartic function

圖4 Schwefel’s problem 22函數Fig. 4 Schwefel’s problem 22 function

圖5 Griewank函數Fig. 5 Griewank function

從圖1～圖5可看出， SSA算法迭代至少400次才可以達到收斂， ASSA算法迭代200～300次就能收斂，相比SSA算法收斂速度變快， ACSSA算法迭代20～50次就能收斂，收斂速度相比前兩者有大幅提高。此外，如圖5相比SSA算法對一些函數尋優容易陷入局部極值，ASSA算法與ACSSA算法不容易陷入局部最優，尋找全局最優解的能力增強。

將ACSSA算法與WOA算法、PSO算法進行對比，同樣采用表1測試函數，種群規模n、迭代次數Tmax、粒子空間維數D統一設定為30、1 000、10。3種算法分別獨立運行10次，并對運行所得的最優值、均值及方差進行比較，結果如表3。

從表3的最優值對比結果可以看出， PSO的最優值達到10-25， WOA最優值達到10-16， ACSSA最優值可以達到0，對于表中的測試函數，ACSSA的尋優精度優于前兩種算法。從測試函數的均值和方差可以看出，PSO的均值和方差分別在10-10和10-19左右，WOA的均值和方差分別在10-10和10-20左右，而ACSSA的均值和方差分別在10-52和0左右，因此，ACSSA與PSO與WOA相比具有較強的尋優能力和穩定性。

表3 ACSSA、WOA 和PSO的估計精度Table 3 Estimation accuracy of ACSSA, WOA and PSO

ACSSA、WOA 和PSO的收斂速度對比如圖6～圖10。

圖6 Ackley函數Fig. 6 Ackley function

圖7 Sphere函數Fig. 7 Sphere function

圖8 Quartic函數Fig. 8 Quartic function

圖9 Schwefel’s problem 22函數Fig. 9 Schwefel’s problem 22 function

從圖6～圖10可以看出， PSO迭代至少50次才可以達到收斂，WOA迭代20～40次能達到收斂，ACSSA迭代5～20次就能收斂，收斂速度相比PSO與WOA有大幅提高。

5 算 例

將改進算法應用到港口卸車調度中。港口卸車工序可描述為：火車運輸煤炭至港口→經過專業化的翻車機卸車→通過皮帶機轉運→通過堆料機在堆場堆放。某港口目前有6條取裝線，4臺翻車機。 假設港口每個時間點駛入3輛列車進行卸車調度，其調度時間表及每列列車可選擇的翻車機序號表，如表4(如6:30的列車1駛入港口后可選擇的翻車機序號為1或2)，各列車在對應翻車機上卸煤所需的時間如表5，單位為min。

表4 列車調度時間及可選翻車機序號Table 4 Train dispatching time and optional dumper serial number

表5 卸車所需時間Table 5 Time required for unloading min

設置ACSSA算法的參數：種群規模n為30, 最大迭代次數Tmax為100，粒子空間維數D為20°。經優化的卸車調度方案甘特圖如圖11，其中橫軸表示列車翻卸時間，縱軸表示4臺作業翻車機。

圖11 最優調度甘特圖Fig. 11 Optimal scheduling Gantt chart

由圖11并結合表4和表5的數據分析可知，人為規劃的列車調度方案使得列車總在港時間超過80多個小時，而采用優化算法解得的最優列車調度方案，列車總在港時間降低為62.250 3 h，大幅度提高了港口的卸車工作效率，節約了資源和人力消耗。ACSSA算法與ASSA和SSA比較，優化的調度結果相同，但是ACSSA算法只用100次迭代就得到了結果，而ASSA需要300次迭代，SSA需要500次迭代，可見ACSSA算法的收斂速度最快。

6 結 語

以港口的卸車作業為研究對象，以載煤列車在港滯留總時間最短為研究目標，構建了考慮多煤種、火車調度時間、工作機械可用性、作業流程可達性及其相互約束關系等因素的卸車作業模型。提出一種改進樽海鞘優化算法，引入自適應慣性權重，有利于提高算法收斂速度；引入隨機柯西變異策略，有利于提高算法尋優能力。5個標準測試函數的尋優結果表明：ACSSA相比于PSO，WOA，SSA，ASSA算法尋優精度更高，收斂速度更快。采用改進樽海鞘優化算法對翻卸工序進行優化，使火車在港滯留時間得到很大的縮減，且算法運算速度快，能滿足實際生產調度中的動態性要求，可使港口資源得到充分利用，大大提升港口的運行效率。