楊曉東 馬洪恩 王寧 許可

（1.杭州微聯(lián)智控科技有限公司，杭州311100；2.同濟大學 汽車學院，上海2018041）

主題詞：電動汽車 充電樁 選址 貪心算法 P中值模型

EV Electric Vehicle

SOC State Of Charge

NCBDC National College Big Data Competition

全國高校新能源汽車大數(shù)據(jù)創(chuàng)新創(chuàng)業(yè)大賽

NP Non-deterministic Polynomial

0 前言

我國目前已經(jīng)是全球充電設施網(wǎng)絡規(guī)模最大的國家。盡管如此，截至2020年6月，我國新能源汽車市場保有量為417萬輛，就此數(shù)據(jù)對比來看，車樁比為3.1∶1，車樁比仍較為懸殊。隨著未來中國新能源電動汽車產(chǎn)業(yè)的發(fā)展，新能源汽車的增長速度將會更快，到2030年，我國新能源汽車數(shù)量預計要達到6 000萬輛，于此同時車樁比也要進一步降低，未來十年，我國充電樁的缺口還會更大。

隨著電池技術(shù)的發(fā)展，新興的新能源造車勢力的興起，傳統(tǒng)車企在新能源研發(fā)和建設方面逐漸加大投入，以及國家對新能源車的各種優(yōu)惠政策的加持，目前新能源汽車正在逐漸走向成熟。充電基礎(chǔ)設施作為保障電動汽車可以大規(guī)模使用的配套基礎(chǔ)設施，將很大程度上影響和制約著整個電動汽車行業(yè)的發(fā)展和電動汽車車主的用戶滿意度。因此，一個城市電動汽車能否充分普及和應用與城市是否提前對充電站的布局進行了科學合理的規(guī)劃息息相關(guān)。

由此可見，對充電樁的建設進行合理規(guī)劃將是每個城市在發(fā)展新能源汽車時所必須要研究的一個課題。如果建設的前期缺乏有必要的規(guī)劃，只是盲目地追求充電樁的數(shù)量、充電站的規(guī)模，必然會造成充電樁得不到充分利用的資源浪費問題以及公共充電站覆蓋范圍重復的問題。所以，各大城市在建設充電基礎(chǔ)設施之初，必須要充分考慮到電動汽車的數(shù)量、電動汽車的時空分布情況、用戶的用車出行習慣方面因素，才能對充電設施的建設做出科學合理的優(yōu)化。做到既可以滿足未來電動汽車數(shù)量增長而產(chǎn)生的充電需求的同時，又不會使充電設施大量浪費。

因此本文從滿足用戶充電需求的角度出發(fā)，利用P中值模型和貪心算法來進行電動汽車充電站選址布局。利用此方法，既可以滿足用戶的充電需求，又能使公共充電設施得到合理的優(yōu)化配置。于此同時，由于電動汽車的充電功率遠高于一般家用電器的使用功率，在進行充電基礎(chǔ)設施建設之前應當與當?shù)氐碾娏?、國家電網(wǎng)等充分溝通、相互協(xié)調(diào)，將充電樁與充電站的建設有效地納入到城市電網(wǎng)的發(fā)展規(guī)劃中。只有城市電網(wǎng)與充電樁充分的相互協(xié)調(diào)與配合，才能使充電設施有可靠的電力供應，才會使城市電網(wǎng)能夠安全平穩(wěn)的運行。因此本論文所討論的對規(guī)劃選址問題的研究十分必要。

1 出行實時數(shù)據(jù)處理

本文所用數(shù)據(jù)為2020年NCBDC大賽提供的2019年10月-12月，北京市87輛純電動私人乘用車的運行數(shù)據(jù)。

科學合理的對新能源乘用車充電需求進行測算，是確保充電樁“新基建”落地的關(guān)鍵因素。通過新能源汽車運行數(shù)據(jù)測算這些車輛的充電需求數(shù)據(jù)，對公共充電站選址定容具有重要意義。

