基于最大利潤模型的高速公路充換電站選址

賈林國 周小琳 姚博彬 葉珍 武奇生

摘 要：合理有效的高速公路充換電站選址布局是提升路網(wǎng)效率的關(guān)鍵。為了滿足電動汽車用戶的通行需求并兼顧投資建設(shè)的利潤回報，文中設(shè)計了用于電動汽車充換電站選址規(guī)劃的最大利潤模型，同時也提出了一種基于自適應(yīng)大鄰域搜索的算法對上述模型進(jìn)行啟發(fā)式求解。算例對比實(shí)驗(yàn)表明，文中所提算法的優(yōu)化性能明顯優(yōu)于采用遺傳算法得到的結(jié)果，證明了文中所設(shè)計的最大利潤模型的有效性。

關(guān)鍵詞：高速公路;電動汽車;充換電站選址;最大利潤模型;自適應(yīng)大鄰域搜索算法;遺傳算法

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：A文章編號：2095-1302（2020）11-00-03

0 引 言

電動汽車作為一種新能源汽車，與傳統(tǒng)燃料汽車相比具有節(jié)能、環(huán)保等優(yōu)點(diǎn)，正逐漸發(fā)展成為當(dāng)前社會的主力交通工具。相比傳統(tǒng)燃料汽車，電動汽車的續(xù)航是制約其在高速公路場景下行駛的短板。為了彌補(bǔ)短板，國家“新型基礎(chǔ)設(shè)施建設(shè)”中特將充換電站作為重點(diǎn)建設(shè)目標(biāo)之一。然而，由于受到政策、資金和空間區(qū)域規(guī)模等因素的限制，在高速公路沿線的每個服務(wù)區(qū)或停車區(qū)建設(shè)充換電站是不現(xiàn)實(shí)的。因此需要進(jìn)行電動汽車充換電站的選址規(guī)劃研究。目前，針對電動汽車充換電站選址模型的研究，從點(diǎn)需求來看，主要是根據(jù)基于P-中位和P-中心的最大覆蓋模型;而考慮流量需求，則主要是根據(jù)基于流量補(bǔ)給選址模型來考慮最小建站成本和庫存成本[1-7]。

與上述研究不同，本文同時考慮了滿足用戶出行服務(wù)需求和充換電站運(yùn)營利潤回報兩個因素，設(shè)計了基于最大利潤模型的充換電站選址模型及其有效求解算法。

1 充換電站選址問題

目前充換電站選址模型大多是在基于路徑已知的情況下最小化總成本（包括建設(shè)成本和電能庫存成本），但并沒有考慮盈虧情況。

假設(shè)路網(wǎng)中共有N個節(jié)點(diǎn)，構(gòu)成點(diǎn)集N。定義變量hi=1，表示在節(jié)點(diǎn)i處建立充換電站;否則，hi=0。令fhi表示在節(jié)點(diǎn)i∈N建立充換電站后的總交通流量，它是由經(jīng)過該節(jié)點(diǎn)的不同路徑q∈Q的交通流量fqhi疊加得到。路網(wǎng)的最大利潤與電動汽車一次充換電所需費(fèi)用ei、電能庫存單位成本si和充換電站建造成本ci有關(guān)，即最大利潤模型要求尋找某一子集∩N使得公式（1）所示的代價函數(shù)J最大化。

式中，Q為所有路徑的集合。在約束條件中，二值化的決策變量hi和路徑流量fhi是代價函數(shù)中的兩個重要參數(shù)。

從公式（1）中可知，求解該模型的核心是必須得到每個候選建站節(jié)點(diǎn)的交通流量;而交通流量又會根據(jù)是否在該節(jié)點(diǎn)建站而發(fā)生變化，即每個充換電站的流量與電動汽車所選擇的路徑有關(guān)。為了解決如上問題，可以對路網(wǎng)中所有出發(fā)地-目的地對（OD對）先考慮做不帶剩余電量的最短路徑規(guī)劃，然后在選址時令選址點(diǎn)必須滿足所有OD對路徑上電動汽車的充電需求。有了固定的路徑以及選址組合，就可以計算選址點(diǎn)中的交通流量。但是電動車用戶在最短路徑上并不需要在每個充換電站點(diǎn)補(bǔ)給電能。這就意味著，在計算流量時，還需要考慮電動汽車的充換電決策，即在哪個充換電站進(jìn)行能源補(bǔ)充。

2 基于自適應(yīng)大鄰域搜索的求解方法

