電動汽車充電路徑規劃研究*

趙文清 王繼發

（華北電力大學計算機系 保定 071003）

1 引言

電動汽車的動力采用對電動車充電，放置充放電電瓶作為存放電動汽車驅動動力的承載裝置，但是電瓶對電動汽車所能承擔的動力有限。因此，對于電動汽車充電問題便成為當今社會致力于研究該內容的專家學者的“重頭戲”，在滿足電動汽車日常充電的需求的基礎上，還需對充電路徑進行深入研究并給予優化，以此保證日漸增多的電動汽車在最有效的時間內完成對車輛的充電。

電動汽車充電路徑規劃可以從多個角度進行分析。文獻［1～2］考慮交通網絡和配電網絡等路徑引導制約因素，將交通路況信息阻礙和充電樁電力調度作為研究目標，達到路徑規劃目的。文獻［3］把動態路徑規劃問題分割成初始階段路徑選擇和充電樁資源搶奪，把多目標路徑規劃的時間離散化處理，佐以資源智能預警，實現動態網絡規劃。文獻［4～7］將路徑規劃算法作為主要研究對象，通過優化算法提高多目標路徑的收斂與搜索能力。文獻［8］針對非滿載問題進行研究，探索最優解的性質，分析總結了較緊的上下界，以及路徑規劃過程的最壞情況與解決方案。

本文通過對交通網絡、配電網絡、車輛本身的各項屬性進行分析，定量的設置電動汽車在路徑規劃過程采用智能水滴算法所涉及到的速度、泥土量等數據，利用智能水滴算法的數學模型，采用libsvm 對所選數據列表進行預測分析，獲取交叉驗證精度，確定最佳路徑，實現智能水滴算法在電動汽車充電路徑規劃上的應用。

2 智能水滴算法模型構建

2.1 智能水滴及其算法

智能水滴算法是根據自然界水滴匯集成流，然后流入大海的過程中“自由選擇”流經路徑的現象仿真得到的，Shah-Hosseini 根據水滴的這些屬性，將之命名為智能水滴（IWD），從而演化出智能水滴算法［9］。根據水滴的特性可以構建出抽象的數學模型，這種模型的屬性主要是包含水滴中攜帶的泥土量soil 和水滴在不斷更新泥土量的同時不斷變化的速度velocity。文獻［10～12］描述了智能水滴算法的實現原理及其合理性，文獻［13～14］建立模型驗證了其性能的優勢，文獻［15～16］分析算法的局限性，優化智能水滴的尋優方式，提高算法的搜索能力。文獻［17～19］采用不同算法與智能水滴算法混合，使用改進的智能水滴算法在車場分配和路徑搜索選擇上展開研究。

2.2 智能水滴算法數學模型

智能水滴所擁有的兩個重要屬性是水滴經過路徑所含泥土量和水滴的當前速率。但是由于水的流動特性，導致這兩個屬性都是處于變化狀態的，因此，智能水滴算法的目的是按照某些約束力，從某個節點到下一個節點找到水滴前進的最佳的一條路徑。

通過數學定量分析對智能水滴算法進行定量分析。假設水滴的當前位置為i，此時的速度為velocity（i），下一節點的位置為j，j位置的速度為velocity（j），由速度與從i 到j 的泥土量soil（i，j）成非線性反比關系可知表達式為

其中，as、bs、cs為用戶預先設定的靜態參數。

在水滴位置的變化過程中，水滴的含沙量的變化量和路徑中的變化量是相等的，泥土量的變化量和水滴移動所需的時間呈現非線性反比關系：

其中，as、bs、cs為可設定的模擬參數。time(i，j)為時間函數。

當水滴在兩節點間移動過程中，水滴中的含沙量和路徑中河道的泥土量在實時變化時的公式更新可以表示為

其中，ρn∈(0，1)，權重系數，一般取值0.9。

水滴的位置在時刻變化，在水滴到達下一節點前，會有多項泥土量的阻礙，也會形成多條路徑的選擇，水滴為了更快、更容易到達下一節點，會選擇一條最佳路徑進行前進，在這條路徑中，水滴在行進時的含沙量最少，速度最大。按照智能水滴在兩節點間位置移動，假設路徑概率為(j)，表達式為

其中，soil(i，j)兩個節點間的泥土量；VC(IWD)為智能水滴節點集合；f(soil(i，j))的表達式如下：

其中，ε為極小的正數，其作用是保證函數f的分母不為零。函數g 是i，j 兩個位置之間泥土量的修正函數，表達式如下：

其中，函數min 表示當前節點未流過的所有路徑的泥土量的最小值。

為實現尋找水滴流入大海的最優路徑，可以在智能水滴算法的的數學模型的基礎上進行模擬水滴選擇路徑的流程。將擬定解決的問題數據集作為輸入信息，得到的優化解為輸出信息。采用迭代的方式對數據集的迭代，當迭代次數不夠或者是精度沒有滿足，隨機選擇當前節點，然后根據數學條件選擇下一節點，選擇的依據是水滴的含沙量和河床中所含泥土量。

3 基于IWD算法的路徑規劃

3.1 智能水滴算法設計

路徑規劃需要考慮電動汽車在行駛過程中可能出現的各種阻礙。在本文中，將可能出現在道路規劃中的交通網絡、配電網絡、電動汽車本身阻礙看作智能水滴算法的泥土量，在泥土量不同的情況下，選擇路徑的概率也會不同，根據路徑情況，選擇路徑概率大的最為最優路徑。根據最優路徑，產生最優規劃方案。

3.2 智能水滴算法模擬實現

