基于改進鯨魚算法的汽車材料運輸應急調度及平臺研究

王 爽,梁 娜,劉慶軍,安繪春

(1.銅川職業技術學院,陜西 銅川 727031;2.陜西科技大學,陜西 西安 710016)

在汽車材料中,存在部分危險化學品,一旦運輸時間過長,容易在空氣中暴露,進而造成嚴重的環境污染[1-2]。因此,建立科學的調度平臺,對提高汽車材料運輸的應急調度起得到積極的作用。而針對應急調度問題,文家燕等提出灰狼優化算法(GWO)和非支配排序遺傳算法(NSGA-Ⅱ)應用到礦車的運輸調度中,驗證了算法尋優的效果,但沒有考慮路況變化因素[3];王思涵等采用鯨魚群算法對車間的調度工作進行了測試,驗證了算法的可行性和有效性[4];蔣華偉等針對鯨魚群算法求解多配送中心帶時間窗的物資應急調度問題時存在的易陷入局部極值等缺點,提出一種改進離散鯨魚群算法[5]?；诖?研究則結合汽車材料應急運輸中存在的暴露易導致環境污染的問題,考慮路況變化因素對運輸調度方案的影響,提出采用鯨魚群算法,并運用到汽車材料運輸的調度方案中,從而保證汽車危險材料的應急調度安全。

1 汽車材料運輸應急調度平臺總體框架

參考主流的運輸調度算法思維導圖(見圖1)總結目前主流的運輸調度方法,研究提出基于分組移動的鯨魚群算法的運輸應急調度平臺,其采用多層次技術結構,將路況、運輸距離、時間等因素加入決策方案中;具體平臺設計框圖如圖2所示。

圖1 主流的運輸調度算法

圖2 平臺整體框架

由圖2可知,整個框架分為4層結構,其中應用服務層是配送中心調度管理的系統平臺;系統支持層是為應用服務層提供相應的算法和基本應用的支持,包括用戶管理和數據的管理;基礎數據層是提供地理及路線等基礎數據,存儲系統應用用戶等重要數據;底層硬件是放置在運輸車輛中的,目的是讓運輸車輛和平臺建立聯系,并接收調度方案,安排運輸車輛行駛路線。

2 平臺硬件與軟件設計

2.1 硬件部分設計

本應急調度平臺的需求:①對運輸車輛進行GPS定位;②對運輸車輛發送調度命令。因此,考慮到上述需求,講運輸車輛基礎硬件設計為如圖3所示。在硬件部分中,主要包括PIC單片機、GPS模塊和GSM模塊等。平臺通過GPS精確定位運輸工具,通過GSM數據接口完成應急調度。

圖3 硬件結構圖

2.2 平臺界面設計

汽車材料運輸的Web頁面是面向應急調度系統的二次開發,其中頁面模塊中對應的關系如圖4所示。

圖4 軟件設計框架

3 基于分組移動的鯨魚群算法平臺應急調度策略設計

對汽車材料運輸的調度主要是通過應急調度決策模塊實現,調度決策過程需要綜合考慮已發出的車輛、路況動態變化、運輸距離等因素,通過算法選擇較優的運輸路徑,再由平臺發送調度方案到需要進行移動的運輸車輛基礎設備中,從而高效完成材料運輸的工作。綜合目前的應急調度優化算法,采用鯨魚群算法(WSA)進行改進和求解[6-8]。具體從以下幾點改進:

3.1 初始化方式

在傳統鯨魚群算法中,引導個體在求解較優路徑時具有較好效果,但在求解大規模車輛路徑問題時,求解速度下降。當道路路況變化時,會導致種群更新或多個種群求解速度不達標,所以提出的基于分組移動的鯨魚群算法進行路線更新。其中,采用基于最短路徑變異的混合算子對種群進行初始化;然后進行分組,并對剩余未接收到材料的接收點進行配送。算法優先使用當前已發出的車輛,若不滿足條件,再從配送中心派出新的車輛進行汽車危險化學品材料的運輸?？紤]到路況信息更新時需要重新規劃未被訪問的接收點,此時開始節點不一定是配送中心(可能是道路交叉點或接收點),且此時的車輛不一定處于滿載狀態。因此,采用最短路徑算法生成的子問題初始解,并對初始解進行擴充,從而得到初始種群。

3.2 種群個體分組

