基于負荷平衡的電動汽車模糊多目標充電調度算法

周美玲，陳淮莉

（上海海事大學物流科學與工程研究院，上海 201306）

0 引言

隨著化石能源消耗的日益增長和新能源技術的發展，電動汽車（Electric Vehicle，EV）迅速發展起來。但EV充電負荷使電網負荷“峰上加峰”，導致配電網線路過載、三相不平衡等問題。三相不平衡會影響用電設備的安全運行，不利于電網的安全運行和電力系統的可靠穩定，因此需引導EV的充電行為，以提高配電網接納EV的安全性與穩定性。

EV 充電調度策略按控制策略分為分散式充電和集中式充電［1］。分散式的核心是對單輛EV 優化［2］，但在平抑負荷波動和把握系統全局信息方面存在不足。集中式充電基本服務于居民小區［3］，部分學者并沒有考慮三相不平衡對電網的影響，而是以等效的單相系統或假設三相平衡為前提，從用戶、充電站和配電網的角度來研究問題，以用戶充電成本最小化［4］、用戶充電滿意度最大［5-6］、配電網運行成本最小化［4，6］、運營商利潤最大［7］、平滑負荷曲線［5，8］等為優化目標，建立含不同約束的混合整數單目標或多目標模型，再用遺傳算法、粒子群算法等進行求解。由于充電站的不同約束，計算成本最小化或用戶滿意度最大化等目標的可行時間表不能有效減小峰谷負荷差［9］，甚至會造成另一個高峰。

黃小慶等［5］和Singh 等［10］研究了EV 充電對三相不平衡的影響，認為負荷應在三相之間合理分配。基于此，占愷嶠等［11］提出了以控制三相負荷平衡和降低網損為目標的充電調度策略，但并不能滿足實時充電需求。李佩杰等［12］引入滾動時域控制理論提出實時調度策略，采用內點法求解來控制三相負荷，但當EV 規模較大時，由于模型維數較高不能滿足實時優化要求。Hernández-Arauzo 等［13］則提出將三相問題分解成三個實體從而解決一個個排序問題來實現三相平衡。上述文獻雖可以降低三相不平衡度，但是未考慮EV實時充電所導致的負荷峰谷差以及能量分配的公平性。

在求解多目標問題上，思路有：1）對多目標進行加權求和轉化為單目標［14］求解，但是權重的選擇標準難以確定和具有主觀性；2）基于帕累托最優解集得到Pareto 最優前沿，不求折中解或通過目標權重法［15］等指標獲得折中解。改進非支配排序遺傳算法-Ⅱ（Non-dominated Sorting Genetic Algorithm-Ⅱ，NSGA-Ⅱ）是求解多目標的進化算法，在求解多目標問題上被廣泛應用。

針對上述問題，本文將三相不平衡度和負荷峰谷差視為一種約束，提出一種考慮負荷平衡的電動汽車多目標充電靜態和在線調度策略。通過滑動窗口得到EV 的充電時間并生成可行時間表，使得總延遲時間最小且盡可能實現公平充電。本文采用改進NSGA-Ⅱ算法進行求解，通過模糊隸屬度方法在Pareto 最優前沿面中得到最優折中解。最后以某小區為例，對本文所提模型和策略進行驗證。

1 電動汽車充電調度模型

本文研究在小區停車場充電的私家EV，假設用戶在私人停車位加充電樁充電，EV 充電的地點以及所在相固定。假設該停車場有M個停車位，每條停車線Li有Mi個充電點。在停車場每個私人停車位都有一個充電點，連接到一個單相，當它有效時以恒定的功率進行充電，充電控制架構如圖1所示。

圖1 電動汽車有序充電控制架構示意圖Fig.1 Schematic diagram of electric vehicle orderly charging control architecture

當用戶到達停車場接入智能充電樁，充電樁讀取EV到達時間和電池剩余電量，用戶輸入期望離開時間，中央控制器通過本文調度策略安排EV的充電時間。其中，通過限制每條線路上可以同時充電的電動汽車數量N來平抑負荷波動，通過將三相負荷不平衡度Δ作為約束，使得三條線路的負荷在所設置的范圍內。

