As part of the overall goal of carbon emissions reduction, European cities are expected to encourage the electrification of urban transport. In order to prepare themselves to welcome the increased number of electric vehicles circulating in the city networks in the near future, they are expected to deploy networks of public electric vehicle chargers. The Electric Vehicle Charging Infrastructure Location Problem is an optimization problem that can be approached by linear programming, multi-objective optimization and genetic algorithms.
Methods
In the present paper, a genetic algorithm approach is presented. Since data from electric vehicles usage are still scarce, origin - destination data of conventional vehicles are used and the necessary assumptions to predict electric vehicles’ penetration in the years to come are made. The algorithm and a user-friendly tool have been developed in R and tested for the city of Thessaloniki.
Results
The results indicate that 15 stations would be required to cover 80% of the estimated electric vehicles charging demand in 2020 in the city of Thessaloniki and their optimal locations to install them are identified.
Conclusions
The tool that has been developed based on the genetic algorithm, is open source and freely available to interested users. The approach can be used to allocate charging stations at high-level, i.e. to zones, and the authors encourage its use by local authorities of other cities too, in Greece and worldwide, in order to deploy a plan for installing adequate charging infrastructure to cover future electric vehicles charging demand and reduce the electric vehicle “driver anxiety” (i.e. the driver’s concern of running out of battery) encouraging the widespread adoption of electromobility.
Notes
This article is part of Topical Collection on Smart cities and transport infrastructures
1 Introduction
1.1 General
Considering the importance of reducing Europe’s dependence on imported oil and carbon dioxide emissions from road transport by 60% until 2020, the White Paper on Transport in 2011 [1] has set the target for the reduction of conventionally fuelled vehicles in cities. Cities are expected to establish an aggressive strategy in order to reduce transport emissions and enhance the urban environment; and among others they need to become more sustainable by turning urban vehicle fleet to more environmentally friendly.
In the recent years, car manufacturers have developed and produced a new generation of alternatively fuelled vehicles, advantageous compared to conventional cars in many aspects: lower dependence in oil, reduced greenhouse gas emissions (GHG) and generally significant reduction in air pollution. Among the most promising of these technologies are those that fully rely on electricity. Currently, more than thirty models of electric vehicles are manufactured while the amount of money invested for the support of design, construction and promotion of electric vehicles (EVs) is continuously increasing.
Advertisement
It is highly expected that the EVs will be able to provide, in time, a viable alternative to conventional vehicles that use fossil fuels. Although electric vehicles are currently more expensive to purchase, they offer users the possibility to save significant amounts of money by reducing the maintenance and operational costs. However, in order to encourage the spread of EVs in urban road transport and decrease the transition time from conventional to EVs, it is essential to eliminate obstacles and encourage policies and actions that promote the wide use of non-conventional vehicles. As part of this goal, cities have to prepare themselves to welcome this impending shift in transport, where EVs have a key role. The current study is focused on this preparation of the cities.
1.2 Electric vehicles (EVs) and charging facilities locations
EVs are vehicles of very low pollutants, since they do not directly emit gases from the combustion of a fuel, and are more efficient and economical than conventionally fuelled vehicles. Even though, GHGs are produced for EVs construction and operation, during the production of the necessary electricity, EVs are much friendlier to the environment and their carbon footprint is at least 40% of conventional vehicles.
However, EVs require electricity, store energy in internal batteries and need recharging by plugging in a charger. Battery range, which often does not allow covering very long distances (usually up to 100–200 km), and the time required for recharging (20 min to 8 h) are their major disadvantages. Charging time of an EV depends on the characteristics of the vehicle as well as the technology and type of the charging system. Chargers can be installed in houses, workplaces, private facilities and public areas. Installation of chargers in public spaces is considered to be crucial for the success of the electromobility system, as it minimizes the “user anxiety” (i.e. the concern of the driver about the exhaustion of the battery while being away from his house or the workplace).
1.3 Objective and paper structure
The objective of this study is to analyse the data and components associated with deployment of EV charging infrastructure and to propose a methodology for EV charging facility location based on a Genetic Algorithm using Origin Destination (OD) data. The study is focused on EVs for which the charging infrastructure is essential; however, the proposed methodology and tool could be used for any type of plug-in vehicles (e.g. plug-in-hybrid vehicles). The study is followed by a case study in Thessaloniki, Greece. The remaining of the paper is structured as follows: following the first introductory part, the research literature is reviewed. The suggested solution for EV charging facility location is then presented through a case study application and the paper ends with the conclusions.
Advertisement
2 Literature review
The deployment of facilities in general is an issue of critical importance for a wide range of private and public actions. The problem of optimal facility location is met at parking spaces planning, installation of fire stations or siting of emergency stations in a city. Moreover, constant changes in the population size, market trends, environmental factors and other elements crate the need for relocation, extension and adaptation of facilities in order to ensure that they meet the needs at all times.
In the area of electromobility as well, there is research interest related to the EVs charging facilities location problem, and a number of optimization processes have been proposed and developed. Optimization algorithms that are used to address the EV infrastructure location problem are usually based on maximization of the covered demand or minimization of the travel costs. Frade et al. [2] developed a maximal covering model for the optimal allocation of EV chargers in Lisbon. The day charging demand was derived by the number of jobs and the night charging demand by the number of households per geographical unit, as opposed to our approach where OD data was used. Sweda and Klabjan [3] developed an agent-based decision support system (DSS) to assist EVs infrastructure positioning. Hanabusa and Horiguchi [4] developed a two-step model based on traffic assignment with stochastic user equilibrium and entropy maximization. In our study, we ignore the traffic assignment and focus on the demand at the Origin and Destination. Wang et al. [5] proposed a multi-objective planning model based on the demand of gas stations. Efthymiou et al. [6] used multi-criteria optimization taking into account spatial attributes. The proposed approach does not necessarily cover the near-maximum demand, but is based on an open, scoring model. Feng et al. [7] proposed a model for the allocation of stations on the trunk road. Worley et al. [8] developed an integer-programming model for the simultaneous solution of the vehicle routing and charging station problem, with the objective to minimize the total cost (travel, recharging and implementation).
Using parking demand as a proxy for EVs charging demand, Chen et al. [9] developed a mixed integer-programming algorithm with the objective to minimize travel cost. He et al. [10] used an active-set algorithm for the optimal deployment of charging stations for plug-in hybrid vehicles, with the objective of maximizing of the social welfare. They recommend that public charging locations and electricity prices should be taken into account at the planning phase. Xi et al. [11] found that while location depends on the optimization criteria, the service levels are not. Sathaye and Kelley [12] explored a way to locate stations on highway corridors. They developed a continuous algorithm that minimizes the deviation of the vehicles from the expected trips. In our approach, we assume that the chargers can only be deployed in nodes (OD). Xu et al. [13] employed the particle swarm optimization (PSO) algorithm to develop a framework for optimal charging stations configuration, with the objective of minimizing total transportation distance.
Baouche et al. [14] used OD data to develop an integer linear programming algorithm mixed with a dynamic consumption demand model, for the City of Lyon. The proposed model aims at minimizing the fixed charge charging station and the vehicle travel cost. The authors computed a minimum time distance between the demand clusters of the area, and enriched the data with information about the consumption. They found that semi-fast chargers should be installed at public parking spaces, and fast at petrol stations. Ghamami et al. [15] modelled the optimal number of chargers and the locations they should be installed in existing parking lots. Sun et al. [16] investigated the impact of the remaining battery life, and therefore the driver’s behaviour, on the way they charge their EVs, using stochastic frontier analysis. Location-routing problem (LRP) is the optimization problem where the facility location and vehicle routing are solved simultaneously. The decision of location and routing differ, since they are strategic and tactical respectively. The electric charger facility location problem is modelled as LRM in a number of studies (Nagi and Salhi, 2007). For computational reasons (i.e. GE is already computationally demanding), in our study we focus on the location problem and assume routing as static.
Chen et al. [17] investigated the impact of charging locations on the network performance. By incorporating charging requirements in a distance constrained equilibrium model, they evaluated alternative charging locations. Lee et al. [18] developed a bi-level optimization framework with the objective of minimizing fail distance and total network travel time. The model uses a probabilistic distribution function of the remaining fuel range. Jung et al. [19] employed a bi-level stochastic queuing model to locate charging stations for electric taxis. Long et al. [20] proposed a graph theoretic model based on demand and supply, that minimizes the total cost (investment and operation).
Jarmillo et al. [21] published an exhaustive research about genetic algorithm applications to solve facility location problems. They examined all the capacitated/un-capacitated fixed charge, maximum covering, p-median and centroid problems. They found that GAs require more time to generate a solution than other optimization algorithms, without this being a limitation for strategic decisions such are the facility location problems; moreover, the results are in many cases superior (except in the fixed charge location problem). For the same reason, we have decided to develop a GA for the purposes of the current study, as presented below. The applicability of GAs to the electric vehicle charging facility location problem has been explored in a number of research papers. Ge et al. [22] proposed a methodology for electric vehicle charging locations, based on grid partitioning and genetic algorithm. Li et al. [23] employed genetic algorithm for facility location to minimize the total costs. Dong et al. [24] proposed a genetic algorithmic framework to minimize “range anxiety”, defined as the total number of missed trips in the network, employing GPS data from conventional vehicles and a household travel choice survey.
Our objective was to develop a framework that would be very easily applicable and in contrast to the above mentioned approaches would be based, since data from electric vehicles usage are limited, on easily accessible OD data. The current paper continuous the research of Efthymiou et al. [25], who investigated the Electric Vehicle Charging Infrastructure Location Problem using OD data of conventional vehicles for Thessaloniki. The authors used the open-source FLP spreadsheet solver [26] developed by the VeRoLog working group of EURO (Association of European Operational Research Societies). They employed a maximum coverage algorithm and performed a sensitivity analysis to find the optimal number of stations required to cover the needs of Thessaloniki. They found that the covered demand increases by 4.4% on average for every extra station used, while 80% of the demand can be covered by 15 stations.
3 EV penetration in Greece
The rate of EVs penetration in Greece is low due to the following factors [27]: 1) the purchase price of an EV is higher than the price of a conventional; 2) the vehicle purchase potential of Greeks depends on imported vehicles; 3) there are no EVs of the most popular vehicle type categories of the market (economy and compact cars) available in the Greek market; 4) there are not EVs charging facilities in the Greek territory; 5) the consumers postpone the purchase of a new vehicle due to the uncertain economic situation; 6) the consumers are reluctant to buy an EV considering that the technologies are still immature.
Nowadays, there are very few EVs in the Greek streets, mainly for research or experimental purposes, while the legal framework about the electrification is under development. Based on the data of the National Statistical Service of Greece [28], Table 1 shows the increase of the number of current passenger cars during the last decade in Greece. It appears that the upward trend in the number of circulating vehicles that prevailed in recent years, seems to be tempered in the years of the economic recession and is estimated that in the forthcoming years will be stabilized at these levels. Table 1 also shows the passenger car sales in Greece over the last ten years. The table shows that the number of new vehicles has reduced.
Table 1
Number of passenger cars in Greece (2004–2016)
Year
Total passenger cars
Passenger cars that were bought between from 2004 to 2016
Total
New
2nd hand
Total
2004
4.093.951
281.841
28.597
310.438
2005
4.269.569
267.683
33.440
301.123
2006
4.509.456
265.892
36.862
302.754
2007
4.764.970
278.022
37.745
315.767
2008
4.990.384
265.251
28.517
293.768
2009
5.098.400
218.776
23.795
242.571
2010
5.181.313
139.514
12.790
152.304
2011
5.170.031
96.916
10.037
106.953
2012
5.133.997
57.817
5.911
63.728
2013
5.090.648
58.165
6.064
64.229
2014
5.077313
70.188
13.432
83.620
2015
5.074.060
74.985
20.200
95.185
2016
5.126.496
78.332
27.082
105.414
The Hellenic Ministry of Environment, Energy and Climate Change [29] has estimated that the penetration of EVs by 2020 will be between 2 and 7% depending on the scenario (optimistic or realistic). The examined scenarios are largely dependent on the political support for the penetration of clean vehicles. Considering a conservative prediction that 5,2 million cars will be circulating in Greece in 2020 and based on the penetration forecast of the Ministry -that by now, with the economic crisis still enduring, seems too optimistic- in 2020 there will be between 104.000 and 364.000 electric passenger cars in Greece.
4 Methodology
4.1 Study area
Thessaloniki is the second largest city in Greece, with a population of 322.240, while in the Metropolitan area lives approximately 1.1 million of people. About 1.300.000 trips are performed on a daily basis, 51% of which is made by private cars, 39% by public transport and the rest by bicycle and on foot. The only public transport mode in Thessaloniki is a service run by buses, while a metro network is under construction. The road network consists of 2.200 km of streets, while there is a bicycle network of 12 km and a bike-sharing system.
The municipality of Thessaloniki is the economic, cultural and administrative centre of the region of Central Macedonia. It attracts visitors from the surrounding areas and neighbouring countries. The increased traffic congestion, energy consumption and air pollution generated by the private transport over the past years, has activated the authorities to recognize the importance of promoting sustainable transport. Therefore, a Sustainable Urban Mobility Plan (SUMP), an adaptive traffic management and control system, that supports the reduction of fuel consumption and information services provided to travellers to promote low energy route choices and sustainable transport modes, have been initiated. In the context of transforming Thessaloniki into a sustainable city, local authorities aim to foster electromobility in the city, giving financial incentives and providing public charging options.
The current research addresses the location of fast charging infrastructure in the Municipality of Thessaloniki (Fig. 1), which concentrates the majority of daily trips in the Metropolitan Area.
Fig. 1
Municipality of Thessaloniki (orange colored area)
×
4.2 Data
In order to estimate the future demand for EVs charging in the Municipality of Thessaloniki, traffic data from the most recent trip Origin – Destination study (2011) and the traffic simulation model of the city were used. Both data and model were collected and developed by the Hellenic Institute of Transport (HIT) of the Center for Research and Technology Hellas (CERTH) within the framework of the project “Thessaloniki’s Intelligent Urban Mobility Management System”. The OD matrix for the city is based on data collected by a wide phone survey addressed to 5.000 residents of Thessaloniki wider area whose daily trips were recorded. Trip generation models were developed based on the results of this survey. Then, attractors and generators were allocated using a gravity model, creating the initial OD matrix for the area. In order to estimate the final matrix, real OD data were used for calibration purposes. 24 hourly OD matrixes have been created for a typical day, totalling in 889.000 vehicles.
The Metropolitan area of Thessaloniki is divided in 339 traffic zones, 124 of which belong to the Municipality of Thessaloniki. Due to the economic crisis that Greece is facing since late 2009, it is considered that in the design year 2020, the number of passenger vehicles in Thessaloniki will be at the 2010 levels. Similarly, the number and allocation of the trips to the traffic zones will be the same. Based on the above, the total number of passenger vehicles with destination to one of the 124 traffic zones of the Municipality, but also the average travel distance between the zones were computed. Based on the Hellenic Ministry of Environment, Energy and Climate Change [29] report the penetration rate of EVs will be 2–7%. Choosing an intermediate scenario, we assume that 5% of the passenger cars will be electric in 2020. The penetration of electric vehicles is assumed to be uniform across all areas of Thessaloniki. Moreover, it is assumed that the use of EVs will not affect the behaviour of commuters and thus their trips. However, not all EVs will require charging when they arrive at a destination zone.
For the purpose of this research, we assume that the EVs with destination to one of the 124 zones of the Municipality of Thessaloniki will need to get charged if they have travelled more than a certain number of km from their origin, and thus have consumed most of their stored energy. In the present context being uncertain of whether drivers will unplug their vehicles immediately after they get charged or if vehicles may stay plugged for hours before the driver returns, we consider each charger to be able to serve one vehicle only. Taking into consideration the current potential autonomy of vehicles available on the market and based on the worst case scenario (vehicle of lowest autonomy), it is assumed that the vehicles that originate from a zone 50 km away from their destination will require charging. Moreover, it is assumed that the vehicles that begin their trip from a zone 10 km from their destination will not need to get charged, while the demand for charging of vehicles that start their trip from a zone between 10 and 50 km from their destination, decreases linearly (Fig. 2). For simplicity reasons, it is assumed that the travel distance is for all vehicles the shortest path between the zone centroids. As a result of the above assumptions, the demand for charging per zone at the peak time of a typical daily (8:00–9:00) was computed and used for the purposes of this research.
Fig. 2
Estimation of electric vehicles charging needs in 2020 based on the assumptions made in this approach
×
4.3 Genetic algorithm and tool
Genetic Algorithm (GA) is an artificial optimization algorithm that can be successfully applied on different combinatorial optimization problems. The idea of GAs was introduced by Holland [30]. GA is a stochastic search heuristic based on the natural selection and evaluation. Due to the genetic roots of the algorithm, the terminology of the optimization parameters follows the same pattern. An initial set/population of solutions/chromosomes is generated. Each chromosome is a solution, usually but not necessarily binary bit string, of the problem. The initial population evolves in new generations through an iterating process. The fitness function (equivalent to objective function) is used to evaluate the “fitness” of each individual in every generation. The parents and offspring that result in higher fitness values are selected to form the next generation, while those of lower are rejected, in order to maintain the size of the population. The offspring are created either by mutation (modification of a parent chromosome) or crossover (merging of parent chromosomes).
For the purposes of this research, a GA and a tool were developed in R [31] using the GA packages [32], ggplot2 [33], ggmap [34] and gWidgets [35]. The tool requires as input two CSV data files: 1) a list of candidate EV charging points (potential locations), their XY coordinates in WGS 84 and the expected charging demand (data columns: [Location ID], [Longitude], [Latitude], [Demand]); 2) the distances between the potential charging locations (data columns: [Location ID 1], [Location ID 2], [Distance]). The expected demand per location is given as input by the analyst (input file 1) and could represent either the real EV charging demand or be an approximation (e.g. based on the number of jobs/households in the area). The between-location distances are the shortest paths, average drive distances or cost-weighted distances in km. Prior to the initiation the optimization algorithm, the user should specify the desired number of stations (0 – total number of locations in the input file) for the examined scenario, the average cover distance radius per station, the charging speed and the average generalized cost per km. The output of the algorithm, namely the locations and coverage nodes of the stations, are visualized in Google Maps. The user should enter the coordinates of the minimum and maximum latitude and longitude (bounding box) of the area. Additional parameters that need to be specified by the user are the: 1) size of the initial population, 2) crossover probability between the pairs of the chromosome and 3) mutation probability in a parent chromosome. Figure 3 below shows the GUI (Graphical user Interface) of the tool.
Fig. 3
Electric Vehicle Charging Locations Optimization Tool (developed in R)
×
In this research, the chromosome is a sequence of binary bits that take the value 1 to the locations that have been selected for implementation of EV charger, and 0 to the others. The size of the initial population was set to 400; the probability of crossover between the pairs of chromosome was set to 0.8 (i.e. the offspring is made 80% from crossover – the new generation is 20% similar to the old) and the probability of mutation in a parent chromosome to 0.1 [i.e. 10% of the chromosome is changed (mutation should not occur very often in order to avoid having a completely random new population)]. Coverage distance for EV chargers is assumed to be 500 m. A sensitivity analysis was performed assuming 5, 10, 15 and 20 EV charging stations. The initial population was composed by randomly generated chromosomes with sum of bits equal to the number of stations, in order to restrict the search area of the algorithm and increase the optimization speed. Assuming the time, number of stations and the coverage distance as given, the optimization parameter is the total demand served.
The results of the optimization process are presented in Table 2 and are compared with Efthymiou et al. [25]. The GA algorithm used in this research results in better solutions than Efthymiou et al. [25] for the scenarios of 5 and 10 stations, while the covered demand for 15 stations is the same (80%) in both cases. The marginal demand coverage from 15 to 20 stations is decreasing; this implies that taking into consideration the additional cost per station established, implementing 15 stations would be a decent policy decision to be taken.
Figure 4 shows the best vs. the average fitness value found during the GA optimization search. The number of iterations required reaching the optimal solution increases between 5 and 15 stations and then decrease from 15 to 20 stations. Figure 5 shows the location of chargers per solution, and the points (zone centroids) that they serve. The 500 m service-distance assumption leads to many unserved zones. By increasing the perceived service-distance, the optimal solution would be reached earlier in the iteration process, and the covered demand would increase.
Fig. 4
Best fitness value among the current and all previous generations vs average fitness values per generation of the GA
Fig. 5
GA result - Optimal locations. Points (zone centroids) of same color are served by the same charger
×
×
5 Conclusions and future prospects
European countries are expected to encourage the electrification of their urban transport networks. In order to reduce the electric vehicle “driver anxiety” (i.e. the driver’s concern of running out of battery), public charging networks should be implemented. In this context, the objective of this research is to propose a solution for optimal EV charging infrastructure deployment, based on Genetic Algorithms and OD data. The results of a case study in Thessaloniki indicate that 15 stations are required in order to cover 80% of the expected demand. The estimation of charging demand is based on assumptions due to the scarce availability of EV data in Greece. The proposed optimization algorithm has been implemented in a user-friendly tool developed in R and is freely available. Since low EV penetration rates are more or less the case in all EU countries (as well as the whole world) this approach as well as the tool could be used to allocate charging stations at high-level in other cities too, in Greece and worldwide, in order to deploy a plan for installing adequate charging. The authors intend to further develop the tool in order to increase its capabilities and render it a flexible policy evaluation platform for the local Authorities.
Acknowledgements
This research has been implemented in the framework of CERTH KRIPIS project, that is funded by the European Regional Development Fund (ERDF) and National Funds, through the Greek General Secretariat for Research and Technology.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
