Siting model of electric taxi charging station based on GPU parallel computing

doi:10.11772/j.issn.1001-9081.2019040762

Abstract

Abstract: Aiming at the problem of optimal siting of charging station for electric taxis, a siting model of charging station for electric taxis was established with the unmet charging demand and the minimum fixed cost of constructing new charging station as objective functions, and a model solution method based on improved multi-objective particle swarm optimization was proposed. In order to solve the performance bottleneck of computing unmet charging demand, a Graphics Processing Unit (GPU)-based unmet charging demand parallel algorithm was designed. Experimental results demonstrat that the running time of the parallel algorithm is about 10%-12% of that of CPU-based serial algorithm. Beijing was taken as an example of applying the proposed charging station siting model, and related multi-source data was collected and processed. The results show that the proposed optimal siting scheme for charging station is feasible.

Key words: electric taxi, charging station siting, multi-objective particle swarm optimization algorithm, Graphics Processing Unit (GPU), multi-source data

摘要： 针对电动出租车充电站优化选址问题，构建了以未满足的电动出租车充电需求量和新建充电站的固定成本最小为目标函数的电动出租车新建充电站选址模型，并提出基于改进的多目标粒子群算法的模型求解方法。为解决未满足充电需求量计算的性能瓶颈问题，设计了一个基于图形处理器（GPU）的未满足充电需求量并行计算算法，并通过实验验证其运行时间约为基于CPU串行算法运行时间的10%~12%。以北京为例，收集、处理相关多源数据，对提出的选址模型进行了应用示例分析，表明所提出的充电站优化选址方案具有可行性。

关键词: 电动出租车, 充电站选址, 多目标粒子群算法, 图形处理器, 多源数据

CLC Number:

TP399

WU Xuchen, PIAO Chunhui, JIANG Xuehong. Siting model of electric taxi charging station based on GPU parallel computing[J]. Journal of Computer Applications, 2019, 39(10): 3071-3078.

武旭晨, 朴春慧, 蒋学红. 基于GPU并行计算的电动出租车新建充电站选址模型[J]. 计算机应用, 2019, 39(10): 3071-3078.

References

