武淵，葉寧

（1. 山西省人事考試中心，山西 太原 030006；2. 南京郵電大學 計算機學院，江蘇 南京 210042）

0 引言

目前，全球能源短缺和溫室氣體排放問題日益顯著。作為人口和制造業(yè)大國，我國的能源消耗和二氧化碳排放量不容忽視。據英國石油公司統(tǒng)計，2016 年中國一次能源消費達30.53 億噸石油當量，占世界一次能源消費總量的23%，由此產生的二氧化碳排放量達91.23 噸，占世界總排放量的27.3%。針對上述問題，我國在《巴黎協(xié)定》和“十四五”規(guī)劃中做出在2030 年實現“碳達峰”、2060 年實現“碳中和”的承諾。為實現上述目標，在交通領域大力發(fā)展具有污染小、噪聲低等特點的電動汽車（Electric Vehicle，EV）成為必然趨勢。然而，由于電池續(xù)航里程不足，充電時間長以及充電站建設又不完善等問題，電動汽車的發(fā)展受到了極大制約［1］。因此，如何合理規(guī)劃充電站位置及容量，以滿足道路交通需求已成為城市綠色交通發(fā)展的關鍵問題。

目前，國內外學者已針對電動汽車充電站選址定容問題開展了相關研究。蔡子龍等［2］總結了應急充電站的選址影響因素指標體系，并基于層次分析法-目標規(guī)劃法提出了一種應急充電站選址模型。吳雨等［3］以充電站年總成本最小為目標，提出了一種基于改進免疫克隆選擇算法的電動汽車充電站選址定容方法。趙炳耀等［4］建立了一種高維非線性的充電站選址定容模型，并通過Voronoi 圖和改進引力搜索算法聯合求解。Wang 等［5］考慮了電動汽車的充電時間、定位能力，以最小化運行成本為目標優(yōu)化了充電站位置。Chen 等［6］將停車需求，土地屬性，人口密度和出行需求為約束，以降低電動汽車用戶的使用成本為目標，確定了充電站的最佳位置。Gagarin 等［7］提出根據經濟因素，工程可行性，服務可用性，社會因素，環(huán)境因素和土地因素標準對候選站點進行綜合評估，進而篩選出最佳充電站位置和容量。

上述文獻大多針對現有的用戶需求，并未挖掘用戶充電行為和充電站建設方案之間的關系，從而忽視了用戶充電需求的潛在變化。實際中，用戶會根據充電站的建設位置和容量情況，自主調整充電決策方案，即充電站建設方案與用戶使用情況具有反饋關系。針對上述問題，近年來，少數學者考慮上述反饋關系，提出了同時從政府和用戶角度充電站選址定容方案。由于充電需求模式的變化是在給定充電站建設方案之后確定的，這些研究大多采用雙層規(guī)劃的思路，并通過相應的啟發(fā)式算法（如粒子群算法）進行求解［8-10］。

然而上述研究仍存在以下三點缺陷：

1）實際中，充電站作為大功率設施，其建設往往需要對接入電網進行擴建和改造，即充電站的建設將產生一定的電網擴展成本。另一方面，由于地域和用地規(guī)劃影響，電網并不能無限制擴建，即電網容量存在上限，而現有研究并未考慮電網容量的限制和擴展成本；

2）充電站的服務質量與該地區(qū)電動汽車的發(fā)展息息相關，若服務質量較差，則用戶更傾向于購買傳統(tǒng)燃油汽車，并不符合“碳中和”的社會需求；若服務質量較好，則用戶更傾向于購買電動汽車，有利于減少碳排放。然而現有研究大多僅以經濟效益為目標，缺乏對地區(qū)服務質量方面的考量；

3）算法的精確度直接影響優(yōu)化結果，因而開發(fā)高效精確的算法尤為重要。現有研究大多采用遺傳、粒子群等原始算法，未針對問題提出改進算法。

