混合變異自適應(yīng)樽海鞘算法的甩掛運(yùn)輸多目標(biāo)調(diào)度優(yōu)化

摘? 要： 建立一種考慮時(shí)間窗的甩掛運(yùn)輸多目標(biāo)調(diào)度模型，提出一種改進(jìn)樽海鞘算法的求解策略。通過引入混合變異算子，改進(jìn)樽海鞘算法領(lǐng)導(dǎo)者位置易陷入局部最優(yōu)的問題，增加種群多樣性；通過引入動態(tài)慣性權(quán)重策略，使追隨者在迭代后期減小搜索步長，提高算法收斂精度。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)的樽海鞘算法具有較高的全局搜索能力，能有效得出甩掛運(yùn)輸多目標(biāo)問題最優(yōu)解，相關(guān)研究結(jié)論能夠?yàn)榇笮推髽I(yè)運(yùn)輸提供決策支持。

關(guān)鍵詞： 樽海鞘算法； 甩掛運(yùn)輸； 混合變異策略； 動態(tài)慣性權(quán)重優(yōu)化算法

中圖分類號：TP18? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ?文章編號：1006-8228（2023）04-53-05

Abstract： A multi-objective scheduling model of the tractor and semi-trailer transportation considering the time window is established， and a solution strategy of the improved salp swarm algorithm is proposed. By introducing a hybrid mutation operator， the problem that the leader position of the algorithm is easy to fall into local optimum is improved， and the population diversity is increased. By introducing the dynamic inertia weight strategy， the search step size of the followers is reduced in the late iteration， and the convergence accuracy of the algorithm is improved. The experimental results show that the improved salp swarm algorithm has the high global search ability， and can effectively obtain the optimal solution of tractor and semi-trailer transportation multi-objective problem. The relevant research conclusions can provide decision-making support for large-scale enterprise transportation.

Key words： salp swarm algorithm; tractor and semi-trailer transportation; hybrid mutation strategy; dynamic inertia weight optimization algorithm

0 引言

甩掛運(yùn)輸是指牽引車將集裝箱甩在指定的地點(diǎn)后，執(zhí)行其他運(yùn)輸任務(wù)的物流模式。其優(yōu)點(diǎn)是可以實(shí)現(xiàn)運(yùn)輸和裝卸同時(shí)進(jìn)行，相對于傳統(tǒng)運(yùn)輸模式，甩掛運(yùn)輸能較好地解決一些企業(yè)車輛等待裝卸時(shí)間長、車輛利用率低、在途車輛多、環(huán)境破壞嚴(yán)重等問題。

目前國內(nèi)外研究的甩掛運(yùn)輸問題主要基于五類單一經(jīng)典模型，使用掛車數(shù)量最少，運(yùn)輸成本最少，二氧化碳排放量最少，客戶滿意度較高，交通擁堵情況少。楊珍花等[1]構(gòu)建混合整數(shù)規(guī)劃模型，設(shè)計(jì)多階段動態(tài)優(yōu)化算法求解甩掛運(yùn)輸成本最小問題。成耀榮等[2]以噸公里 CO2排放量為目標(biāo)函數(shù)，構(gòu)建了考慮碳排放的大型制造企業(yè)內(nèi)牽引車優(yōu)化調(diào)度模型。Zhang R等[3]提出多掛車模型，提出了一種回溯自適應(yīng)閾值接受算法來解決該問題。目前有關(guān)文獻(xiàn)中很少有研究多目標(biāo)的甩掛運(yùn)輸調(diào)度優(yōu)化模型，而實(shí)際中，能源消耗、運(yùn)輸成本、客戶滿意度等因素之間相互影響，需考慮綜合因素的共同影響。本文在已有研究的基礎(chǔ)上，綜合環(huán)境和經(jīng)濟(jì)效益因素，在考慮時(shí)間窗的情況下，以碳排放量最少和運(yùn)輸成本最少為雙重目標(biāo)，構(gòu)建考慮碳排放與運(yùn)輸成本的甩掛運(yùn)輸帶時(shí)間窗的車輛調(diào)度問題模型，尋找最優(yōu)配送路徑，從而降低能耗，實(shí)現(xiàn)企業(yè)經(jīng)濟(jì)效益。

針對該問題，提出一種混合變異的自適應(yīng)樽海鞘算法的甩掛運(yùn)輸調(diào)度策略。樽海鞘算法有過早收斂、容易陷入局部最優(yōu)等缺點(diǎn)。國內(nèi)外眾多學(xué)者對樽海鞘算法進(jìn)行改進(jìn)，如Wang等[4]提出一種基于單純形法的隨機(jī)變異改進(jìn)樽海鞘算法，提高算法局部搜索能力。Sayed等[5]提出混沌樽海鞘算法，采用十種不同的混沌方案，提高結(jié)果精度和收斂速度。這些改進(jìn)策略在不同程度上提升了樽海鞘算法的尋優(yōu)能力，但該算法的性能仍有較大的提升空間。本文提出一種引入混合變異算子與動態(tài)慣性權(quán)重的策略來改進(jìn)樽海鞘算法，最后將改進(jìn)樽海鞘算法求解甩掛運(yùn)輸多目標(biāo)模型。

