Keywords

1 Introduction

Road transportation is one of the main sources of air pollutants in our cities [12]. Reducing the road vehicles’ emissions would have an important impact on tackling global warming [17] and improving inhabitants’ health [11]. An extended use of electric vehicle (EV) transportation will reduce the emission of pollutants. However, at the time of this research, the EV adoption is limited by several factors. One of the main factors is the need for a specific charging infrastructure for EV, which present two main issues [9]: a) charging times determine the number of vehicles that can be charged over the time; and b) charging stations have high energy consumption requirements, which limits the number of stations that can be installed in a given area. Improving the availability of charging stations will lead to increasing the adoption of this type of green transportation [9].

Smart cities provide a series of tools for advanced knowledge and decision-making support [2, 3, 8, 12]. In this line, this work focuses on providing a solution to efficiently allocate EV charging stations to ease EV uptake by the citizens. The proposed approach takes into account the distance the users have to travel to charge their EV and the power electric substations installed in the city to provide electric power to the different urban areas. These electric substations produce a limited energy, which determines the maximum EV charging stations to be allocated in a given area. Thus, we have defined an optimization problem named Electric Vehicle Charging Stations Locations (EV-CSL).

Finding the best locations of EV charging stations is attracting the attention of the research community. In Brandstätter et al. [1] the authors presented an ad-hoc heuristic for solving the EV-CSL problem. The main drawback of their approach is that it does not take into account the energy constraints of the substations. Other research studies only considered the aspects related to the installation of the EV charging points [10], i.e., installation price, maintenance, etc., leaving quality of service (QoS) and users aside of the problem.

The problem of finding the optimal locations for the EV charging stations for a full city can be defined as a variant of a p-median problem [5, 14], which have been proven to be an NP-Hard optimization problem. The large search space makes impractical the use of traditional optimization methods (e.g., enumeration techniques or dynamic programming). Thus, heuristic and metaheuristics are useful methods to perform the search using bounded computational resources [4]. Here, two metaheuristic algorithms have been applied to address EV-CSL: a genetic algorithm (GA) [19] and a variable neighborhood search (VNS) [15].

To evaluate the proposed approach, a realistic scenario of the whole city of Malaga (Spain) has been modeled by taking into account real data (i.e., open data provided by the municipality of the city, road maps from Open Street Maps [16], and electric substations locations). In turn, the computed results are compared against the current solution provided by the municipality (actual locations of the charging stations), as a baseline solution.

The main contributions of our work are:

  • Providing the mathematical formulation of EV-CSL.

  • Modeling a realistic instance based on real data of the city of Malaga to address EV-CSL focusing on citizens’ needs and electricity supply constraints.

  • Implementing and applying two metaheuristics to EV-CSL: a GA and a VNS.

  • Studying the solutions computed by the proposed algorithms to analyze their performance when addressing this problem and comparing them with the actual solution deployed in Malaga.

The rest of this article is organised as follows: the following section defines the EV-CSL addressed in this research. Section 3 introduces the main aspects of the metaheuristics applied and implemented. Section 4 describes the real-world scenario defined to tackle the EV-CSL problem and the main experimental settings. The experimental analysis is reported in Sect. 5. Finally, Sect. 6 presents the conclusions and formulates the main lines for future work.

2 Efficient Full City EV Charging Station Locations

