基于遺傳模擬退火算法的電動汽車充電調度方法研究

任小強

(西南交通大學希望學院，四川 成都 610400)

0 引 言

新能源電動汽車(Electric Vehicles ，EV)具有無污染、低噪音和高能效等特點，在降低環境污染和減少對化石能源的依賴方面具有較大潛力，已成為燃油汽車的重要替代品[1]。與燃油汽車相比，EV在大規模推廣過程中，仍面臨諸多問題，例如續行里程不足[2]、需要頻繁充電、充電成本高等[3]，不確定的電動汽車無序充電方式容易影響車主的出行體驗和充電效率[4]。此外，大量EV的無序充電還會導致充電樁利用率低、給電網帶來巨大的負荷壓力，從而影響充電站的安全運行和車主的充電體驗。因此，如何對充電站內的EV進行合理的充電調度是一個亟待解決的問題。許多學者和專家對EV的充電調度問題進行深入研究，并取得了不錯的研究成果。例如高建樹等[5]以車輛數量和充電時長為目標，構建電動車輛充電調度模型，并采用多目標粒子群優化算法(Multi-Objective Particle Swarm Optimization，MOPSO)對模型進行求解，能夠有效降低EV的充電等待時長和充電成本，但未考慮充電站的成本。劉巖等[6]構建了EV的動態多目標充電調度模型，并使用動態粒子群算法對模型進行了求解，能夠起到降低電網負荷壓力的效果，但未考慮車主的充電滿意度。侯尚武等[7]建立了有序充電調度模型，并利用遺傳算法求解該模型，該模型可通過實時電價的有序調度緩解負荷波動，降低峰谷電價，但未完全考慮到EV的實時充電需求，同時所設計算法的復雜度高，在實際應用中還存在一定的局限性。李春亭等[8]引入動態調整策略的蝙蝠算法解決EV停車充電優化調度問題，能夠更好地適應EV的實時充電需求，能夠實現更好的調度效果，但在求解過程中容易陷入局部最優。避免陷入局部最優的有效方式是融合兩種以上算法，已被廣泛應用到紙張表面缺陷智能化檢測[9]、艦船分段裝載順序優化[10]、刀具準時化配送路徑規劃[11]、艦船資源裝配效率優化[12]和有機磷農藥殘留檢測[13]。因此，為了對電動汽車技術的不斷發展提供理論支持和實踐指導，本文提出一種基于遺傳模擬退火算法(Genetic Simulated Annealing Algorithm，GASA)的EV充電調度模型，并與無序充電調度和其他優化算法進行對比，用以驗證GASA算法的預測性能。

1 問題描述及模型構建

當EV進入充電站并連接充電樁后，充電調度系統獲取車輛的到達時間、離開時間、已行駛里程數以及預期離開時間，同時結合充電站費用和配電網電價，對EV充電進行有序控制，以實現充電站運營商的利潤和車主滿意度最大化為目標。充電調度系統采用離散時間控制模式，將一天劃分為144個調度時間段，用Δti(i=1，2，…，144)表示第i個充電調度時間段。該模型文中所用符號及含義如表1所示。

表1 主要符號及其含義

停車場運營商的利潤由其向電網支付的購電費用和車主向其支付的充電費用兩部分組成，如式(5)所示。

車主滿意度包括費用滿意度、時長滿意度和懲罰函數，如式(6)和式(7)所示，其中σ為懲罰系數。

目標函數如式(8)～式(10)所示，其中a、b為權重系數。約束條件如式(11)、式(12)、式(13)所示，式(11)表示最多可為m輛EV同時充電，式(12)表示允許進入的EV，最終充電量要滿足其需求，式(13)表示所有充電的EV能夠在離開前完成充電需求。

2 遺傳模擬退火算法設計

2.1 GASA算法

遺傳算法(Genetic Algorithm，GA)是一種通過模擬自然進化過程搜索最優解的方法，最早由美國的John Holland于20世紀70年代提出，具有較強的全局尋優能力，但局部搜索能力較差，易陷入局部最優和出現過早收斂等問題。模擬退火算法(Simulated Annealing，SA)來源于固體退火原理，它原理簡單，參數較少會以一定概率接受比當前解更差的新解，從而跳出局部最優，該算法具有較強的局部搜索能力，但對全局信息了解不多并且尋優速度較慢。針對這兩種算法存在的優勢和不足，本文提出一種遺傳模擬退火算法(Genetic Simulated Annealing Algorithm，GASA)，將SA算法的Metropolis準則融入GA算法的交叉和變異操作中，提高GA算法的局部搜索能力，防止其陷入局部最優。GASA算法的具體步驟如下：

2.1.1 編碼方式

假設有5輛EV，表2列舉了一種編碼方式，其中第5輛車在第112、119、120及143個時間片充電，第4輛車在第34、67、70、78及120個時間片充電，第3輛車在第56、78、79及80個時間片充電，第2輛車在第4、5、19及27個時間片充電，第1輛車在第1、4及7個時間片充電。

表2 編碼方式

2.1.2 初始化種群

2.1.3 適應度函數

將式(12)所示的目標函數視為GA算法的適應度函數。

2.1.4 選擇操作

選擇操作的目的是把適應度函數值最優的個體直接遺傳到下一代，采用錦標賽選擇方法，每次從初始種群中隨機選取δ個適應度函數值最高的個體，組成下一代種群。

2.1.5 交叉操作

交叉操作是指將兩個父代個體的部分基因交換，以產生新的子代個體。采用兩點交叉方式，即在(0，1)內生成的隨機數，如果小于Pc，則執行兩點交叉操作。

2.1.6 變異操作

