電動汽車路徑優化調度的改進飛蛾算法

張 強，毛清華，梁 萍

(燕山大學 經濟管理學院，河北 秦皇島 066004)

隨著我國經濟水平不斷提高，私家車擁有率逐年提升，環境污染和能源消耗過度問題日益突出.為了節能減排，建設美麗中國，電動汽車成為國家戰略新興產業，其市場蓬勃發展.但是與燃油車相比，電動汽車存在續航里程短的缺點，半路拋錨現象比較常見，因此科學規劃電動汽車充電路徑具有重要價值.

國內外學者進行了電動汽車充電路徑規劃的相關研究.在模型構建上，主要分為四類：第一類主要從能量消耗角度建立模型，如Baum等[1-2]以能量消耗最低為目標建立路徑優化模型；第二類主要從成本角度出發建立模型，如Fu等[3]考慮時間成本和旅行成本最小化，張佳佳等[4]以配送總成本最小化為目標建立電動物流車輛路徑優化模型，李英等[5-6]考慮差異化服務成本，建立多車型混合車隊配置的成本最優模型；第三類考慮從負載角度建立模型，Schiffer等[7-8]考慮負載影響，分別建立了距離最小化模型，以及固定成本和能耗成本構成的總成本最小化模型；第四類從充電策略角度出發建立模型，如葛顯龍等[9]考慮部分充電策略，建立帶時間窗的電動汽車物流配送路徑整數規劃模型，周天沛等[10]建立行駛路程最近、時間最短、充電站時間利用率偏差最小和功率利用率偏差最小的多目標路徑優化模型.在模型求解上，大多采用傳統智能優化算法，如遺傳算法[11-12]、粒子群算法[13]和蟻群算法[14-16]，粒子群算法比遺傳算法和蟻群算法收斂速度快，但三者都容易陷入局部最優解.Mirjalili[17]提出了新型智能優化算法-飛蛾火焰算法(MFO)，其具有參數少和魯棒性強的優點，但和其他智能算法一樣，在算法后期容易陷入局部最優的問題，目前，該算法鮮見應用于電動汽車路徑規劃問題.

綜上分析，當前電動汽車充電路徑規劃研究大多以能量消耗最小或出行總成本最小為優化目標，多采用傳統智能優化算法求解模型.本文考慮道路擁擠度，將電池能耗作為約束條件，建立以出行總時間最小為目標的路徑優化調度模型，并設計一種改進飛蛾算法進行求解，并將此算法應用在電動汽車路徑規劃上，拓展了該算法的應用領域.

1 電動汽車充電路徑優化調度模型構建

1.1 問題描述

電動汽車由于續航能力較差，經常會出現電量耗盡被困路途中的情況，因此合理規劃電動汽車出行路徑很重要.對于用戶來說，在剩余電量有限的情況下，行駛時間越短越好.本文擬建立以用戶從起始點到目的地的行駛總時間最短為優化目標，考慮道路擁擠影響，以電池能耗為約束條件，建立路徑優化調度模型.為方便建模和求解，做出以下假設：

1)電動汽車在整個路段行駛過程中，保持勻速；

2)將道路網格化處理，劃分為水平路段和垂直路段；

3)各個路段的車輛數隨機產生；

4)只考慮快速充電樁，不考慮慢速充電樁.

1.2 電動汽車路徑優化調度模型

1.2.1 道路擁擠度 道路擁擠度對電動汽車行駛時間有一定影響，汽車經過路段的擁擠度越高，耗費時間越長，反之耗費時間越短.引進擁堵系數ε表示擁堵程度，系數值越大，擁堵程度越高，其計算公式為[18]：

(1)

其中：N表示進入道路的車輛數，M為道路順暢通行的閾值容量，H為引起道路擁堵的車輛數臨界值.當道路車輛數小于閾值容量時，表明道路順暢無阻；大于車輛數臨界值時，表明道路擁堵；其余情況，表示通行緩慢.