本文針對上述問題，以最小化充電站建設成本和最大化充電站服務質量為目標，考慮電網容量的影響，建立了充電站選址定容多目標雙層規(guī)劃模型，并提出了一種基于混沌理論的NSGA-II 算法（CNSGA-II）對上述模型進行求解。最后通過仿真分析和對比實驗，驗證了CNSGA-II 算法求解充電站選址定容多目標雙層規(guī)劃模型的有效性。

1 充電站選址定容多目標雙層規(guī)劃模型

本文利用圖論的方法，將城市地區(qū)道路交通主干道抽象為一張網絡圖G=（V，A），其中V為網絡圖G中的節(jié)點集合，A為節(jié)點之間路徑的集合。為便于建模求解，本文假設V為備選充電站地址，且擴建電網能夠滿足用電需求。

上層模型即從政府的角度出發(fā)，以最小化充電站運行周期內的綜合成本和最大化服務質量為目標，優(yōu)化充電站位置和規(guī)模（即充電樁數量）。

下層模型即從用戶的角度出發(fā)，在給定充電站位置和規(guī)模的情況下，以最小化充電成本為目標，優(yōu)化充電站選擇策略。

1.1 上層模型目標函數

充電站建設需要盡可能減小充電站運行周期內的綜合成本，同時考慮到充電站的服務屬性，應盡可能提高服務質量。其中，綜合成本包括土地成本、充電站建設成本，設備維護成本和用戶使用成本。此外，由于充電站是高功率電力設施，電網擴展成本同樣不容忽視。本文中，服務質量量化為充電站的覆蓋范圍，覆蓋范圍越大，服務質量越高。

1.1.1 綜合成本

綜合成本即為土地成本（CL）、充電站建設成本（CR）、設備維護成本（CG）、電網擴展成本（CK）以及用戶使用成本（CU）之和，表述如下：

其中考慮到用戶將根據路網結構和充電站位置改變充電策略，用戶使用成本（CU）在下層模型中給出，其余各項成本的計算方式如下：

式中：cl為單位充電樁的土地成本；xi為二元變量，xi=1 表示在第i個節(jié)點建充電站，反之，xi=0 表示不在第i個節(jié)點建充電站；Ni為在第i個節(jié)點建立充電站的規(guī)模，即充電樁個數；cr1和cr2分別表示建立充電站的固定成本和每個充電樁的投資成本；cg1，cg2和cg3分別表示建立充電站系統(tǒng)的每日固定維護成本，每個充電樁的固定維護成本和與充電負荷相關的可變維護成本；T為規(guī)劃周期內的時段數；PLi為第i個節(jié)點的t時段的電力負荷；ck表示電網的單位容量擴展成本；fi是第i個節(jié)點的充電電流；RPi是第i個節(jié)點的額定功率負載；IPi是第i個節(jié)點施工之前的額定電力負載。

1.1.2 服務質量

如前所述，本文采用充電站覆蓋范圍量化服務質量。由于城市路網可以看作線路和節(jié)點的組合，難以直接通過服務半徑衡量充電站服務范圍。因此，本文使用同一條道路上相鄰兩個充電站之間的平均距離來表示覆蓋強度，數學描述如下：

式中：α是將節(jié)點之間的距離轉換為實際距離的參數；d（xi+1，xi）表 示 節(jié) 點i+1 和 節(jié) 點i的 點 對 點距離。

1.2 上層模型約束條件

1.2.1 需求約束

在服務區(qū)域內，充電站容量不應小于該區(qū)域內電動汽車的總充電需求。

式中：Lmax表示該地區(qū)電動汽車的總充電需求。

1.2.2 距離約束

假設充電車輛僅在充電站接受充電服務，直到充滿電位置。因此，兩個相鄰充電站節(jié)點間的距離不得大于平均最大行駛距離。

式中：Dmax是電動汽車在電池充滿電后的平均最大行駛距離。

1.2.3 規(guī)模約束

