Keywords

1 Introduction

In the recent years there has been an extensive increase in the use of electrical vehicles (EV). EVs can play a major role in the progressive decarbonisation of road transport and in the improvement of air quality in urban areas. For this reason governments have been strongly supporting their adoption through a combination of purchase subsidies, non monetary incentives (free parking and use of car pooling lanes), the provision of public charging networks, etc. This has resulted in rapid adoption of EVs. Public chargers are a key enabler of EV adoption [18, 28] and therefore for the market to continue to grow the existing networks need to continue to expand as well.

On the other hand the adoption of electric cars has had a high growth and is steadily increasing. In contrast to fossil fuel vehicles, where the only way of refueling is visiting a station, EV’s pose several possibilities due to different charger speeds [9]. To be more precise, it is possible to charge a vehicle using slow Level 1 chargers at home or using faster ones for out-of-home charging. For example, Level 2 (medium speed) chargers can be used at office parking lots with many positive impacts [12, 19, 31]. This type of infrastructure has the additional benefit of being suitable for use in demand management systems [15, 21, 26]. The last approach is the use of Level 3 (fast) chargers, which can fully charge a typical EV in around 30 min. Level 3 chargers come at a high cost and are frequently close to 10 times more expensive than Level 2 ones, but are a necessity.

As the EV industry expands, drivers are becoming increasingly concerned about the comfort of usage, which is highly dependent on the available charging infrastructure. [20]. Due to the high cost of stations with Level 3 chargers, it is necessary to optimize their network. A large amount of research on EV charging infrastructure is modeled as location-allocation problems [22]. The high computational complexity of these problems, generally NP-Hard, has resulted in a large number of metaheuristics being developed for solving them [7, 10, 27].

A major body of this research is dedicated to optimizing infrastructure for long distance and regional travel due to range anxiety. In such systems one of the main goals is to make it possible for a majority of EVs to be able to reach EV stations with the minimal need for additional travel [14, 23]. An essential part of such models is the use of origin-destination pairs and attempting to position charging stations at locations that catch the majority of traffic [17]. Another part of this research is focused on optimal locations of charging infrastructure within a city [6, 13]. This research sites a more dense network of charging stations, over a city. Consequently, the models used for finding optimal locations of charging stations and their capacity has a high similarity to classical covering problems [10, 25, 32]. This is due to the assumption that an additional drive to reach a station is expected to be relatively short. An extended commute is acceptable for drivers if the waiting time is lower, this type of behavior is commonly observed for petrol car users.

In this paper, the focus is on developing a tool that makes it possible to assist in the decision making for the expansion of the EV charging network. This is done using a mixed integer program (MIP) for modeling the potential charging network of a city. The primary objective is to find the optimal locations of charging stations and their capacity. The optimality is observed as the minimization of the number of new stations that are installed. The second objective is to minimize the travel distances needed by an EV user to reach the charging stations.

The proposed model is used to assess the expansion strategies of charging infrastructure through case studies for two cities having different levels of existing infrastructure. This is done through using real world data on population density and existing charging infrastructure. In order to achieve a more realistic model, data regarding the electric distribution system is also used to specify the potential locations for new charging stations. The model is used to evaluate the expansion of the charging infrastructure for an increasing numbers of chargers per 10,000 population.

The paper is organized as follows. The second section introduces the mixed integer program for the problem of interest. The next section provides information how real world data is used to generate the instances for the model. The fourth section is dedicated to the case studies of the selected cities. The paper concludes with a discussion of the main insights derived from the study performed.

2 Mathematical Model

In this section, we present the mixed integer linear program for modeling the expansion of existing EV charging infrastructure on a city level. This type of problem is closely related to the capacitated facility location problem (CFLP) [30]. In the CFLP, it is expected that most facilities can satisfy demand from all locations and the distance only influences the cost. When modeling locations and capacities of EV charging stations this is not the case due to the fact that EV drivers are not willing to commute very far to use them. On the other hand, it is assumed that drivers will wish to avoid stations with long queuing times and in such cases they will go to a charging station that is not necessarily the closest. This common behavior of drivers often manages to balance the demand for charging stations over the whole system.

When setting up such infrastructure, the main question is how to select the best locations for new charging stations and their capacity. This should be done based on the population density of a city and the potential locations of charging stations based on the existing electrical distribution system. In practice, a complete EV charging systems for a city is not setup at once but through the expansion of an existing one with the goal of lowering the number of EVs per charger. The objective of the proposed MIP formulation is to be able to find the best locations and capacities of stations in this type of system.

In the proposed mathematical model several assumptions and simplifications are made. Firstly, it is assumed that the modeling is done on city scale and that the city is divided into sections. Each section has a fixed population and is considered as a single location. Each location has a potential capacity of EV charging that it can provided. More precisely, at each location some additional maximum charging capacity can be installed. The demand for EV charging for a location is proportional to its population. It is assumed that all the demand for EV charging must be satisfied. A demand can only be satisfied from a charging location that an EV driver is willing to travel to.

