電動(dòng)汽車(chē)充電路徑規(guī)劃研究*

趙文清 王繼發(fā)

（華北電力大學(xué)計(jì)算機(jī)系 保定 071003）

1 引言

電動(dòng)汽車(chē)的動(dòng)力采用對(duì)電動(dòng)車(chē)充電，放置充放電電瓶作為存放電動(dòng)汽車(chē)驅(qū)動(dòng)動(dòng)力的承載裝置，但是電瓶對(duì)電動(dòng)汽車(chē)所能承擔(dān)的動(dòng)力有限。因此，對(duì)于電動(dòng)汽車(chē)充電問(wèn)題便成為當(dāng)今社會(huì)致力于研究該內(nèi)容的專(zhuān)家學(xué)者的“重頭戲”，在滿(mǎn)足電動(dòng)汽車(chē)日常充電的需求的基礎(chǔ)上，還需對(duì)充電路徑進(jìn)行深入研究并給予優(yōu)化，以此保證日漸增多的電動(dòng)汽車(chē)在最有效的時(shí)間內(nèi)完成對(duì)車(chē)輛的充電。

電動(dòng)汽車(chē)充電路徑規(guī)劃可以從多個(gè)角度進(jìn)行分析。文獻(xiàn)［1～2］考慮交通網(wǎng)絡(luò)和配電網(wǎng)絡(luò)等路徑引導(dǎo)制約因素，將交通路況信息阻礙和充電樁電力調(diào)度作為研究目標(biāo)，達(dá)到路徑規(guī)劃目的。文獻(xiàn)［3］把動(dòng)態(tài)路徑規(guī)劃問(wèn)題分割成初始階段路徑選擇和充電樁資源搶奪，把多目標(biāo)路徑規(guī)劃的時(shí)間離散化處理，佐以資源智能預(yù)警，實(shí)現(xiàn)動(dòng)態(tài)網(wǎng)絡(luò)規(guī)劃。文獻(xiàn)［4～7］將路徑規(guī)劃算法作為主要研究對(duì)象，通過(guò)優(yōu)化算法提高多目標(biāo)路徑的收斂與搜索能力。文獻(xiàn)［8］針對(duì)非滿(mǎn)載問(wèn)題進(jìn)行研究，探索最優(yōu)解的性質(zhì)，分析總結(jié)了較緊的上下界，以及路徑規(guī)劃過(guò)程的最壞情況與解決方案。

本文通過(guò)對(duì)交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、車(chē)輛本身的各項(xiàng)屬性進(jìn)行分析，定量的設(shè)置電動(dòng)汽車(chē)在路徑規(guī)劃過(guò)程采用智能水滴算法所涉及到的速度、泥土量等數(shù)據(jù)，利用智能水滴算法的數(shù)學(xué)模型，采用libsvm 對(duì)所選數(shù)據(jù)列表進(jìn)行預(yù)測(cè)分析，獲取交叉驗(yàn)證精度，確定最佳路徑，實(shí)現(xiàn)智能水滴算法在電動(dòng)汽車(chē)充電路徑規(guī)劃上的應(yīng)用。

2 智能水滴算法模型構(gòu)建

2.1 智能水滴及其算法

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

2.2 智能水滴算法數(shù)學(xué)模型

智能水滴所擁有的兩個(gè)重要屬性是水滴經(jīng)過(guò)路徑所含泥土量和水滴的當(dāng)前速率。但是由于水的流動(dòng)特性，導(dǎo)致這兩個(gè)屬性都是處于變化狀態(tài)的，因此，智能水滴算法的目的是按照某些約束力，從某個(gè)節(jié)點(diǎn)到下一個(gè)節(jié)點(diǎn)找到水滴前進(jìn)的最佳的一條路徑。