1 多目標(biāo)甩掛運(yùn)輸調(diào)度模型

在滿足時(shí)間窗等約束條件下，牽引車需將重掛車從裝貨節(jié)點(diǎn)拖帶到卸貨點(diǎn)，使得完成運(yùn)輸任務(wù)的總成本與碳排放最小。為了便于描述，本文做出以下合理假設(shè)：

一輛牽引車只拖帶一輛掛車。牽引車和掛車的甩掛操作只能在裝卸貨點(diǎn)完成。牽引車最初停放在中心節(jié)點(diǎn)，完成任務(wù)后返回中心節(jié)點(diǎn)。每一個(gè)運(yùn)輸任務(wù)都可用一輛掛車完成裝貨任務(wù)。

本文用有向圖V網(wǎng)絡(luò)來定義甩掛的運(yùn)輸網(wǎng)絡(luò)。N表示所有的運(yùn)輸節(jié)點(diǎn)合集，E表示第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)之間運(yùn)輸路徑的集合。K為牽引車集合，M為任務(wù)集合，Oi為任務(wù)i的起點(diǎn)，Di為任務(wù)i的終點(diǎn)，[ωpq]為車輛行駛耗費(fèi)的可變成本。[α]為燃油二氧化碳排放系數(shù)，Qr是任務(wù)順序?yàn)閞的運(yùn)輸量，dij是第i個(gè)節(jié)點(diǎn)到第j個(gè)節(jié)點(diǎn)之間的距離，c是每公里燃油消耗量。決策變量定義如下：

[ykij=1，牽引車連續(xù)執(zhí)行任務(wù)i和任務(wù)j0，其他]

[xki=1，牽引車執(zhí)行任務(wù)i0，其他]

考慮運(yùn)輸成本和碳排放的多目標(biāo)函數(shù)與考慮時(shí)間窗的約束條件的具體模型如下：

⑴ 目標(biāo)函數(shù)

⑵ 約束函數(shù)

時(shí)間窗約束⑶⑷表示牽引車到達(dá)節(jié)點(diǎn)的時(shí)間不能早于該節(jié)點(diǎn)的最早到達(dá)時(shí)間，不能晚于該節(jié)點(diǎn)最遲到達(dá)時(shí)間。約束⑸一輛牽引車只能訪問一次運(yùn)輸任務(wù)。

2 改進(jìn)的樽海鞘算法

2.1 基本樽海鞘算法

樽海鞘有一種稱為樽海鞘鏈的群體行為，這種行為可以幫助他們快速地尋覓食物[6]。S.Mirjalili等[6]以數(shù)學(xué)模型模擬了樽海鞘鏈，并應(yīng)用于求解優(yōu)化問題。

樽海鞘鏈分為兩組，第一組是領(lǐng)導(dǎo)者，第二組是追隨者，鏈的前面的鞘被稱為領(lǐng)導(dǎo)者，后面的鞘被稱為追隨者[6]。在優(yōu)化問題中，樽海鞘可以看作是候選解，海洋可以看作是搜索空間，食物的濃度可以看作最優(yōu)目標(biāo)函數(shù)，排在第一位置的個(gè)體可看作全局最優(yōu)解。領(lǐng)導(dǎo)者和追隨者位置更新公式如下：

[x1j]是第一個(gè)領(lǐng)導(dǎo)者鞘的第j維位置，[Fj]是第j維的食物源，第j維搜索的上邊界和下邊界分別是[ubj]和[lbj]，[c2]和[c3]是在0到1之間取的隨機(jī)數(shù)以保持搜索空間。[c1]是重要的參數(shù)，用來平衡開發(fā)和勘探能力。公式如下：

t和tmax是當(dāng)前迭代次數(shù)和最大迭代次數(shù)。領(lǐng)導(dǎo)者位置更新完成后，更新追隨者位置。公式如下：

2.2 樽海鞘算法的改進(jìn)策略

在標(biāo)準(zhǔn)樽海鞘算法中，算法在迭代過程中，會隨著迭代次數(shù)的增加，鏈中領(lǐng)導(dǎo)者位置的多樣性降低，從而使其陷入局部最優(yōu)。高斯變異、柯西變異、萊維變異已被證實(shí)可以增強(qiáng)元啟發(fā)式算法的全局搜索能力。因此，提出一種混合高斯變異、柯西變異、萊維變異算子策略，在每次迭代開始時(shí)，對樽海鞘領(lǐng)導(dǎo)者的位置進(jìn)行混合變異，集成三種變異算子的優(yōu)勢，使各變異算子以各自不同的概率作用于種群中的不同個(gè)體[7]。