隨機生成(0，1)內的隨機數，若小于預先設置的Pm，則進行變異操作，否則不執行。如果個體可行，隨機選擇一個分位，執行變異操作；如果個體不可行，則選擇不滿足約束條件最多的時間片分位進行變異操作。同時，為了避免GA算法的早熟情況，選用SA算法的Metropolis準則對交叉算子和變異算子得到的結果進行模擬退火處理，其中，Metropolis準則定義如式(17)所示，其中，Pm為接受概率，f1為交叉、變異后個體的適應度函數值，f2為交叉、變異前個體的適應度函數值，t0為當前溫度，τ為迭代次數，tm為溫度控制參數。

2.1.7 自適應交叉、變異策略

為了提高GASA算法的自適應能力，避免早熟收斂，加快收斂速度，使用動態自適應交叉概率Pc和變異概率Pm，如式(18)和式(19)所示，其中，kc、km為區間[0，1]內的常數，fa為種群的平均適應度函數值，fmax為最大適應度函數值，fc為交叉個體的適應度函數值，fm為變異個體的適應度函數值。μ為修正因子，如式(20)所示，其中ψ為調整系數，取值范圍為區間[1，5]內的整數。

2.2 算法流程

基于以上所述，提出的基于GASA算法的電動汽車充電調度策略流程如圖1所示。

3 仿真實驗

3.1 仿真環境及參數設置

為分析驗證本文設計的GASA算法在處理電動汽車充電調度的有效性和可行性，使用文獻[14]中的GA算法、文獻[15]中的SA算法和本文提出的GASA算法，分別求解300輛、400輛、500輛和600輛電動汽車的充電調度問題。為了使實驗結果更加可靠，每種算法進行50次獨立實驗，將平均值作為最終結果。GASA相關的參數和電價的參數設置[16]如表3和表4所示，GA算法和SA算法的參數設置同文獻[14]和文獻[15]。

圖1 充電調度策略流程圖

表3 算法的參數設置

表4 電價參數設置

3.2 實驗結果與分析

實驗1：僅考慮停車場利潤時的仿真結果如圖2所示，橫坐標為車輛數，縱坐標為停車場運營商的利潤偏差率，基準值為車輛在無序充電調度下的利潤，車輛數為300、400、500和600時，對應的基準值分別為2820、3660、4184和4425元。由圖2可知，當車輛數為300輛時，利潤偏差率為負，這是由于充電樁數量遠大于車輛數，車主可以隨意選擇其中的充電樁對車輛進行充電。隨著車輛數的增加，停車場運營商利潤偏差率逐漸上升，算法的優勢逐漸體現出來。當車輛數固定時，GASA算法的利潤偏差率最大，GA算法和SA算法比較接近，這說明GASA算法的仿真結果要優于GA算法和SA算法。

實驗2：僅考慮車主滿意度的仿真結果如圖3所示，橫坐標為車輛數，縱坐標為車主滿意度偏差率，基準值為車輛在無序充電調度下的滿意度，車輛數為300、400、500和600時，對應的基準值分別為274、371、331和223。由圖3可知，當車輛數為300輛時，滿意度偏差率為負，原因同實驗1。隨著車輛數的增加，車主滿意度偏差率逐漸增大，當車輛數為600時，GASA算法的利潤偏差率高達75%，GA算法和SA算法為68%和67%，可以看出，GASA算法的性能最好。

實驗3：綜合考慮停車場利潤和車主滿意度仿真結果如圖4所示，橫坐標為車輛數，縱坐標為函數適應度值偏差率，基準值為車輛在無序充電調度下的適應度函數值，車輛數為300、400、500和600時，對應的基準值分別為0.5398、0.5377、0.4649和0.3821。由圖4可知，當車輛數為300輛時，函數適應度值偏差率為負，原因同前。隨著車輛數的增加，GASA算法的優勢逐漸體現出來，當車輛數為600時，GASA算法的函數適應度值偏差率高達41%，SA算法和GA算法較為接近，分別為35%和32%。這說明GASA算法相較于SA算法和GA算法，仿真結果最優。

圖2 停車場運營商利潤對比

圖3 車主的充電滿意度對比

實驗4：假設車輛數為400，GASA、SA和GA算法的收斂速度如表5和圖5所示。從表3可以看出，GA算法陷入局部最優值0.318815；SA算法先陷入局部最優值0.316837后，然后跳出局部最優，最后收斂于0.317845；GASA算法跟SA算法類似，先陷入局部最優值0.317448，最后收斂于0.319542。由圖5可知，隨著迭代次數的增加，三種算法逐漸收斂，但收斂時，三種算法的迭代次數不同，GASA算法迭代到150次時，逐漸收斂；SA和GA算法迭代到250次時，才逐漸收斂。并且收斂時，GASA算法得到的適應度函數值高于GA及SA算法。因此，相較于另外兩種啟發式算法，GASA算法的性能更好。

表5 三種算法的收斂速度對比表

圖4 函數適應度值對比

圖5 三種算法的收斂速度對比

4 結 語

本文以充電站運營商的利潤和車主滿意度最大化為目標，構建充電調度模型，并使用遺傳模擬退火算法求解。實驗結果表明，遺傳模擬退火算法在求解電動汽車充電調度模型時，具有顯著效果，可以有效提高充電樁的利用率和用戶的充電體驗，對推動電動汽車行業的發展具有積極作用。后續研究中，繼續圍繞遺傳模擬退火算法進行改進，進一步提升算法的穩定性和收斂速度；同時考慮更多的實際因素，例如充電站的空間分布、車輛行駛模式、充電模式以及在更廣泛場景下的算法應用。