1.1 靜態調度模型

1.1.1 問題描述

在靜態模型中，問題表述如下：考慮三條線路Li（i=1，2，3)，每條Li上有mi車輛到達，車輛被表示為：已知EV 到達時間tij≥0，充電時間pij＞0，以及期望離開時間dij。根據文獻［8-9］可知在18：00—21：00負荷疊加后會超出變壓器總量，甚至會超出總量的10%左右，威脅電網安全運行。為簡化計算，18：00—21：00 的可同時充電的電動汽車數量設為N-5，從而減少該時間段的充電車輛。

1.1.2 目標函數

模型同時考慮兩個優化目標，具體如下：

1）目標1。

該充電策略是為得到可行時間表，為車輛vij分配決策變量的充電時間xij（i=1，2，3，1 ≤j≤mi），并得到車輛的充電完成時間Cij，即xij中的最后一個充電時間。目標函數是總延遲時間最小化，定義如下：

2）目標2。

由于部分EV 可能無法充滿，因此應盡可能公平充電，將EV 在期望離開時間之前的充電量與所需總充電量的比值的差值的絕對值Xij的總和最小化作為另一個目標，如下所示：

其中：Tij是車輛vij進行充電的所有時間段；t'為在期望離開時間之前的時刻；xijt是車輛vij在一個時間段的充電量分別是vij在期望離開時間之前得到的充電量和所需總充電量。

1.1.3 約束條件

1）車輛vij在一個時間段ΔT的充電量xijt。

其中：u為額定充電功率；η為充電效率。

2）車輛vij的充電量不大于其需求Dij。

3）車輛只能在其可用的充電時間段內充電。

4）每條線路上車輛的開始充電時間stij不能小于它的到達時間tij。

5）在t時刻，Li線路上的車輛同時可活動充電點數量Ni(t)不得超過N。

通過限制線每條線路上每個時間段的同時充電車輛數量，降低每個時間段的負荷峰值，從而減小負荷峰谷差。

6）在t時刻，用任意兩條線路上同時充電的車輛數量差與N的比值來衡量三相不平衡度，Δ為最大允許的三相不平衡度。

對EV進行調度時，選擇該線路在車輛分配充電時間段與其他線路計算得到的三相不平衡度最大值與Δ比較，若不符合式（9）則重新安排開始充電時間，直到約束得到滿足。

1.2 在線調度模型

在實際情況中，車輛的到達時間和充電時間是未知的，因此是在線調度問題。在線調度問題可以看成是每個時刻下產生的靜態問題實例P1、P2、…、Pn。

在時間Tk上的實例Pk由已經到達充電站但還未開始充電的車輛和已經在充電的車輛組成，車輛可表示為｛vi1，vi2，…，viai，…，vimi｝。已知vij的充電時間pij和期望離開時間dij。其中一部分車輛（vi1，vi2，…，viai）在充電，但未充完，即對所有車輛1 ≤j≤ai，滿足Cij＞Tk和stij＞Tk。剩下的車輛（viai+1，viai+2，…，vimi）尚未開始充電。

在給定時間t中的實例Pk中，在Li上可為新車輛充電的容量按以下方式計算：

該充電策略是為在Tk上的Pk中的EV 分配滿足靜態問題所有約束的充電時間x'ij，得到該Pk的可行時間表。

考慮到無法預測未來EV的接入時間和充電需求，因此本文按Tk-1-Tk=ΔT（10 min）建立144 個時段，并采用滑動窗口方案［17］，如圖2所示。

圖2 控制時段示意圖Fig.2 Schematic diagram of control period