在實際建設過程中，受土地面積和充電質量需求的影響，不允許充電站的規(guī)模過小或過大。因此，對于任一xi=1 的節(jié)點，其充電站規(guī)模具有以下約束：

1.3 下層模型目標函數

下層模型主要從用戶角度出發(fā)，優(yōu)化目標為用戶綜合成本，決策變量為充電策略。其中，充電策略即為電動汽車在特定時刻選擇充電站進行充電操作的方案（ψ（v，xi，t）），用戶綜合成本包括充電成本（C1）和用戶從當前位置抵達充電站的驅動成本（C2），以及充電負荷需求未滿足的損失成本（C3）可表述如下：

各項成本的計算方式如下［10-11］：

式中：εi，t為t時段的單位充電電價；tv為電動汽車v在時段t內的充電時長；dv，i為車輛初始位置至充電節(jié)點i的最短距離；ψ（v，xi，t）為二元函數，當電動汽車v于時刻t在充電站xi充電時，ψ（v，xi，t）=1，反之，為0；c2和c3分別表示單位距離的驅動成本和單位負荷未滿足的損失成本；PLi，tloss表示未滿足的充電負荷需求。

1.4 下層模型約束條件

1.4.1 可達充電站距離約束

電動汽車的電池電量有限，因此，對于任意電動汽車，均存在最大可達充電站距離約束，表述如下：式中：Dv，max為電動汽車v的最大行駛距離。

1.4.2 充電電量約束

本文將充電電量設為電動汽車從出發(fā)位置至充電站的電量消耗，表述如下：

1.4.3 容量約束

優(yōu)化后的所有充電站在對應的充電計劃之下，各個充電站節(jié)點的充電負荷加上未滿足的充電負荷需求等于該節(jié)點的容量配置，該約束為：

1.5 綜合模型

整合上層和下層模型的目標函數及約束條件，即可得出電動車充電站多目標選址定容雙層規(guī)劃模型：

其中，ψ由下層模型得出，可轉換為

約束條件即為上層和下層模型約束條件的集合。

根據式（17）和（18）可以看出，下層模型本質上可以歸約為上層模型的一個等式約束，即上層模型的求解依賴于下層模型的優(yōu)化結果。若給定一組選址定容方案，首先，需要輸入至下層模型求解，并將其結果（即用戶使用成本）輸入至上層模型。因此，所建立的上下層模型存在反饋關系。由此，即可計算出給定址定容方案對應的綜合成本和服務質量目標函數值。若采用枚舉方法，即將可能的選址定容方案的目標函數值均按照上述過程計算得出，既可以通過Pareto 非支配理論，比較得出最佳折中解。

然而，復雜的路網結構往往存在巨量的選址定容方案，枚舉方法對于海量解空間搜索效率較低。因此，需要開發(fā)一套有效的充電站選址定容多目標優(yōu)化算法。

2 基于改進CNSGA-II 的充電站選址定容多目標優(yōu)化算法

如前所述，充電站選址定容下層模型可歸約為路徑規(guī)劃問題，進而通過Floyd 算法求解。而上層規(guī)劃模型是一個多目標優(yōu)化問題，可通過NSGA-II（快速非支配排序遺傳算法II）求解。作為遺傳算法（GA）的多目標形式，NSGA-II 算法具有收斂性好，魯棒性強等優(yōu)點，已被廣泛應用于各種選址和調度優(yōu)化問題中［12-14］。本研究在傳統(tǒng)NSGA-II 算法的基礎上，引入混沌序列，以增強算法的尋優(yōu)能力和收斂速度。此外，本文采用TOPSIS 算法（逼近理想解排序方法）從NSGA-II 算法產生的Pareto 最優(yōu)解集中篩選出最佳折中解。本文所設計的算法框架主體結構如圖1 所示。

圖1 算法整體框架結構圖Fig. 1 Overall framework structure diagram of algorithm

2.1 改進的CNSGA-II算法