數(shù)據(jù)的主要字段為車輛唯一編號、數(shù)據(jù)采集時間、車輛狀態(tài)、充電狀態(tài)、電池電量(State of Charge,）以及經(jīng)緯度信息。字段說明如表1所示，其中每輛車都會有一個唯一的隨即編號，車輛采集時間精確到秒，數(shù)據(jù)時間間隔以30 s居多，車輛狀態(tài)中1表示啟動，2表示熄火，3表示其它。充電狀態(tài)中1表示停車充電，2表示行駛充電，3表示未充電狀態(tài)，4表示充電完成。的范圍為0%～100%，精度為1%。經(jīng)緯度默認為東經(jīng)、北緯。

表1 原始數(shù)據(jù)字段說明

利用以上數(shù)據(jù)，本案例從北京市政府角度出發(fā)，對即將發(fā)放的新能源小客車指標，提前進行充電基礎(chǔ)設施的選址布局規(guī)劃。本案例假設政府只能在提出申請加裝充電樁的現(xiàn)有停車場的備選范圍內(nèi)，通過給予停車場經(jīng)營者部分補貼的方式，對相應停車場進行充電基礎(chǔ)設施的建設。因此，本文假設某月共56個停車場提出加裝充電樁申請，政府需要根據(jù)其是否能滿足用戶充電需求為衡量指標，在這56個停車場中選出部分停車場給予補貼，從而對充電站的建設順序進行一定的選擇，防止出現(xiàn)建設過快和過慢現(xiàn)象的發(fā)生。本文所建充電站均為滿足公共需求的充電站，如前所述，目前，公共充電站只是充當電動汽車臨時充電的場所，因此用戶對大充電功率要求較高，本文選址布局的充電站均可以滿足這一趨勢需求，并且假設充電站的建設對北京電網(wǎng)影響不大。

原始數(shù)據(jù)有大量的缺失和異常2種情況，包括數(shù)據(jù)值缺失、工況矛盾、車輛狀態(tài)變化異常以及數(shù)據(jù)數(shù)值情況異常的情況。因此根據(jù)物理意義，本文數(shù)據(jù)清洗時，對部分可修復數(shù)據(jù)進行了修復。對于數(shù)據(jù)值缺失，比如一些車輛的充電狀態(tài)數(shù)據(jù)有缺失，需要根據(jù)其的變化來對缺失值進行補充。如果上升，則將充電狀態(tài)重新設置為1（停車充電），如果下降，則將充電狀態(tài)重新設置為3（未充電狀態(tài)）。對于工況矛盾這種情況，比如某輛車同時處于啟動和停車充電兩種狀態(tài)時，可以根據(jù)前后時段的變化，來得到具體哪個值異常，并將其重置。對于車輛狀態(tài)變化異常，有些車輛的車輛狀態(tài)一直為熄火，但其經(jīng)緯度會發(fā)生變化，于是便需要根據(jù)車輛經(jīng)緯度變化情況，重新設置其車輛狀態(tài)。對于數(shù)據(jù)數(shù)值情況異常情況，比如某輛車在短時間內(nèi)突然增加到100%，或突然降為零，那么會判定該數(shù)據(jù)值異常，此時會根據(jù)其前后情況，插值得到此時刻的。

數(shù)據(jù)清洗結(jié)束后，與原始數(shù)據(jù)進行對比，發(fā)現(xiàn)原始數(shù)據(jù)中存在異常值的數(shù)據(jù)約占數(shù)據(jù)總數(shù)的25%，對其中64%的數(shù)據(jù)進行了重構(gòu)與補充，修復了47%的異常數(shù)據(jù)。之后對原始數(shù)據(jù)汽車的充電片段進行累積，去除了3個月內(nèi)累計充電時長小于1 h的10輛車。并刪除相應數(shù)據(jù)，得到有效數(shù)據(jù)2 708 403條和有研究價值的車輛77輛。通過地圖得到北京市的經(jīng)緯度范圍,即北京位于北緯39.5?到41?之間,東經(jīng)115.5?到117.5?之間。因此對不在本文研究范圍內(nèi)的北京市以外區(qū)域的數(shù)據(jù)進行刪除，最終得到2 414 754條在研究范圍內(nèi)的數(shù)據(jù)。

2 用戶公共充電需求分析

通過對車輛充電狀態(tài)進行篩選，得到各充電狀態(tài)為1的點，并將其充電位置的經(jīng)緯度在圖中顯示出來，便可得到該輛車日常充電的點的位置。

最終將763個不同經(jīng)緯度的充電點聚合為267個充電樁。之后依據(jù)充電樁服務的車輛是否唯一，以及充電的時間是否規(guī)律，來判斷這267個充電樁是私人樁還是公共充電樁。最終得到這些充電樁有49個私人樁，218個為公共樁。

對用戶的充電習慣進行分析，即將每個用戶的充電數(shù)據(jù)單獨提取出來，得到用戶每次充電的起始值。將每個用戶充電的起始值從大到小排序，選取下四分之三位數(shù)作為此輛車充電的最低閾值。由于每輛車的電池容量以及車主的使用習慣不同，每輛車的充電最低閾值也各不相同，但其充電閾值均在20%到40%之間。由于本文所用數(shù)據(jù)車輛數(shù)量較少，采取一車一閾值的方式，以最大程度上保障需求的可靠性。

對數(shù)據(jù)中所給車輛的電池電量進行分析，發(fā)現(xiàn)樣本中車輛電池電量平均值為45.06 kW·h，考慮到用戶長時間使用車輛后電池會有一定的衰減，因此數(shù)據(jù)中每輛車可裝載的最大電量平均為40 kW·h左右。通過對所有車輛信息進行統(tǒng)計，發(fā)現(xiàn)用戶在3個月內(nèi)的平均充電次數(shù)為24.73次。平均私家車用戶每3到4天充一次電。數(shù)據(jù)中有私人樁的私家車為49輛，無固定充電樁的車輛為28輛。擁有私人充電樁與沒有私人充電樁的比例為7：4。

對數(shù)據(jù)進一步研究發(fā)現(xiàn)，擁有私人充電樁的用戶對公共充電需求較低，平均每月在外充電1次左右。擁有私人樁的車主在外充電主要原因是由于當日出行較遠，其電池電量無法支撐其一整天的行程距離之和時才會選擇在公共充電樁進行臨時充電。通過對用戶出行較遠時行駛距離進行統(tǒng)計，發(fā)現(xiàn)當用戶每日行程往返超過130 km時，認為此用戶當日出行必有公共充電需求，這一數(shù)據(jù)可能會由于未來電池最大容量的提升而發(fā)生變化。

3 用戶公共充電需求測算

上文已經(jīng)將存在充電需求的點在地圖上表示了出來，在這些點中，用其最終停車點表征其這段路上的需求。將離車輛自己家用充電樁附近的需求點去掉，即可得到這輛車的真實公共充電需求點的分布。由于電動汽車車主充電行為隨機性很強，而以往的研究將充電概率設為一個固定的常數(shù)，這樣的做法有些主觀，不夠準確。本文考慮了電動汽車當前的荷電狀態(tài)與車主下一次行駛里程這兩個主要因素，將上文提到的各個需求點建立了一個充電概率計算模型，作為該需求點的權(quán)重。概率模型公式為：

式（1）中：P、P分別表示當前電動汽車的電池荷電狀態(tài)與下一段行駛里程對充電概率的影響；表示電動汽車電池荷電狀態(tài)的最小閾值； 表示電池容量；ω表示每公里耗電量；表示下一段行駛里程；、為影響因子。

本文假設電動汽車的當前電量如果不足以支撐其下一次出行，那么電動汽車車主必定選擇充電，并且為了安全性，電動汽車的需要有一定的閾值。所以，當電動汽車滿足上述假設條件時，車主充電概率為1。

對于下一行駛目的地，可以根據(jù)下次車輛狀態(tài)為熄火的地點來判定。眾所周知，電動汽車當前越低，下一次行駛里程越高，充電概率越高?；谶@一規(guī)律，考慮不同影響因素建立出的概率計算公式見式（2）。

電動汽車當前對電動汽車充電概率影響具體計算公式如式（2）所示：

下一次行駛里程對電動汽車充電概率影響具體計算公式如式（3）所示。

式（3）中：與為根據(jù)北京市地圖確定為5和105。本文引入、兩個參數(shù)作為影響因子，代表電動汽車當前與下一次行駛里程這兩個因素所占的權(quán)重，本文認為電動汽車的當前對電動汽車是否進行充電影響較大，因此，?。?0.65，=0.35。將式（2）與式（3）代入式（1）中，便可以得到電動汽車充電概率計算模型。

通過概率公式得到各點的需求概率作為權(quán)重，賦予每個需求點。

將需求點在地圖上（基于百度folium地圖生成器，圖1～5）顯示出來，需求點的散點圖、熱力圖和聚類數(shù)字圖如圖1、2、3所示。

圖1 充電需求點散點圖

圖2 充電需求熱力圖

4 選址模型

考慮到本文所用數(shù)據(jù)類型為汽車經(jīng)緯度點，以及上文所得到的需求為點需求，所以決定用P中值模型作為本文的充電站選址模型?？紤]到目前北京市的房價和地價，以及土地利用率，得出北京市市中心目前很難會再有空地來單獨建設充電站，因此目前充電樁的建設將以在現(xiàn)有停車場上加裝充電樁為主。在北京市發(fā)展和改革委員會官方網(wǎng)站上得到擬申請市政府固定資產(chǎn)投資補助的公用充電樁項目清單，找到其經(jīng)緯度點，作為P中值模型中的候選點集合，并將各停車場位置在圖中標識出來，如圖4所示，備選停車場集合為圖中藍色點。將充電需求點為作為客戶，以備選停車場集合作為服務點，從而構(gòu)造出從需求點到備選停車場距離之和最短的P中值模型。