在每個Tk內，控制系統監測在［Tk-1，Tk］內的到達車輛來創建Pk，并檢查該時間段EV 的充電信息，再為隨后的調度定義新的滑動窗口。新的滑動窗口被定義為滿足N和Δ約束的新EV 到達和正在充電的EV 的最新可用充電時間之間的時間。隨后，控制系統根據新的滑動窗口得到新的解決方案sk，而sk會取代之前的解決方案sk-1。若車輛未能在期望離開時間之前完成充電，則生成滿足約束的開始充電時間進行充電直到充滿。在Tk內，只要車輛還沒有充電，可以在不同的Pk中分配不同的x'ij。一旦該車輛正在充電，該車輛的x'ij就不能再改動。

2 模型求解

2.1 改進的NSGA-Ⅱ算法

對于該模型而言，決策變量是車輛充電時間。改進非支配排序遺傳算法Ⅱ（NSGA-Ⅱ）的特點是對種群進行非支配排序和擁擠度計算，生成子代后選擇父代與子代中的優先個體作為新種群，最后得到Pareto最優解集。主要內容如下：

2.1.1 編碼方法

本 文 用A={ai，j，t|i∈[0，3]，j∈[0，Mi]，t∈[0，144]，i，j，t∈N}來描述EV 的分配狀況，ai，j，t表示在線路i上第j輛EV是否在t時刻正在充電。

2.1.2 種群初始化

根據規則和約束（7）隨機生成初始種群，依次將EV 分配到充電位置，若正在充電，則令ai，j，t=1。

傳統的NSGA-Ⅱ算法中初始解的構建是隨機的，因此本文運用順序貪婪隨機（Sequential Greedy Stochastic，SGS）算法分配EV的充電時間，得到初始解。

為了盡量減少延遲時間，在每個時間表α中未充電車輛的最早可能充電時間為E(α)，所有沒有安排充電的車輛即ai，j，t=0時在E(α)時充電的選擇概率Πj為：

為得到不同的解決方案，首先對選擇概率按升序對所有車輛進行排序；然后執行競賽選擇，選擇tSize數量的隨機車輛并從中取出最優個體放入到列表中，從而得到優先級列表；最后遍歷列表，按列表中順序為車輛分配滿足所有約束的盡可能早的充電時間，從而得到初始解。其中，tSize若較小會導致幾乎隨機的解，而較大的值會產生相似的解，因此本文設置tSize=8。

在該算法下，一定可以獲得一個滿足所有約束的初始解，在最壞的情況下即將EV的最大完成時間作為開始充電時間。因此，在N＞0和Δ＞1/N的情況下，得到可行時間表。

2.1.3 適應度函數和選擇算子

適應度函數F=1/f，在選擇過程中，將父代和子代種群合并進行非支配排序和擁擠度計算，從中選取最優個體組成新種群進行交叉、變異等操作。

2.1.4 交叉算子

本文比較三種交叉算子并選擇最優的一種，交叉策略如下：

1）單點交叉。隨機選擇染色體的位置，對在p1、p2中選擇該位置的車輛進行交叉，產生o1、o2。

2）基于到達時間的交叉算子。生成隨機數x，若x＜pc，則隨機選擇到達時間t0，在p1中選出到達時間大于t0的車輛，按照這些車輛在p2中出現順序放在o1的末尾，o2也是如此創建。圖3展示了該交叉方式的操作，假設p1中車輛到達時間為（9，11，10，15，17，16，18，18，21，17，17），p2為（9，11，17，16，21，10，18，17，18，15，17）。隨機選擇到達時間t0=17，則子代如圖3所示。

3）基于離開時間的交叉算子。隨機選擇到達時間t1，在p1中選出到達時間大于t1的車輛，按照這些車輛在p2中出現順序放在o1的末尾，o2也是如此創建。

圖3 基于到達時間的交叉算子Fig.3 Crossover operator based on arrival time

2.1.5 變異算子

采用自適應變異概率，若f＞favg，pm=0.1；否則pm=0.01。若下一代最優個體適應度值大于當前最優個體適應值，則用輪盤賭法保存最優個體，替代較差個體。

2.1.6 外部檔案集合

通過設置一定容量的外部檔案以保存先前找到的帕累托最優解，每次通過判定是否被外部檔案內個體支配和是否支配外部檔案個體來迭代和更新Pareto 最優解集。當外部檔案的大小超過上限時，則根據擁擠度對外部檔案執進行輪盤賭選擇存入外部檔案集合的解。

