最小費用充電站選址問題的分支定界算法

摘 要： 電動汽車的充電站選址問題是當前社會的熱點問題，其實質是組合優化中經典的NP-hard問題。基于最小開設費用對充電站選址問題進行研究，首先對該問題進行了數學建模，進而研究了該問題的數學性質并給予相應的證明，利用這些性質減小問題的規模，從而降低問題的求解難度；然后設計了上下界子算法以及降階子算法，基于這些子算法提出了一種可以快速縮小問題規模同時得到最優解的分支定界算法，降低了時間復雜度，同時可以對解空間進行大量剪枝加快求解速度；最后通過分析和求解一個示例來進一步闡述所提算法的原理和執行過程。

關鍵詞： 充電站選址； 精確算法； 上界算法； 下界算法； 分支定界算法

中圖分類號： O223"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-014-0080-04

doi：10.19734/j.issn.1001-3695.2021.07.0248

Branch and bound algorithm for minimum cost charging station location problem

Sun Zhiyong， Ning Aibing， Fu Tangyi， Yin Simiao， Zhang Huizhen

（Business School， University of Shanghai for Science amp; Technology， Shanghai 200093， China）

Abstract： The location problem of electric vehicle charging station is a hot issue in the current society，its essence is the classical NP-hard problem in combinatorial optimization.This paper studied the location of charging station based on the minimum opening cost.Firstly，this paper established the mathematical model of the problem，then studied the mathematical properties of the problem and gave the corresponding proof.It used these properties to reduce the scale of the problem，so as to reduce the difficulty of solving the problem.Then this paper designed the upper and lower bound sub algorithm and the reduced order sub algorithm.Based on these sub algorithms，this paper proposed the branch and bound algorithm which could quickly reduce the size of the problem and obtain the optimal solution，which reduced the time complexity and pruned the solution space to speed up the solution speed.Finally，it gave an example to illustrate the principle and implementation of the algorithm.

Key words： charging station location problem； exact algorithm； upper bound algorithm； lower bound algorithm； branch and bound algorithm

設施選址問題的實際應用非常廣泛，如倉庫選址［1］、基站選址［2］、垃圾站選址［3］、共享單車停放點選址［4，5］、應急設施選址［6～8］以及電動汽車充電站等設施的選址問題。非特殊的設施選址問題是NP-hard問題，除非P=NP，否則不存在多項式時間內的精確算法。當前，隨著能源短缺和環境污染問題日益嚴重，節能環保的電動汽車成為越來越多人的選擇。因此充電站選址問題具有很強的實際應用背景［9，10］，求解該問題有助于幫助決策者進行決策。本文結合集合覆蓋模型對充電站選址問題進行求解，集合覆蓋已被廣泛應用到設施選址［11，12］、人員行程安排［13］、車輛路線安排［14，15］等領域。對于充電站選址問題，大多數學者通過啟發式算法進行求解，例如綜合考慮充電站排隊時間和電動汽車里程約束，以最大化用戶總效用為目標建立競爭環境中的充電站選址模型，并采用免疫優化算法對模型進行求解［16］；考慮充電站運營商、電動汽車用戶以及電網企業綜合利益建立充電站選址定容規劃模型，采用混沌模擬退火粒子群優化算法對問題進行求解［17］；考慮到地理信息、建造成本以及運行成本的文化算法［18］；建立了綜合充電站、電動汽車用戶與配電網多方利益的快速充電站規劃模型，提出考慮充電需求空間分布的改進自適應遺傳算法進行求解［19］。啟發式算法的優點是可以快速得到問題的可行解，但是此類算法所獲得的解的質量不能保證。

本文首先研究了電動汽車充電站選址問題的數學性質，給出上界和下界子算法，并結合降階子算法設計了一個分支定界算法，它與單純的分支定界算法相比通過降階子算法縮小了問題的規模，通過上下界子算法加快了求解的速度。然后對該算法的時間復雜度與特點進行分析，最后通過一個示例驗證該算法可以快速減少節點和分支，加快問題的求解速度，最終得到問題的最優解。