In addition, it is assumed that there is already some infrastructure in place which can provide charging. This is an additional property for each location. A location can at most satisfy the amount of charging demand that is less or equal to its capacity. It is expected that the majority of the cost for setting up the charging system is related to setting up a new locations and less to the number of chargers included. Because of this the objective will be to minimize the number of new locations that will be selected. It is assumed that a new location is being set up even if there are some existing charging facilities at the same area.

In formulating this model is it important to define the used parameters:

  • Let N be the number of locations in the city. In relation let us define the set \(V = \{1..N \}\) as the set of all locations.

  • It is assumed that the distance between any two locations i and j is known. Let us define a real parameters \(d_{ij}\) for each pair \(i, j \in V\) equal to the distance between the locations i and j. Note that the distance between location i to itself will be equal to zero.

  • Let us define a parameter \(c_v\) for each \(v \in V\) corresponding to the potential additional charging capacity of location v

  • Let us define the parameter \(e_v\) for each \(v \in V\) corresponding to the existing capacity of location v

  • Let us define the parameter \(p_v\) for each \(v \in V\) corresponding to the population of location v.

  • Let W be the maximal distance a driver is willing to compute to the EV charging stations.

  • Let \(\alpha \) be the number of chargers needed per a 10 000 population.

Next, let us define the set of decision variables needed to fully specify the model.

  • Let \(x_i\) be defined as a binary decision variable for each location \(i \in V\). It has a value of 1 if at least one new charging stations will be set at location i and 0 otherwise.

  • For each two locations \(i,j \in V\), a real variables \(r_{ij}\) is defined. \(r_{ij}\) holds the information on how much of the population of location j is using the chargers at location i.

It is assumed that if a new charging facility is installed at location i that its total additional capacity can be used by EV drivers. The objective is to minimize the number of used locations for installing the additional chargers as follows:

$$\begin{aligned} \text {minimize} \sum _{v \in V} x_v \end{aligned}$$
(1)

Let us define the constraints that these variables need to satisfy in the following way.

$$\begin{aligned} \sum _{j \in V} r_{vj} \le x_i c_v + e_v&\qquad&v \in V \end{aligned}$$
(2)
$$\begin{aligned} \sum _{i,v \in V} r_{iv} = \alpha p_v&\qquad&v \in V \end{aligned}$$
(3)
$$\begin{aligned} r_{ij} = 0&\qquad&i, j \in V \wedge d_{ij} > W \end{aligned}$$
(4)
$$\begin{aligned} 0 \le r_{ij} \le c_i + e_i&\qquad&i,j \in V \end{aligned}$$
(5)
$$\begin{aligned} x_i \in \{0, 1\}&\qquad&i, j \in V \end{aligned}$$
(6)
$$\begin{aligned} r_{ij} \in \mathbb {R}&\qquad&i, j \in V \end{aligned}$$
(7)

The constraint given in (2) states that the maximal charge that can be provided from location v is less or equal to the sum of existing capacity and additional capacity. The constraints given in (3) guaranties that all the charging demand of a location is covered. Note that all the charging demand of a location is satisfied if it has \(\alpha \) chargers per 10,000 population. The constraints given in Eq. (4) state that a location j can use chargers from location i only if the distance is less than a specified maximal distance.

The MIP with the objective (1) using constraints (2)–(6) provides us with the minimal number of locations needed to satisfy a specific number of chargers per 10 000 population. The MIP indirectly provides the additional capacity of location \(v \in V\) and is equal to \(\sum _{j \in V} r_{vj}\). More precisely, the capacity needed at location v is equal to number of chargers used by other locations in the city. Note that this sum is a real value and can be rounded up to the nearest integer value.

As previously stated, the majority of costs is related to the setup of new charging locations and significantly less to the number of chargers used at such a location. The setup of the new charging infrastructure is in essence a dual objective problem. Whilst the first one is related to the minimizing the cost, the second one is related to satisfaction of EV drivers. In case of the later, a good measure is to minimize the average distance the EV drivers need to reach the station. In practice, our goal is to find the optimal capacities for each new charging location. This can be done in two steps. The first one is finding the minimal number L of new locations using the previously presented model. Secondly, finding the capacities of the L locations. This can be achieved by a new model having the following objective function

$$\begin{aligned} \text {minimize} \sum _{i,j \in V} r_{ij}d_{ij} \end{aligned}$$
(8)

Equation (9) states that the objective is to minimize the sum of distances traveled by the EV drivers. The constraints of the new MIP use the Eq. (2)–(6) but with an additional constraint that fixes the number of new stations as follows.