1.2.2 電動汽車路徑優化調度數學模型 基于城市道路的復雜性，將城市道路網格化，劃分成水平道路和垂直道路，如圖1所示，電動汽車從S點出發，先到充電站充滿電，然后行駛到目的地D，形成一個完整的SD路徑.其中水平道路集合為{x11,x12,x13,…,xfm}，對應的長度為{dl,11,dl,12,…,dl,fm}，垂直道路集合為{y11,y12,…,ynm}，對應的長度為{dv,11,dv,12,…,dv,nm}，充電站的集合為{C1,C2,…,Cf}，充電站到目的地的路段集合為{z1,z2,…,zf}，對應的長度為{dz,1,dz,2,…,dz,f}，其中m表示水平道路條數，n表示垂直道路條數，f=n+1[14].

圖1 路網結構圖Fig.1 Structure of the network

1.2.3 數學模型表達式

目標函數：

(2)

約束條件：

xfm,ynm,zf={0,1},

(3)

x11+y11=1,

(4)

xnm+ynm=xnm′+yn′m，?n,m,

(5)

xfm=xfm′+ynm，?n,m,

(6)

xfm=zf，?f,

(7)

(8)

(9)

(10)

上述模型中各個表達式及符號說明如表1所示.

表1 表達式及符號含義Tab.1 Expressions and symbolic meaning

2 飛蛾算法及其改進

2.1 初始化種群

飛蛾的集合矩陣如下：

M=(m1,m2,…,mn′)T,mi=(mi,1,mi,2,…,mi,d)T.

(11)

其中，n′表示飛蛾的數量，d′是變量(維度).

飛蛾的適應度值矩陣如下：

OM=(OM1，OM2,…,OMn′)T.

(12)

火焰的集合矩陣表示如下：

F=(f1,f2,…,fn′)T,fi=(fi,1,fi,2,…,fi,n′)T.

(13)

火焰的適應度值矩陣如下：

OF=(OF1,OF2,…,OFn′)T.

(14)

2.2 位置更新方式

飛蛾的位置一直是圍繞火焰螺旋飛行來不斷更新，位置更新公式為：

S(Mi,Fj)=Di·ebt·cos(2πt)+Fj,

(15)

Di=|Fj-Mi|.

(16)

其中：Mi表示第i只飛蛾，Fj表示第j個火焰，S為螺旋形函數，Di表示第i只飛蛾與第j個火焰間的距離；b為定義數螺旋線形狀的一個參數；t為[-1,1]內的隨機數，表示飛蛾的下一個位置靠近火焰的程度，t值越大，表示距離火焰越近，反之，表示距離火焰越遠.

2.3 火焰數量減少機制

火焰數量會隨著迭代進程的推進而不斷地減少，即劣解不斷地會被淘汰，此過程也被稱為棄焰行為.火焰數量減少公式為：

flameno=round(Z-l(Z-1)/L).

(17)

其中：Z表示火焰數量的最大值，l為當前迭代次數，L表示最大迭代次數.

2.4 改進飛蛾算法(IMFO)

2.4.1 動態自適應權重 參考慣性權重的思想，提出一種正弦動態慣性權重因子ω，并引入到飛蛾位置更新方式中，ω的計算公式和改進后的飛蛾位置更新公式為：

ω=(ωmax+ωmin)/2+(ωmax-ωmin)sin(π·l/2L+π),

(18)

S(Mi,Fj)=Di·ebt·cos(2πt)+ωFj.

(19)

其中ωmax為初始慣性權重，ωmin為迭代結束時的慣性權重.圖2為動態權重因子的變化趨勢圖，從圖2可以清晰地看出，動態權重在迭代初期擁有較大的值，有助于全局搜索，到迭代后期，曲線下降速度變慢，權值較小，增強了局部開發的能力，提高精度.

圖2 動態權重變化趨勢 圖3 改進前后火焰數量變化Fig.2 Trends in dynamic weights Fig.3 Changes in flame number before and after improvement

