李長安，趙德隆，王國勇，吳忠強(qiáng)，張立杰

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

0 引 言

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

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

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

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

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

火車pi開始被翻車機(jī)cj作業(yè)的時間為：

Sij=ai+wi+dij

(1)

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

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

li=Sij+Fij+Bij

(2)

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

火車pi的等待時間為：

(3)

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

目標(biāo)函數(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)者負(fù)責(zé)帶領(lǐng)跟隨者進(jìn)行協(xié)調(diào)運(yùn)動，在搜索空間中尋找更好的食物源作為群體運(yùn)動目標(biā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)的隨機(jī)數(shù)，作用是增強(qiáng)領(lǐng)導(dǎo)者位置更新的隨機(jī)性，增強(qiáng)個體的多樣性和加強(qiáng)全局搜索能力；c1為收斂因子，起到權(quán)衡種群勘探和開發(fā)食物源的作用，當(dāng)其大于1時，算法進(jìn)行全局搜索，當(dāng)其小于1時，算法進(jìn)行局部開發(fā)，得到精確的估計(jì)值，c1的取值通常是一個2～0的遞減函數(shù)，表達(dá)式如式(8)：

(8)

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

3)追隨者位置更新

(9)

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

3 ACSSA算法

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

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

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

(10)

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

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

(11)

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

(12)

3.2 柯西變異策略

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

(13)

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

4 算法測試與分析

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

表1 標(biāo)準(zhǔn)測試函數(shù)Table 1 Standard test functions

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

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

下面對3種算法的收斂速度進(jìn)行比較，將運(yùn)行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次才可以達(dá)到收斂， ASSA算法迭代200～300次就能收斂，相比SSA算法收斂速度變快， ACSSA算法迭代20～50次就能收斂，收斂速度相比前兩者有大幅提高。此外，如圖5相比SSA算法對一些函數(shù)尋優(yōu)容易陷入局部極值，ASSA算法與ACSSA算法不容易陷入局部最優(yōu)，尋找全局最優(yōu)解的能力增強(qiáng)。

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

從表3的最優(yōu)值對比結(jié)果可以看出， PSO的最優(yōu)值達(dá)到10-25， WOA最優(yōu)值達(dá)到10-16， ACSSA最優(yōu)值可以達(dá)到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相比具有較強(qiáng)的尋優(yōu)能力和穩(wěn)定性。

表3 ACSSA、WOA 和PSO的估計(jì)精度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次才可以達(dá)到收斂，WOA迭代20～40次能達(dá)到收斂，ACSSA迭代5～20次就能收斂，收斂速度相比PSO與WOA有大幅提高。

5 算 例

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

表4 列車調(diào)度時間及可選翻車機(jī)序號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è)翻車機(jī)。

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