基于改進(jìn)鯨魚算法的汽車材料運(yùn)輸應(yīng)急調(diào)度及平臺(tái)研究

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

(1.銅川職業(yè)技術(shù)學(xué)院,陜西 銅川 727031;2.陜西科技大學(xué),陜西 西安 710016)

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

1 汽車材料運(yùn)輸應(yīng)急調(diào)度平臺(tái)總體框架

參考主流的運(yùn)輸調(diào)度算法思維導(dǎo)圖(見圖1)總結(jié)目前主流的運(yùn)輸調(diào)度方法,研究提出基于分組移動(dòng)的鯨魚群算法的運(yùn)輸應(yīng)急調(diào)度平臺(tái),其采用多層次技術(shù)結(jié)構(gòu),將路況、運(yùn)輸距離、時(shí)間等因素加入決策方案中;具體平臺(tái)設(shè)計(jì)框圖如圖2所示。

圖1 主流的運(yùn)輸調(diào)度算法

圖2 平臺(tái)整體框架

由圖2可知,整個(gè)框架分為4層結(jié)構(gòu),其中應(yīng)用服務(wù)層是配送中心調(diào)度管理的系統(tǒng)平臺(tái);系統(tǒng)支持層是為應(yīng)用服務(wù)層提供相應(yīng)的算法和基本應(yīng)用的支持,包括用戶管理和數(shù)據(jù)的管理;基礎(chǔ)數(shù)據(jù)層是提供地理及路線等基礎(chǔ)數(shù)據(jù),存儲(chǔ)系統(tǒng)應(yīng)用用戶等重要數(shù)據(jù);底層硬件是放置在運(yùn)輸車輛中的,目的是讓運(yùn)輸車輛和平臺(tái)建立聯(lián)系,并接收調(diào)度方案,安排運(yùn)輸車輛行駛路線。

2 平臺(tái)硬件與軟件設(shè)計(jì)

2.1 硬件部分設(shè)計(jì)

本應(yīng)急調(diào)度平臺(tái)的需求:①對(duì)運(yùn)輸車輛進(jìn)行GPS定位;②對(duì)運(yùn)輸車輛發(fā)送調(diào)度命令。因此,考慮到上述需求,講運(yùn)輸車輛基礎(chǔ)硬件設(shè)計(jì)為如圖3所示。在硬件部分中,主要包括PIC單片機(jī)、GPS模塊和GSM模塊等。平臺(tái)通過GPS精確定位運(yùn)輸工具,通過GSM數(shù)據(jù)接口完成應(yīng)急調(diào)度。

圖3 硬件結(jié)構(gòu)圖

2.2 平臺(tái)界面設(shè)計(jì)

汽車材料運(yùn)輸?shù)腤eb頁(yè)面是面向應(yīng)急調(diào)度系統(tǒng)的二次開發(fā),其中頁(yè)面模塊中對(duì)應(yīng)的關(guān)系如圖4所示。

圖4 軟件設(shè)計(jì)框架

3 基于分組移動(dòng)的鯨魚群算法平臺(tái)應(yīng)急調(diào)度策略設(shè)計(jì)

對(duì)汽車材料運(yùn)輸?shù)恼{(diào)度主要是通過應(yīng)急調(diào)度決策模塊實(shí)現(xiàn),調(diào)度決策過程需要綜合考慮已發(fā)出的車輛、路況動(dòng)態(tài)變化、運(yùn)輸距離等因素,通過算法選擇較優(yōu)的運(yùn)輸路徑,再由平臺(tái)發(fā)送調(diào)度方案到需要進(jìn)行移動(dòng)的運(yùn)輸車輛基礎(chǔ)設(shè)備中,從而高效完成材料運(yùn)輸?shù)墓ぷ鳌＞C合目前的應(yīng)急調(diào)度優(yōu)化算法,采用鯨魚群算法(WSA)進(jìn)行改進(jìn)和求解[6-8]。具體從以下幾點(diǎn)改進(jìn):

3.1 初始化方式

在傳統(tǒng)鯨魚群算法中,引導(dǎo)個(gè)體在求解較優(yōu)路徑時(shí)具有較好效果,但在求解大規(guī)模車輛路徑問題時(shí),求解速度下降。當(dāng)?shù)缆仿窙r變化時(shí),會(huì)導(dǎo)致種群更新或多個(gè)種群求解速度不達(dá)標(biāo),所以提出的基于分組移動(dòng)的鯨魚群算法進(jìn)行路線更新。其中,采用基于最短路徑變異的混合算子對(duì)種群進(jìn)行初始化;然后進(jìn)行分組,并對(duì)剩余未接收到材料的接收點(diǎn)進(jìn)行配送。算法優(yōu)先使用當(dāng)前已發(fā)出的車輛,若不滿足條件,再?gòu)呐渌椭行呐沙鲂碌能囕v進(jìn)行汽車危險(xiǎn)化學(xué)品材料的運(yùn)輸?？紤]到路況信息更新時(shí)需要重新規(guī)劃未被訪問的接收點(diǎn),此時(shí)開始節(jié)點(diǎn)不一定是配送中心(可能是道路交叉點(diǎn)或接收點(diǎn)),且此時(shí)的車輛不一定處于滿載狀態(tài)。因此,采用最短路徑算法生成的子問題初始解,并對(duì)初始解進(jìn)行擴(kuò)充,從而得到初始種群。