2.4.2 改變火焰數量更新機制 通過改變棄焰行為公式[19]，如圖3所示，將火焰數量更新機制由直線下降改為曲線下降，可以加快火焰數量的淘汰速度，進而提升算法的收斂速度.改進后的火焰更新公式為：

flameno=round[L/(l+(L/Z))].

(20)

2.4.3 變螺旋位置更新 飛蛾在找尋火焰的階段中，會根據自身與火焰間的螺旋形狀，隨時調整每次位置更新的移動距離，在螺旋更新機制(15)中，常數b是控制螺旋形狀的主要參數，通常情況下，該參數設置成一個固定數值，每次位置更新依據不同的螺旋角度進行移動調整，但是如果b設置為固定數值，會導致飛蛾圍繞火焰更新位置方式過于單一，缺乏靈活性，容易導致算法陷入局部極值的誤區，降低算法全局搜索的能力.

為解決該問題，使飛蛾能夠開發出更加多樣變化的搜索路徑進行位置更新，引入變螺旋探索的思想，將常數b設計成隨迭代次數變化的變量，動態隨機調整飛蛾搜索火焰的螺旋形狀，增加飛蛾探尋未知區域的能力[20]，與此同時，為增強火焰的多樣性和隨機性，在火焰位置加入隨機變量rand，進而提高算法全局探索能力.結合自適應動態權重，新的飛蛾螺旋位置更新方式為：

(21)

2.4.4 柯西變異 為提升算法后期逃逸局部區域的能力，在迭代后期對所有的飛蛾和火焰位置進行柯西擾動，通過柯西擾動變異算子，擺脫局部空間，加強全局尋優能力.柯西擾動機制為：

(22)

其中cauchy(0,1)為標準柯西分布.柯西分布隨機變量生成函數為η=tan[(ξ-0.5)π].S′(l)為柯西擾動變異后的新位置，b1是變異控制系數[21].

2.4.5 融合模擬退火算法 模擬退火算法具有一定概率接受劣解的特點，借助這一特性，可以進一步提高飛蛾算法全局尋優的能力.具體步驟如下.

步驟1 初始化：設定初始溫度t0，任取初始解S1，確定每個t的迭代次數.

步驟2 對當前溫度t重復步驟3至步驟6.

步驟3 給當前解S1附近進行隨機擾動，得到新解S2.

步驟4 計算增量Δh=f(S2)-f(S1).

步驟6 判斷是否達到終止條件，達到輸出最優解，否則降低溫度t跳轉步驟2.

改進飛蛾算法步驟如下：

步驟1 初始化算法參數，設置種群規模n′、迭代次數L等參數.

步驟2 計算飛蛾的適應度值，并按照大小進行排序，然后賦值給火焰，形成火焰的初始空間位置.

步驟3 按照公式(21)更新飛蛾的位置.

步驟4 重新計算飛蛾和火焰的適應度值并排序，將更優的適應度值對應的位置作為下一代火焰的位置.

步驟5 按照改進后的火焰更新公式(20)減少火焰數量，并引入模擬退火機制接收劣解.

步驟6 依據公式(22)對當前所有飛蛾和火焰位置進行柯西擾動產生新解，并融合模擬退火策略接受劣解.

步驟7 判斷是否達到終止條件，若滿足，輸出最優解，否則，跳轉執行步驟2.

2.5 算法性能測試

為測試IMFO的有效性，與PSO[13]、MFO[17]、GWO[22]基于8個基準測試函數進行性能比較，測試函數中包括單峰函數和多峰函數，為公平驗證IMFO的有效性，實驗仿真過程均在MATLAB2019a，CPU：Inter(R)Core(TM) i5-3230M CPU@2.60GHz 2.600GHz，操作系統：Microsoft Windows 8.1同一運行環境中完成，且各個函數獨立運行30次.并且算法通用條件設置相同，種群數量為50，最大迭代次數為300次.

2.5.1 算法參數設置 表2、表3分別為算法參數設置信息和8個基準測試函數的具體信息.

表2 算法參數表Tab.2 Parameters of the algorithm

