電動汽車的充電站選址問題是當(dāng)前社會的熱點問題,其實質(zhì)是組合優(yōu)化中經(jīng)典的NP-難問題.文章首先研究了該問題良好的數(shù)學(xué)性質(zhì)并給予相應(yīng)的證明,其中包括可以批量確定某些設(shè)施一定開設(shè)或一定不開設(shè)的性質(zhì),利用這些性質(zhì)降低問題的規(guī)模,從而降低問題的求解難度;然后設(shè)計了上界子算法,下界子算法,分配子算法以及降階子算法,基于這些子算法提出了一種可以快速縮小問題規(guī)模同時得到最優(yōu)解的降階回溯算法;最后通過分析和求解一個示例來進一步闡述文章算法的原理和執(zhí)行過程,結(jié)果表明所提出的算法能夠有效地降低時間復(fù)雜度. 

【文章來源】：系統(tǒng)科學(xué)與數(shù)學(xué). 2020年07期 北大核心

【文章頁數(shù)】：13 頁

【部分圖文】：

圖１分配圖??（Ｆｉｇｕｒｅ?１?Ｄｉｓｔｒｉｂｕｔｉｏｎ?ｄｉａｇｒａｍ）??

１１４０??系統(tǒng)科學(xué)與數(shù)學(xué)??４０卷??和／７，?％和／７，?和／９，?和／９，同時這些邊的流量限制為流入相應(yīng)虛擬設(shè)施點的流量，按??順序分別為２５，?２０，?３０，?２０，?３０，?３０，?４０，?２５；最終得到圖２；??圖２最大流分配圖??（Ｆｉｇｕｒｅ?２?Ｍａｘｉｍｕｍ?ｆｌｏｗ?ｄｉｓｔｒｉｂｕｔｉｏｎ?ｄｉａｇｒａｍ）??３）然后按照最大流：算法進行求解，計算得到從超級源點》到超級ｒ點，《的最大流黧為??２００；??４降階回溯算法??降階回溯算法包括降階乎算法和回溯算法兩個部分．降階乎算法主要通過前面研究的??一些．?dāng)?shù)學(xué)性質(zhì)判斷哪些設(shè)施點一定要選取或者一定不選取，從而減少設(shè)施點的個數(shù)進而減??�。皖}的規(guī)模．回溯算法采用深度優(yōu)先的搜索方式搜索解空間．從根節(jié)點開始對每個未確定??的設(shè)施點進行判斷，計每種情況下目標(biāo)函數(shù)的上界，如果計算得到的目標(biāo)函數(shù)上界比之前??得到的下界還要小，那么進行剪枝，逐級向上回溯．??４．１降階子算法??降階子算法的具體步驟如下??步驟１初始化朽＝孫＝｛｝，丹＝Ｆ＝｛／＃＝１，筆．．．，ｍ?＋??步驟２對每個ｃｉ＾（／ｓ）＝ｌ進行判斷，如果滿足性質(zhì)１，則Ｊ｜＝場參拽＼仏｝；??步驟３?計黎集合踔中所有設(shè)施點的皋少服務(wù)人數(shù)和皋多服務(wù)人數(shù)，對集合＇??馬中每個設(shè)施／ｆｃ分別進行判斷，如果有設(shè)施九滿足性質(zhì)５則蚵＝朽ｕ｛／ｆｃ｝５丹＝馬??如果有設(shè)施Ａ滿足性質(zhì)７，則押＝＾＾｛九｝，拆＝拽＼｛／６｝，?ＫＦｗ＝｛／ｆｃ｝；判斷??中是否有元素，如果有，則跳入步驟２；??步驟４如果有設(shè)施／ｆｃ滿足性質(zhì)８則與＝讒＼仏｝，朽＾＝｛九｝；如果有設(shè)??施／ｆｃ滿足性質(zhì)９，則蚵＝＾＾｛／仏耗＝馬＼｛／

＝??７５??ｍｉｎ＿／２?＝?０??ｍａｘ＿／２?＝??７０??ｍｉｎ＿／３?＝?０??ｍａｘ＿／３?＝??５０??ｍｉｎ＿／７?＝?０??ｍａｘ＿／７?＝??８０??ｍｉｎ．／ｓ?＝?０??ｍａｘ．／ｓ?＝??４０??ｍｉｎ．／ｇ?＝?２５??ｍａｘ＿／ｇ?＝??６５??６）計算得到此時的上界《＝３那和下界６＝３６０，根據(jù)性脫８和性質(zhì)ａ，對每一個設(shè)施九進??行判斷，得到如果開設(shè)段施為，則上界《＝３５５�。嫦陆纾�，因此設(shè)施／ｓ不開設(shè)，馬＝鄭Ｊ｛／ｓ｝，??馬１韓＼｛／８｝，得到圖４；??１２０?丨?００?４０?８０??圖例：〇）居民點?ｎ工作點??（虛線框代表不開設(shè)）??圖４居民點與工作點二分圖??（Ｆｉｇｕｒｅ?４?Ｂｉｐａｒｔｉｔｅ?ｇｒａｐｈ?ｏｆ?ｒｅｓｉｄｅｎｔｉａｌ?ａｒｅａ?ａｎｄ?ｗｏｒｋｉｎｇ?ａｒｅａ）??

【參考文獻】：
期刊論文
[1]基于文化算法的電動汽車充電站規(guī)劃[J]. 王雨虹,王治國,邱微.  控制工程. 2019(08)
[2]基于Petri網(wǎng)的最大流-最小割問題建模與求解[J]. 劉石堅,鄒崢,樂曉波.  福建工程學(xué)院學(xué)報. 2018(01)
[3]動態(tài)網(wǎng)絡(luò)中最大流快速增量求解[J]. 張柏禮,王媛瑗,洪亮,田偉,呂建華.  東南大學(xué)學(xué)報(自然科學(xué)版). 2017(03)
[4]基于螢火蟲算法的電動汽車充電站優(yōu)化布局[J]. 邱金鵬,牛東曉,朱國棟.  華北電力大學(xué)學(xué)報(自然科學(xué)版). 2016(05)
[5]電動汽車充電站選址問題研究[J]. 周文峰,李珍萍,崔曉潔,馮卉妍.  數(shù)學(xué)的實踐與認(rèn)識. 2016(11)
[6]基于遺傳算法的快慢充充電站綜合布局優(yōu)化研究[J]. 韓煜東,郭錦錦.  數(shù)學(xué)的實踐與認(rèn)識. 2016(03)
[7]基于差分進化粒子群算法的城市電動汽車充電站最優(yōu)規(guī)劃[J]. 趙書強,李志偉.  華北電力大學(xué)學(xué)報(自然科學(xué)版). 2015(02)
[8]基于量子粒子群優(yōu)化算法的城市電動汽車充電站優(yōu)化布局[J]. 劉自發(fā),張偉,王澤黎.  中國電機工程學(xué)報. 2012(22)



本文編號：2955588