$$\begin{aligned} \sum _{i\in V} x_i = L \end{aligned}$$
(9)

3 Use of Real World Data

The main goal of this work is to evaluate the expansion of existing EV charging networks in metropolitan areas, because of this, special attention is given to generating instance based on real word data. In this section an overview of the used information and how it is converted to parameters of the model are given.

In generating instances for the model, the following real world data has been used.

  • Population density is essential for specifying the population of each of the locations in the model.

  • Latitude and longitude data on existing charging infrastructure is used so that the model can build upon this.

  • Data on transformer substations provide the information on the potential new locations for EV charging stations. This property has been selected since it is possible to add large energy consumers, like an EV charging stations, close to them without a high increase in capital expenditure (CAPEX)

The first step in converting this type of data to an instance is defining what is considered a location within the model. In the conducted work, a grid approach is used in the following way. The area corresponding to the city of interest is divided into a grid (rectangular subsections of the city) and each location resembles to a cell in the grid. The next step is specifying the methods for calculating the parameters in the model. The distance between locations i and j is equal to the distance between cell centers calculated using their latitudes and longitudes based on the Haversine formula [29]. The used measure unit for distances is kilometer.

The value of the population parameter \(p_v\), for location v, is calculated based on the population density. To be exact, the used population density data provides the density for the region of a specific cell (location) and based on its area the corresponding total population can be trivially calculated. The parameter for the existing capacity \(e_v\), for a location v, is calculated based on the locations of existing charging stations. It is equal to the total number of charging stations with a location that is inside the region of the corresponding cell.

The parameter \(c_v\) corresponding to the potential additional charging capacity has been calculated using the locations of transformer substations. New charging stations can be added in areas that are less than a specific maximal distance to transformer substations. To be more precise, if the distance from a charging cell is less than a value l it can provide an additional capacity of 1 to that cell. In the proposed instance generation method the value \(c_v\) of location v is be equal to the sum of all the additional charging capacity of all substations based on distance of the substation to the corresponding cell and the l value.

4 Case Studies

In this section the proposed model and the method for integrating real world data are used to evaluate the growth of EV charging infrastructure. This has been done through two case studies for Doha, Qatar and San Francisco, USA. Firstly, the specifics for data collection for these two cities are presented. Next, an analysis of the results of the conducted computational results using this data and the proposed model are given.

4.1 Instance Generation

To represent the versatility of the model, it was important to select cities with a variety of economic, demographic, and geographical landscapes. The cities selected were Doha and San Francisco. These exemplified urban areas with ambitious EV targets but differing EV markets, demographic characteristics, and geographical landscapes. Doha is an example of a very small EV Market, it currently only hosts 9 charging stations but looks to expand its charging network to reach targets of 10% EV penetration by 2030 [24]. Comparatively, San Francisco has a comprehensive network of 155 charging stations, but also seeks an expansion of its charging facilities to reach 100% EVs by 2030 [11]. Moreover, whilst both cities are considered densely populated, much of Doha’s population is concentrated in a relatively small area towards the east, whereas San Francisco’s population is more equally dispersed throughout the city. Furthermore, whilst San Francisco is surrounded by sea and hosts several lakes and large parks, Doha has sea on one side and has relatively little water bodies or parks in the city but large areas of desert. Hence, by selecting urban areas with differing geographical landscapes, demographic characteristics and EV markets, the adaptability of the model can be represented.

Fig. 1.
figure 1

Illustration of the conversion of population density to values of parameters within the model for Doha and San Francisco. The input data is on the left and the values of parameters corresponding to the population at a location (\(p_v\)) are on the right.

Full size image
Fig. 2.
figure 2

Illustration of the conversion of transformer substation location data to values of parameters within the model for Doha and San Francisco. Red circles are used to indicate the 1-mile buffer zone for a substations. The input data is on the left and the values of parameters corresponding to the potential additional capacity that can be installed at a location (\(c_v\)) are on the right.

Full size image
Fig. 3.
figure 3

Illustration of the conversion of existing charging stations positions to values of parameters within the model for Doha and San Francisco. The green circles indicate the locations of the stations. The input data is on the left and the values of parameters corresponding to the existing capacity at a location (\(e_v\)) are on the right. (Color figure online)

Full size image

The real-world data for both cities (population density, pre-existing charging facilities and transformer substation) used for generating instances, was gathered from freely accessible online resources. For San Francisco pre-existing charging data was accessed from ‘Open Charge Map’ [5], transformer substation data from ‘The Homeland Infrastructure Foundation’ [2], and population data from ‘WorldMap’ [1]. For Doha, pre-existing charging information was extracted from online news articles and from a case study regarding the hindrances of EV adoption in Qatar [16]. Moreover, transformer substation data was collected from ‘Overpass Turbo’ [4] and population data from ‘WorldMap’. As sources such as ‘Overpass Turbo’ and ‘Open Charge Map’ used public contributions as part of their information, the reliability of their data was ensured through reviewing sites on Google Earth.