表3 基準測試函數Tab.3 Benchmarking function

表3中，f1至f5均為30維的單峰函數，主要測試算法的求解速率；f6至f8均為30維的多峰函數，主要測試算法跳出局部最優的能力和收斂精度.

2.5.2 算法性能結果對比分析 基于以上參數設置和8個基準測試函數，使用Matlab2019a完成算法編寫和仿真實驗.為增強實驗結果說服力，降低偶然誤差的可能性，各個算法在每一個基準測試函數上獨立運行30次.求解結果如表4所示.

表4 基準測試函數優化結果比較Tab.4 Comparison of optimal results of benchmarking function

由表4可以發現，IMFO求解各個基準測試函數的平均值與其余3種算法更接近理論全局最優值，標準差的數值更小，標準差低表明求解數據波動較小，尋優過程魯棒性更強.因此IMFO算法在尋優性能上相較于MFO、GWO和PSO算法精確度更高，更容易尋到最優解.

2.5.3 算法收斂曲線對比分析 基準測試函數曲線能夠直觀地描述各個算法的收斂速率和收斂精度.8個基準測試函數的收斂曲線如圖4所示，其中橫軸代表迭代次數，縱軸代表適應度值的對數log.從收斂曲線圖可知，改進飛蛾算法(IMFO)具備更優的收斂性能，其收斂曲線更加平滑，較大的拐點很少，曲線一直位于最下方，表明收斂速度更快，與其他3種算法相比，IMFO算法的log值更小，表明收斂精確度更高.

圖4 8個基準測試函數收斂曲線Fig.4 Convergence curve of 8 benchmark functions

3 算例分析

3.1 測試實例

3.2 結果分析

為了驗證IMFO算法的性能，與GA[11]、PSO[12]、MFO[17]進行比較，各算法優化結果如表5所示.

表5 四種算法路徑信息表Tab.5 Four algorithm path information tables

IMFO最優迭代曲線如圖5所示.4種算法收斂曲線比較如圖6所示.

圖5 IMFO最優迭代曲線 圖6 四種算法收斂曲線比較Fig.5 IMFO Optimal iteration curve Fig.6 Comparison of convergence curves of four algorithms

由表5可知，IMFO算法路徑優化的行駛總時間為2.106 6h，比GA、PSO、MFO算法行駛時間更短.與基本飛蛾算法(MFO)相比，行駛時間節省了0.085h.由圖6可知，相比其它3種算法，改進飛蛾算法(IMFO)求解精度更佳，說明IMFO算法有效地跳出了局部最優，具有更好的全局搜索性能.綜上可得，改進飛蛾算法(IMFO)在求解電動汽車路徑優化問題上是一種更為高效的優化算法.

4 結論

提出了一種改進飛蛾算法(IMFO)，并基于基準測試函數與PSO、GWO和MFO進行了性能比較，然后利用IMFO算法求解了電動汽車路徑優化模型，得出以下結論.

考慮了道路擁擠性，以電池能耗作為約束條件，建立了以行駛總時間最小為目標的電動汽車路徑優化模型，模型更加貼近現實.

改進飛蛾算法(IMFO)的求解精度和收斂速率均得到一定增幅.通過設計變螺旋位置更新機制，提高了全局開掘能力，融合模擬退火和柯西變異策略，增強了算法逃逸局部領域的能力；引入自適應權重因子，改變飛蛾位置更新方式，以及改變火焰數量減少方式，加快了收斂速度.

基于基準測試函數發現，IMFO比PSO、GWO和MFO3種算法具有更好的全局搜索性能，尋優精度更佳，求解速率更快.

求解電動汽車路徑優化模型發現，IMFO具備更好的尋優能力，求解結果更優，路徑規劃更加合理，證明其能夠有效求解路徑優化問題，拓寬了算法的應用領域.未來研究可以在模型上考慮用戶的主觀選擇行為，或尋找一種更為高效的算法求解此類問題，或者將此算法求解其他問題，擴大該算法的應用領域.