1 充電站選址模型

1.1 問題介紹

目前在政府的各種有力措施之下，電動汽車用戶在快速增長，同時對于充電站的需求也越來越大。假設城市中有n個聚集地和m個可以開設充電站的地點，政府期望在總費用最小的情況下建立一些充電站來滿足所有聚集點的充電需求，即每個聚集點都至少需要被一個充電站服務。

1.2 數學符號及解釋

該問題中的選址模型可用二分圖G =（V，E）表示，模型中所涉及的數學符號如表1所示。算法設計中涉及到的數學符號如表2所示。

1.3 數學模型

目標函數式（1）表示在滿足所有約束條件下，開設充電站的總費用最小；約束式（2）表示新建的充電站總數不大于m個；約束式（3）表示開設的充電站必須能夠服務所有的聚集點；約束式（4）表示設施fi是否開設充電站，xi=1表示在設施fi處開設充電站，xi=0表示在設施fi處不開設充電站；約束式（5）表示聚集點ej是否被服務，yj=1表示被服務，yj= 0表示未被服務。

3 示例分析

為了更清晰地說明算法執行的整個過程，下面給出一個示例進行說明。如圖1所示，現有9個可新建充電站的設施{f1，f2，f3，f4，f5，f6，f7，f8，f9}，每個可開設充電站的設施上方的數字代表該設施點開設充電站的費用wi；12個聚集點{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11，e12}；實線代表聚集點可以由連接的設施點提供服務。現從9個可新建充電站的設施點中選取某些設施點新建充電站，使得可以給所有聚集點提供服務且開設充電站總費用最小。

對示例的計算過程描述如下：

a）調用降階子算法，初始化F1=F0=H1={}，F5={f1，f2，f3，f4，f5，f6，f7，f8，f9}，H5={e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11，e12}。

b）根據性質1，因為deg（e5）=1，所以設施f3必須開設；根據性質2，聚集點e4和e5由設施f3提供服務，更新圖；根據性質3，由于N（f2）N（f1）且w2≥w1，設施f2不開設，根據性質1，設施f1必須開設，更新圖；此時繼續根據性質3，由于N（f4）N（f6）且w4≥w6，設施f4不開設，更新圖；F1=F1∪{f1，f3}，F0=F0∪{f2，f4}，F5=F5＼{f1，f2，f3，f4}，H1=H1∪{e1，e2，e3，e4，e5}，H5=H5＼{e1，e2，e3，e4，e5}。

c）此時降階后的問題轉為圖2，調用上下界子算法，計算上界ub=380，下界lb=295，令W=ub=380。

d）對集合{f5，f6，f7，f8，f9}執行回溯算法，執行過程如圖3的二叉樹所示。

（a）在搜索過程中，從根節點0出發，假設f5開設，進入左子樹，上界ub=380，下界lb=320lt;W；因此假設f6開設，進入左子樹，上界ub=380，下界lb=380=W。下界lb等于當前最優值W，此時左子樹剪枝。

（b）節點1搜索完成，回溯到上一層，假設f6不開設，此時調用降階子算法發現deg（e9）=1，因此設施f7開設；更新圖后deg（e6）=1，從而設施f5開設；更新圖后，根據性質4可知設施f8開設；所有聚集點已被到達節點2服務。此時best_q=385gt;W，右子樹剪枝。

（c）節點2搜索完成，回溯到上一層，假設f5不開設，此時調用降階子算法發現deg（e6）=1，deg（e7）=1，所以設施f6和設施f7開設，所有聚集點已被到達葉子節點3服務。best_q=350lt;W，更新W=350。