混合變異的思想如下：算法初始時(shí)，高斯變異、柯西變異、萊維變異三種算子的選擇概率設(shè)置為0.3，0.3，0.4。因?yàn)槿R維變異比高斯變異和柯西變異有更大的靈活性，所以初始設(shè)置的選擇概率較大。當(dāng)變異發(fā)生后，比較適應(yīng)度函數(shù)值，如果當(dāng)前適應(yīng)度函數(shù)值優(yōu)于變異前的適應(yīng)度函數(shù)值，該個(gè)體所使用的變異算子的概率就要相應(yīng)地增加[7]。每一次迭代都需要根據(jù)動態(tài)計(jì)算得到的變異算子的概率來確定將要使用的變異算子類型。

引入高斯變異機(jī)制的領(lǐng)導(dǎo)者位置更新公式：

其中，[gaussion0，1]為標(biāo)準(zhǔn)高斯分布。

引入柯西變異機(jī)制的領(lǐng)導(dǎo)者位置更新公式：

引入萊維變異機(jī)制的領(lǐng)導(dǎo)者位置更新公式：

在追隨者位置更新公式中引入動態(tài)慣性權(quán)重[8]，隨迭代次數(shù)自適應(yīng)遞減的慣性權(quán)重表示了樽海鞘追隨者受全局最優(yōu)解影響程度的變化。在迭代前期，追隨者受全局最優(yōu)解影響較大，有較大的全局搜索步長，能夠更快地找到全局最優(yōu)區(qū)域，而在迭代后期，大部分樽海鞘已達(dá)到最優(yōu)值，追隨者受全局最優(yōu)解影響較小，追隨者可以在最優(yōu)解附近深度探索，提高了算法的收斂精度。追隨者自適應(yīng)慣性權(quán)重更新公式如下：

[ω]是自適應(yīng)慣性權(quán)重，[ωmax]和[ωmin]分別是慣性權(quán)重的最大值和最小值界限，[α]是15到30之間的隨機(jī)數(shù)。

具體的改進(jìn)樽海鞘算法的尋優(yōu)流程如下：

步驟1 初始化設(shè)置，包括種群規(guī)模，最大迭代次數(shù)，外部檔案大小，維度，上下邊界值；

步驟2 計(jì)算樽海鞘個(gè)體的適應(yīng)度值，根據(jù)適應(yīng)度值確定非支配解；

步驟3 根據(jù)非支配解確定外部檔案，如果外部檔案已滿，根據(jù)擁擠度計(jì)算來刪除與添加非支配解；

步驟4 從外部檔案中選擇食物源；

步驟5 更新種群個(gè)體位置，按一定的概率選擇一種變異策略領(lǐng)導(dǎo)者更新公式進(jìn)行混合策略變異操作；

步驟6 如果變異后的適應(yīng)度函數(shù)值更優(yōu)，則增加該個(gè)體所使用的相應(yīng)變異算子的概率，否則，減少該個(gè)體所使用的相應(yīng)變異算子的概率；

步驟7 計(jì)算追隨者的慣性權(quán)重值，并更新帶有自適應(yīng)慣性權(quán)重值的追隨者位置；

步驟8 判斷當(dāng)前迭代次數(shù)是否達(dá)到當(dāng)前設(shè)定的最大迭代次數(shù)，若是，則停止運(yùn)行并輸出最優(yōu)解，此時(shí)食物源庫中的個(gè)體即為所求最優(yōu)解集，若否，則返回步驟2繼續(xù)運(yùn)行。

3 改進(jìn)樽海鞘算法的收斂性與有效性分析

為驗(yàn)證本文提出的改進(jìn)樽海鞘算法具有較強(qiáng)的搜索精度和優(yōu)化能力。采用S.Mirjalili等的文獻(xiàn)中的benchmark的單峰測試函數(shù)和多峰測試函數(shù)對改進(jìn)算法的精度和收斂性進(jìn)行驗(yàn)證分析。收斂曲線對比如圖1所示。從基準(zhǔn)測試函數(shù)的收斂曲線可看出，改進(jìn)的樽海鞘算法收斂速度更快，有較好的尋優(yōu)精度。從F2和F3函數(shù)收斂曲線可看出，原樽海鞘算法在迭代早期陷入局部最優(yōu)解區(qū)域，有較低的收斂精度。

