基于用戶滿意度與排隊論的電動汽車充電站選址定容優化

胡丹丹 蔡曙軒

摘?要：以電動汽車使用方的視角下，為盡可能提高用戶在獲得與接受充電服務過程中的滿意度并結合排隊論，提出最小化計及耗時與耗電的用戶總成本的規劃模型；采用遺傳算法與貪婪算法相結合的混合啟發式算法求解，并通過不同規模的算例證實了算法的有效性，從而優化了采用快速充電模式的充電設施布局。

關鍵詞：電動汽車；充電站；選址優化；排隊論；用戶滿意度

中圖分類號：F27?文獻標識碼：A??doi：10.19311/j.cnki.16723198.2023.03.028

0?引言

城鎮化快速發展與人民生活水平的提高讓燃油汽車（ICE）基本走進每家每戶，加重燃料依賴和空氣污染，由此造成能源短缺和環境惡化。于是各國廣泛關注新能源，新能源汽車成為其重要應用，其中電動汽車（EV）能有效減少碳排放量。快速充電方式因有效緩解“充電慢”痛點而成為補能首選，快速充電站因提高電動汽車在城市間的機動性而被用戶青睞。我國發布了《新能源汽車產業發展規劃（2021-2035年）》等一系列政策，車輛保有量逐年激增帶來的巨大電力需求突顯了充電設施建設的不充分和布局的不合理。因此，科學規劃快速充電站的選址，將有效緩解用戶的里程焦慮與充電擔憂，吸引更多的潛在人群購買電動汽車，逐漸形成為雙碳目標提供強大助力的繁榮市場。

經典的設施選址模型分為基于點與基于流的模型，前者有P-Median問題、P-Center問題和覆蓋問題等基本模型；后者有Hodgson提出的截流選址模型（FCLM），而后擴展出流續航選址模型（FRLM）等。因電動汽車的充電需求可分“點需求”和“流需求”，故充電設施選址也應基于點或流的模型研究。然而，基于流的選址模型對預測電動汽車保有量的精度要求較高，且在獲取盡可能準確的概率分布模型上有難點，更適用于在高速網絡上的充電設施部署。對于城市內部的充電設施選址，Anjos等認為使用基于點的模型更適合，且常從成本的角度討論。Xiao等最小化充電站建設與運營商經營的成本之和，Zhang等研究了不同類型充電設施的建設總成本，楊磊等以用電成本、車輛出行成本、機會成本和懲罰成本之和最小化為目標，Gan等在最大化運營商總利潤等。但這些文獻沒有關注到使用者及其滿意度，其結果常難以滿足用戶需求。

電動汽車充電站的優化研究除選址決策外，還涉及定容問題，即決定所要安裝充電樁的數量。任何一類服務設施都有排隊系統，學者基于排隊論的思想來優化定容決策，其中M/M/c等待制排隊模型廣泛應用于模擬電動汽車充電站排隊系統。Li等最小化車輛到充電站的平均行駛時間和平均等待時間之和，Hu等研究如何通過找到合適的設施位置和相應服務臺數，以在承諾的響應時間內最大限度地滿足需求。

上述文獻多以運營方的角度建模，很少關注使用方的充電體驗和滿意程度。因此本文提出基于用戶滿意度、目標函數為最小化包括時間與電力在內的用戶總成本的電動汽車快速充電站最佳位置和容量規劃模型，用遺傳算法結合貪婪算法的混合啟發式算法（GgA）求解模型。本研究的創新點主要為：①研究視角新穎，從基于滿意度的用戶總成本出發；②引入道路彎曲系數計算距離，更符合實際；③考慮用戶無不滿的充電路程及充電站的服務半徑，以衡量車主在充電可獲得性上滿意度的距離吸引力；④進行一定比例的指派，而非簡單的0-1指派。本文其余部分為：第2節做假設和符號說明，并描述問題與建模；第3節介紹遺傳嵌套貪婪求解算法，并在第4節的算例驗證其有效性；最后第5節給出結語和未來研究方向。

1?問題描述

本文以電動汽車用戶的視角，從其滿意度出發，基于車輛泊松到達、多服務臺負指數服務時間的排隊模型，考慮服務范圍、預算約束等，盡可能減少顧客為充電所消耗的電量與時間，從而最小化用戶總成本。我們進行三方面決策：選址（在哪些位置建電動汽車快充站）、指派（各需求區域車輛指派給哪些充電站及比例）和定容（各建站所安裝的快充樁數）。