通過上述算法得到該問題的最優解集合為Fbest={f1，f3，f6，f7}，最優目標函數值W=350，即建設充電站的最小總費用為350。其中一個可行的方案：花費50建設設施f1服務聚集點{e1，e2，e3}、花費80建設設施f3服務聚集點{e4，e5}、花費100建設設施f6服務聚集點{e6，e8，e9，e10}、花費120建設設施f7服務聚集點{e7，e11，e12}，算法結束。

4 結束語

本文基于最小開設費用對充電站選址問題進行研究，首先得出一些可以減小問題規模的數學性質，其中某些性質可以批量確定某些設施開設或者不開設，使得在預處理的過程當中可以迅速降低問題規模；然后設計出上下界子算法，當在算法中某個階段時問題的最小費用大于其上界，那么可以剪枝；最后在前面的基礎上設計出能快速減小問題規模且能求出開設充電站最小費用的分支定界算法。從示例分析可以看出，采用本文設計的算法來求解時，可以將問題中某些特殊結構在多項式時間內處理完畢，從而減小問題的規模；同時在示例中，待確定的設施點由9個下降到5個，時間復雜度由O（29）下降到O（25），并且本文算法在回溯搜索時，需要搜索的空間較一般精確算法大幅減少，從而進一步提高了算法的求解速度。本文下一步研究將考慮充電站容量對選址的影響以及從充電站整體收益最大化的角度考慮選址問題。

參考文獻：

［1］杜天松，郭海湘，潘雯雯，等.基于多目標演化算法的油田危險品物流系統選址—路徑問題［J］.系統管理學報，2018，27（4）：739-752，768. （Du Tiansong，Guo Haixiang，Pan Wenwen，et al.Location routing problem in oilfield hazardous material logistics based on multi-objective evolutionary algorithm［J］.Journal of Systems amp; Management，2018，27（4）：739-752，768.）

［2］鄭俊杰，王先峰，羅順湖.面向5G移動通信的基站選址方法及優化策略研究［J］.信息通信技術與政策，2017，43（11）：71-74. （Zheng Junjie，Wang Xianfeng，Luo Shunhu.Research on base station location method and optimization strategy for 5G mobile communication［J］.Information and Communications Technology and Policy，2017，43（11）：71-74.）

［3］胡文，范強，史月.基于AHP和GIS的垃圾中轉站選址研究［J］.測繪與空間地理信息，2020，43（8）：102-105，109. （Hu Wen，Fan Qiang，Shi Yue.Research on site selection of garbage transfer station based on AHP and GIS［J］.Geomatics amp; Spatial Information Technology，2020，43（8）：102-105，109.）

［4］劉嘉文，代穎，楊斐，等.共享單車停放點聯合覆蓋選址及車輛配置模型［J］.工業工程與管理，2020，25（1）：127-135. （Liu Jiawen，Dai Ying，Yang Fei，et al.A cooperative covering model for location of bike sharing stations and its fleet deployment［J］.Industrial Engineering and Management，2020，25（1）：127-135.）

［5］鄢章華，劉蕾.考慮服務水平與動態轉移規律的共享單車投放策略研究［J］.中國管理科學.2019，27（9）：195-204. （Yan Zhanghua，Liu Lei.Supply optimization for bicycle sharing system conside-ring service level and dynamic transfer［J］.Chinese Journal of Management Science，2019，27（9）：195-204.）

［6］付德強，陳煜舟，萬曉榆.自然災害風險下區域應急儲備設施選址可靠性研究［J］.運籌與管理，2015，24（3）：14-19. （Fu Deqiang，Chen Yuzhou，Wan Xiaoyu.The study on the reliable model for the regional emergency storage facility under the risk of natural disaster［J］.Operations Research and Management Science，2015，24（3）：14-19.）

［7］孫華麗，項美康，薛耀鋒.不確定信息下應急設施選址—路徑魯棒優化［J］.系統管理學報，2019，28（6）：1126-1133. （Sun Huali，Xiang Meikang，Xue Yaofeng.Robust optimization for emergency location-routing problem with uncertainly［J］.Journal of Systems amp; Management，2019，28（6）：1126-1133.）