可以用Dijkstra算法[8]確定最短路徑;對于充換電站策略選擇，由于單一路徑上的充換電站節(jié)點(diǎn)數(shù)量有限，可以用窮舉法求解。但對最大利潤模型的求解卻是十分困難的，因?yàn)殡S著節(jié)點(diǎn)規(guī)模的增大，選址方案呈指數(shù)級增長，屬于NP-hard問題。因此，模型求解的關(guān)鍵就在于如何設(shè)計有效的近似算法。在數(shù)學(xué)優(yōu)化中，特別是針對組合優(yōu)化問題，鄰域搜索是在當(dāng)前解的鄰域范圍內(nèi)重復(fù)將該解轉(zhuǎn)變?yōu)槠渌獠⒆罱K獲得近似最優(yōu)解的有效手段之一。當(dāng)鄰域規(guī)模無法顯式定義時，可采用一個破壞（Destroy）方法破壞解并用修補(bǔ)（Repair）方法修復(fù)解來隱式地定義鄰域。自適應(yīng)大鄰域搜索（Adaptive Large Neighborhood Search，ALNS）算法采用了多種Destroy方法和Repair方法，并在迭代過程中為Destroy方法和Repair方法動態(tài)分配權(quán)重[9]。算法流程見表1所列。

在表1中，和Ω分別表示Destroy方法和Repair方法的集合，而和表示各自的權(quán)重。

每次搜索之后，將采用如下函數(shù)為每個Destroy方法和Repair方法進(jìn)行評估：令ψ∈{ω1， ω2， ω3， ω4}，其中ω1>ω2>ω3>ω4>0為自定參數(shù)，分別表示“新解是當(dāng)前全局最優(yōu)解”“新解比當(dāng)前解更好”“新解被接受”“新解被拒絕”四種情況下的權(quán)重。Destroy和Repair方法的權(quán)重更新規(guī)則為：

式中，λ∈（0， 1）為參數(shù)。

在求解最大利潤模型時，本文所設(shè)計的Destroy方法是在可行解O中n個充換電站節(jié)點(diǎn)進(jìn)行破壞。破壞策略有三種：

（1）不考慮流量，隨機(jī)取出n個站點(diǎn)進(jìn)行破壞;

（2）選擇n1個流量較大的站點(diǎn)和n2個流量較小的站點(diǎn)進(jìn)行破壞，n1+n2=n;

（3）通過計算每個站點(diǎn)的流量，選擇流量較小的n個節(jié)點(diǎn)進(jìn)行破壞。為了保證解的穩(wěn)定，本文中規(guī)定破壞的點(diǎn)數(shù)滿足n≤|O|/4。

本文所設(shè)計的Repair方法有兩種：

（1）隨機(jī)添加節(jié)點(diǎn)直到解滿足約束條件;

（2）利用被破壞后的解對所有OD對做滿足可達(dá)性檢驗(yàn)，找出所有潛在節(jié)點(diǎn)中流量最大的節(jié)點(diǎn)。

經(jīng)過Destroy和Repair操作后，需要決定是否接受新解。本求解方法所采用的準(zhǔn)則包括Metropolis接受準(zhǔn)則[10]和Random Walk接受準(zhǔn)則[11]（以下簡稱M接受準(zhǔn)則和R接受準(zhǔn)則）。前者是當(dāng)新解比原解差時以概率P=exp{α[J（Onew）-J（Oold）]}接受新解，參數(shù)α在初始時設(shè)為較小的數(shù)（使接受新解的概率較大），隨著迭代進(jìn)行，逐漸變大（使接受新解的概率降低，變穩(wěn)定）;后者則是不管新解是好是壞全都接受。為了方便，將前者稱為ALNS-M算法，后者稱為ALNS-R算法。

3 算例設(shè)計與數(shù)值結(jié)果分析

算例中使用的交通網(wǎng)絡(luò)節(jié)點(diǎn)分布如圖1所示，共有30個節(jié)點(diǎn)?？紤]到部分OD對路徑較短的情況，篩選出了296個主要的OD對，并用Dijstra算法求出了每個OD對的最短路徑;每個OD對的流量通過重力模型計算：fq=（wiwj/dij）×1.5，其中wi和wj分別表示OD對起點(diǎn)和終點(diǎn)的權(quán)重。在本算例中權(quán)重由計算機(jī)在區(qū)間[300，600]之間隨機(jī)生成。

