基于改進(jìn)灰狼算法的港作拖輪調(diào)度研究

姚鵬 段興鋒

(集美大學(xué) 航海學(xué)院,福建廈門 361021)

在我國維持港口開放與經(jīng)濟(jì)發(fā)展的背景下,港口規(guī)模的擴(kuò)張與作業(yè)需求的持續(xù)增長已成為大趨勢[1],而今港口船舶眾多,港口結(jié)構(gòu)復(fù)雜,拖輪資源有限,故拖輪調(diào)度問題的優(yōu)化顯得尤為重要。而合理優(yōu)化拖輪調(diào)度能節(jié)省大量港口拖輪資源,加快港口船舶運(yùn)行效率[2]。

拖輪調(diào)度問題起源于作業(yè)車間調(diào)度問題(Job-shop scheduling problem,JSP),傳統(tǒng)的拖輪調(diào)度主要依靠調(diào)度工作人員的經(jīng)驗(yàn),輔以一些整數(shù)規(guī)劃方法[3-6],隨著港口作業(yè)需求量的增大,傳統(tǒng)的方法已難以應(yīng)對新的挑戰(zhàn),就需要有更科學(xué)更有效的方法來解決拖輪調(diào)度問題。目前相關(guān)的研究主要聚焦在建立貼合實(shí)際的拖輪調(diào)度模型,并采用合適的元啟發(fā)式算法求解等方面?，F(xiàn)有文獻(xiàn)大部分拖船調(diào)度模式均以拖船最大運(yùn)行時(shí)間為優(yōu)化目標(biāo)[7],這與實(shí)際應(yīng)用需求有差距。李伯棠等[8]構(gòu)建了以拖輪燃油成本最小化為目標(biāo)函數(shù)、考慮多停泊基地條件下的一體化拖輪調(diào)度模糊規(guī)劃模型,設(shè)計(jì)了鯨魚—遺傳混合算法(Whale Optimization-Genetic hybrid Algorithms based on Scheduling Plan coding,SPWOGA)進(jìn)行求解,并與CPLEX、Memtic算法進(jìn)行對比試驗(yàn),驗(yàn)證了該算法的可行性。Wang等[9]以拖輪平均利用率、船舶平均等待時(shí)間和最大等待隊(duì)列長度為多優(yōu)化目標(biāo),根據(jù)調(diào)度規(guī)則構(gòu)建混合整數(shù)規(guī)劃模型,結(jié)合GA、ACO算法提出GA-ACO算法,對該模型進(jìn)行求解,驗(yàn)證了該算法的有效性;Chang等[10]基于動(dòng)態(tài)分析,以船舶等待時(shí)間和拖船溢出馬力最小化構(gòu)建最佳目標(biāo)函數(shù),建立拖船動(dòng)態(tài)的調(diào)度優(yōu)化模型,并通過引入熵函數(shù)和精英保留策略,改進(jìn)了基本粒子群算法進(jìn)行優(yōu)化研究。劉志勇等[11]針對港口運(yùn)輸路徑優(yōu)化問題,構(gòu)建最低運(yùn)輸成本的調(diào)度模型,并采用了改進(jìn)后的螢火蟲算法進(jìn)行優(yōu)化求解。