［8］項寅.基于雙層規劃的反恐應急設施選址模型及算法［J］.中國管理科學，2019，27（7）：147-157. （Xiang Yin.A bi-level programming model for locating terror response facilities［J］.Chinese Journal of Management Science，2019，27（7）：147-157.）

［9］Alan J.Emissions benefits of electric vehicles in Uber and Lyft ride-hailing services［J］.Nature Energy，2020，5（7）：520-525.

［10］Matteo M.Impact of uncoordinated plug-in electric vehicle charging on residential power demand［J］.Nature Energy，2018，3（3）：193-201.

［11］Wu Qiang，Du Zhili，Zhao Yingwang，et al.Optimal location of water level sensors for monitoring mine water inrush based on the set cove-ring model［J］.Scientific Reports，2021，11（1）：2621.

［12］曹德勝，呂靖，艾云飛，等.基于集合覆蓋的VTS雷達站選址優化模型［J］.北京理工大學學報，2014，34（7）：752-756. （Cao De-sheng，Lyu Jing，Ai Yunfei，et al.Optimization location model of VTS radar stations based on set covering theory［J］.Trans of Beijing Institute of Technology，2014，34（7）：752-756.）

［13］魏金麗，郭亞娟，張萌萌.基于集合覆蓋理論的公交線路駕駛員排班優化方法［J］.公路交通科技，2016，33（1）：125-129. （Wei Jinli，Guo Yajuan，Zhang Mengmeng.A method of optimizing work sche-dule of bus drivers based on set covering theory［J］.Journal of Highway and Transportation Research and Development，2016，33（1）：125-129.）

［14］Leo G B，Richard L C.Location set-covering inspired models for designing harvesting and cable road layouts［J］.European Journal of Forest Research，2018，137（6）：771-792.

［15］李玉民，王新露，郭曉燕.基于集合覆蓋模型的農產品冷鏈網絡布局［J］.中國農業大學學報，2017，22（9）：212-220. （Li Yumin，Wang Xinlu，Guo Xiaoyan.Cold chain network layout of agricultural products based on cluster coverage model［J］.Journal of China Agricultural University，2017，22（9）：212-220.）

［16］邵賽，關偉，畢軍.考慮排隊時間和里程約束的競爭充電站選址問題［J］.交通運輸系統工程與信息，2016，16（6）：169-175. （Shao Sai，Guan Wei，Bi Jun.Charging station location problem with queue and range in competitive multi-site service system［J］.Journal of Transportation Systems Engineering and Information Technology，2016，16（6）：169-175.）

［17］艾欣，李一錚，王坤宇，等.基于混沌模擬退火粒子群優化算法的電動汽車充電站選址與定容［J］.電力自動化設備，2018，38（9）：9-14. （Ai Xin，Li Yizheng，Wang Kunyu，et al.Locating and sizing of electric vehicle charging station based on chaotic simulated annealing particle swarm optimization algorithm［J］.Electric Power Automation Equipment，2018，38（9）：9-14.）

［18］王雨虹，王治國，邱微.基于文化算法的電動汽車充電站規劃［J］.控制工程，2019，26（8）：1585-1591. （Wang Yuhong，Wang Zhiguo，Qiu Wei.Planning of electric vehicle charging station based on culture algorithm［J］.Control Engineering of China，2019，26（8）：1585-1591.）

［19］臧海祥，傅雨婷，陳銘，等.基于改進自適應遺傳算法的EV充電站動態規劃［J］.電力自動化設備，2020，40（1）：163-170. （Zang Haixiang，Fu Yuting，Chen Ming，et al.Dynamic planning of EV charging stations based on improved adaptive genetic algorithm［J］.Electric Power Automation Equipment，2020，40（1）：163-170.）