通過(guò)數(shù)學(xué)定量分析對(duì)智能水滴算法進(jìn)行定量分析。假設(shè)水滴的當(dāng)前位置為i，此時(shí)的速度為velocity（i），下一節(jié)點(diǎn)的位置為j，j位置的速度為velocity（j），由速度與從i 到j(luò) 的泥土量soil（i，j）成非線(xiàn)性反比關(guān)系可知表達(dá)式為

其中，as、bs、cs為用戶(hù)預(yù)先設(shè)定的靜態(tài)參數(shù)。

在水滴位置的變化過(guò)程中，水滴的含沙量的變化量和路徑中的變化量是相等的，泥土量的變化量和水滴移動(dòng)所需的時(shí)間呈現(xiàn)非線(xiàn)性反比關(guān)系：

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

當(dāng)水滴在兩節(jié)點(diǎn)間移動(dòng)過(guò)程中，水滴中的含沙量和路徑中河道的泥土量在實(shí)時(shí)變化時(shí)的公式更新可以表示為

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

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

其中，soil(i，j)兩個(gè)節(jié)點(diǎn)間的泥土量；VC(IWD)為智能水滴節(jié)點(diǎn)集合；f(soil(i，j))的表達(dá)式如下：

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

其中，函數(shù)min 表示當(dāng)前節(jié)點(diǎn)未流過(guò)的所有路徑的泥土量的最小值。

為實(shí)現(xiàn)尋找水滴流入大海的最優(yōu)路徑，可以在智能水滴算法的的數(shù)學(xué)模型的基礎(chǔ)上進(jìn)行模擬水滴選擇路徑的流程。將擬定解決的問(wèn)題數(shù)據(jù)集作為輸入信息，得到的優(yōu)化解為輸出信息。采用迭代的方式對(duì)數(shù)據(jù)集的迭代，當(dāng)?shù)螖?shù)不夠或者是精度沒(méi)有滿(mǎn)足，隨機(jī)選擇當(dāng)前節(jié)點(diǎn)，然后根據(jù)數(shù)學(xué)條件選擇下一節(jié)點(diǎn)，選擇的依據(jù)是水滴的含沙量和河床中所含泥土量。

3 基于IWD算法的路徑規(guī)劃

3.1 智能水滴算法設(shè)計(jì)

路徑規(guī)劃需要考慮電動(dòng)汽車(chē)在行駛過(guò)程中可能出現(xiàn)的各種阻礙。在本文中，將可能出現(xiàn)在道路規(guī)劃中的交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、電動(dòng)汽車(chē)本身阻礙看作智能水滴算法的泥土量，在泥土量不同的情況下，選擇路徑的概率也會(huì)不同，根據(jù)路徑情況，選擇路徑概率大的最為最優(yōu)路徑。根據(jù)最優(yōu)路徑，產(chǎn)生最優(yōu)規(guī)劃方案。

3.2 智能水滴算法模擬實(shí)現(xiàn)

上一節(jié)中提到將交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、車(chē)輛本身所產(chǎn)生的對(duì)充電路徑造成阻礙的一些因素看作智能水滴的泥土量，將不同類(lèi)型的泥土量進(jìn)行量化模擬。在泥土量設(shè)置中，設(shè)置了51 項(xiàng)泥土量，在大數(shù)據(jù)的模擬環(huán)境能夠更好地展現(xiàn)智能水滴算法的特點(diǎn)。根據(jù)模擬的泥土量數(shù)據(jù)，在智能水滴的兩個(gè)屬性的基礎(chǔ)上，對(duì)數(shù)據(jù)進(jìn)行處理，從而實(shí)現(xiàn)路徑選擇的目的。

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

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

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

基于選定的位置創(chuàng)建簡(jiǎn)化數(shù)據(jù)集，利用Matlab運(yùn)行l(wèi)ibsvm，根據(jù)svmtrain創(chuàng)建動(dòng)態(tài)數(shù)據(jù)預(yù)測(cè)結(jié)果，獲取交叉驗(yàn)證精度。然后進(jìn)行下一代的迭代，經(jīng)歷30 代的迭代，更新最佳路徑，選擇最大概率的IWD，更新每條路徑的泥土量soil(i，j)，根據(jù)訪問(wèn)列表中的特征將全局最佳路徑寫(xiě)入文件，輸出最佳路徑作為智能水滴的最佳路徑。