圖3 充電需求點聚類數(shù)字圖

圖4 備選停車場位置

當充電需求點與備選停車場個數(shù)較大時，P中值模型具有組合爆炸的特點，因此P中值模型是NP難題。由于本文所用數(shù)據(jù)遍布北京市，范圍較大，因此選用貪心算法進行求解。

貪心算法并不一味地追求最優(yōu)解，只需從眾多解中得到一個較為滿意的解即可。在算法設計時，首先要明確目標函數(shù)和優(yōu)化條件，并制定一個可行的貪心準則。之后并不需要列舉所有情況，而是以當前情況為最優(yōu)解，利用制定的貪心準則，一步步往下搜索，直到找到滿足該問題的目標值。貪心算法具有步驟相對簡單，計算量較小、節(jié)約時間的優(yōu)點，因此在解決NP難題以及具體的選址問題中得到了廣泛應用。

基本步驟如下：

（1）令當前選中設施點數(shù)=56，也就是將所有56個候選停車場全部都選中；

（2）求出各個需求點到離其最近的停車場的距離，并乘以各需求點的權(quán)重，計算出總距離；

（3）將56個設施候選點從候選集中每次取出一個，比較這56種情況下的總距離，找出總距離增量最小的停車場，將其從候選集中去除。

依此類推，當k值減少到P時，得到的即為最能滿足公共充電需求的站點。通過對總距離增量的分析，發(fā)現(xiàn)P值在15左右增長迅速，結(jié)合前文對充電站規(guī)模的測算，P值選為15左右也較為合理。最終選址15作為本文模型的P值。

