基于改進樽海鞘群算法的卸車調(diào)度優(yōu)化

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

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

0 引 言

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

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

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

1 卸車調(diào)度數(shù)學(xué)模型

以優(yōu)化火車總在港時間為目標，卸車調(diào)度的數(shù)學(xué)模型為：①火車集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作業(yè)的時間為：

Sij=ai+wi+dij

(1)

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

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

li=Sij+Fij+Bij

(2)

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

火車pi的等待時間為：

(3)

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

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

(4)

約束條件為：

(5)

2 樽海鞘群搜索算法

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

算法步驟如下：

1)初始化種群

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

(6)

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

2)領(lǐng)導(dǎo)者位置更新

(7)

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

(8)

式中：t為當(dāng)前迭代次數(shù)；tmax為最大迭代次數(shù)。

3)追隨者位置更新

(9)

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

3 ACSSA算法

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

3.1 自適應(yīng)慣性權(quán)重

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

(10)

式中：g, h為常數(shù)；t為當(dāng)前迭代次數(shù)。

將(10)式代入式(7)，得出領(lǐng)導(dǎo)者位置更新表達式為：

(11)

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

(12)

3.2 柯西變異策略

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

(13)

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

4 算法測試與分析

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

表1 標準測試函數(shù)Table 1 Standard test functions

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

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

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

圖1 Ackley函數(shù)Fig. 1 Ackley function

圖2 Sphere函數(shù)Fig. 2 Sphere function

圖3 Quartic函數(shù)Fig. 3 Quartic function

圖4 Schwefel’s problem 22函數(shù)Fig. 4 Schwefel’s problem 22 function

圖5 Griewank函數(shù)Fig. 5 Griewank function

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

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

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

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

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

圖6 Ackley函數(shù)Fig. 6 Ackley function

圖7 Sphere函數(shù)Fig. 7 Sphere function

圖8 Quartic函數(shù)Fig. 8 Quartic function

圖9 Schwefel’s problem 22函數(shù)Fig. 9 Schwefel’s problem 22 function

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

5 算 例

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

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

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

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

圖11 最優(yōu)調(diào)度甘特圖Fig. 11 Optimal scheduling Gantt chart

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

6 結(jié) 語

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