上一節中提到將交通網絡、配電網絡、車輛本身所產生的對充電路徑造成阻礙的一些因素看作智能水滴的泥土量，將不同類型的泥土量進行量化模擬。在泥土量設置中，設置了51 項泥土量，在大數據的模擬環境能夠更好地展現智能水滴算法的特點。根據模擬的泥土量數據，在智能水滴的兩個屬性的基礎上，對數據進行處理，從而實現路徑選擇的目的。

根據智能水滴算法，聲明路徑中的泥土量pathsoil 并對其進行初始化，將路徑中的泥土量設置初始值為1000。將智能水滴分代迭代，設置為30代，每代執行以下操作。

創建IWD，對IWD 進行迭代，隨機選擇設定泥土量的行數，在選擇的行數長度中計算pathsoil 范圍內的一部分，然后更新IWD 訪問列表，查找IWD從i 到j 的概率，其中j 不在訪問路徑列表中。將每一代的IWD 數據分為10 個子集，把每個IWD 從當前位置移動到下一位置，直到把自己全部遍歷。一個子集的開始，根據智能水滴算法的數學模型，在路徑泥土量pathsoil 矩陣范圍內計算g(soil(i，j))、智能水滴f(soil(i，k))集合元素之和，找到最小泥土量（minsoil(i，j)）。此時檢查i 是否在訪問列表當中，根據式（7）計算泥土量，并計算下一個數據，信息增益排序濾波器對輸入的數據采用搜索排序，對602條數據的51個屬性進行排序，標準化概率。

根據排序數組標準化排序，獲取新特征排序，然后更新IWD。首先獲取IWD 的初始速度和位置，在驗證中，設置水滴的初始速度velocity為100，含沙量soilcontent 為0，然后計算速度，按照式（1）進行更新，設置av=1，cv=1，bv=0.01；計算泥土量，根據式（3）對泥土量進行更新，設置as=1，bs=1，cs=0.01，ρ=0.9。

基于選定的位置創建簡化數據集，利用Matlab運行libsvm，根據svmtrain創建動態數據預測結果，獲取交叉驗證精度。然后進行下一代的迭代，經歷30 代的迭代，更新最佳路徑，選擇最大概率的IWD，更新每條路徑的泥土量soil(i，j)，根據訪問列表中的特征將全局最佳路徑寫入文件，輸出最佳路徑作為智能水滴的最佳路徑。

4 路徑規劃模型分析

4.1 函數驗證

智能水滴算法是利用智能水滴速度和泥土量這兩個屬性，加之本身具有的靈活性，對路徑進行優化。在對智能水滴算法的驗證中，使用四種測試函數對智能水滴進行驗證，通過函數本身與設定值之間的圖像展示，可以直觀地看出算法的有效性。

4.1.1 Rosenbrock函數驗證

函數表達式為f(x1，x2)=-10 ≤x1，x2≤10。該函數使用的是二維函數，設置全局的最小值f(1，1)=0。Rosenbrock 函數立體圖見圖1。根據立體圖可以看出二維Rosenbrock函數在最低點取得全局最小值，可以測試求解方法的執行能力。該函數的仿真實驗函數值收斂曲線見圖2，通過圖線的曲線走勢，可以找到最優值。

圖1 Rosenbrock函數立體圖

圖2 Rosenbrock函數仿真實驗函數值收斂曲線

4.1.2 Beale函數驗證

函數表達式為f(x)=(1.5-x1+x1x2)2+(2.25-，-4.5 ≤x1，x2≤4.5 。該函數使用的是二維函數，設置全局的最小值為X*=(3，0.5)，f(X)*=0。二維Beale函數的立體圖見圖3。根據立體圖可以看出二維Beale 函數是多峰函數，多峰函數可以測試全局最優和局部最優的搜索能力。

圖3 二維Beale函數的立體圖

4.1.3 Rastrigin函數驗證

函數表達式為f(x)=cos(2πx2))+20 ，-5.12 ≤x1，x2≤5.12 。該函數使用的是二維函數，設置全局的最小值為f(0)=0。二維Rastrigin 函數的立體圖見圖4，根據立體圖可以看出二維Rastrigin函數是多峰函數，多峰函數可以測試函數的局部極值。該函數的仿真實驗函數值收斂曲線見圖5。

圖4 二維Rastrigin函數的立體圖

圖5 二維Rastrigin函數仿真實驗函數值收斂曲線

4.1.4 Griewank函數驗證

圖6 二維Griewank仿真實驗函數值收斂曲線

4.2 數據迭代最優值

智能水滴算法在上述測試函數的測試中，通過立體圖和曲線觀察發現，智能水滴算法是可以實現算法的有效性的，根據測試函數的函數表達式和原有設定的值，求解出數據算法的最優值和迭代的次數，見表1。通過數據可以直觀地看出智能水滴算法的迭代情況。

表1 四種函數驗證智能水滴算法找到的最優值和迭代次數

通過表1 可見，二維Rosenbrock 函數在迭代153 次達到最優值，二維Beale函數在迭代162 次達到最優值，二維Rastrigin函數和二維Griewank 函數在迭代200 次基本趨于理論最優值。從數據值看，智能水滴算法在有限的迭代次數后達到最優值。

5 結語

研究基本實現了智能水滴與電動汽車充電路徑的結合，從數據結果可以看出，智能水滴算法在電動汽車充電路徑規劃上是可行的。智能水滴算法的運用是一個很便利、能夠動態掌握電動汽車的充電路徑規劃，但是有些方面的不適用是需要改進的。后期，將主要針對智能水滴算法的改進進行研究，并研究數據挖掘以及大數據分析對人類生活的便利程度。