灰狼優(yōu)化算法(Grey Wolf Optimization,GWO)是澳大利亞格里菲斯大學(xué)學(xué)者M(jìn)irjalili[12]于2014年提出的一種新型群體智能優(yōu)化算法,此算法的優(yōu)點(diǎn)為結(jié)構(gòu)簡單、設(shè)置參數(shù)少、收斂速度快以及全局尋優(yōu)能力強(qiáng),故在工程制造[13]、圖像信息[14]、能源優(yōu)化[15]等多個(gè)領(lǐng)域均得到應(yīng)用,其中也包括調(diào)度領(lǐng)域。王玉芳等[16]針對柔性作業(yè)車間調(diào)度問題,采用整數(shù)編碼方式,提出了一種自適應(yīng)灰狼算法進(jìn)行求解,通過引入自適應(yīng)社會(huì)等級(jí)分布制度策略提高算法的魯棒性,以及變領(lǐng)域搜索策略用于平衡算法的尋優(yōu)能力,但未考慮GWO與整數(shù)編碼存在一定的沖突,影響到算法的性能;顧九春等[17]建立多優(yōu)化目標(biāo)下的節(jié)能調(diào)度模型,在整數(shù)編碼的條件下采用GWO進(jìn)行求解,并通過交叉操作策略進(jìn)行個(gè)體優(yōu)化,它僅在尋優(yōu)方面進(jìn)行調(diào)整,并未對初始種群進(jìn)一步優(yōu)化;胡澤洲等[18]對于GWO易陷入局部最優(yōu)的缺點(diǎn),采用精英反向?qū)W習(xí)與非線性控制因子策略,分別強(qiáng)化算法的初始種群多樣性與搜索性能,但此算法在非多峰函數(shù)上的應(yīng)用效果并不顯著,且未考慮多優(yōu)化目標(biāo)的求解情況。

針對上述拖輪調(diào)度現(xiàn)存模型的構(gòu)建問題及灰狼算法存在的整數(shù)編碼沖突問題,本文基于多艘不同單位成本拖輪的復(fù)雜條件,以拖輪空駛?cè)加统杀九c拖輪助航燃油成本為最小化優(yōu)化目標(biāo),建立混合整數(shù)規(guī)劃模型,提出一種結(jié)合小生境技術(shù)[19-20]與交叉修正更新策略的灰狼算法進(jìn)行求解,通過多個(gè)規(guī)模下的算例進(jìn)行對比試驗(yàn),以驗(yàn)證本文所提算法的有效性。

1 港作拖輪調(diào)度模型構(gòu)建

1.1 問題假設(shè)

1)任務(wù)計(jì)劃安排:在拖輪任務(wù)開始之前,獲取到港口當(dāng)天的船舶作業(yè)需求及具體的靠離泊量的相關(guān)信息,并按時(shí)間順序?yàn)槊克掖皠澏ㄈ蝿?wù),同時(shí)結(jié)合港口現(xiàn)有的拖輪數(shù)量、功率等信息,對前后時(shí)間相近的任務(wù)(前一任務(wù)結(jié)束時(shí)間與后一任務(wù)開始時(shí)間相近)進(jìn)行合并,共用部分拖輪;

2)拖輪作業(yè):拖輪完成靠離泊任務(wù)后,返回某一基地并等待下一任務(wù)(不一定是緊接的任務(wù));

3)拖輪基地:初始狀態(tài)下拖輪隨機(jī)分布于各拖輪基地中,拖輪駛?cè)?、駛出基地花費(fèi)時(shí)間忽略不計(jì);

4)拖輪功率:各拖輪有固定的行駛功率,具備相應(yīng)空駛速度;

5)通航規(guī)則:港口為單向航道,船舶不能并行。

1.2 參數(shù)設(shè)定

1)集合。

J,J′為任務(wù)或作業(yè)的集合,j∈J={1,2,3,…,NJ};0表示任務(wù)開始時(shí)的階段;I為拖輪集合,i∈I={1,2,3,…,NI};K為基地集合,k∈K={1,2,3,…,NK}。

2)參數(shù)。

3)決策變量。

1.3 模型建立

以拖輪空駛?cè)加统杀九c助航作業(yè)燃油成本之和最小化為優(yōu)化目標(biāo),具體目標(biāo)函數(shù)與約束條件如下:

(1)

(2)

(3)

Pi≥Mjxij,?i∈I,?j∈J;

(4)

(5)

?i∈I,j∈{2,3,…,NJ};

(6)

(7)

(8)

(9)

(10)

(11)