The Electric Vehicle Charging Stations Locations (EV-CSL) problem is defined to provide potential locations of EV charging stations for a full city given a maximum number of charging stations (Ms) to provide the best QoS possible. In this study, as a preliminary approach, the QoS is given by the distance between the citizens’ homes and the EV charging station. The mathematical formulation of EV-CSL is defined considering the following:

  • A maximum number of electric car charging station defined by Ms.

  • A set \(S = \{s_1, \ldots , s_M\}\) of potential street segments for charging stations. For this version of the problem, each street segment of S can be the location of one charging station.

  • A set \(C = \{c_1, \ldots , c_N\}\) of client locations. Following a usual approach in the related literature, nearby locations are grouped in clusters, assuming a similar behavior between elements in each cluster. The number of users to serve at each location c is \(u_{c}\). The distance from client c to the charging station \(s \in S\) is \(dc_{c,s}\), and the maximum distance between any client in C and its assigned charging station (in meters) is Dc.

  • A set \(E = \{e_1, \ldots , e_T\}\) of electrical substations that serve as electric power source for the charging stations. The distance from the electrical substation e to the charging station in \(s \in S\) is \(de_{e,s}\), and the maximum distance between substation e in E and its assigned charging station s (in meters) is De. As the substations have electric power restrictions, the number of charging stations that can be fed by a substation e is limited by \(mp_{e}\).

Equations 1–7 describe the model, using the following variables: \(x_{c,s}\) is 1 if the client c is assigned to the station located in s and 0 otherwise, and \(y_{e,s}\) is 1 if the electrical substation e is feeding the charging station located in s and 0 otherwise.

$$\begin{aligned} \small \min&\sum _ {c\in C, \text { } s\in S} x_{c,s} d_{c,s} u_{c} \end{aligned}$$
(1)
$$\begin{aligned} \text {subject to} \nonumber \\ \sum _{s\in {}S} x_{c,s} ={}&1&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \forall {}\ c\in {}C&\end{aligned}$$
(2)
$$\begin{aligned} \sum _{c\in C, \text { } s\in S} x_{c,s} =&\left| {}C\right| {} \end{aligned}$$
(3)
$$\begin{aligned} dc_{c,s} x_{c,s}\le {}&Dc&\qquad \qquad \qquad \qquad \qquad \forall {}\ c\in {}C,\ s\in {}S&\end{aligned}$$
(4)
$$\begin{aligned} de_{e,s} y_{e,s}\le {}&De&\qquad \qquad \qquad \qquad \qquad \forall {}\ e\in {}E,\ s\in {}S&\end{aligned}$$
(5)
$$\begin{aligned} \sum _{s\in {}S} y_{e,s} \le {}&mp_{e,s}&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \forall {}\ e\in {}E&\end{aligned}$$
(6)
$$\begin{aligned} \left| {}S_o\right| {} ={}&Ms&\qquad \qquad \qquad \qquad S_o = \{s_o {\setminus } \forall {} s_o\in {} S , \sum _{c\in C} x_{c,s_o} > 0 \} \end{aligned}$$
(7)

As the QoS provided is measured in terms of distance between the clients and the charging stations, a single objective is provided in Eq. 1: minimizing the distance between the clients and the assigned charging stations. Regarding the problem constraints, all the clients are assigned to a unique charging station (Eq. 2); all the clients are served for any charging station, i.e., there are not potential clients without a charging station assigned (Eq. 3); the maximum distance between the charging station and the client assigned should be lower than Dc (Eq. 4); the maximum distance between the electric substation and the fed charging station should be lower De (Eq. 5); the number of charging stations that are fed by a given electric substation should be lower or equal than \(pm_e\) (Eq. 6); and the number of charging stations located should be lower than the maximum number of charging stations to be located Ms.

3 Metaheuristics for Efficient EV-CSL

This section summarizes the applied metaheuristics to address EV-CSL in the city of Malaga and introduces the main implementation details.

3.1 Algorithms

Genetic Algorithm: It was originally presented by John Holland inspired by the evolution of species in Nature [19]. A basic pseudocode is showed in Algorithm 1. GA is an iterative method. In each iteration, the algorithm generates \(\lambda \) new solutions (new population). A new solution is generated from several parent solutions (two parents this case, \(p_1\) and \(p_2\)) selected from the previous population. The selected solutions are mixed (crossover) between them to generate a new one, which is probabilistically disturbed (mutated). At the end of an iteration, the new solutions replace others from the previous population following some kind of strategy. Finally, the algorithm returns the best solution found.