2.1.7 擁擠度判定

過于擁擠或稀疏的Pareto 解集不利于選取折中最優解，因此采用擁擠度判定使Pareto前沿面更均衡，公式為：

其中：z為目標函數個數；a、c分別為待擁擠判定解b的相鄰解。

2.2 Pareto前沿面的最優折中解

本文所求是目標值最小，因此采用偏小型模糊隸屬度函數［18］，再計算Pareto 最優解集中各最優決策滿意度，函數值越大則滿意程度越高，滿意度最高的解將作為折中解，模糊隸屬度函數為：

其中：fe.min、fe.max為在滿足約束條件下的目標函數最小值、最大值；e=1，2。利用滿意程度作評價標準，公式為：

其中：Y表示最優解個數；μs表示標準化條件下第s個最優解的滿意度。

2.3 局部優化

由于約束（9）中最大三相不平衡的約束會導致一些EV分配到不理想的充電時間，因此本文運用局部優化方法［14］進行改進，如圖4所示。

圖4 局部優化示意圖Fig.4 Schematic diagram of local optimization

假設N=3，Δ=2/3；v31的到達時間為5，其他車輛的到達時間為0；所有車輛充電時間為10；v13、v31的期望離開時間為15，其他車輛離開時間為10。對車輛進行排序得到排列V（v11、v12、v21、v22、v13、v31）。

先對前四輛EV進行調度，再根據約束（9）可計算出在［0，10］內ΔL13=2/3，若v13的開始充電時間為0，則在［0，10］內ΔL13=1＞2/3，因此需對v13重新調度，其開始充電時間為10。按順序對v31進行調度，其開始充電時間為5，此時總延遲時間為5，如圖4（a）所示。但v31的調度使得在［5，10］內ΔL13=1/3，因此重新給v13分配開始充電時間為5，此時ΔL13=2/3，如圖4（b），此時總延遲時間為0。

此示例說明需要運用局部優化方法，因此按下列方式重新調度車輛。當為新車輛調度時，檢查Lj上充電時間為p'的可行開始充電時間為t'的電動汽車v'的調度是否會在［t'，t'+p'］打破先前車輛充電的不平衡限制。

當且僅當在調度之前，在Li和Lj上達到了最大不平衡限制即不能再對EV進行調度，形式上，?t∈[t′，t′+p′]滿足：

若以上約束都能滿足，則意味著對v'的調度打破了［t'，t'+p'］的不平衡限制，則可對部分EV重新進行調度。若出現這種情況，則取消Li中所有x'ij≥t'的EV 的調度，使得在滿足所有約束的前提下這些車輛的x'ij能更早。

3 算例分析

3.1 基礎數據

本文以居民小區配電網為例分析，采用2009 年全美家庭出行調查（National Household Travel Survey，NHTS）的結果，車輛到達時間、期望離開時間、日行駛里程的概率密度表達式見文獻［5］。

假設EV 電池容量為50 kW·h，額定充電功率u=7 kW，充電效率η=0.92；電動汽車數量M=180；假定用戶期望離開荷電狀態為1，用戶未在充電完成時間前將車輛開走。

為說明本文模型和策略的有效性，選取兩種不同類型進行測試。類型1：每條Li有60 輛車輛到達；類型2：60%到達L1，30%到達L2，10%到達L3。顯然類型2 加劇線路之間的不平衡。選取4 種不平衡度值Δ（0.2，0.4，0.6，0.8）和3 種N值（20，30，40），因此總共有由類型、N、Δ組成的48種情形。

在Matlab 環境下編程，種群大小為100，交叉概率為0.9，自適應變異概率為0.1 和0.01，迭代的最大次數為120 或者找到一個零延遲的解。外部檔案容量上限為種群大小。考慮到算法的隨機性，運行30次得到具有統計意義的結果。

3.2 改進NSGA-Ⅱ算法參數選擇