自適應(yīng)大鄰域搜索算法中各Destroy和Repair方法的初始權(quán)重都設(shè)為1;四種權(quán)重更新情況所對應(yīng)的權(quán)重值分別設(shè)定為3，2，1，0.5。為了便于性能比較，使用遺傳算法[12]（Genetic Algorithm，GA）求解，參數(shù)設(shè)置如下：交叉概率為0.7、變異概率為0.6、種群規(guī)模為50、迭代次數(shù)為200。三種算法的初始解可以由計算機(jī)隨機(jī)生成。圖2和圖3分別給出了自適應(yīng)大鄰域算法在M接受準(zhǔn)則和R接受準(zhǔn)則下每次迭代的代價函數(shù)值。

在表2中，本算例給出了遺傳算法以及ALNS算法在兩種接受準(zhǔn)則下的最佳選址方案及所獲得的利潤。

從上述結(jié)果來看，兩種不同接受準(zhǔn)則下的自適應(yīng)大鄰域搜索算法的性能都要優(yōu)于遺傳算法，而且M準(zhǔn)則比R準(zhǔn)則更好。主要原因是本算例所設(shè)計的基于最大利潤模型的充換電站選址具有一定的隨機(jī)性，這就使得遺傳算法沒有一個明確的進(jìn)化方向，所以導(dǎo)致算法不能有效地尋優(yōu)。而對于自適應(yīng)大鄰域搜索算法，基于流量最小的Destroy方法和基于流量最大的Repair方法的使用和接受的次數(shù)要遠(yuǎn)多于其他方法，可見基于流量的修補(bǔ)和破壞策略更有助于良好解的產(chǎn)生;而對于M準(zhǔn)則和R準(zhǔn)則而言，前者的優(yōu)化結(jié)果要比后者更好，這就證明了自適應(yīng)大鄰域搜索可以根據(jù)當(dāng)前較優(yōu)解產(chǎn)生更優(yōu)解。

4 結(jié) 語

本文針對高速公路充換電站選址規(guī)劃問題提出了更具實(shí)際意義的最大利潤模型。該模型包含兩個基本問題，即最短路徑問題和電能補(bǔ)給決策優(yōu)化問題。結(jié)合模型特點(diǎn)，本文設(shè)計了基于自適應(yīng)大鄰域搜索算法對模型進(jìn)行啟發(fā)式求解。通過算例驗(yàn)證，表明自適應(yīng)大鄰域搜索算法明顯優(yōu)于遺傳算法。

參考文獻(xiàn)

[1] HAKIMI SL. Optimum locations of switching centers and the absolute centers and medians of a graph [J]. Oper Res，1964，12（3）：450-459.

[2] Constantine Toregas，Charles ReVelle. Optimal location under time or distance constraints [J]. Papers of the Regional Science Association，1972，28（1）：131-143.

[3] Richard Church，Charles ReVelle. The maximal covering location problem [J]. Papers of the Regional Science Association，1974，32（1）：101-118.

[4] M John Hodgson. A Flow-Capturing Location-Allocation Model [J]. Geographical analysis，1990，22（3）：270-279.

[5] Inês Frade，Anabela Ribeiro，Gon?alo Gon?alves，et al. Optimal location of charging stations for electric vehicles in a neighborhood in lisbon portugal [J]. Transp Res Rec，2011（1）：91-98.

[6] Baouche，F(xiàn)ouad，Billot，et al. Efficient Allocation of Electric Vehicles Charging Stations：Optimization Model and Application to a Dense Urban Network [J]. IEEE intelligent transportation systems magazine，2017，6（3）：33-43.

[7] Sung Hoon Chung，Changhyun Kwon. Multi-period planning for electric car charging station locations：a case of korean expressways [J]. Eur J Oper Res，2015，242（2）：677-687.

[8]陸鋒，盧冬梅，崔偉宏. 基于四叉堆優(yōu)先級隊(duì)列及逆鄰接表的改進(jìn)型Dijkstra算法[J]. 中國圖象圖形學(xué)報，1999，4（12）：3-5.

[9]胡大偉，陳希瓊，高揚(yáng). 定位-路徑問題綜述[J]. 交通運(yùn)輸工程學(xué)報，2018，18（1）：111-129.

[10]龐峰.模擬退火算法的原理及算法在優(yōu)化問題上的應(yīng)用[D].長春：吉林大學(xué)，2006.

[11] WANG F，LANDAU DP. Efficient，multiple-range random walk algorithm to calculate the density of states [J]. Phys Rev Lett，2001，86（10）：2050-2053.

[12]高媛. 非支配排序遺傳算法（NSGA）的研究與應(yīng)用[D]. 杭州：浙江大學(xué)，2006.