1.1?假設

（1）將研究區域的連續空間轉換為離散空間，并劃分成若干個網格，視各中心點為質點及需求點和候選站點；（2）任何一個需求網格里的電動汽車用戶可選擇去往服務半徑范圍內的所建充電站中的任何一或幾座處充電；（3）假設電動汽車到達充電站的過程形成一個泊松流，且在站排隊系統里的服務時間服從負指數分布；（4）雖然車輛的充電時間實際取決于其電池容量與電池荷電狀態（SOC），但假定充電樁滿足一次車輛充電需求的時間不變。

1.2?符號說明

（1）集合。

N：研究區域內所劃分的網格數集；I：所有需求點的集合，其中i∈I；J：全部候選充電站集合，且j∈J；Ji：需求點i在充電站服務半徑內可選的候選站點集合（簡稱篩選后的候選點集），i，Ji=jαdij≤R，j∈J。

（2）參數。

cs：電動汽車快充站的單位建造成本；cp：充電樁的單位購置成本；ce：電力單位成本（即電價）；ct：單位時間成本（即人均單位時薪）；B：總預算；Ns：預建的充電站數；r：用戶對與充電站之間距離無不滿的充電路程，若超過會有不滿；R：充電站的服務半徑，車輛在此范圍內可來充電；M：極大正常數；Nevi：需求點i所有的電動汽車數量；fc：電動汽車充電頻率；Di：需求點i的總充電需求；v：電動汽車平均行駛速度；α：道路非直線系數，取值范圍在1.01到1.41之間；β：電動汽車平均行駛一公里的耗電；μ：充電樁平均服務率；dij：需求點i與候選站j的距離；tij：電動汽車從需求點i到候選充電站j的行駛時間；Fij：候選充電站j對需求點i處電動汽車的距離吸引力值。

（3）變量。

Xj：代表是否在候選站點j建站；Yij：表示需求點i處指派給候選站j的電動汽車比例；Zj：表示候選站j安裝的充電樁數；λj：代表候選站點j的平均到達率；Wj：表示車輛在充電站j排隊等待與接受服務的平均逗留時間。

1.3?模型構建

考慮電動汽車用戶滿意度，找到Ns個最優充電站位置的選址決策Xj，得到相應的指派方案Yij，然后基于M/M/c排隊模型確定各建站最佳充電樁數目的定容決策Zj，從而最小化電動汽車的用戶總成本。

（1）目標函數。

Min?TUC=ce·∑i∈I∑j∈JαβdijYij+ct·∑j∈J∑i∈ItijYij+INsWjXj=∑i∈I∑j∈Jαβcedij+cttijYij+INs∑j∈JctWjXj（1）

用戶總成本（TUC）包括電力成本與時間成本，也可分為路途總成本與逗留總成本。

（2）約束條件。

M=B-csNscp-Ns+1（2）

Di=Nevifc，i∈I（3）

tij=αdijv，i∈I，j∈J（4）

Fij=1120+12cosπR-rαdij-R+r2+π2r<αdij≤r

r<αdij<Rαdij>R，

i∈I，j∈J（5）

M具體指代有限預算下各充電站所能安裝的最大充電樁數目；Di由需求點i處Nevi輛電動汽車乘上充電頻率fc所得；式（4）用以計算電動汽車從需求點i行駛到候選充電站j所花費的時間。候選充電站j對需求點i處電動汽車的距離吸引力值通過如（5）所示的分段函數計算，當兩者的非直線距離不大于用戶無不滿的充電路程，則距離吸引力值為1；若等于或超過充電站服務半徑，則為0；而介于兩者間則類似余弦函數，隨距離變大而減小。

∑j∈JXj=Ns（6）

∑j∈JiXj≥1，i∈I（7）

Xj=0，1，j∈J（8）

式（6）使選址方案達到預建站數；式（7）確保各需求點i都被覆蓋到；Xj在（8）中定義為0-1變量，取1代表在候選站點j建立充電站，取0則不建站。

Yij≤Xj，i∈I，j∈J（9）

αdij「Yij≤R，i∈I，j∈J（10）

Yij=eFijXj∑j∈JieFijXjj∈Ji0???jJi，i∈I（11）

∑j∈JiYij=1，i∈I（12）