傳統(tǒng)NSGA-II 算法的初始種群是隨機生成的，并且交叉和變異過程也是隨機執(zhí)行的，降低了收斂速度。本研究將混沌序列引入NSGA-II，以解決第1 節(jié)中所建立的多目標優(yōu)化模型。

本文所提出CNSGA-II 算法詳細步驟如下：

步驟1（產生混沌初始解）：使用一維logistic 映射方法產生基于混沌序列的初始種群?；煦缡且环N隨機行為，具有靈敏性，遍歷性和隨機性的特征［15］?；诨煦缧蛄挟a生的初始種群同樣具有上述特征，從而能夠提高算法迭代初期種群的多樣性。對于實數編碼的連續(xù)性變量而言，初始種群是在決策變量的上限和下限內生成的浮點數，其中混沌序列取代了隨機成分：

式中：Xj，i表示第j個體的第i個染色體位置對應的變量，整形變量對其取整即可；M為種群規(guī)模。UBi和LBi分別表示第i個染色體位置對應變量的上限和下 限；τj，i表 示 混 沌 序 列，可 根 據 以 下logistic 映 射生成：

式中：δ等于4 時，將完全混沌序列。τj，1是初始隨機混 沌 變 量，其 范 圍 在0 至1 之 間，并 且τj，1不 等 于｛0.25，0.50，0.75｝，因為這些初始值導致式（20）產生確定數值［15］?；煦缧蛄兄械拿總€值都依賴于初始值，初始值的微小變化會導致其長期行為的巨大差異，這是混沌的基本特征。因此，生成的初始種群是一個混沌序列，具有混沌特性。

步驟2（適應度計算）：將每個個體具有的選址（xi）和定容（Ni）變量傳遞給下層模型，并調用Floyd算法計算下層模型（式（10）－（16））的最優(yōu)解，反饋給上層模型。結合式（1）－（6）計算種群中每個個體的適應度值。

步驟3（基于非支配排序和擁擠度距離的個體排序）：根據適合度值和個體的非支配性對染色體進行分類并排序。例如，個體a的綜合成本（F1）小于個體b，且個體a的服務質量（F2）不小于個體b，則稱個體a支配個體b。若個體a不被其他個體支配，則稱個體a為非支配個體。擁擠度距離的詳細解釋參見文獻［16-18］。

步驟4（選擇、混沌交叉和變異操作）：按照排序選擇出部分個體進行混沌交叉和混沌變異操作。

式中：βi為第i個染色體位置對應變量的交叉擴展因子，可通過下式得出：

式中：η為交叉的分布指數，η較大時，將產生“近親”子代。在傳統(tǒng)NSGA-II 算法中，hi是隨機生成的0-1 區(qū)間內的浮點數，而本文則采用類似于式（20）的混沌映射生成hi。

同理，本文對變異策略進行了改進，提出了一種基于混沌序列的改進突變策略。對于一個給定的個體X1，i，其變異個體X*1，i表述為：

式中：θi為第i個染色體位置對應變量的變異擴展因子；γi為混沌映射生成的0～1 區(qū)間內的浮點數；φ表示變異的分布指數。

步驟5（種群合并和選擇子代操作）：合并當前父代和子代作為一個種群，對合并種群執(zhí)行步驟3和4，篩選出子代個體。

步驟6（結束判斷指令）：判斷當前迭代次數是否達到最大迭代次數，是，算法結束，并輸出Pareto最優(yōu)解集；否則回到步驟5。

2.2 TOPSIS算法

NSGA-II 算法生成的Pareto 最優(yōu)解集包括許多非支配解，并且每個解都有兩個屬性（綜合成本和服務質量）。因此，從Pareto 最優(yōu)解集中篩選出折衷解決方案是一個多屬性決策問題。層次分析法（AHP）和與逼近理想解法（TOPSIS）是解決多屬性問題的兩種主要方法，已被應用于各種問題中［21-23］。與TOPSIS 相比，AHP 常用于確定屬性的權重。此外，TOPSIS 是根據人類的決策過程提出的，具有強大的邏輯基礎和簡單的計算過程［24］。因此，在本研究中選擇TOPSIS 從Pareto 最優(yōu)解集中篩選出權衡解決方案。