模型中,式(1)的3部分分別表示拖船至任務(wù)起始點(diǎn)的空載燃料成本、拖船工作時(shí)的助航燃料成本、拖船至任務(wù)終點(diǎn)的空載燃料成本;式(2)表示每個(gè)作業(yè)的拖船配置數(shù)量;式(3)表示第一次作業(yè)之前拖船的位置;式(4)表示完成作業(yè)的拖船必須達(dá)到目前作業(yè)的最小功率需求;式(5)表示第一次作業(yè)的拖船應(yīng)在第一次作業(yè)之前就抵達(dá)作業(yè)起點(diǎn);式(6)表示拖船在完成上一次作業(yè)后,返回停靠基地,并能按時(shí)抵達(dá)當(dāng)前作業(yè)起點(diǎn);式(7)表示拖輪必須回到基地,然后再進(jìn)行下次作業(yè);式(8)表示一個(gè)基地目前的拖船數(shù)量,應(yīng)符合完成任務(wù)所需要的拖船數(shù)量;式(9)表示一艘拖船只能在同一時(shí)間內(nèi)?？吭谝粋€(gè)基地;式(10)表示在目前階段沒有任何任務(wù)的情況下,拖輪停留在上一基地;式(11)代表變量是0到1的整型變量。

2 面向拖輪調(diào)度的HNGWO

2.1 灰狼算法原理

GWO是模仿灰狼群的捕食特點(diǎn),以狼群追蹤、包圍、追捕、攻擊獵物為目標(biāo),實(shí)現(xiàn)最優(yōu)搜索?；依堑牟东C過程根據(jù)式(12)、式(13)實(shí)現(xiàn):

(12)

(13)

其中表示t為當(dāng)前迭代次數(shù),Xp表示獵物的位置向量,X(t)表示當(dāng)前灰狼的位置向量;A和C是協(xié)同系數(shù)向量,根據(jù)式(14)、式(15)變化:

(14)

(15)

在狼群的捕食過程中,a由2線性接近至0;r1和r2是[0,1]中的隨機(jī)向量,顯然隨著迭代過程的深入,a逐漸減小為0,灰狼逼近獵物,與此同時(shí),r1與r2使得灰狼有機(jī)會(huì)跳出局部最優(yōu)解。

2.2 混合小生境技術(shù)

由于灰狼算法本身的機(jī)制,以及拖輪調(diào)度的混合整數(shù)規(guī)劃特性,導(dǎo)致初始種群對GWO在拖輪調(diào)度問題上的迭代收斂具有很大程度的影響,所以本文從初始種群入手,引入改進(jìn)遺傳算法中的小生境技術(shù),提高初始種群的多樣性,具體如圖1所示。

圖1 小生境技術(shù)路線圖

2.3 交叉修正更新策略

灰狼算法的更新過程中往往伴隨非整數(shù)解的出現(xiàn),且拖輪調(diào)度問題的解個(gè)體存在約束限制(主要包括處理同一任務(wù)時(shí)拖輪不可重復(fù)、任務(wù)所需拖輪最低功率的限制),灰狼算法更新后的個(gè)體極易出現(xiàn)非法解,故本文提出一種交叉修正更新機(jī)制,具體步驟如下:

1)根據(jù)當(dāng)前狼的位置與種群中當(dāng)代頭狼α、β、δ的位置,以及當(dāng)前各自協(xié)同系數(shù)向量A和C,分別計(jì)算當(dāng)前狼與各頭狼的距離向量,取各距離向量的中心;

2)將向量中心修正為整數(shù)解(大概率仍然是非法解);

3)根據(jù)任務(wù)最低功率要求計(jì)算可選拖輪集;

4)將2)中得到的非法整數(shù)解與3)中的可選拖輪集取交集,進(jìn)而獲取最接近于非法整數(shù)解的個(gè)體,完成當(dāng)前個(gè)體的更新;

5)對灰狼中包含的所有個(gè)體均按上述步驟進(jìn)行更新,即完成對灰狼個(gè)體的更新。