0≤Yij≤1，i∈I，j∈J（13）

式（9）指需求點i處電動汽車能指派給候選充電站j的前提是該處有建站；式（10）為充電站的服務半徑限制；由（11）得指派方案：當j不屬于需求點i篩選后的候選點集jJi時Yij=0，否則建站，再根據Fij計算對應的指派比例；式（12）保證各需求點i的電動汽車的指派比例之和為1；式（13）對指派決策變量Yij進行約束：Yij=0說明需求點i處的電動汽車不指派給候選站j，0<Yij<1表明部分指派給多個充電站，Yij=1時則全指派給j。

∑j∈JcsXj+cpZj≤B（14）

上式表示建站總成本與配樁總成本兩方面的總和不得大于總預算B。

Zj≤MXj，j∈J（15）

λj=∑i∈IDiYij，j∈J（16）

λj<μZj，j∈J（17）

Zj∈

，j∈J（18）

式（15）避免對非建站點安裝充電樁，且限制建站點的樁數；由式（16）計算候選站點j的平均車輛到達率λj，顯然j不建站時λj=0；式（17）認定排隊系統到達率要小于其服務率μZj；各候選站點j的充電樁數Zj在（18）定義為非負整數，若不建站為0，否則至少為1。

θjZj=11+μλjZj-1θjZj-1Zj=1Zj>1，j∈J

（19）

Wj=1μ+λjμZj-λj2θj+λjμZj-λj，j∈J（20）

為避免因充電站j的服務強度λjμ過大而導致下溢，Pasternack和Drezner引入參數θj，其計算如（19）；充電站j排隊系統屬于M/M/Zj模型，車輛到達形成參數為λj的泊松流，Zj個充電樁的服務時間服從參數為μ的負指數分布，平均逗留時間Wj由（20）所得。

最終建起基于用戶滿意度并結合M/M/c的電動汽車充電站混合整數非線性規劃模型：

Min?TUC=∑i∈I∑j∈Jαβcedij+cttijYij+INs∑j∈JctWjXj

s.t.?2-20〗

2?求解算法

服務設施選址類問題是NP-hard問題，尤其要做位置和容量雙決策時更難求解。于是將問題劃分為上層做出選址決策的主問題和下層進行定容決策的子問題，再運用啟發式算法求解：遺傳算法（GA，?genetic?algorithm）求解充電站位置選擇的選址主問題，由貪婪算法（ga，greedy?algorithm）來進行各站內充電樁分配的定容次問題，GgA求解的基本流程如圖1所示。

2.1?遺傳算法求解選址優化問題

模型涉及較多參數和變量，短時間內難以求解，故使用廣泛求解選址優化問題的遺傳算法。本文采用二進制編碼、輪盤賭選擇算子、單點交叉變換算子與單點變異算子，但交叉與變異在增加種群多樣化的同時可能會帶來不可行解，要進行一定的修復。當約束條件不多時，采用罰函數法，將較簡單的約束條件并入目標函數；若約束太多則可用如下啟發式修復算子：交叉后群體中鄰近兩個體交叉點上的等位基因不一定發生改變，若該點元素相等則不變，否則由1變0使充電站數少1，就在除交叉點外基因為0的位置里選一個令其為1并確保可行性，如遍歷完都不可行則在保證交叉點處元素始終為1下隨機生成一條可行的染色體；由0變1的修復同理。變異過后染色體變異點上的基因則必然改變，其修復策略同上。

2.2?貪婪算法求解定容優化問題

計算非線性方程會大幅度增加時間，逐次確定充電樁數也加大復雜度，如用遺傳算法會讓收斂速度變慢。給定選址方案后，問題轉化為只有定容決策的，可通過貪婪算法得出各設施樁數的精確分配結果。具體采用貪婪算法求解定容優化模型的步驟如圖2所示。

圖2?貪婪算法過程

3?算例分析

為檢驗GgA的計算性能，在Matlab?R2021a求解不同規模算例。所有算例都在一臺CPU為Intel（R）?Core（TM）?i5-11300H、運行頻率為3.10GHz和16GB內存的筆記本電腦上進行。

3.1?隨機算例設計