本文用非參數統計檢驗來分析不同參數的差異，先用SW（Shapiro-Wilk）檢驗數據的非正態性，再用Wilcoxon 匹配對符號秩檢驗計算p值來驗證差異是否具有統計學意義。在這些檢驗中，設置置信度為95%，備擇假設是“平均總延遲值之間的差不等于0”。

3.2.1 交叉概率選擇

表1 列出靜態和在線調度不同交叉概率pc下最優折中解下的平均總延遲時間。可看出pc=0.9 的結果優于pc=0.8 和pc=0.6，且p值都小于0.1，差異具有統計學意義。

表1 靜態和在線調度不同交叉概率的平均總延遲時間 單位：hTab.1 Average total delay time of static and online scheduling with different crossing probability unit：h

3.2.2 交叉算子選擇

表2 顯示靜態和在線調度三種交叉算子最優折中解下的平均總延遲時間，可看出基于到達時間的交叉算子能夠得到更優的解，且p值都小于0.1，可知基于到達時間的交叉算子與其他算子之間存在統計學上的顯著差異。

表2 靜態和在線調度三種交叉算子的平均總延遲時間 單位：hTab.2 Average total delay time of static and online scheduling with three crossover operators unit：h

3.3 算法分析

為分析局部優化對解決方案的作用，圖5 顯示使用和不使用局部優化的總延遲時間的差值。可知在使用局部優化后結果更優。且隨著Δ的增加，使用局部優化的改進量減小；在給定Δ值下，隨著參數N的增加，改進量隨之減小。

運用改進NSGA-Ⅱ算法得到N=20 和Δ=0.2 下的Pareto最優前沿和折中最優解，如圖6（a）所示；圖6（b）所示為遺傳算法（Genetic Algorithm，GA）得到的Pareto 最優前沿。從圖6可知，采用改進NSGA-Ⅱ算法能夠得到更加完整的Pareto 最優前沿，基于擁擠度篩選后的Pareto 最優前沿更加均勻。然后采用模糊隸屬度函數求解折中最優解，如表3 所示，在極端解的情況下，其他目標優化較小甚至出現劣化現象。

圖5 使用與不使用局部優化的總延遲時間差值Fig.5 Difference in total delay time with and without local optimization

圖6 兩種算法的Pareto最優前沿Fig.6 Pareto optimal frontiers of two algorithms

表3 系統極端解和折中最優解Tab.3 System extreme solution and optimal compromise solution

表4 給出GA 算法和改進NSGA-Ⅱ算法在最優折中解下的平均總延遲時間和平均充電平衡的結果。由表4 可知，相較于GA算法，改進NSGA-Ⅱ算法的折中解更優。

表4 兩種算法實驗結果對比Tab.4 Comparison of experimental results of two algorithms

3.4 結果分析

根據式（9）可知三相不平衡度的計算與N有關，因此在不同的N下，無序充電中的不平衡度值也不同。表5 給出無序充電和充電調度策略下折中最優解的結果，在本文充電調度策略下，EV 接入電網后負荷調度效果明顯。與無序充電相比，在約束最嚴格時峰谷差、負荷方差、三相不平衡度和三相不平衡度方差分別下降56.54%、67.64%、69.23%、93.49%；而在約束最寬松的情形下（N=40 時，目標值為0）分別下降35.43%、53.99%、38.46%、47.47%。這表明與無序充電相比，該策略能夠明顯降低峰谷負荷差和三相負荷不平衡度，平抑負荷曲線波動，起到改善負荷特性的效果。

以類型1 中代表性的組合來說明該策略在降低負荷峰谷差的作用，圖7 為無序充電和充電調度策略不同組合同時充電的車輛數。可知在無序充電下，大部分EV 集中在18：00—24：00 充電，加大了峰谷負荷值，不利于電網系統安全穩定運行。N=20 時，負荷削峰填谷效果非常明顯。隨著N的增加，峰值降低的程度隨之下降，但與無序充電相比峰谷負荷差仍顯著性降低。在N=40和Δ=0.2時，雖然峰值削減的力度沒有其他組合的大，但避開電網負荷的高峰時段，使EV 負荷能在更長時間內分配，減小了對電網的沖擊，從而更有效地平滑電網負荷波動。