Variable Neighbourhood Search: It is based on the concept of neighbourhood [15]. The pseudocode is showed in Algorithm 2. Each solution has a defined neighbourhood, i.e., a set of solutions with closest facilities to it. The current solution x is modified according to these neighbourhoods (next() indicates the number of modifications) and improved by a local search. In this version, a number K of consecutive non-improvements is allowed before finishing the algorithm. The VNS applied in the proposed approach is based on the version defined in [6].

figure a

3.2 Implementation Details

The solution encoding and the fitness function evaluation are defined in this section. Other details about the applied algorithms (i.e., GA and VNS variation operators) are presented in the parameter settings section (see Sect. 5).

Solution Encoding: The applied solution encoding considers a vector \(S^o\) of \(S_M\) binary elements, i.e., \(S^o = \langle s^o_0, ..., s^o_{S_M}\rangle \), being \(S_M\) the number of road segments that are potential locations for the EV charging stations (in the modeled scenario \(S_M=33,550\), see Sect. 4.1). Thus, if in the road segment i there is an EV charging station \(s^o_i=1\), otherwise \(s^o_i=0\).

Fitness Function: The fitness function evaluates the QoS provided by installing EV charging stations in the locations represent by the solution \(S^o\). In this approach, the QoS is given by the distance that the users have to travel from their homes to the charging station. Thus, the EV-CSL problem is defined as a minimization problem in which the objective function is the average distance the citizens travel from their homes (in EV-CSL are known as neighborhood centers that groups a set of buildings) to the EV charging station. The objective function is defied according to Eq. 1.

4 Experimental Settings

This section describes the main aspects of the experiments carried out to address EV-CSL by using GAs and VNSs. It presents the real-world scenario/instance defined to evaluate the proposed approach. It summarizes the implementation and computational platform. It describes the experiments performed by using irace to configure the main parameters of the applied algorithms.

4.1 Scenarios

The EV-CSL is addressed over the city of Malaga, as case study. This realistic scenario consists of 567,953 citizens in 363 neighborhoods. The road map is defied by using the data of Open Street Maps Based. The map includes total of 33,550 road segments as tentative locations for the charging stations (i.e., \(S_M\) = 33,550). Finally, the scenario includes the main data of the actual 14 electrical substations, i.e., locations, maximum energy flow capacity, etc. (see Fig. 1). The maximum energy flow capacity limits the number of charging stations that can be located in a given area. Thus, it is not realistic to place as many charging stations as we want in any place because a fast charge of a medium-class EV station consumes more than a whole building of apartments. The different colors in Fig. 1 show the areas of the city covered by each substation.

Fig. 1.
figure 1

Road map of Malaga, Spain. The edges represent each possible street segment associated with a substation.

Full size image

Different instances have been defined by changing the maximum number of EV charging stations to be installed, i.e., \(M_s\). To compare among the different methods, five instances are use with \(M_s \in \{10, 20, 30, 40, 50\}\). Besides, to compare the provided solutions against the actual one provided by the municipality of Malaga (baseline), another instance was defined with \(M_s\) = 45 because at the time of this research Malaga has 45 EV charging stations.

4.2 Implementation and Hardware Platform

The computation platform used in this work consists of a cluster of 144 cores, equipped with three Intel Xeon CPU (E5-2670 v3) at 2.30 GHz and 64 GB memory. We have carried out 30 runs of each experiment. The stop condition for both algorithms is the computational time, in this case, they run for 60 CPU seconds. After that, the algorithms report the best solution found in each of the runs. The algorithms were implemented by using C++, the source code can be found in https://github.com/NEO-Research-Group/EV-CSL.

4.3 Parameter Settings

GAs and VNSs can use parameters and operators: crossover, mutation, local searches, etc. We have implemented several alternatives for these operators. To get the best parameter setting of the algorithms for our problem, a preliminary parameter setting study was performed. Using a reduced scenario, i.e., the northwest area of Malaga, and irace [13] tool to obtain the best configuration of our algorithms. The two best configurations returned by irace are the ones used in the experimental analysis, trying to avoid possible overfitting in the process carried out by irace. Table 1 shows the configurations of the GA and the VNS.