最終將選擇的15個停車場在地圖上顯示出來，如圖5所示，最終得到備選點為圖5中圓環(huán)點所示，淺色點為需求點，深色點為未被選中的停車場。

圖5 最終選定停車場位置

5 結(jié)論與展望

通過研究發(fā)現(xiàn)，采用需求點的測算方式在測算純電動汽車充電需求時可以有一定作用，可以對需求做出合理的測算。另外，以往的研究將充電概率設為一個固定的常數(shù)，這樣的做法有些主觀，不夠準確。通過考慮電動汽車當前的荷電狀態(tài)（）與車主下一次行駛里程這兩個主要因素，結(jié)合點需求與出行鏈需求，將各個需求點建立了一個充電概率計算模型，這樣的需求測算更加科學合理。在選址模型上，P中值模型在解決從備選點中選出服務點的這類選址問題中優(yōu)勢明顯。最終提出了一種將電動汽車用戶需求與電動汽車充電概率模型相結(jié)合的充電站選址方法，并采用貪心算法得到了最終選址方案。此方法不僅可以確定最終的選址方案，還可以為各個候選點進行排序。

由于本文采用數(shù)據(jù)驅(qū)動的方式，從真實數(shù)據(jù)出發(fā)，通過對北京市充電基礎(chǔ)設施相關(guān)問題的調(diào)研，并結(jié)合北京市實際停車場的位置確定最終選址方案。因此，得到了一系列選址布局優(yōu)化建議與選址方法，可以指導未來北京市及其它城市的充電站建設。同時此方法的數(shù)據(jù)處理方式、研究模型與方法也具有充分的擴展性，只要給定設施候選點，便可得到最為滿足需求的選址位置，并可對各個充電站選址位置進行排序，可直接移植到更大數(shù)據(jù)量的選址問題中。

但是，由于用戶的充電行為具有一定的主觀性，需求測算模型考慮因素還不夠全面。后期可增加測算模型因素，如：充電站的建設成本以及充電站建設對電網(wǎng)的影響、分時定價方案對于用戶充電需求的影響等，并對各類參數(shù)進行回歸分析，進行準確程度驗證，提升數(shù)據(jù)真實性。另外，本文充電樁樣本數(shù)較少，只是使用了北京市77輛車所用的充電樁數(shù)據(jù)，未來可以拓展數(shù)據(jù)量。相關(guān)數(shù)據(jù)由于受到限制的原因，無法進行深入分析。未來可以將更多影響充電站建設的因素加入到需求測算與選址模型中，使模型更加科學合理。