對于具有W個解的給定的Pareto 最優(yōu)集S，S=［S1，S2，…，Si，…，SW］，每個解的目標可以表示為Yi=［yi1，yi2，…，yij，…，yiZ］，其中Z是目標數量。TOPSIS 算法的主要步驟如下：

步驟1：將目標函數值映射到［0，1］區(qū)間，以消除量綱影響。

步驟2：定義權重向量［λ1，λ2，…，λj，…，λZ］，其中λj（λj≥0）表示決策者對目標j的重視程度。權重向量的總和等于1。

步驟3：根據式產生正（S+）理想解和負（S-）理想解，如下所示：

步 驟4：計 算 偏 好 向 量D=［D1，D2，…，1Di，…，DZ］，其中Di表示解決方案i的質量。 最佳折衷解決方案即為具有最小偏好Di的解決方案，表示如下：

2.3 Floyd算法

由于路網被抽象為無向圖，電動汽車在路網拓撲圖中選擇充電站進行充電操作實質上是一個與時段相關的最短路問題，其最優(yōu)方案可通過Floyd算法得出［25-26］。實質上，Floyd 算法已經被應用于求解路網中最短路徑的求解，并驗證了其合理性［25］。此時，充電站的選址定容方案已由CNSGA-II 算法生成，Floyd 是一種動態(tài)規(guī)劃算法，其狀態(tài)轉移方程如下：H[m，n]=min{H[m，l]+H[l，n]，H[m，n]}，（30）式中：H［m，n］為給定電動汽車從初始位置m到節(jié)點n的 最 小 成 本；l為m和n之 間 的 斷 點；初 始 時，電動汽車位于m節(jié)點，即H［m，m］=0。

對于任一電動車輛在任意t時刻，Floyd 算法求解下層模型的具體步驟如下：

步驟1：初始值設為H［m，m］=0；

步驟2：根據式（10）－（13）和（30），計算初始位置到下一節(jié)點的最小成本；

步驟3：判斷是否抵達充電節(jié)點，是則輸出充電節(jié)點n對應的成本；否則，返回步驟2；

步驟4：枚舉CNSGA-II 算法生成的所有充電節(jié)點，并對比其成本。選擇出具有最小成本的充電節(jié)點，即為下層模型的求解結果。

3 算例分析

3.1 路網和相關參數設置

本文以西安市的道路交通干線路網為例（如圖2 所示），將所建立模型和算法應用于該城市路網，優(yōu)化電動汽車充電站的選址和容量。所選地區(qū)的路網干線拓撲結構如圖3 所示，其中，節(jié)點之間采用直線連接，而實際路網中節(jié)點之間并不一定是直線。實際計算時，使用真實的路網節(jié)點距離，且所有節(jié)點均為待選充電站建設節(jié)點，模型中主要參數如表1 所示。

表1 模型中主要參數Table 1 The main parameters in the model

圖2 西安市干線實際路網圖Fig. 2 Actual road network map of Xi′an arterial road

圖3 西安市路網干線拓撲結構圖Fig. 3 Topological structure diagram of Xi′an arterial road network

經過多次仿真實驗，選擇表現較好的CNSGAII 算法相關參數，并假定綜合成本和服務質量同等重要，算法參數如表2 所示。

3.2 選址定容方案結果及分析

將上述參數和路網結構輸入所建立模型，并通過所提出的算法框架求解，所得出的Pareto 前沿如圖4 所示，其中充電站平均距離即為服務質量的表征量。該模型得到最佳折中解近似位于Pareto 前沿的中間位置，且距離正理想解較近，離負理想解較遠，這說明本文算法得到的結果是綜合成本和服務質量的有效折中。表2 列出了最佳折中解的相關參數，即選址定容方案。