各假設網絡均采用網格化法劃分成一個個5ⅹ5（單位：公里）的等大網格，并將各網格中心點視為充電需求點，所有需求點都可作為充電站候選點。網格數集N取25、30、35、40、45、50、55、60和65，需求點集I與候選充電站集J也隨之確定。各網絡下預建站數、總充電需求、投資額有所不同：規定建站數與需求點數的比例不超過1比10，故相應預建站數為2、3、3、4、4、5、5、6和6座；假設各需求點電動汽車總數由指定泊松分布隨機生成且平均三天充一次電，可得到充電需求；總預算分別為430、580、630、780、820、980、1050、1200和1250萬元。模型其他參數值在表1列出。

種群規模大小分別為30、35、40、50、60、65、75、80、90，染色體長度等同于候選充電站點數，交叉概率各為0.80、0.85、0.85、0.90、0.92、0.92、0.92、0.95、0.95，變異概率均為0.10，最大迭代次數依次為200、250、300、350、400、450、500、550、600。

3.2?算法性能比較

在不同規模算例下，以枚舉法為基準對GgA做性能評估。各算例均用該算法隨機運行20次；并用枚舉法求解，若在7200秒內無法解完則不保證是最優解，再運行兩次后取3次中的最優數值為近似最優解。Zh是GgA所得目標函數值，Ze為枚舉法2h內所得值，誤差定義為：Zh-ZeZe；除誤差外還比較它們的計算時間。9個算例所得數據結果記錄在表2。

前五種規模算例下枚舉法和GgA都得到了最優解，由最大誤差不超過0.15%與平均差距在0%～0.04%可見算法穩定和性能良好；后四種算例里枚舉法不保證取得最優解，誤差顯示GgA更可能找到更優解。就求解時間而言，隨著網絡規模的擴大，枚舉法所需計算時間呈指數增長，從第3個算例的3.65秒突增到第四個算例的350.33秒，后四個算例則無法2小時內枚舉完；而GgA平均僅需2分多鐘求解完，僅小規模時慢于枚舉法，表現要更優。

3.3?算法求解性能

以N=30為例，對GgA進行穩定性、求解時間及收斂性的評估。圖3展示隨機運行20次程序所得結果，用戶總成本只有三種取值，最大波動僅為0.65，可見該算法有良好的穩健性；算法運行時間在12.15～14.67秒，平均時間為13.95秒，很短時間內都可求解問題。取其中目標函數值最優的一次隨機實驗，記錄各代種群中最優個體對應的目標函數值及逐代平均數值，如圖4所示。隨著初始種群不斷遺傳迭代，不到50代前搜索到最優結果，隨后一直保持水平無波動，表現了算法良好的收斂性能。這點在逐代最好個體平均值上也能體現出。

選址定容結果為在點8、22、25建站并對應配置52、35、25臺充電樁，具體指派方案如圖5所示。點8處所建站給左半部分區域內電動汽車提供充電服務，其中最左邊的需求點1到10全部指派給它，而中間部分區域的因距離增大為部分指派；點22的給右下部分領域車輛服務，且最右下的點21、22、27和28處車輛全部指派，其余部分指派；點25的給左上部分區域車輛服務，且最左上的25和30點處的車輛全部指派，其余則部分指派。各建站的充電樁數與其所被指派的需求量相適配，其中充電站8負責提供服務的需求點數顯然最多而配置了52個充電樁，而站22的樁數和所滿足充電需求要少一些，站25的則要更少。

4?結語

為了改善設施規劃不合理、與車輛數比例失衡、分布密度不適配的現狀，有必要優化電動汽車充電基礎設施的布局。本文以電動汽車使用方為視角，基于用戶滿意度并結合排隊系統，建立了以最小化包括時間成本與電力成本在內的用戶總成本為目標函數的電動汽車快速充電站選址定容模型，最大限度地提高電動汽車用戶在獲得與接受充電服務過程中的滿意度；并采用在遺傳算法中嵌套貪婪算法而結合成的啟發式算法（GgA）在Matlab中求解模型，通過不同規模的算例證實了算法的有效性。

由于充電站選址與定容規劃仍有許多需要考慮的因素，本文還存在一些不足之處，未來將在以下幾方面進行研究：①只是關于應用快速充電樁的充電站的選址定容規劃，可進一步研究采用慢速充電樁的充電站或是換電站的情況；②沒有考慮到電網與充電站之間的相互影響，后續可將電網負荷納入模型之中；③在模型結合車輛軌跡數與流量、POI點數據等估計現實中的充電需求，并將不同類型和電池容量的車輛分開進行討論。