3.2 種群個(gè)體分組

對(duì)當(dāng)前種群的個(gè)體根據(jù)其差異性進(jìn)行等量劃分,進(jìn)行層次聚類分組,具體算式:

(2)

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

衡量種群中個(gè)體的質(zhì)量,具體衡量公式:

(3)

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

計(jì)算個(gè)體間的差異,具體計(jì)算公式:

(4)

式中:n代表總接收點(diǎn)數(shù);m表示個(gè)體使用的車輛數(shù)。

3.3 個(gè)體移動(dòng)方式

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

圖5 改進(jìn)算法圖示

3.4 擴(kuò)展搜搜空間策略

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

(5)

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

另外,由式(3)可知,個(gè)體質(zhì)量與個(gè)體所表示的車輛總行駛距離成反比,即個(gè)體所表示的車輛總行駛距離越長(zhǎng),其質(zhì)量越差。而在同一個(gè)體中,由于每輛車所配送的接收點(diǎn)不同,導(dǎo)致車輛行駛的距離具有一定差異,因而個(gè)體中每輛車的行駛距離對(duì)其質(zhì)量產(chǎn)生的影響程度也不同。在同一車輛段(車輛段表示一個(gè)車輛的完整行駛路徑,包括車輛所訪問的接收點(diǎn)及其配送順序)中,車輛訪問某一接收點(diǎn)所行駛的距離與該接收點(diǎn)在車輛段中的相對(duì)位置有關(guān),所以需要考慮個(gè)體中不同車輛段或接收點(diǎn)訪問順序?qū)λ阉骺臻g產(chǎn)生的影響。因此對(duì)于種群中的個(gè)體,分別計(jì)算個(gè)體中每輛車的行駛距離在總行駛距離中的占比,從而得到每個(gè)車輛段權(quán)重:

w=di/Di

(6)

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

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 實(shí)驗(yàn)準(zhǔn)備

為驗(yàn)證算法及平臺(tái)生成初始路徑的有效性,利用不同算法對(duì)采集到的汽車材料應(yīng)急運(yùn)輸數(shù)據(jù)集進(jìn)行對(duì)比實(shí)驗(yàn)。其中設(shè)置數(shù)據(jù)集的節(jié)點(diǎn)數(shù)分別為10、20、50和100,節(jié)點(diǎn)位置和節(jié)點(diǎn)需求量為隨機(jī)選取,種群大小為30、LTMU大小為6,分組數(shù)為2,多樣性閾值為0.4。

4.2 算法橫向?qū)Ρ?/h3>

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

表1 不同節(jié)點(diǎn)數(shù)下2組數(shù)據(jù)在3種算法的計(jì)算結(jié)果

由表1可知,隨著種群的迭代更新,節(jié)點(diǎn)數(shù)的增加,傳統(tǒng)算法的偏差逐漸增大,最優(yōu)解在改進(jìn)的算法下計(jì)算出的距離最小,對(duì)運(yùn)輸成本和運(yùn)輸時(shí)間上更有優(yōu)勢(shì)。同時(shí),在解算相同問題時(shí),分組進(jìn)行的鯨魚群算法的計(jì)算結(jié)果遠(yuǎn)遠(yuǎn)高于ACS和ACGA算法,對(duì)節(jié)點(diǎn)數(shù)多的時(shí)候更加有優(yōu)勢(shì)。同時(shí),在解算相同問題時(shí),分組進(jìn)行的鯨魚群算法的計(jì)算結(jié)果遠(yuǎn)遠(yuǎn)高于ACS和ACGA算法,對(duì)節(jié)點(diǎn)數(shù)多的時(shí)候更加有優(yōu)勢(shì)。

5 結(jié)語

綜上,基于汽車材料運(yùn)輸中路況這一動(dòng)態(tài)因素,結(jié)合鯨魚群算法的原理進(jìn)行改進(jìn),用于制定初始車輛的行駛路徑,并能經(jīng)過路況這一因素進(jìn)行及時(shí)的調(diào)整調(diào)度方案,從個(gè)體移動(dòng)和種群搜索空間兩個(gè)方面對(duì)算法進(jìn)行了優(yōu)化,實(shí)現(xiàn)了在動(dòng)態(tài)路況變化下汽車危險(xiǎn)化學(xué)材料運(yùn)輸?shù)膶?shí)時(shí)更新調(diào)度,且平均距離得到了較大的改善,對(duì)運(yùn)輸成本的控制有著實(shí)際作用,保證了調(diào)度方案的可行性和高效性。