混合變異自適應樽海鞘算法的甩掛運輸多目標調度優化

摘? 要： 建立一種考慮時間窗的甩掛運輸多目標調度模型，提出一種改進樽海鞘算法的求解策略。通過引入混合變異算子，改進樽海鞘算法領導者位置易陷入局部最優的問題，增加種群多樣性；通過引入動態慣性權重策略，使追隨者在迭代后期減小搜索步長，提高算法收斂精度。實驗結果表明，該改進的樽海鞘算法具有較高的全局搜索能力，能有效得出甩掛運輸多目標問題最優解，相關研究結論能夠為大型企業運輸提供決策支持。

關鍵詞： 樽海鞘算法； 甩掛運輸； 混合變異策略； 動態慣性權重優化算法

中圖分類號：TP18? ? ? ? ? 文獻標識碼：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 引言

甩掛運輸是指牽引車將集裝箱甩在指定的地點后，執行其他運輸任務的物流模式。其優點是可以實現運輸和裝卸同時進行，相對于傳統運輸模式，甩掛運輸能較好地解決一些企業車輛等待裝卸時間長、車輛利用率低、在途車輛多、環境破壞嚴重等問題。

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

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

1 多目標甩掛運輸調度模型

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

一輛牽引車只拖帶一輛掛車。牽引車和掛車的甩掛操作只能在裝卸貨點完成。牽引車最初停放在中心節點，完成任務后返回中心節點。每一個運輸任務都可用一輛掛車完成裝貨任務。

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

[ykij=1，牽引車連續執行任務i和任務j0，其他]

[xki=1，牽引車執行任務i0，其他]

考慮運輸成本和碳排放的多目標函數與考慮時間窗的約束條件的具體模型如下：

⑴ 目標函數

⑵ 約束函數

時間窗約束⑶⑷表示牽引車到達節點的時間不能早于該節點的最早到達時間，不能晚于該節點最遲到達時間。約束⑸一輛牽引車只能訪問一次運輸任務。

2 改進的樽海鞘算法

2.1 基本樽海鞘算法

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

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

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

t和tmax是當前迭代次數和最大迭代次數。領導者位置更新完成后，更新追隨者位置。公式如下：

2.2 樽海鞘算法的改進策略

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

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

引入高斯變異機制的領導者位置更新公式：

其中，[gaussion0，1]為標準高斯分布。

引入柯西變異機制的領導者位置更新公式：

引入萊維變異機制的領導者位置更新公式：

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

[ω]是自適應慣性權重，[ωmax]和[ωmin]分別是慣性權重的最大值和最小值界限，[α]是15到30之間的隨機數。

具體的改進樽海鞘算法的尋優流程如下：

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

步驟2 計算樽海鞘個體的適應度值，根據適應度值確定非支配解；

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

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

步驟5 更新種群個體位置，按一定的概率選擇一種變異策略領導者更新公式進行混合策略變異操作；

步驟6 如果變異后的適應度函數值更優，則增加該個體所使用的相應變異算子的概率，否則，減少該個體所使用的相應變異算子的概率；

步驟7 計算追隨者的慣性權重值，并更新帶有自適應慣性權重值的追隨者位置；

步驟8 判斷當前迭代次數是否達到當前設定的最大迭代次數，若是，則停止運行并輸出最優解，此時食物源庫中的個體即為所求最優解集，若否，則返回步驟2繼續運行。

3 改進樽海鞘算法的收斂性與有效性分析

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

為進一步驗證算法的精度性能，對每個標準測試函數運行30次，其結果表示如表1所示。平均值為精度平均值，標準差可反應算法的穩定性。對比表1中試驗結果可得出，改進的KESSA算法的標準差要比SSA算法的小很多，說明改進算法有更好的穩定性，從最優值和平均值來看，改進算法的求解精度更高。由此得出，引進的混合變異自適應樽海鞘算法比原算法尋優能力更強。

4 改進樽海鞘算法在甩掛運輸調度優化的應用

本文對成耀榮等[2]的甩掛運輸數據進行改進并實驗。以廠內棒材廠、成品庫、熱軋板廠、冷軋板、轉爐廠等十個主要廠址為網絡節點，編號為0的中心節點停放牽引車。網絡的弧為運輸道路。表2為網絡節點坐標，表3為每日的運輸量與運輸時間窗數據。

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

5 結束語

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

參考文獻（References）：

[1] 楊珍花，王滋承，魏照坤，等.掛車裝卸時間不確定的甩掛車輛動態調度優化[J].系統工程理論與實踐，2021，41（5）：1081-1095

[2] 成耀榮，楊謙，鄭國華.考慮碳排放的大型制造企業甩掛運輸牽引車調度優化[J].吉林大學學報（工學版），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] 丁蕊.復雜高維多目標優化方法[M].北京：電子工業出版社，2020

[8] 周密，王瀟棠，閆河，等.一種混沌映射動態慣性權重的樽海鞘群算法[J].小型微型計算機系統，2021：1-7

作者簡介：馬明明（1993-），男，河北省邢臺市人，在職研究生，主要研究方向：計算機應用技術研究、物流系統優化研究。