面向用戶行駛計劃的電動汽車充電調度策略

曾鳴　冷甦鵬　張科

摘要：充電站（樁）尚未普及以及電動汽車有限的行駛里程，使得大多數汽車用戶關于是否選擇電動汽車猶豫不決。為了減少用戶對于電動汽車有限電池容量的擔心，并且降低因頻繁充電以及偏離原定行駛路線繞路進行充電所增加的電動汽車使用費用，提出一種基于匹配理論面向用戶行駛計劃的電動汽車充電調度方案TPCS。首先，分別根據電動汽車用戶的行駛計劃和對各充電站的電量需求構建電動汽車用戶與充電站的偏好表；然后，建立電動汽車用戶與充電站之間的多對一匹配模型；最后，以系統總效用為優化目標進行充電站接口分配。數值仿真結果顯示，與隨機分配（RCS）算法和僅考慮電動汽車效用分配（OEVS）算法相比，TPCS算法將系統總效用較RCS算法最多提高了39.3%，較OEVS算法最多提高了5%；而在電動汽車充電需求輕負載時，TPCS算法始終保證用戶滿意度在90%以上，高于RCS算法。所提算法能夠有效地提高系統總效用和用戶滿意度，同時降低計算復雜度。

關鍵詞：充電調度；行駛計劃；車輛入電網；匹配理論；偏好表

中圖分類號：TP393.07

文獻標志碼：A

0引言

近年來電動汽車（Electric Vehicle， EV）的低碳環保性和經濟實用性使得電動汽車在汽車市場中的比例逐步上升，由電動汽車充電帶來的大規模用電需求若不經過合理的充電調度，將大幅增加現有電網的電力負擔[1]。此外，對于行駛模式下的電動汽車，頻繁地充電與繞路充電都會影響電動汽車使用者的用戶體驗。

目前國內外研究大多將電動汽車與智能電網這一研究熱點相結合，旨在利用調度電動汽車充電調節電網的峰谷值差。文獻[2]考察了充電方案和充電速率對某一特定住宅樓的電網負載情況的影響；文獻[3]研究了風能作為電網能量來源時電動汽車的充電調度問題，文中考慮了風能的不確定性與動態變化及電動汽車的停泊時長，利用馬爾可夫決策過程對問題進行了建模；在文獻[4]中，充電站之間互相競爭形成非合作博弈，以提高配電網絡的穩定性和充電站的收益為目標制定電動汽車的充電站選擇策略；文獻[5]以二次函數建模電網網損，以最小化網損為優化目標；文獻[6]研究在電動汽車需在某一截止時間前充滿電的約束條件下最小化電網的峰值負荷；文獻[7]通過控制電動汽車的充電行為減少大規模電動汽車充電對電網的影響，同時也減少了電網網損。以上關于電動汽車充電調度問題的研究均未在以減小電網峰均比為優化目標的同時考慮用戶行駛計劃對電動汽車用戶選擇充電站的影響。

本文運用基于效用函數的匹配理論框架[8]，考慮行駛模式下電動汽車的行駛計劃，將電動汽車充電調度問題建模成一個帶雙邊偏好的多對一匹配問題，設計了面向用戶行駛計劃的電動汽車充電調度（Traveling Plan-aware Charging Scheduling， TPCS）算法，比較在考慮電動汽車行駛計劃的情況下，系統效用函數和電動汽車使用者滿意度的變化情況。

1系統建模

如圖1所示，假設N個充電站（Charging Station， CS）和M輛需要充電的電動汽車（Electric Vehicle， EV）分布在考察的道路區域內。每個充電站可同時最多提供個充電接口為充電汽車進行充電。每個充電接口的充電速率假Ki（i=1，2，…，N）定為不變的，且各充電站各充電接口的充電速率一致。

電動汽車選擇充電站通常有自己的偏好。一般來說，首先，電動汽車的使用者通常希望充電站在其之后行駛路線的沿路上，而無須開車繞路去充電。其次，充電站所在的位置需滿足該電動汽車當前剩余電量可達的條件，否則電動汽車無法抵達充電站。再次，根據用戶的行程安排，通常對于充電完成時間會有所要求。比如，電動汽車的行程安排為上午11點之后會去到比較偏遠暫時還沒有布設充電站的區域，用戶會要求充電過程必須在上午11點之前完成。

其中：p為充電站向電動汽車收取的充電單價，本模型中假設各充電站向需要充電的各電動汽車收取相同的充電單價。因此，為了最大化效用函數，各充電站會優先選擇請求充電量大的電動汽車為其提供充電服務。