Table 1. Two best parameter configurations found by irace for GA and VNS.
Full size table

5 Experimental Analysis

This section presents the main results of the experiments carried out by performing 30 independent runs of each algorithm variation and each of the instances (i.e., \(M_s \in \{10,20,30,40,45,50\}\)).

5.1 Optimization Results Comparison

Figure 2 and Table 2 presents the results of each algorithm for the six instances addressed in terms of fitness value (i.e., average distance that users have to travel to get the assigned charging station) of the best solution found. The blue line represents the fitness value obtained for the solution that represents the actual location of the EV charging stations in Malaga (baseline solution). Comparing the four metaheuristic alternatives, GA-2 provides the best (lowest) results for all the instances. In turn, GA-2 provides the most robust method because it shows the lowest variability among the different runs.

According to Wilcoxon Signed Ranks with Bonferroni correction, GA-2 is the best method and GA-1 provides the worst results, for all the instances. This remarks the importance of finding the proper configuration of the GA. For instances \(M_s=10\) and \(M_s=20\), VNS-1 and VNS-2 do not show statistical difference. VNS-2 provides statistically the second best results the rest of instances.

As it can be seen in Fig. 2, all the proposed algorithms improve the baseline QoS (distance) when installing only 20 stations. In turn, GA-2 is able to improve the baseline using only 10 stations.

Fig. 2.
figure 2

Fitness value (average distance) of each algorithm for the different instances. The blue line represents the fitness value of baseline solution. (Color figure online)

Full size image
Table 2. Experimental results for each algorithm in each instance (\(\times 10^2\)).
Full size table

5.2 Improvement on Travel Distance over the Real Layout of Stations

To better illustrate the improvement offered by our algorithms versus the actual stations locations in the city of Malaga (a.k.a. baseline solution), we have compare the solutions found by installing the same number of stations (\(M_s=45\)) in terms of average distance that the EV users have to travel to charge their cars.

Fig. 3.
figure 3

Empirical cumulative distribution of the percentage of improvement of our solutions in each algorithm, compared to the baseline solution.

Full size image

Figure 3 shows the proportion of solutions for each algorithm (y-axis) obtained less than the percentage of improvement defined in the x-axis, i.e., the percentage of computed solutions that achieved at most that percentage of improvement. GA-1 lags far behind the other algorithms by only over 30% in the 75% of its solutions. The two versions of VNS offer improvements between 40–50%. The best algorithm is GA-2, being also the most stable (less steep curve) with a 52% of improvement in more than the 70% of its solutions. In general, it is interesting to note that the algorithms using the second-best configurations found by irace offer the most significant improvements. This result underlines the importance of take into account the overfitting when we configuring machine learning techniques.

6 Conclusion

This article presented a definition of the EV-CSL optimization problem. The optimization problem takes into account the QoS provided (in terms of distance customers have to travel to get the charging station) and the energy limitations of the different electric substations around the city. Two different metaheuristic algorithms, both parameterized using irace, have been proposed and implemented to address the problem: GA and VNS.

A realistic scenario based on city of Malaga has been defined by using real data (i.e., road maps, inhabitants’ home location, electric substations location, etc.) Different instances have been defined by locating a different number of charging stations (from 10 to 50).

The main results of the experimental evaluation indicate that the proposed metaheuristics were able find competitive solutions. The solutions provided by the proposed methodology were able to improve the actual QoS provided in Malaga with 45 stations installing only 20. In general, a variation of GA provided the best results for the different instances. When comparing the actual solution in the city with the ones provided by the four metaheuristic variations analyzed here, metaheuristic dramatically improve the QoS.

The main lines for future work are related to extending the proposed problem model to consider the number of parking slots in each station and the charging time, exploring other optimization methods, and defining a multi-objective variation of the problem by including other objectives, such as the installation costs. In addition, we are working to improve the proposed model to include in the QoS the idea that the vehicles can be charged when the citizens are working or doing other activities.