對當前種群的個體根據其差異性進行等量劃分,進行層次聚類分組,具體算式:

(2)

式中:μi、Si分別表示第i類樣本的均值向量和樣本集合。

衡量種群中個體的質量,具體衡量公式:

(3)

式中:di表示個體i完成配送行駛的總距離。

計算個體間的差異,具體計算公式:

(4)

式中:n代表總接收點數;m表示個體使用的車輛數。

3.3 個體移動方式

在上述基礎上,引入長期記憶單元(LTMU)來記錄種群中最優個體。當路況發生變化時,若當前種群不是初始種群,則將新種群最優個體與初始種群中的最優個體進行比較,若新種群的個體優于初始種群個體,則用新種群替換初始種群;反之不變。替換后更新LTMU的其他個體,具體過程如圖5所示[9-15]。

圖5 改進算法圖示

3.4 擴展搜搜空間策略

隨著節點個數增加,鯨魚個體的移動是以原有個體為基礎,引導個體為導向進行的局部小范圍搜索;而種群個體的更新趨于空間解,在移動時,計算量呈爆炸式增長,若種群中個體都進行移動會導致種群多樣性降低,不能獲取在全局范圍內的最優解。因此使用種群多樣性來反映種群個體移動時總搜索空間的大小和個體間差異表示,因此在式(4)基礎上構建式(5)來衡量種群多樣性。

(5)

式中:s代表種群大小;dij為式4計算所得的個體間的差異性。

另外,由式(3)可知,個體質量與個體所表示的車輛總行駛距離成反比,即個體所表示的車輛總行駛距離越長,其質量越差。而在同一個體中,由于每輛車所配送的接收點不同,導致車輛行駛的距離具有一定差異,因而個體中每輛車的行駛距離對其質量產生的影響程度也不同。在同一車輛段(車輛段表示一個車輛的完整行駛路徑,包括車輛所訪問的接收點及其配送順序)中,車輛訪問某一接收點所行駛的距離與該接收點在車輛段中的相對位置有關,所以需要考慮個體中不同車輛段或接收點訪問順序對搜索空間產生的影響。因此對于種群中的個體,分別計算個體中每輛車的行駛距離在總行駛距離中的占比,從而得到每個車輛段權重:

w=di/Di

(6)

式中:Di表示所有車輛總的行駛距離。

根據式(6)可得到每個節點在該車輛段中的權重,刪除權重最大的節點,計算當前車輛段中車輛的可用載重。依次對其余節點進行遍歷,隨機選擇其中一個節點插入一個新節點后總距離最小,且滿足所選節點的需求量不超過可用載重,則交:2個節點的位置,從而產生新個體。

4 實驗結果與分析

4.1 實驗準備

為驗證算法及平臺生成初始路徑的有效性,利用不同算法對采集到的汽車材料應急運輸數據集進行對比實驗。其中設置數據集的節點數分別為10、20、50和100,節點位置和節點需求量為隨機選取,種群大小為30、LTMU大小為6,分組數為2,多樣性閾值為0.4。

4.2 算法橫向對比

為驗證分組移動的鯨魚群(WSA-PM)算法求解的性能,與目前常使用的蟻群系統(ACS)、自適應混沌遺傳算法(ACGA)對相同問題進行求解,計算結果如表1所示。

表1 不同節點數下2組數據在3種算法的計算結果

由表1可知,隨著種群的迭代更新,節點數的增加,傳統算法的偏差逐漸增大,最優解在改進的算法下計算出的距離最小,對運輸成本和運輸時間上更有優勢。同時,在解算相同問題時,分組進行的鯨魚群算法的計算結果遠遠高于ACS和ACGA算法,對節點數多的時候更加有優勢。同時,在解算相同問題時,分組進行的鯨魚群算法的計算結果遠遠高于ACS和ACGA算法,對節點數多的時候更加有優勢。

5 結語

綜上,基于汽車材料運輸中路況這一動態因素,結合鯨魚群算法的原理進行改進,用于制定初始車輛的行駛路徑,并能經過路況這一因素進行及時的調整調度方案,從個體移動和種群搜索空間兩個方面對算法進行了優化,實現了在動態路況變化下汽車危險化學材料運輸的實時更新調度,且平均距離得到了較大的改善,對運輸成本的控制有著實際作用,保證了調度方案的可行性和高效性。