令Ω表示分配矩陣，其中矩陣元素aij={0，1}，aij=1表示充電站i被分配給電動汽車提供充電服務，aij=0表示充電站未被分配給電動汽車提供充電服務。令β為電動汽車效用函數與充電站效用函數之間的權重參數，在本文所建立的優化模型中，同等對待充電樁的效用與電動汽車的效用，因此將權重參數β設為1。實際應用中，若從充電站運營的角度出發，可以將充電站的權重系數增大，但同時也應適當考慮充電電動汽車的效用，需要根據實際應用場景權衡電動汽車與充電站兩者之間的效用，在不同應用場景下選取恰當的權重系數。

以上電動汽車與充電站之間的匹配問題的優化目標為最大化系統總效用，因此考慮電動汽車行駛計劃的充電調度優化問題可建模為：

2.2算法求解

電動汽車集合與充電站集合為兩個不相交的集合，因此本文將為電動汽車分配充電站的優化問題映射為多對一的匹配問題。文獻[8]中提出了用于求解一對一匹配的接收延遲算法，本文將該算法擴展到為電動汽車分配充電站的多對一匹配問題中。

第一階段：首先，每輛電動汽車通過GPS信號獲得行駛計劃中可能途經的充電站的位置信息，根據到達這些充電站的路程信息、當前電池的剩余電量以及行駛計劃中的時間安排按照式（1）計算在各充電站處充電能夠獲得的效用值。其次，按照式（1）計算每輛電動汽車的效用值，并以降序排列的方式將效用值為正的充電站放入相應電動汽車的偏好表中。

第二階段：首先，每輛電動汽車同時向在其偏好表中排名第一的充電站，即電動汽車行駛計劃中途經的充電站中用戶最希望去充電的充電站，發出充電請求。各充電站收到這一輪的充電請求后，檢查收到充電請求數目的多少，若多于充電站現有空閑充電接口數目，則選擇請求充電量較大的Ki個充電請求，緩存下這Ki個充電請求的電動汽車編號和充電請求電量，并向其他電動汽車發送拒絕其充電請求的消息。若充電請求的數目少于Ki，則將這一輪所有發送充電請求的電動汽車的編號和充電請求電量緩存下來。

第三階段：收到拒絕充電請求消息的電動汽車向其偏好表中的次優充電站發送充電請求。收到充電請求的充電站將本輪收到的充電請求和上一輪緩存的充電請求進行比較，從中選出請求充電量較大的Ki個充電請求，并緩存其電動汽車編號和充電請求電量。依此循環，直至所有充電站的緩存集合的并集等于電動汽車的集合或者未在充電站緩存集合中的電動汽車已被所有充電站拒絕，循環結束。

3性能仿真分析

仿真場景為50km×50km的區域內有10個充電站隨機分布，每個充電站有10個充電接口；4種單位行駛距離需要消耗不同電量的電動汽車發出充電請求[11]；電動汽車到充電站的路程服從均勻分布U（0，30]km；電動汽車的充電請求電量服從均勻分布U（10，20]kWh；充電完成時間晚于截止時間的概率為0.2；延遲代價常數C=100。本文所建立的優化模型中假定若電動汽車預計到達某充電站的時刻晚于該電動汽車行駛計劃中期望抵達此充電站的最晚時刻，則放棄在此充電站進行充電。因此，將C設為100使得根據式（1）計算的電動汽車若在此充電站進行充電得到的效用值為負。C還可以根據其他準則來選取，例如，如果電動汽車預計到達某充電樁的時刻晚于行駛計劃中規定可以到達該充電樁的最晚時刻，依然將該充電樁放入其偏好表中，則C可小于100。

為了便于比較，仿真實驗結果中加入了隨機分配（Random Charging Scheduling， RCS）和僅考慮電動汽車效用分配（Only utility of Electric Vehicle concerned Scheduling， OEVS）的兩種方案。

圖2給出了三種調度方案下的系統效用隨電動汽車數量變化的變化情況。相比RCS和OEVS調度方案，TPCS調度方案可以獲得最大的系統效用。當電動汽車數目小于等于100輛時，TPCS算法獲得的系統效用與OEVS幾乎相當，均高于RCS算法獲得的系統效用；當電動汽車數目為120輛時，與RCS算法相比，采用TPCS算法系統效用提高了39.3%；當電動汽車數目增至140輛時，與OEVS算法相比，采用TPCS算法系統效用提高了5%。

圖3給出了隨電動汽車數量變化不同調度方案下電動汽車充電滿意度的變化情況。當電動汽車的數量少于110輛時，TPCS調度算法和OEVS調度算法均能保證電動汽車充電滿意度在90%以上，遠高于RCS調度算法；當需要充電的電動汽車的數量大于110輛時，由于充電站和各充電站能夠提供的充電接口有限，三種調度方案下的電動汽車充電滿意度都急劇下降。

