曾鳴　冷甦鵬　張科

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

關(guān)鍵詞：充電調(diào)度；行駛計(jì)劃；車輛入電網(wǎng)；匹配理論；偏好表

中圖分類號(hào)：TP393.07

文獻(xiàn)標(biāo)志碼：A

0引言

近年來(lái)電動(dòng)汽車（Electric Vehicle， EV）的低碳環(huán)保性和經(jīng)濟(jì)實(shí)用性使得電動(dòng)汽車在汽車市場(chǎng)中的比例逐步上升，由電動(dòng)汽車充電帶來(lái)的大規(guī)模用電需求若不經(jīng)過(guò)合理的充電調(diào)度，將大幅增加現(xiàn)有電網(wǎng)的電力負(fù)擔(dān)[1]。此外，對(duì)于行駛模式下的電動(dòng)汽車，頻繁地充電與繞路充電都會(huì)影響電動(dòng)汽車使用者的用戶體驗(yàn)。

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

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

1系統(tǒng)建模

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

電動(dòng)汽車選擇充電站通常有自己的偏好。一般來(lái)說(shuō)，首先，電動(dòng)汽車的使用者通常希望充電站在其之后行駛路線的沿路上，而無(wú)須開(kāi)車?yán)@路去充電。其次，充電站所在的位置需滿足該電動(dòng)汽車當(dāng)前剩余電量可達(dá)的條件，否則電動(dòng)汽車無(wú)法抵達(dá)充電站。再次，根據(jù)用戶的行程安排，通常對(duì)于充電完成時(shí)間會(huì)有所要求。比如，電動(dòng)汽車的行程安排為上午11點(diǎn)之后會(huì)去到比較偏遠(yuǎn)暫時(shí)還沒(méi)有布設(shè)充電站的區(qū)域，用戶會(huì)要求充電過(guò)程必須在上午11點(diǎn)之前完成。

其中：p為充電站向電動(dòng)汽車收取的充電單價(jià)，本模型中假設(shè)各充電站向需要充電的各電動(dòng)汽車收取相同的充電單價(jià)。因此，為了最大化效用函數(shù)，各充電站會(huì)優(yōu)先選擇請(qǐng)求充電量大的電動(dòng)汽車為其提供充電服務(wù)。

令Ω表示分配矩陣，其中矩陣元素aij={0，1}，aij=1表示充電站i被分配給電動(dòng)汽車提供充電服務(wù)，aij=0表示充電站未被分配給電動(dòng)汽車提供充電服務(wù)。令β為電動(dòng)汽車效用函數(shù)與充電站效用函數(shù)之間的權(quán)重參數(shù)，在本文所建立的優(yōu)化模型中，同等對(duì)待充電樁的效用與電動(dòng)汽車的效用，因此將權(quán)重參數(shù)β設(shè)為1。實(shí)際應(yīng)用中，若從充電站運(yùn)營(yíng)的角度出發(fā)，可以將充電站的權(quán)重系數(shù)增大，但同時(shí)也應(yīng)適當(dāng)考慮充電電動(dòng)汽車的效用，需要根據(jù)實(shí)際應(yīng)用場(chǎng)景權(quán)衡電動(dòng)汽車與充電站兩者之間的效用，在不同應(yīng)用場(chǎng)景下選取恰當(dāng)?shù)臋?quán)重系數(shù)。

以上電動(dòng)汽車與充電站之間的匹配問(wèn)題的優(yōu)化目標(biāo)為最大化系統(tǒng)總效用，因此考慮電動(dòng)汽車行駛計(jì)劃的充電調(diào)度優(yōu)化問(wèn)題可建模為：

2.2算法求解

電動(dòng)汽車集合與充電站集合為兩個(gè)不相交的集合，因此本文將為電動(dòng)汽車分配充電站的優(yōu)化問(wèn)題映射為多對(duì)一的匹配問(wèn)題。文獻(xiàn)[8]中提出了用于求解一對(duì)一匹配的接收延遲算法，本文將該算法擴(kuò)展到為電動(dòng)汽車分配充電站的多對(duì)一匹配問(wèn)題中。

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