以5個(gè)任務(wù)、8艘拖輪為例,圖2展示了交叉修正更新過程,個(gè)體由全部任務(wù)所需的拖輪組成,其中當(dāng)前個(gè)體基于參數(shù)A、C與當(dāng)前代3個(gè)頭狼α、β、δ進(jìn)行交叉融合,經(jīng)取整后得到下一代灰狼位置向量X1、X2、X3,取3者向量中心并修正,再與可選拖輪集取交集(個(gè)體余下缺失部分隨機(jī)選取),完成對當(dāng)前個(gè)體的更新,重復(fù)多個(gè)個(gè)體的更新后最終得到新一代灰狼個(gè)體。

圖2 交叉修正更新實(shí)例

3 HNGWO算法流程

主要以小生境技術(shù)初始化種群,并針對拖輪調(diào)度問題的特點(diǎn),引入交叉修正更新機(jī)制,算法流程如圖3所示。

圖3 算法流程圖

4 算例分析

4.1 多規(guī)模算法結(jié)果對比

為驗(yàn)證HNGWO在港作拖輪調(diào)度中的求解效果,本文生成多個(gè)不同規(guī)模的算例,模擬不同規(guī)模的拖輪調(diào)度情況,算例規(guī)模如表1所示。

表1 算例規(guī)模

針對表1所設(shè)算例規(guī)模下的拖輪調(diào)度問題,分別采用CPLEX(數(shù)學(xué)求解器)、GA、GWO、HNGWO進(jìn)行求解對比,求解指標(biāo)采用最優(yōu)值(Bes.)、平均值(Avg.)、收斂代數(shù)(Con.),各代碼均使用軟件python3.7編寫代碼(CPLEX為python代碼調(diào)取函數(shù)庫使用),運(yùn)行環(huán)境為11th Gen Intel(R)Core(TM) i5-11400H @ 2.70 GHz處理器、16 GB內(nèi)存、Windows(64位操作系統(tǒng))的筆記本電腦,具體求解結(jié)果如表2所示。

表2 各算法求解結(jié)果對比

表2中對比了6個(gè)不同規(guī)模算例下的算法求解結(jié)果,顯然HNGWO在各個(gè)指標(biāo)上的表現(xiàn)均優(yōu)秀,最優(yōu)值相較于同類智能算法GA、PSO得到了優(yōu)化,且隨算例規(guī)模的增大,該調(diào)度問題的維度不斷提高,各算法的性能差距愈發(fā)明顯,具體如表3,最優(yōu)值優(yōu)化比例也隨規(guī)模增大不斷升高,且HNGWO的收斂速度相較于原始GWO有了顯著提升,收斂速度采用指標(biāo)(Cona.)衡量,Cona.為達(dá)到最優(yōu)解時(shí)的當(dāng)前迭代次數(shù), HNGWO相比于GWO的收斂代數(shù)優(yōu)化比例見表4,可以看出,隨算例規(guī)模的增大Cona.隨之提升,并趨于穩(wěn)定。本文所給出的6個(gè)算例中,Cona.平均值達(dá)13.23%,因HNGWO增加了每代種群的多樣性,在空間搜索中能更快地定位到最優(yōu)解附近,但它會(huì)導(dǎo)致其最終種群的平均值稍差。

表3 最優(yōu)值優(yōu)化對比

表4 收斂代數(shù)優(yōu)化對比

其中CPLEX作為數(shù)學(xué)求解器,求解精度最高,求解速度極快,但求解至算例5、算例6時(shí)卻無法獲得結(jié)果,由此可見CPLEX無法求解大規(guī)模調(diào)度問題;對于GA算法,針對此類高維度復(fù)雜問題時(shí),受限于搜索空間,當(dāng)搜索空間范圍不斷增大時(shí),表現(xiàn)較差;而PSO算法,同樣受到解個(gè)體的維度限制,可以看出PSO算法在小規(guī)模算例(低維度)中的表現(xiàn)較好,但當(dāng)全局學(xué)習(xí)對象僅有一個(gè)時(shí),在大規(guī)模算例中易陷入局部最優(yōu);而對于原始灰狼算法GWO,相比較于GA、PSO更為優(yōu)秀,但其收斂速度較慢,這是由GWO求解整數(shù)規(guī)劃問題時(shí)的沖突所致。