表5 無序充電和充電調度策略下的指標對比Tab.5 Comparison of indexes under disorder charging and charging scheduling strategy

圖7 無序充電和充電調度策略不同參數組合下的充電車輛數Fig.7 Numbers of charging vehicles under parameter of disorderly charging and charging scheduling strategy with different combinations

為進一步說明該充電策略對三相不平衡度的影響，根據不同N值以L1和L3的三相不平衡度來分析無序充電和調度策略。如圖8 所示，在所有參數組合下，三相不平衡度基本低于0.2，且波動較小，利于電網的安全穩定。無序充電中三相不平衡度高達0.65，三相不平衡度值在整個時間范圍內波動較大，影響配電網安全運行。而在采取調度策略后，三相不平衡度整體趨勢較為平穩。隨著N值的增加即約束更加寬松，三相不平衡度仍顯著降低且波動不大。由此可見，將三相不平衡度作為一種約束，不僅對降低三相不平衡度有著重要意義，還使得三相負荷波動平穩，驗證了該模型和策略的有效性。

為分析該充電策略對總延遲時間的影響，對靜態和在線調度的48 種情形計算得到最優折中解下的平均總延遲時間，如表6 所示。從表6 中可看出，在折中最優解下，靜態調度的總延遲時間要低于在線調度。另外，在靜態調度類型1 中要找到總延遲時間為0的解是較容易的（N=40）。這是由于在線調度對EV 充電時間的分配受到實時限制，部分EV 的充電時段不能進行局部優化，得到不理想的充電時間。

圖8 無序充電和充電調度策略中不同N值的三相不平衡度Fig.8 Three-phase unbalance value under disorderly charging and charging scheduling strategy with different values of N

表6 靜態和在線調度不同參數組合的平均總延遲時間 單位：hTab.6 Average total delay time of different parameter combinations of static and online scheduling unit：h

為進一步對EV不同到達類型進行分析，主要比較不同參數組合的平均總延遲時間。在每個參數組合下，類型1 中的總延遲時間要低于類型2，這是因為類型1中線路上的車輛分布是均勻的。而類型2 中車輛到達的差異非常大（L1為60%，L2為30%，L3為10%），由于三相不平衡限制使得總延遲時間的增加較為顯著。

根據表6 可看出總延遲時間的大小取決于參數N和Δ的值，隨著N和Δ值的減小即約束更加嚴格，總延遲時間會隨之增加。在最極端的情況下，可參考在線調度類型2（N=20，Δ=0.2）的結果，車輛的平均延遲時間超過24 h。這主要是由于當L3中的18 輛EV 完成充電后，由于Δ=0.2 的限制，L1和L2中可同時充電的電動汽車數量值為4，使得L1和L2中的車輛充電時間出現巨大的延遲。這種極端的參數組合不能反映實際情況，但這些情況有助于測試調度算法管理極端情況的能力。該算法可以利用EV的到達時間、充電時間和期望離開時間的所有數據來獲得較好的解決方案。

4 結語

本文提出一種兼顧負荷波動和三相不平衡的電動汽車多目標靜態和在線調度充電策略，具有現實意義。采用改進NSGA-Ⅱ算法求解多目標問題，得到更加完整均勻的Pareto前沿面，并采用模糊隸屬度函數得到折中最優解，避免了傳統權重系數法對多目標優化的主觀影響。實驗結果表明，在不同約束組合下，該充電策略能夠有效做到平抑負荷波動和實現三相平衡，并盡可能實現公平充電。隨著可同時活動充電點數量和三相不平衡度值的減小，對于平抑負荷差和降低三相不平衡度的作用就越大，但總延遲時間也會隨之增加，運營商可以根據實時情況進行選擇，具有較好的參考意義。

另外靜態調度中的目標值要優于在線調度，因此可以盡量獲取到小區內車輛的數據，從而能夠更好地解決在線調度問題。