第二階段：首先，每輛電動(dòng)汽車同時(shí)向在其偏好表中排名第一的充電站，即電動(dòng)汽車行駛計(jì)劃中途經(jīng)的充電站中用戶最希望去充電的充電站，發(fā)出充電請(qǐng)求。各充電站收到這一輪的充電請(qǐng)求后，檢查收到充電請(qǐng)求數(shù)目的多少，若多于充電站現(xiàn)有空閑充電接口數(shù)目，則選擇請(qǐng)求充電量較大的Ki個(gè)充電請(qǐng)求，緩存下這Ki個(gè)充電請(qǐng)求的電動(dòng)汽車編號(hào)和充電請(qǐng)求電量，并向其他電動(dòng)汽車發(fā)送拒絕其充電請(qǐng)求的消息。若充電請(qǐng)求的數(shù)目少于Ki，則將這一輪所有發(fā)送充電請(qǐng)求的電動(dòng)汽車的編號(hào)和充電請(qǐng)求電量緩存下來(lái)。

第三階段：收到拒絕充電請(qǐng)求消息的電動(dòng)汽車向其偏好表中的次優(yōu)充電站發(fā)送充電請(qǐng)求。收到充電請(qǐng)求的充電站將本輪收到的充電請(qǐng)求和上一輪緩存的充電請(qǐng)求進(jìn)行比較，從中選出請(qǐng)求充電量較大的Ki個(gè)充電請(qǐng)求，并緩存其電動(dòng)汽車編號(hào)和充電請(qǐng)求電量。依此循環(huán)，直至所有充電站的緩存集合的并集等于電動(dòng)汽車的集合或者未在充電站緩存集合中的電動(dòng)汽車已被所有充電站拒絕，循環(huán)結(jié)束。

3性能仿真分析

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

為了便于比較，仿真實(shí)驗(yàn)結(jié)果中加入了隨機(jī)分配（Random Charging Scheduling， RCS）和僅考慮電動(dòng)汽車效用分配（Only utility of Electric Vehicle concerned Scheduling， OEVS）的兩種方案。

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

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

圖4給出了TPCS調(diào)度方案下迭代次數(shù)與充電站個(gè)數(shù)的關(guān)系。給定電動(dòng)汽車的數(shù)量M，TPCS算法的迭代次數(shù)先隨充電站個(gè)數(shù)的增加而增加，然后隨充電站個(gè)數(shù)的增加而減少，迭代次數(shù)的最大值在電動(dòng)汽車數(shù)量與所有充電站可提供的充電接口總額相近時(shí)取得。這是因?yàn)楫?dāng)電動(dòng)汽車數(shù)目遠(yuǎn)小于所有充電站可提供的充電接口總額時(shí)，即充電請(qǐng)求輕負(fù)載時(shí)，循環(huán)結(jié)束條件“未在充電站緩存集合中的電動(dòng)汽車已被所有充電站拒絕”易被滿足進(jìn)而循環(huán)結(jié)束；當(dāng)電動(dòng)汽車數(shù)目遠(yuǎn)大于所有充電站可提供的充電接口總額時(shí)，即充電請(qǐng)求重負(fù)載時(shí)，循環(huán)結(jié)束條件“所有充電站的緩存集合的并集等于電動(dòng)汽車的集合”易被滿足而導(dǎo)致循環(huán)結(jié)束。從圖4也可以看出，迭代次數(shù)并未以指數(shù)級(jí)增長(zhǎng)，因此該算法的計(jì)算復(fù)雜度在可接受范圍內(nèi)。

4結(jié)語(yǔ)

本文對(duì)考慮了電動(dòng)汽車用戶行駛計(jì)劃的電動(dòng)汽車充電調(diào)度問(wèn)題進(jìn)行了建模，運(yùn)用匹配理論提出TPCS算法對(duì)優(yōu)化問(wèn)題進(jìn)行求解。通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了在TPCS調(diào)度方案下，相比RCS和OEVS調(diào)度方案，系統(tǒng)效用和電動(dòng)汽車用戶的滿意度均有提升，且該算法具有可接受的計(jì)算復(fù)雜度。該研究結(jié)果能夠通過(guò)設(shè)計(jì)電動(dòng)汽車調(diào)度算法幫助提高現(xiàn)有充電站充電負(fù)載能力，并且提升用戶使用電動(dòng)汽車的滿意度。后續(xù)研究可以進(jìn)一步考慮構(gòu)建電動(dòng)汽車用戶偏好表時(shí)的其他影響因素。

參考文獻(xiàn)：

[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網(wǎng)站提供的就有問(wèn)題？

[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.