4.2 中等規(guī)模收斂曲線驗(yàn)證

為進(jìn)一步驗(yàn)證HNGWO的求解效果,選取中等規(guī)模的算例3進(jìn)行不同算法的迭代曲線驗(yàn)證,算例3的拖輪相關(guān)數(shù)據(jù)、任務(wù)相關(guān)數(shù)據(jù)如表5、表6所示。

表5 任務(wù)相關(guān)數(shù)據(jù)

表6 拖輪相關(guān)數(shù)據(jù)

對比同等規(guī)模下GA、PSO、GWO、HNGWO的最優(yōu)解迭代曲線,如圖4所示,可以看出:GA由于缺少GWO的交叉修復(fù)更新機(jī)制,收斂速度會(huì)快一些,但最優(yōu)解較差,PSO面對高維度問題時(shí)則早早陷入局部最優(yōu),而GWO與HNGWO的求解效果顯然更好,兩者的最優(yōu)值相差不多,但HNGWO的收斂速度較快,在港口的實(shí)際應(yīng)用中能有效提高調(diào)度效率。

圖4 中等規(guī)模下各算法迭代效果對比

針對該算例,由HNGWO生成最優(yōu)調(diào)度方案的甘特圖,如圖5所示,可以清晰地看出,各拖輪執(zhí)行任務(wù)的時(shí)間段與作業(yè)情況,如4號(hào)拖輪執(zhí)行任務(wù)的順序?yàn)槿蝿?wù)1—任務(wù)9—任務(wù)14,執(zhí)行任務(wù)3的拖輪為5號(hào)拖輪、9號(hào)拖輪、19號(hào)拖輪。受拖輪功率的影響以及任務(wù)需求的變動(dòng),最優(yōu)調(diào)度方案中各拖輪的使用率并不均衡,即在不同條件下得到的動(dòng)態(tài)求解方案可以為港作拖輪調(diào)度問題提供參考。

圖5 最優(yōu)調(diào)度方案甘特圖

5 結(jié)語

為求解單向拖輪調(diào)度問題提出了一種基于小生境技術(shù)的改進(jìn)灰狼算法,在不同規(guī)模的船舶情況下進(jìn)行對比試驗(yàn),驗(yàn)證了該算法在拖輪調(diào)度領(lǐng)域的可行性。主要貢獻(xiàn)有3點(diǎn):1)設(shè)定不同拖輪成本的多目標(biāo)函數(shù),構(gòu)建基于混合整數(shù)規(guī)劃的港作拖輪調(diào)度模型,并根據(jù)船舶作業(yè)時(shí)間劃分多個(gè)任務(wù),便于后續(xù)求解;2)在灰狼算法的理論基礎(chǔ)上,混合小生境技術(shù)優(yōu)化GWO的初始種群,增加了初始種群的多樣性,使算法加快收斂;3)在應(yīng)用GWO求解拖輪調(diào)度問題的過程中,存在整數(shù)沖突問題(GWO基于非整數(shù)解進(jìn)行收斂,而拖輪調(diào)度問題為整數(shù)解),采用交叉修正更新策略進(jìn)行處理,并使算法相較于傳統(tǒng)GWO更快收斂至最優(yōu)解,為港口拖輪調(diào)度實(shí)踐提供解決思路。

本研究存在的不足:首先,算法針對拖輪調(diào)度問題作出交叉修正更新環(huán)節(jié)的改進(jìn),導(dǎo)致該混合算法在非整數(shù)規(guī)劃領(lǐng)域的適用性不強(qiáng),需要進(jìn)行一定的修改才能應(yīng)用;其次,算法并未對GWO的后期收斂趨緩問題進(jìn)行改進(jìn),這將是后續(xù)改進(jìn)方向,目前則主要考慮以貪心算法、馬爾科夫過程等方法加快GWO的后期收斂性能,得到更優(yōu)秀的港作拖輪調(diào)度方案。