Energy and Power Engineering, 2013, 5, 14041409 doi:10.4236/epe.2013.54B266 Published Online July 2013 (http://www.scirp.org/journal/epe) Optimal Siting of Electric Vehicle Charging Stations Based on Voronoi Diagram and FAHP Method Zheci Tang, Chunlin Guo, Pengxin Hou, Yubo Fan State Key Laboratory of Alternate Electrical Power System with Renewable Energy Sources, North China Electric Power University, Beijing, China Email: tangzheci05@163.com Received March, 2013 ABSTRACT The electric vehicle charging station should be allocated based on traffic density, geographical distribution and other factors, and Voronoi diagram is adopted to set the service area of charging station. In combination with the actu al situa tion of site selection of electric vehicle charging station, the comprehensive benefits index system is established. There are numerous factors influencing the site selection, among which there are uncertainty and fuzziness. The comprehen sive evaluation method based on the fuzzy analysis and Analytical Hierarchy Process (AHP) is used to evaluate the comprehensive benefits in the site selection of electric vehicle charging stations, with the consultation of experts. This paper contributes to the best selection of comprehensive benefits and provides the reference for the decisionmaking of building the electric vehicle charging station. Actual examples show that the method proposed is effective. Keywords: Electric Vehicles; Charging Station; Voronoi Diagram; FuzzyAHP; Optimal Siting 1. Introduction With the growing problem of global fossil energy crisis and environmental degradation, all countries turn their attention to the development and application of new en ergy currently so that exploration and research of large scale electric vehicles has become a hot spot. Meantime, Markets around the world have a greater demand for family cars with economic development and the im provement of people’s income levels, which has certain positive significance in improv ing residents' trav el modes and the development of th e automobile industry, but also has a negative impact on energy security and environ mental protection. Construction of electric vehicle charg ing station is a prerequisite for the popularity of electric vehicles while improving the efficiency of energy supply network is one of the necessary conditions for electric vehicles widely used [1, 2]. 2. Basic Description of the Voronoi Diagram The Voronoi diagram on the plane is the result of each vertex Pi(i = 1, 2, …, n) in the point set P expanding outward at the same speed until they meet each other. These outmost points form open area, each of the re maining points forms a convex polygon. The Voronoi diagram plays an important role in solving a dis tancerelated geometry object problem, and has been widely applied in many areas related to the geometric information [3], especially in geospatial facility location analysis. Suppose that 12 {, ,},3 n PPP Pn is a point set in the Euclidean p lane, these points are different from each other, that is to say ,,, {1,2,, ij n PPijijI n}, (, ) ij dPP represents the Euclidean distance between Pi and Pj Suppose there is a point x on the plane, then area 2 () {(,)(, ii VxEdxpdxp ), j 1, 2,,,}jnj i is called Voronoi polygon, remembered as V(pi). V pol ygon of each point comes together to form V diagram of the closest point. Figure 1 shows V polygon generated by given points P1, P2, …, P9. 3. FuzzyAHP Model The site selection of electric vehicle charging station is a complex multifactor system and its content of the evalu ation is multifaceted. A comprehensive evaluation about the main factors affecting the location and its indicators would be carried out in order to select the optimal pro gram from many other site options. In the current evalua tion methods, the fuzzy comprehensive evaluation *This work is supported by: National High Technology R&D Program of China (863Program) (2012AA050804), Key Project of the National Research Program of China (2011BAG02B14), National High Tech nology R&D Program of China (863 Program) (2011AA05A109). Copyright © 2013 SciRes. EPE
Z. C. TANG ET AL. 1405 method and the Analytic Hierarchy Process are often Figure 1. Voronoi diagram example. used to evaluate the qualitative indicators. The fuzzy comprehensive evaluation method measures fuzzy dif ferences with strict figures languages and utilizes mem bership function to divide its boundaries. But, establish ment of the weight of fuzzy comprehensive evaluation often relies on the judgment of experts’ subjective ex perience inevitably. Analytic Hierarchy Process (AHP) is a combination of qualitative and quantitative, expresses and processes the subjective judgment of persons with number forms, which would not only fully reflect the fuzziness of the evaluation index and the evaluation pro cess, but also eliminate the onesidedness of the subjec tive judgment so that the results of the evaluation could be more objective and credible. Therefore, this paper combines the advantages of these two methods, deter mines the weights of the subtargets and indexes by AHP, evaluates the comprehensive benefits of the site selection of electric vehicle charging station by Fuzzy AHP and provides the reference for the optimal decisionmaking of the site selection [4, 5]. FuzzyAHP is a comprehensive evaluation model that applies AHP and fuzzy comprehensive evaluation to the establishment of comprehensive evaluation model in fuzzy layer, gives play to the advantages of these two methods, takes full account of the various factors affect ing the evaluation system, and combines the qualitative and quantitative analysis[6]. 3.1. Determine the Weights of Each Evaluation Index by AHP Analytic hierarchy process (AHP) was introduced by Professor T. L. Saaty, an American operations researcher, in the 1970. The basic principle of AHP is: Through the analysis of factors and correlation of complicated system, make the problem methodical and hierarchical in order to objectively build a multilevel analysis structure model. Compare the various elements of each level pairwise, by introducing 1~9 ratio scaling method (Table 1) to construct the judgment matrix. Through calculating the biggest eigenvalues and corre sponding eigenvectors of judgment matrix, getting im portance orders of elements of all levels for a certain element, the weight vector is established. Finally, a com prehensive judgment is made. As follows are the main steps. 1) According to Table 1, construct comparison matrix pairwise, i.e., judgment matrix: ()(, 1,2,,) ijn n ij n (1) where 1, 1/ ii ijji . 2) Multiply the elements of each row of the judgment matrix A, and find the nth root of the results respectively, i.e. 1/ 1 () nn iij j W (2) 3) Normalize i W to achieve Wi. 1 /n ii i WW W i (3) 4) Calculate the maximum eigenvalues and their cor responding eigenvectors. 12 (, ,,) n WWW W (4) max 1()/ n i ii WnW (5) 5) Consistency check a) Calculate the consistency index max ()/(CInn 1) (6) b) According to Table 2, find the average random consistency index RI corresponding to CI. Table 1. 1~9 ratio scaling. Criteria scale Definition 1 X and Y are equally important 3 X is a little important than Y 5 X is obviously important than Y 7 X is strongly important than y 9 X is absolutely important than Y 2,4,6,8 Its important degree between the above two adjacent judgment value Table 2. The average random consistency index RI of the judgment matrix. n123 4 5 6 7 8 9 RI 000.580.901.12 1.24 1.32 1.411.45 Copyright © 2013 SciRes. EPE
Z. C. TANG ET AL. 1406 c) Calculate consistency proportion /CRCI RI The judgment matrix A passes the consistency check When CR < 0.1, otherwise, it is required to reconstruct, until the consistency proportion meets the requirements. 3.2. Main Steps of the FuzzyAHP Model 1) The establishment of the factors set of comprehen sive evaluation, , reflects the main indicators of the evaluation object (first grade indexes), which is also affected by the subindicators (secondary indexes). 12 ,,, k UUU U ) 12 ,,, (1,2,,) j iiiin Uuu uik (7) 12 1 k ki i nnn nn (8) 2) Determine the weight distribution set of secondary indexes according to the result of AHP. 12 ,,, (1,2,, i iiiin Wwwwik (9) 3) Determine the weight distribution set of first grade indexes according to the result of AHP. 12 ,,, k AA A (10) 4) In combination with the actual situation of site se lection of electric vehicle charging station, select the evaluation set to form a judgment collection 12 ,,, n VVVV. In this model, n = 4, the judgment collection is 12 ,,, n VVVV = {better, good, general, poor} 5) Evaluate secondary indexes by several experts’ voting to reach evaluation matrix Ri. 11 121314 21 222324 1234 ii ii i nn nn rrrr rrrr R rrrr (11) 6) Figure out the total evaluation matrix B. a) Calculate the evaluation vector Bi of every first grade index Ui. (1,2,,) iii BWRi k (12) b) The total evaluation matrix B is 12 (, ,, ) T k BBB B (13) 7) Obtain the total objective evaluation vector C. CAB (14) 8) Figure out the comprehensive benefits of site selec tion of electric vehicle charging station after the total objective evaluation vector C is ready, which depends on maximum memb ership d egree l aw. 4. Example of the Optimal Decision of the Site Selection of Electric Vehicle Charging Station 4.1. Use the Voronoi Diagram to Differentiate Areas Assuming a city as the planning area of electric vehicle charging station network, According to the city's traffic density distribution and regional distribution, several center points are selected. The Voronoi diagram is used to differentiate areas, in which a charging station is build, to finish the earlier work for charging station location. The center point is not necessarily the optimal charging station location. The optimal siting of charging station is optimized by using the FuzzyAHP model [7, 8]. 4.2. Establishment of Evaluation Index System for Electric Vehicle Charging Station Location Reviewing the related literature material and the princi ple of comprehensive evaluation index system, the com prehensive evaluation index system is established for electric vehicle charging station location, in considera tion of traffic factors, economic factors, and social fac tors and influencing factors. Lane crossing number, road conditions and main roads are considered in the area of transportation; Total cost of construction investment, operation and maintenance, and cost of wear and tear are considered in. economic aspects. Social aspects include local government’s opinions, construction conditions, technical conditions and resource distribution. Effects include environmental impact, power grid safety and people life, and so forth. An evaluation index system for electric vehicle charging station location is shown in Figure 2. Figure 2. Comprehensive evaluation index system of the site selection of thermal power plant. Copyright © 2013 SciRes. EPE
Z. C. TANG ET AL. 1407 4.3. Determine the Weights of Each Evaluation Index by AHP 4.3.1. Establish Index Sets Four first grade indexes and thirteen secondary indexes in Figure 2 are established to evaluate the comprehen sive benefits of the site selection of electric vehicle charging station. Then, comprehensive evaluation index set U includes four first grade indexes, i.e. 12 3 4 ,,,UUUUU 1234 ,,,UUUU . The first grade indexes set is , and thirteen secondary indexes are 111 12132212223 331 3233 344414243 ,, ,,,, ,,, ,,, UuuuUuuu UuuuuUuuu . 4.3.2. Determine the Weights of Each Evaluation Index Reviewing a large number of the existing date, in con sideration of the actual situation of electric vehicle charging station location, each level of judgment matrix based on Table 1 is established in order to calculate the weight of each index and have a consistency check [9]. Traffic factors are taken for example. 1) Construct judgment matrix of 1111213 ,,Uuuu U1 u11 u12 u13 u11 1 1/3 1/5 u12 3 1 1/4 u13 5 4 1 2) Multiply the elements of each row of the judgment matrix, and find the 3th root of the results respectively. So, 11 1213 0.41, 0.91, 2.71.WWW 3) Normalize 1i W to achieve 1(1,2,,5) i Wi 11 12 13 0.10, 0.23,0.67WWW 4) Calculate the maximum eigenvalues and their cor responding eigenvectors. i.e. 1 max 1 (0.10,0.23,0.67) () /=3.0863 n ii i W AW nW 5) Consistency check a) Calculate the consistency index max () / (1)0.0432CIn n b) According Table 2, RI=0.58, CR=CI/RI=0.074<0.1, the assignment of the judgment matrix constructed is reasonable. Similarly, the judgment matrixes about 221 2223331 323334 4414243 1234 ,, ,,,, ,, ,,,, UuuuUuuuu UuuuUUUUU , as follows: u22 u23 U3 u31 u32 u33 u34 U2 u21 u21 1 5 5 u31 1 1/4 1/41/2 u22 1/51 1/2 u32 4 1 1 3 u23 1/52 1 u33 4 1 1 4 u34 2 1/3 1/41 U4 u41 u42 u43 U U1 U2 U3 U4 u41 1 1/5 1/3 U1 1 1/3 1/21/3 u42 5 1 4 U2 3 1 1/21/4 u43 3 1/4 1 U3 2 2 1 1/2 U 4 3 4 2 1 Finally, the result is: 4.4. Construct a Fuzzy Evaluation Matrix esult is esult in Table 3, by calculating the m 2(0.7W 3 4 1,0.11,0.18) (0.08,0.38,0.41,0.13) (0.10,0.67,0.23) (0.11,0.17,0.25,0.47) W W A Evaluate each index by ten experts’ voting, the r shown in Table 3. According the r embership degree of each index corresponding evalua tion sets, the fuzzy evaluation matrix are: 0.2 0.4 0.400.3 0.4 12 34 0.2 0.1 0.10.6 0.2 0.10.3 0.30.2 0.2 0.4 0.4 0.200.4 0.20.30.1 0.3 0.50.1 0.10.10.3 0.4 0.2 0.2 0.50.2 0.10.40.40.10.1 0.4 0.3 0.300.2 0.3 0.3 0.2 0.1 0.4 0.3 0.2 RR RR 1(0.10,0.23,0 .67)W The weight set is established by AHP, further, comn vector about traffic is prehensive evaluatio 111 (0.31,0.45,0.22,0.02)BWR 2(0.71,0.11,0.18)W , cSimilarly, accordingompre hensive evaluation vecto 222 (0.32,0.35,0.22,0.11BWR r about traffic is ) 3(0.08,0.38,0.41,0.13),W According comehensive ev pr aluation vec 333 (0.28,0.4BWR tor about traffic is 1,0.25,0.07) 4(0.10,0.67,0.23),W According comprehensive evalua tion vector ab 444 (0BWR out traffic is .32,0.37,0.18,0.13) The general goal of the evaluation matrix is obtained from the B1, B2, B3 and B4.i.e. Copyright © 2013 SciRes. EPE
Z. C. TANG ET AL. Copyright © 2013 SciRes. EPE 1408 s of experts’ voting to the index of the site selection of charging stations. Table 3. Result evaluation grade First grade indexes Secondary indexes weight better poor good general Transportation Lan e crossing numbers u11 0.10 2 4 4 0 U10.11 Road conditions u12 0.23 1 6 2 1 Main roads u13 0.67 4 4 2 0 Economy struction investment u21 Society ns u31 Ef ct Total cost of con0.71 3 4 2 1 U20.17 Cost of operation and maintenance u22 0.11 3 3 2 2 Cost of wear and tear u23 0.18 4 2 3 1 Local government’s opinio0.08 3 5 1 1 U30.25 Construction conditions u32 0.38 2 5 2 1 Technical conditions u33 0.41 4 3 3 0 Resource distribution u34 0.13 1 4 3 2 feEnvironmental impact u41 0.10 1 3 4 2 U40.47 Power grid safety u42 0.67 4 4 1 1 People life u43 0.23 2 3 3 2 4.5. The Comprehensive Benefit Evaluation of The eight se ng st 5. Conclusions iagram is used to divide the zone, in w combining AHP and fuzzy com pr fore, the evaluation results are more objective and credi REFERENCES [1] F. Xu, G. Q. ntative analysis of layout of electtions,” East China a nsive Evaluation for Power Plant ower Plant,” Power System Technol nmaking System,” harging Stations making of the Site Selection of rithm,” Auto 12 34 0.31 0.45 0.22 0.02 0.32 0.35 0.220.11 (,, ,)0.280.41 0.25 0.07 0.320.37 0.18 0.13 T BBBBB Electric Vehicle Charging Stations Location general goal of the evaluation vector about electric Ele vehicle charging stations location, i.e. CAB= (0.31, 0.39, 0.21, 0.10) is the result of the wt of first grade evaluation indexes calculated by AHP [10, 11]. The comprehensive benefit of electric vehicle chargi tio ation location is better and the site is reasonable, which is based on the maximum membership degree law [12]. 1) The Voronoi d hich a charging station is build, to finish the earlier work for charging station location. The center point is not necessarily the optimal charging station location. The optimal siting of charging station is optimized by using the FuzzyAHP model. 2) The FAHP model ehensive evaluation, takes the advantages of the two approaches at the same time. Considering various factors of electric vehicle charging station location, the organic combination of the qualitative and quantitative analysis not only adequately reflect the fuzziness of evaluation index and evaluation process, but also try to eliminate onesidedness of individual subjective judgment. There ble. Yu, L. F. Gu, et al. Te rical vehicle charging sta ctric Power, Vol. 37, No. 10, 2007, pp. 1678 1682. [2] F. Q. Zhou, Z. W. Lian, X. L. Wang, et al., “Discussion on Operation Mode to the Electric Vehicle Charging St n,” Power System Protection and Control, Vol. 38, No. 21, 2010, pp. 6367. [3] J. H. Chen, D. Sheng, W. Li, et al., “A Model of Multi Objective Comprehe Projects,” Proceedings of the CSEE, Vol. 22, No. 12, 2002, pp. 152155. [4] D. X. Niu, “The Gray Layer Analysis Method for Optimal siting of Thermal P ogy, 1994, Vol. 18, No. 6, pp. 2731. [5] Y. F. Zhao, J. F. Chen, W. L. Guo, “The Analytic Process and its Application in Power Decisio Relay, Vol. 33, No. 3, 2005, pp. 8388. [6] J. G. Kang, Z. L. Wei, D. M. Cheng, et al., “Research on Electric Vehicle Charging Mode and C Construction,” Power Demand Side Management, Vol. 11, No. 5, 2009, pp. 6466. [7] C. Zhu, X. Ma and H. Gong, “Application of FuzzyAHP Model to the Decision Thermal Power Plant,” Safety and Environmental Engi neering, Vol. 17, No. 1, 2010, pp. 8286. [8] D. S. Wang, T. Liu and Y. H. Xie, “Substation Locating and Sizing Based on Hybrid Genetic Algo mation of Electric Power Systems, 30, No. 6, 2006, pp. 3034.
Z. C. TANG ET AL. 1409 [9] J. X. Yao, M. Wang and W. M. Luo, “Construction and Application of Charging Systems for Electric Mobiles,” ocation of Country's Transformer Substation y Process in Buried Rebuilding of Ur tilities: An Analytic Hierarchy Approach,” ban E East China Electric Power, Vol. 36, No. 8, 2008, pp. 107110． [10] J. J. Xu, S. Y. Yang and J. Yuan, “A New Method of Selecting L Proc Based on FuzzyAHP,” Electrical Engineering, Vol. 1, 2009, pp. 6569. [11] Z. Dong, M. G. Han, C. Q. Xu, et al., “Application of the Analytic Hierarch lectrical Network,” Relay, 2006, Vol. 34, No. 22, pp. 6468. [12] R. R. Clarke, “Choosing an Integrated Resource Plan for Electric U eedings of the Intersociety Energy Conversion Engi neering Conference, Washington, USA: IEEE, 1996, pp. 15921597. Copyright © 2013 SciRes. EPE
