賈林國(guó) 周小琳 姚博彬 葉珍 武奇生

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

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

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

0 引 言

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

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

1 充換電站選址問(wèn)題

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

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

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

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

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

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

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

每次搜索之后，將采用如下函數(shù)為每個(gè)Destroy方法和Repair方法進(jìn)行評(píng)估：令ψ∈{ω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ù)。

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

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

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

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

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

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

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

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

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

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

自適應(yīng)大鄰域搜索算法中各Destroy和Repair方法的初始權(quán)重都設(shè)為1;四種權(quán)重更新情況所對(duì)應(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ī)隨機(jī)生成。圖2和圖3分別給出了自適應(yīng)大鄰域算法在M接受準(zhǔn)則和R接受準(zhǔn)則下每次迭代的代價(jià)函數(shù)值。

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

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

4 結(jié) 語(yǔ)

本文針對(duì)高速公路充換電站選址規(guī)劃問(wèn)題提出了更具實(shí)際意義的最大利潤(rùn)模型。該模型包含兩個(gè)基本問(wèn)題，即最短路徑問(wèn)題和電能補(bǔ)給決策優(yōu)化問(wèn)題。結(jié)合模型特點(diǎn)，本文設(shè)計(jì)了基于自適應(yīng)大鄰域搜索算法對(duì)模型進(jìn)行啟發(fā)式求解。通過(guò)算例驗(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)先級(jí)隊(duì)列及逆鄰接表的改進(jìn)型Dijkstra算法[J]. 中國(guó)圖象圖形學(xué)報(bào)，1999，4（12）：3-5.

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

[10]龐峰.模擬退火算法的原理及算法在優(yōu)化問(wèn)題上的應(yīng)用[D].長(zhǎng)春：吉林大學(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.