參考文獻

[1]胡大偉，劉成清，胡卉，等.基于低碳視角的兩階段開放式選址路徑問題——燃油車與電動車對比[J].系統工程理論與實踐，2020，40（12）：32303242.

[2]COLMENARSANTOS?A，de?PALACIO?C，BORGEDIEZ?D，et?al.Planning?Minimum?Interurban?Fast?Charging?Infrastructure?for?Electric?Vehicles：Methodology?and?Application?to?Spain[J].ENERGIES，2014，7（3）：12071229.

[3]黃柳，胡丹丹.考慮路徑偏差和里程焦慮下充/換電站聯合布局定容優化[J].物流技術，2021，40（06）：6875.

[4]HAKIMI?S?L.Network?location?theory?and?contingency?planning[J].Energy，1983，8（8）：697702.

[5]CHURCH?R，REVELLE?C.The?maximal?covering?location?problem[J].Papers?of?the?Regional?Science?Association，1974，32（1）：101118.

[6]JOHN?HODGSON?M.The?location?of?public?facilities?intermediate?to?the?journey?to?work[J].European?Journal?of?Operational?Research，1981，6（2）：199204.

[7]KUBY?M，LINES?L，SCHULTZ?R，et?al.Optimization?of?hydrogen?stations?in?Florida?using?the?FlowRefueling?Location?Model[J].International?Journal?of?Hydrogen?Energy，2009，34（15）：60456064.

[8]曹小曙，胡培婷，劉丹.電動汽車充電站選址研究進展[J].地理科學進展，2019，38（01）：139152.

[9]郭磊，王克文，文福拴，等.電動汽車充電設施規劃研究綜述與展望[J].電力科學與技術學報，2019，34（03）：5670.

[10]ANJOS?M?F，GENDRON?B，JOYCEMONIZ?M.Increasing?electric?vehicle?adoption?through?the?optimal?deployment?of?fastcharging?stations?for?local?and?longdistance?travel[J].European?Journal?of?Operational?Research，2020，285（1）：263278.

[11]XIAO?D，AN?S，CAI?H，et?al.An?optimization?model?for?electric?vehicle?charging?infrastructure?planning?considering?queuing?behavior?with?finite?queue?length[J].Journal?of?Energy?Storage，2020，29：101317.

[12]H.Z，Z.H，Z.X，et?al.An?Integrated?Planning?Framework?for?Different?Types?of?PEV?Charging?Facilities?in?Urban?Area[J].IEEE?Transactions?on?Smart?Grid，2016，7（5）：22732284.

[13]楊磊，郝彩霞，唐瑞紅.基于電動物流車的充電和換電設施選址模型[J].系統工程理論與實踐，2019，39（07）：17811795.

[14]X.G，H.Z，G.H，et?al.FastCharging?Station?Deployment?Considering?Elastic?Demand[J].IEEE?Transactions?on?Transportation?Electrification，2020，6（1）：158169.

[15]楊洋，高攀，趙聰澤.城市中電動汽車臨時充電站選址和定容模型[J].重慶師范大學學報（自然科學版），2020，37（06）：16.

[16]Y.L，J.L，C.Y?C，et?al.Growing?;the?charging?station?network?for?electric?vehicles?with?trajectory?data?analytics：2015?IEEE?31st?International?Conference?on?Data?Engineering[C].2015.

[17]HU?D?D，LIU?Z?W，HU?W?S.Congestion?Service?Facilities?Location?Problem?with?Promise?of?Response?Time[J].MATHEMATICAL?PROBLEMS?IN?ENGINEERING，2013，2013.

[18]馮樹民，高賀，郭彩香.城市道路網結構形式的評價[J].哈爾濱工業大學學報，2007（10）：16101613.

[19]PASTERNACK?B?A?D?Z.Classroom?note：A?note?on&nbsp;calculating?steady?state?results?for?an?m/m/k?queuing?system?when?the?ratio?of?the?arrival?rate?to?the?service?rate?is?large[M].Journal?of?Applied?Mathematics?&?Decision?Sciences，1998：201203.

[20]ZHOU?G，ZHU?Z，LUO?S.Location?optimization?of?electric?vehicle?charging?stations：Based?on?cost?model?and?genetic?algorithm[J].Energy，2022，247：123437.