圖4給出了TPCS調度方案下迭代次數與充電站個數的關系。給定電動汽車的數量M，TPCS算法的迭代次數先隨充電站個數的增加而增加，然后隨充電站個數的增加而減少，迭代次數的最大值在電動汽車數量與所有充電站可提供的充電接口總額相近時取得。這是因為當電動汽車數目遠小于所有充電站可提供的充電接口總額時，即充電請求輕負載時，循環結束條件“未在充電站緩存集合中的電動汽車已被所有充電站拒絕”易被滿足進而循環結束；當電動汽車數目遠大于所有充電站可提供的充電接口總額時，即充電請求重負載時，循環結束條件“所有充電站的緩存集合的并集等于電動汽車的集合”易被滿足而導致循環結束。從圖4也可以看出，迭代次數并未以指數級增長，因此該算法的計算復雜度在可接受范圍內。

4結語

本文對考慮了電動汽車用戶行駛計劃的電動汽車充電調度問題進行了建模，運用匹配理論提出TPCS算法對優化問題進行求解。通過仿真實驗驗證了在TPCS調度方案下，相比RCS和OEVS調度方案，系統效用和電動汽車用戶的滿意度均有提升，且該算法具有可接受的計算復雜度。該研究結果能夠通過設計電動汽車調度算法幫助提高現有充電站充電負載能力，并且提升用戶使用電動汽車的滿意度。后續研究可以進一步考慮構建電動汽車用戶偏好表時的其他影響因素。

參考文獻：

[1]BARI A， JIANG J， SAAD W， et al. Challenges in the smart grid applications： an overview [J]. International Journal of Distributed Sensor Networks， 2014， 2014： Article ID 974682.

[2]VAN ROY J， LEEMPUT N， GETH F， et al. Apartment building electricity system impact of operational electric vehicle charging strategies [J]. IEEE Transactions on Sustainable Energy， 2014， 5（1）： 264-272.

[3]HUANG Q， JIA Q-S， QIU Z， et al. Matching EV charging load with uncertain wind： a simulation-based policy improvement approach [J]. IEEE Transactions on Smart Grid， 2015， 6（3）： 1425-1433.

[4]TAN J， WANG L. Real-time charging navigation of electric vehicles to fast charging stations： a hierarchical game approach [J]. IEEE Transactions on Smart Grid， 2015， 8（1）： 1-11.

https：//www.researchgate.net/publication/280924799， IEEE網站提供的就有問題？

[5]CLEMENT-NYNS K， HAESEN E， DRIESEN J. The impact of vehicle-to-grid on the distribution grid [J]. Electric Power Systems Research， 2011， 81（1）： 185-192.

[6]ZHAO S， LIN X， CHEN M. Peak-minimizing online EV charging： price-of-uncertainty and algorithm robustification [C]// INFOCOM 2015： Proceedings of the 2015 IEEE International Conference on Computer Communications. Washington， DC： IEEE Computer Society， 2015： 2335-2343.

[7]VERZIJLBERGH R A， GROND M O W， LUKSZO Z， et al. Network impacts and cost savings of controlled EV charging [J]. IEEE Transactions on Smart Grid， 2012， 3（3）： 1203-1212.

[8]GALE D， SHAPLEY L S. College admissions and the stability of marriage [J]. American Mathematical Monthly， 1962， 69（1）： 9-15.

[9]SAAD W， DAWY Z， SHARAFEDDINE S. A utility-based algorithm for joint uplink/downlink scheduling in wireless cellular networks [J]. Journal of Network & Computer Applications， 2012， 35（1）： 348-356.

[10]PANTISANO F， BENNIS M， SAAD W， et al. Match to cache： joint user association and backhaul allocation in cache-aware small cell networks [C]// ICC 2015： Proceedings of the 2015 IEEE International Conference on Communications. Washington， DC： IEEE Computer Society， 2015： 3082-3087.

[11]SEMIARI O， SAAD W， DAWY Z， et al. Matching theory for backhaul management in small cell networks with mmWave capabilities [C]// ICC 2015： Proceedings of the 2015 IEEE International Conference on Communications. Washington， DC： IEEE Computer Society， 2015： 3460-3465.

[12]EL-HAJJ A M， DAWY Z， SAAD W. A stable matching game for joint uplink/downlink resource allocation in OFDMA wireless networks [C]// ICC 2012： Proceedings of the 2012 IEEE International Conference on Communications. Washington， DC： IEEE Computer Society， 2012： 5354-5359.

[13]ZENG M， LENG S， ZHANG Y. Power charging and discharging scheduling for V2G networks in the smart grid [C]// ICC 2013： Proceedings of the 2013 IEEE International Conference on Communications workshops. Washington， DC： IEEE Computer Society， 2013： 1052-1056.