4 路徑規(guī)劃模型分析

4.1 函數(shù)驗(yàn)證

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

4.1.1 Rosenbrock函數(shù)驗(yàn)證

函數(shù)表達(dá)式為f(x1，x2)=-10 ≤x1，x2≤10。該函數(shù)使用的是二維函數(shù)，設(shè)置全局的最小值f(1，1)=0。Rosenbrock 函數(shù)立體圖見(jiàn)圖1。根據(jù)立體圖可以看出二維Rosenbrock函數(shù)在最低點(diǎn)取得全局最小值，可以測(cè)試求解方法的執(zhí)行能力。該函數(shù)的仿真實(shí)驗(yàn)函數(shù)值收斂曲線(xiàn)見(jiàn)圖2，通過(guò)圖線(xiàn)的曲線(xiàn)走勢(shì)，可以找到最優(yōu)值。

圖1 Rosenbrock函數(shù)立體圖

圖2 Rosenbrock函數(shù)仿真實(shí)驗(yàn)函數(shù)值收斂曲線(xiàn)

4.1.2 Beale函數(shù)驗(yàn)證

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

圖3 二維Beale函數(shù)的立體圖

4.1.3 Rastrigin函數(shù)驗(yàn)證

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

圖4 二維Rastrigin函數(shù)的立體圖

圖5 二維Rastrigin函數(shù)仿真實(shí)驗(yàn)函數(shù)值收斂曲線(xiàn)

4.1.4 Griewank函數(shù)驗(yàn)證

圖6 二維Griewank仿真實(shí)驗(yàn)函數(shù)值收斂曲線(xiàn)

4.2 數(shù)據(jù)迭代最優(yōu)值

智能水滴算法在上述測(cè)試函數(shù)的測(cè)試中，通過(guò)立體圖和曲線(xiàn)觀察發(fā)現(xiàn)，智能水滴算法是可以實(shí)現(xiàn)算法的有效性的，根據(jù)測(cè)試函數(shù)的函數(shù)表達(dá)式和原有設(shè)定的值，求解出數(shù)據(jù)算法的最優(yōu)值和迭代的次數(shù)，見(jiàn)表1。通過(guò)數(shù)據(jù)可以直觀地看出智能水滴算法的迭代情況。

表1 四種函數(shù)驗(yàn)證智能水滴算法找到的最優(yōu)值和迭代次數(shù)

通過(guò)表1 可見(jiàn)，二維Rosenbrock 函數(shù)在迭代153 次達(dá)到最優(yōu)值，二維Beale函數(shù)在迭代162 次達(dá)到最優(yōu)值，二維Rastrigin函數(shù)和二維Griewank 函數(shù)在迭代200 次基本趨于理論最優(yōu)值。從數(shù)據(jù)值看，智能水滴算法在有限的迭代次數(shù)后達(dá)到最優(yōu)值。

5 結(jié)語(yǔ)

研究基本實(shí)現(xiàn)了智能水滴與電動(dòng)汽車(chē)充電路徑的結(jié)合，從數(shù)據(jù)結(jié)果可以看出，智能水滴算法在電動(dòng)汽車(chē)充電路徑規(guī)劃上是可行的。智能水滴算法的運(yùn)用是一個(gè)很便利、能夠動(dòng)態(tài)掌握電動(dòng)汽車(chē)的充電路徑規(guī)劃，但是有些方面的不適用是需要改進(jìn)的。后期，將主要針對(duì)智能水滴算法的改進(jìn)進(jìn)行研究，并研究數(shù)據(jù)挖掘以及大數(shù)據(jù)分析對(duì)人類(lèi)生活的便利程度。