[1] 曹小曙, 胡培婷, 刘丹. 电动汽车充电站选址研究进展[J]. 地理科学进展, 2019, 38(1):139-152. (CAO X S, HU P T, LIU D. Progress of research on electric vehicle charging stations[J]. Progress in Geography, 2019, 38(1):139-152.)
[2] TOREGAS C, SWAIN R, REVELLE C, et al. The location of emergency service facilities[J]. Operations Research, 1971, 19(6):1363-1373.
[3] HSU V N, DASKIN M, JONES P C, et al. Tool selection for optimal part production:a Lagrangian relaxation approach[J]. ⅡE Transactions, 1995, 27(4):417-426.
[4] HODGSON M J. A flow-capturing location-allocation model[J]. Geographical Analysis, 1990, 22(3):270-279.
[5] GHOSH A, MACLAFFERTY S L. Location Strategies for Retail and Service Firms[M]. Lanham, MD:Rowman & Littlefield Publishing Group, 1987:28-40.
[6] 张国亮. 城市内和城市间电动汽车充电站的选址布局研究[D]. 天津:天津大学, 2012:23-41. (ZHANG G L. Research on the location problem of electric vehicle charging station intra-city and inter-city[D]. TianJin:Tianjin University, 2012:23-41.)
[7] JIA L, HU Z, LIANG W, et al. A novel approach for urban electric vehicle charging facility planning considering combination of slow and fast charging[C]//Proceedings of the 2014 International Conference on Power System Technology. Piscataway:IEEE, 2014:3354-3360.
[8] 徐智邦, 周亮, 蓝婷, 等. 基于POI数据的巨型城市消防站空间优化——以北京市五环内区域为例[J]. 地理科学进展, 2018, 37(4):535-546. (XU Z B, ZHOU L, LAN T, et al. Spatial optimization of mega-city fire station distribution based on Point of Interest data:a case study within the 5th Ring Road in Beijing[J]. Progress in Geography, 2018, 37(4):535-546.
[9] 褚玉婧, 马良, 张惠珍. 时间满意逐渐覆盖电动汽车充电站选址及算法[J]. 数学的实践与认识, 2015, 45(10):101-106. (CHU Y J, MA L, ZJANG H Z. Location-allocation and its algorithm for gradual covering electric vehicle charging stations[J]. Mathematics in Practice and Theory, 2015, 45(10):101-106.)
[10] 王俊秀. 北京市通州区纯电动出租车充电站布局规划研究[D]. 北京:北京交通大学, 2017:3-4. (WANG J X. Study on the layout planning of pure electric taxi charging station in Tongzhou district of Beijing[D]. Beijing:Beijing Jiaotong University, 2017:3-4.)
[11] 王振伟. 北京市电动出租车充电设施选址优化[D]. 北京:北京交通大学, 2017:19-22. (WANG Z W. Optimization of charging infrastructure siting for electric taxis in Beijing[D]. Beijing:Beijing Jiaotong University, 2017:19-22.)
[12] HODGSON M J. A flow-capturing location-allocation model[J]. Geographical Analysis, 1990, 22(3):270-279.
[13] KUBY M, LINES L, SCHULTZ R, et al. Optimization of hydrogen stations in Florida using the flow-refueling location model[J]. International Journal of Hydrogen Energy, 2009, 34(15):6045-6064.
[14] 陆坚毅, 杨超, 揭婉晨. 考虑绕行特征的电动汽车快速充电站选址问题及自适应遗传算法[J]. 运筹与管理, 2017, 26(1):8-17. (LU J Y, YANG C, JIE W C. An adaptive-self genetic algorithm for solving electric vehicle fast recharging location problem with detour characteristic[J]. Operations Research and Management Science, 2017, 26(1):8-17.)
[15] 卢芳. 基于排队论的电动汽车充电站选址定容研究[D]. 北京:北京交通大学, 2015:18-22. (LU F. The location-sizing problem of electric vehicle charging station deployment based on queuing theory[D]. Beijing:Beijing Jiaotong University, 2015:18-22.)
[16] 北京市质量技术监督局. 电动汽车电能供给与保障技术规范充电站:DB11/Z 728-2010[S]. 北京:中国标准出版社, 2010:3-4.(Beijing municipal administration of quality and technology supervision. Technical specifications of electricity supply and assurance for electric vehicle:electric veicle chaging station:DB11/Z 728-2010[S]. Beijing:Standards Press of China, 2010:3-4.)
[17] 刘自发, 张伟, 王泽黎. 基于量子粒子群优化算法的城市电动汽车充电站优化布局[J]. 中国电机工程学报, 2012, 32(22):39-45. (LIU Z F, ZHANG W, WANG Z L. Optimal planning of charging station for electric vehicle based on quantum PSO algorithm[J]. Proceedings of the CSEE, 2012, 32(22):39-45.)
[18] 舒隽, 唐刚, 韩冰. 电动汽车充电站最优规划的两阶段方法[J]. 电工技术学报, 2017, 32(3):10-17. (SHU J, TANG G, HAN B. Two-stage method for optimal planning of electric vehicle charging station[J]. Transactions of China Electrotechnical Socity, 2017, 32(3):10-17.)
[19] 赵书强, 李志伟. 基于差分进化粒子群算法的城市电动汽车充电站最优规划[J]. 华北电力大学学报(自然科学版), 2015, 42(2):1-7. (ZHAO S Q, LI Z W. Optimal planning of charging station for electric vehicle based on PSODE algorithm[J]. Journal of North China Electric Power University (Natural Science Edition), 2015, 42(2):1-7.)
[20] 熊虎, 向铁元, 祝勇刚, 等. 电动汽车公共充电站布局的最优规划[J]. 电力系统自动化, 2012, 36(23):65-70. (XIONG H, XIANG T Y, ZHU Y G, et al. Electric vehicle public charging stations location optimal planning[J]. Automation of Electric Power Systems, 2012, 36(23):65-70.)
[21] 朱光宇, 徐文婕. 考虑能耗与质量的机床构件生产线多目标柔性作业车间调度方法[J]. 控制与决策, 2019, 34(2):252-260. (ZHU G Y, XU W J. Multi-objective flexible job shop scheduling method for machine tool component production line considering energy consumption and quality[J]. Control and Decision, 2019, 34(2):252-260.)