為進(jìn)一步驗(yàn)證算法的精度性能，對每個(gè)標(biāo)準(zhǔn)測試函數(shù)運(yùn)行30次，其結(jié)果表示如表1所示。平均值為精度平均值，標(biāo)準(zhǔn)差可反應(yīng)算法的穩(wěn)定性。對比表1中試驗(yàn)結(jié)果可得出，改進(jìn)的KESSA算法的標(biāo)準(zhǔn)差要比SSA算法的小很多，說明改進(jìn)算法有更好的穩(wěn)定性，從最優(yōu)值和平均值來看，改進(jìn)算法的求解精度更高。由此得出，引進(jìn)的混合變異自適應(yīng)樽海鞘算法比原算法尋優(yōu)能力更強(qiáng)。

4 改進(jìn)樽海鞘算法在甩掛運(yùn)輸調(diào)度優(yōu)化的應(yīng)用

本文對成耀榮等[2]的甩掛運(yùn)輸數(shù)據(jù)進(jìn)行改進(jìn)并實(shí)驗(yàn)。以廠內(nèi)棒材廠、成品庫、熱軋板廠、冷軋板、轉(zhuǎn)爐廠等十個(gè)主要廠址為網(wǎng)絡(luò)節(jié)點(diǎn)，編號為0的中心節(jié)點(diǎn)停放牽引車。網(wǎng)絡(luò)的弧為運(yùn)輸?shù)缆?。?為網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)，表3為每日的運(yùn)輸量與運(yùn)輸時(shí)間窗數(shù)據(jù)。

合理的甩掛運(yùn)輸調(diào)度方案能減少噸公里二氧化碳的排放量、同時(shí)減少車輛運(yùn)營成本，提高運(yùn)輸效率。本文提出的混合變異自適應(yīng)樽海鞘算法，能有效求得最優(yōu)配送路徑，具有較高的收斂精度，很大程度上節(jié)省了配送成本。表4為最優(yōu)的甩掛牽引車的調(diào)度方案。

5 結(jié)束語

本文考慮時(shí)間窗下的甩掛運(yùn)輸噸公里二氧化碳排放量和運(yùn)輸成本的多目標(biāo)問題，建立甩掛運(yùn)輸車輛調(diào)度優(yōu)化模型，提出一種改進(jìn)的樽海鞘算法的求解策略，通過將算法種群的領(lǐng)導(dǎo)者位置進(jìn)行混合變異，來提高算法全局搜索能力，增加種群多樣性。在迭代后期，為避免追隨者受全局影響而偏離最優(yōu)解，在算法種群的追隨者位置更新公式中引入動態(tài)慣性權(quán)重，從而提高算法的收斂精度。為測試算法性能，在基礎(chǔ)數(shù)據(jù)集上驗(yàn)證算法的收斂性和有效性，實(shí)驗(yàn)結(jié)果表明，引入混合變異算子與動態(tài)慣性權(quán)重能夠提高基本樽海鞘算法的求解和收斂速度。最后將改進(jìn)的樽海鞘算法優(yōu)化多目標(biāo)甩掛運(yùn)輸模型，結(jié)果表明，改進(jìn)的樽海鞘算法所得出的調(diào)度方案能有效降低運(yùn)輸成本，噸公里二氧化碳排放量，可提供給企業(yè)有效且合理的甩掛運(yùn)輸調(diào)度方案。

參考文獻(xiàn)（References）：

[1] 楊珍花，王滋承，魏照坤，等.掛車裝卸時(shí)間不確定的甩掛車輛動態(tài)調(diào)度優(yōu)化[J].系統(tǒng)工程理論與實(shí)踐，2021，41（5）：1081-1095

[2] 成耀榮，楊謙，鄭國華.考慮碳排放的大型制造企業(yè)甩掛運(yùn)輸牽引車調(diào)度優(yōu)化[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2021，51（3）：893-899

[3] Zhang R， Wang D， Wang J. Multi-Trailer Drop-and-Pull Container Drayage Problem[J]. IEEE Transactions on Intelligent Transportation Systems， 2020（99）：1-13

[4] Wang D， Zhou Y， Jiang S， et al. A Simplex Method-Based Salp Swarm Algorithm for Numerical and Engineering Optimization[J]. Springer， Cham，2018

[5] Sayed G I， Khoriba G， Haggag M H. A novel chaotic salp swarm algorithm for global optimization and feature selection[J]. Applied Intelligence，2018

[6] Mirjalili S， Gandomi A H， Mirjalili S Z， et al. Salp swarm algorithm： a bio-inspired optimizer for engineering design problems[J]. Advances in Engineering Software， 2017：163-191

[7] 丁蕊.復(fù)雜高維多目標(biāo)優(yōu)化方法[M].北京：電子工業(yè)出版社，2020

[8] 周密，王瀟棠，閆河，等.一種混沌映射動態(tài)慣性權(quán)重的樽海鞘群算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2021：1-7

作者簡介：馬明明（1993-），男，河北省邢臺市人，在職研究生，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)研究、物流系統(tǒng)優(yōu)化研究。