圖4 Pareto 前沿Fig. 4 Pareto front

表2 各算法的參數設置Table 2 Parameter setting of each algorithm

從表3 可以看出，該地區(qū)共需配置6 個充電站，結合路網可以看出，充電站大致離散的分布于城區(qū)內部的路網節(jié)點，這是由于內部節(jié)點的車輛較多，充電需求更大。

表3 所選地區(qū)充電站的選址定容決策方案Table 3 Decision-making plan for location and capacity of charging stations in selected areas

3.3 算法的穩(wěn)定性分析

本文使用M-index 方法進一步測試CNSGA-II算法的穩(wěn)定性和有效性，M-index 是衡量所設計的多目標優(yōu)化算法搜索到的Pareto 解與問題的理論Pareto 解集之間差距的指標，在數學上定義為：

式中：Ω（A）即為算法產生的Pareto 解集和理論Pareto 解集之間的差；A是算法產生的Pareto 最優(yōu)解集；|A|是A集合中非支配解的個數；||χ-ζ||為算法產生的非支配解χ和理論非支配解ζ之間的歐式距離；ζP為理論Pareto 最優(yōu)解集。

表4 列出了獨立進行15 次M-index 試驗的結果，可以看出CNSGA-II 產生的Pareto 最優(yōu)解集和理論Pareto 最優(yōu)解集的偏差均值為5.753，在10 以內，差別較小。因此，所提出的CNSGA-II 算法在求解電動汽車充電站雙層多目標規(guī)劃選址定容模型時，具有較高的可靠性及有效性。

表4 15次M-index分析的試驗結果Table 4 15 times of test results of M-index analysis

3.4 算法的對比分析

Pareto 前沿的收斂性是衡量多目標優(yōu)化算法的優(yōu)越度的重要指標。目前，常用的多目標算法主要包括包括NSGA-II 算法、多目標粒子群算法（MOPSO）、多目標差分進化算法（MODA）。為驗證本文算法的優(yōu)越性，則需與上述算法進行結果對比。由于上述算法具有一定的隨機性，因此，需要獨立執(zhí)行多次，從統(tǒng)計學的角度分析各算法的優(yōu)劣。

假設兩種算法a與b對上述多目標優(yōu)化模型執(zhí)行N次所得到的Pareto 最優(yōu)解集為Ai和Bj（i，j=1，2，…，N）。即可根據式（32）計算兩種算法的平均控制率DR。

式中：χa和χb分 別為Ai和Bj中的元素；χa?χb表示χa支配χb。若DR（a，b）＞DR（b，a），則表明算法a得到的Pareto 最有解集支配算法b的結果，即算法a收斂性優(yōu)于算法b。

對各算法獨立執(zhí)行20 次，計算平均控制率DR結果如表5 所示。可以看出，DR（CNSGA-II，MOPSO），DR（CNSGA-II，MODA）和DR（CNSGA-II，NSGA-II）均高于對應的元素翻轉DR。這表明本文算法的收斂性優(yōu)于其他三種方法。這也證明將混沌映射引入NSGA-II 算法能夠顯著提高其收斂性能。

表5 平均控制率DR計算結果Table 5 DR calculation results of average control rate

4 結語

本文采用二層規(guī)劃模型和多目標優(yōu)化理論，建立了充電汽車選址定容模型。并開發(fā)了一套以改進的CNSGA-II 算法和TOPSIS 求解上層模型，Floyd 算法求解下層模型的綜合求解方法。其中下層模型計算所需的選址定容方案由上層模型算法產生，并將求解結果反饋給上層模型算法。因此，所構建的綜合求解方法具有強耦合的特性。仿真算例表明所建立的模型和算法具有良好的可靠性和有效性，適用于城市路網充電站選址定容問題。此外，所提出求解方法同樣可以遷移至其他雙層規(guī)劃求解問題中，具有廣闊的應用前景。