The data was extracted and reviewed, and adjustments were made to ensure it was suitable to be collected in the grid format and read into the optimization model. The accessible population data (density) for all the urban areas was only available online via census block data. Illustration of it’s transformation to the model parameters can be seen in Fig. 1. The location of each transformer substation was assigned a 1-mile buffer zone (Fig. 2) to indicate the reach of its capacity, as recommended by [8]. Hence, any new charging station had to be located within a buffer zone of a Transformer Substation. The pre-existing charging data did not require any adjustments and so could be directly read into the grid data collection format (Fig. 3).

4.2 Computational Experiments

In this section the results of the conducted computational experiments are presented. The main objective was to analyze the expansion of the charging infrastructure based on the proposed model and real world data.

In the case studies for Doha and San Francisco, the selected maximal distance that a driver is willing to travel to a charging station (W) has 10 km. This value has been chosen to be an improvement to the current distance of EV drivers to the charging stations. For example is San Francisco, an EV drivers has a charging station with-in 16 km from his home [3].

In case of Doha and San Francisco there was a total of 127 and 213 potential locations (grid cells), respectively. The evaluation was done for several values of the number of chargers per 10 000 population (\(\alpha \)). The selected lower bound was equal to the value of \(\alpha _l\) for the current infrastructure, simply as the number of chargers divided by the total population scaled by 10 000. The upper bound \(\alpha _u\) was calculated in the same way using the sum of existing number of chargers and the maximal number of potential additional ones. It should be noted that due to the constraints related to parameter W, in practice these values could not be reached. The tests have been done for a 10 intermediate values \(\alpha _i\) calculated as follows:

$$\begin{aligned} \alpha _i = \alpha _l + i \frac{\alpha _u-\alpha _l}{10} \end{aligned}$$
(10)

The propose MILP has been implemented using OPL in IBM ILOG CPLEX Optimization Studio Version: 12.6.1.0, and executed using the default solver settings. A single problem instance could be solved to optimality within less than five seconds. The main results of the case studies for Doha and San Francisco are summarized in Figures 4 and 5, respectively. In addition in Table 1, the growth in the number of new charging locations that are needed to achieve different levels of charger availability, corresponding to values of \(\alpha _i\), are given.

Fig. 4.
figure 4

Illustration of the expansion of charging infrastructure for Doha from current state to high levels of adoption. The numbers indicate the amount of charging capacity that is inside a location (cell in the grid) in the city.

Full size image
Fig. 5.
figure 5

Illustration of the expansion of charging infrastructure for San Francisco from current state to high levels of adoption. The numbers indicate the amount of charging capacity that is inside a location (cell in the grid) in the city.

Full size image
Table 1. Number of new locations need to achieve different levels of chargers per 10 000 population for the cities of Doha and San Francisco.
Full size table

In the case of Doha, where the EV charging infrastructure is at a very early stage, the initial stations have been deployed as test beds. Therefore, they are not positioned at the most densely populated areas of the city. The model indicates that the expansion of the infrastructure should be done initially at the most densely populated areas. In addition it can be observed that it is advantages to have the earlier stages of expansion focused in areas that can provide a high level of new charging capacity. It should be noted that for most areas the initial amount of charging provided would be equal to the maximal potential capacity.

This type of behavior is less noticeable in case of San Francisco, were an extensive EV charging network already exists. In this case, it is common that the charging capacity of an area would be expanded at later stages. The additional capacity is generally added mostly in densely populated areas. In case of both cities, in later stages of infrastructure development the network becomes more evenly distributed over the areas were installation is possible. It can also be observed that even at later stages of infrastructure expansion some areas do not have near by charging stations. One reason for this is that the objective in the model is minimal average distance from a charging station. Some of the disadvantages of this is that a small number of EV drivers will need to travel further and there is a potential that the high density of charging stations in some areas will result in potential traffic congestion.

5 Conclusion

In this paper, a new approach has been presented for analyzing the expansion of EV charging infrastructure. The method uses information related to existing charging and electrical distribution infrastructure in combination with population density. The proposed method is based on a mixed integer linear program. One of the main objectives of the conducted research was to develop a method that can be used for real world application, consequently a large amount of effort has been dedicated to data collection. The analysis has been done through two case studies for the cities of Doha and San Francisco. It should be noted, that the data sources used for this have information for a wide range of other cities and the presented approach can easily be applied to them. The proposed MIP can be used to solve this problem for real world cities for a low computational cost. The two case studies indicate that by optimizing each stage of the infrastructure growth can results in a non-optimal final solution.

In the future we plan to extend this model to include additional parameters for the selection of charging stations like land area costs, points of interest, traffic and similar.