Exact Approach for Electric Vehicle Charging Infrastructure Location: A Real Case Study in Málaga, Spain

Abstract

This article presents an exact approach for solving the problem of locating electric vehicle charging stations in a city, whose goal is upon minimizing the distance citizens must span to charge their vehicles. Mixed integer programming formulations are presented for two variants of the problem: relaxed (i.e., without considering electrical constraints for the infrastructure) and full versions. The experimental evaluation is performed over a real-world case study defined in Málaga, Spain. Results show that the proposed approach can deal with the large number of variables (i.e., millions) of the problem, computing optimal solutions for all problem instances and variants addressed. The improvements in solutions quality over a previous metaheuristic approach applied to the same problem and application case are notorious.

1 Introduction

Sustainability has become a priority goal for society. Agreements and conventions, such as the Sustainable Development Goals, are shifting societies towards green-conscious ones. An important change is being experienced in road mobility because vehicles are shifting from inefficient combustion engines to more sustainable ones (i.e., hybrid or electric engines). Cars, scooters, and electric motorcycles are novel ways preferred by newer generations to move along the cities. Thus, electric vehicles (EV) have a great boom and socioeconomic impact [11].

Electric cars allow citizens to reduce gas emissions, if the electricity used to charge the cars is obtained from green sources. The number of kilometers that an electric car can drive without stopping is a decisive factor when deciding to opt for an electric car. Maximum kilometers would not be such a pressing problem if there were a good network of charging stations. Cities have not yet adapted to this new trend in transportation. Even though there are many plans to deploy networks of charging points for electric vehicles in the main cities of the world [9].

The selection of locations for these charging points has been studied by the Electric Vehicle Charging Stations Locations (EV-CSL) problem. The problem proposes determining the location of electric vehicle charging stations to optimize a quality of service metric, i.e., minimizing the sum of distances that citizens must walk to charge their vehicles. Our previous research addressed EV-CSL over a real scenario defined in Málaga city (Spain) [7]. A realistic instance was defined taking into account real information about the roads, the limitations of the power grid, and the location of the tentative charging point users. In turn, two metaheuristics were proposed to solve the problem.

This article present a new version of the EV-CSL problem model, to better capture realistic features in terms of energy supply constraints. In turn, an exact method based on ILP is applied to solve the problem. The main contributions of the research reported in this article include: i) Providing a new improved mathematical formulation of EV-CSL; ii) Proposing a new exact approach to address EV-CSL based on ILP; iii) Designing new realistic instances and variations of the problem to evaluate the proposed approach; iv) Reporting a comparison among the solutions provided in previous research and the results computed by our approach; v) Discussing the different solutions obtained in terms of the quality of service and the distribution of the charging points.

The article is organized as follows. Next section introduces the optimization problem addressed in this research and its mathematical formulation. Section 4 describes the main details of the proposed optimization approach. The experimental evaluation is reported in Sect. 5, including discussion of the obtained results and their applicability in the real case study in Málaga. Finally, Sect. 6 presents the conclusions and formulates the main lines for future work.

2 Infrastructure Location for Electric Vehicles Charging

The mathematical formulation of the EV-CSL problem is defined attending to the elements and considerations described in the following subsections.

2.1 Problem Data

An instance of the EV-CSL problem is determined by the following data:

• The set of potential charging points $S=\{s_1,s_2,\dots ,s_M\}$ comprises those physical locations considered suitable for installing recharging infrastructure. The formulation makes no distinction between points, other than its location and the set of power stations within the distribution grid capable of feeding each point. Particularly, no difference is considered regarding the number of customers that can be served in parallel at any given point.

• The maximum number of charging points to be deployed all over the city, $M_s$. For the optimization problem to be realistic, it is assumed that $M_s<<M$.

• The set $C=\{c_1,c_2,\dots ,c_N\}$ comprises clusters of clients, grouped according on their geographical proximity. For each cluster $c\in C$, the number $u_c$ of clients is known. Since clusters are pre-calculated so that their members are not widely separated from each other, the average distance $d_{cs}$ between cluster c clients and every potential charging point $s\in S$ is known in advance, and its variance is low regarding the average.

• There is a known bound $D_c$ for the maximum distance that customers in cluster $c\in C$ are willing to walk to charge their vehicles. So, only points $s\in S$ where $d_{cs}\le D_c$ are considered to serve customers of the cluster c.

• $E=\{e_1,e_2,\dots ,e_T\}$ is the set of power stations that might serve as source to feed charging points. For every pair $e\in E$, $s\in S$, the reference distance $d_{es}$ over the power grid necessary to connect e with s is known in advance. This correspondence imposes viability among connections because of electric constraints, such as: tension drops, thermal or stability limits the grid must comply with. A maximum extent $D_e$ is assumed between each power station $e\in E$ and those points $s\in S$ to be connected to it. Only those (e, s) pairs where $d_{es}\le D_e$ are considered.

• A power-stations to charging-points assignment cannot lead to configurations that overload stations beyond their capacity. Every station $e\in E$ has a specific limit $mp_e$ to the number of charging points it can feed.

2.2 Design Premisses and Control Variables

A feasible deployment of charging points must comply with a simple set of rules:

• 1. Every cluster of clients $c\in C$ must count an effective charging point $s\in S$ at a distance $d_{cs}$ of at most $D_c$.

• 2. Every charging point to be installed must be fed from a unique power station $e\in E$, whose distance $d_{es}$ is lower or equal to $D_e$.

• 3. The power-stations to charging-points assignment cannot press the number of charging points to be served by any station $e\in E$ beyond its limit $mp_e$.

• 4. The objective to optimize accounts the accumulated distance between clients and their nearest charging points available. Hence, though a cluster $c\in C$ could have more than one charging point within $D_c$ range, only that at the nearest distance is considered to account in the QoS.

• 5. The number of charging-points is bound to a total limit $M_s$, so the election affects the whole and it must be globally coordinated.

• 6. Power limits at stations only concern with the number of charging points fed from them, not with the associated number of customers.

The main control variables of the problem regard with the selection of charging points to be installed. However, the formulation includes additional variables to capture other design concerns. The list of variables by kind is as follows:

• Boolean variables $z_s$ indicate whether some charging point $s\in S$ is to be installed or not, so they are as many as $|S|=M$.

• Boolean variable $x_{cs}$ is active if and only if those clients in the cluster $c\in C$ find their closest point of the charge at $s\in S$.

Constraint $d_{cs}\le D_c$ must hold to comply with distance limits, what is achieved by solely considering $x_{cs}$ variables where $d_{cs}\le D_c$. Let $CS\subseteq C\times S$ be the a-priori computed set of distance viable clusters to charge-points assignments. Observe that the number |CS| of $x_{cs}$ variables could be as high as $M\times N$ ($|S|=M$, $|C|=N$) in the limit. The value depends of the maximum allowed distance $D_c$, the higher the limit, the greater |CS|.

Variables described so far only concern with the physical placement of charging points. Electric grid constraints require additional variables:

• Boolean variables $y_{es}$ capture the fact that station $e\in E$ supplies power to charging point $s\in S$. Since the problem description also integrates distance limits amid these connections, (e, s) assignments fulfilling $d_{es}\le D_e$ are pre-filtered, whose outcome is referred to as $ES\subseteq E\times S$. The number |ES| of $y_{es}$ variables could be as high as $T\times M$ ($|E|=T$, $|S|=M$) in the limit. Unlike the previous CS set, the number |ES| is fixed among instances to solve, since it is inherited by constraints coming from the power grid rather from some ultimately adjustable service goal, such as $D_c$.

Equations (1a)–(1g) expresses the mixed integer programming (MIP) for EV-CSL, i.e., finding the most efficient location for the electric vehicle charging infrastructure, in terms of the sum of distances between clusters and charging points.

$$\begin{aligned} \displaystyle \min _{x_{cs},y_{es},z_s}&\sum _{cs\in CS} u_c d_{cs} \cdot x_{cs} \end{aligned}$$

(1a)

$$\begin{aligned} \text {subject to:}&\nonumber \\&\displaystyle \sum _{cs\in CS} x_{cs} = 1,&\forall c\in C \end{aligned}$$

(1b)

$$\begin{aligned}&\displaystyle ~z_s \ge x_{cs},&\forall cs\in CS \end{aligned}$$

(1c)

$$\begin{aligned}&\displaystyle \sum _{s\in S} z_s \le M_s \end{aligned}$$

(1d)

$$\begin{aligned}&\displaystyle \sum _{es\in ES} y_{es} = z_s,&\forall s\in S \end{aligned}$$

(1e)

$$\begin{aligned}&\displaystyle \sum _{es\in ES} y_{es} \le mp_e,&\forall e\in E \end{aligned}$$

(1f)

$$\begin{aligned}&x_{cs},y_{es}\in \{0,1\}, 0\le z_s \le 1 \end{aligned}$$

(1g)

The objective function (1a) directs the optimization towards the lowest per-customer combined distance between clusters and charging points. Given that the number of clients is fixed and it is assumed that they always recharge at the closest point available, the sum in Eq. (1a) is indeed a metric for the Quality of Service (QoS) of the infrastructure as presented earlier in this section.

Note that (1a) adds up to the distance that the whole of the customers should travel to recharge their vehicles. Without any other constraint, that number could be as low as zero when every $x_{cs}=0$, which makes no sense, since no charge point is provisioned in that case. To prevent that, (1b) forces every cluster c to have one assigned station within $D_c$ range, because CS only contains (c, s) pairs where $d_{cs}\le D_c$ and there must be one and only one variable for which $x_{cs}=1$. Whenever more than one station s is within $D_c$ range, the optimization itself will choose that closest to c. Therefore, (1a) and (1b) combined guarantee that: i) every cluster c counts a charging point within $D_c$ range; ii) each cluster is optimally assigned for a given set of charging points; and iii) after consolidated, that assignment achieves the lowest total distance for all clients combined.

Since installing a station accounts no cost, an optimal configuration would assign every cluster to the nearest station possible, what most certainly leads to configurations where the limit of stations $M_s$ is exceeded. To prevent this violation, (1c) and (1d) are incorporated. Equations (1c) simply make a station $s\in S$ to be installed whether any cluster c is going to use it, since a variable $x_{cs}=1$ is enough to force $z_s=1$. Observe that although the integrality of $z_s$ variables is intrinsic, it should not be explicitly imposed as it is with $x_{cs}$ ones, which unlike $z_s$ variables are declared as boolean in (1g).

The problem with variables and constraints defined so far only concerns with the physical placement of charging points, not with other limits imposed by the electric grid. Since it has less constraints, this subproblem clearly is a relaxation of the complete one, and its optimal solutions represent lower bounds of EV-CSL. Subtler is the fact that, since power station limits are set by the number of charge points assigned to them, not by the number of users, solutions to the previous relaxation might also be feasible in the complete problem, as long as the $M_s$ limit is low when compared with $mp_e$ values. This property is in fact exploded during the experimental evaluation, Sect. 5.

Power stations limits are incorporated into the problem, to get to the full version, as follows. Equations (1e) are equivalent to (1b), except that in this case, the assignment of a charging point $s\in S$ to a power-station $e\in E$ within $D_e$ range (captured by variables in ES set) is triggered if and only if that point is to be installed (i.e. only if $z_s=1$). Finally, Eqs. (1f) guarantee that no station $e\in E$ is assigned with a number of charging points higher than its limit $mp_e$.

3 Related Work

The optimal location of electric vehicle charging stations has been a relevant problem since the emergence of a renewed interest in electric transportation infrastructures, in the early 21st century.

Frade et al. [10] applied a maximal covering model to maximize the demand within a maximum desirable distance, assuming that coverage decays beyond that threshold distance. A MIP model was proposed, including a penalty term to prevent the installation of unnecessary supply points. The model was evaluated on four scenarios in Lisbon, Portugal, installing up to 324 supply points in 43 charging stations in a higher-demand scenario. Accurate covered demand results were computed, providing an acceptable level of service. Wagner et al. [17] proposed a business intelligence model for EV-CSL to maximize demand coverage, based on potential trip destinations of vehicle owners, defined using urban data analysis [13]. An iterative method was proposed to find optimal locations using penalties to define ranks for points of interest and a MILP model solved in CPLEX. The proposed model achieved promising results on two case studies from Amsterdam and Brussels. Chen et al. [5] proposed a MILP formulation for locating charging stations minimizing the total walking distance according to parking patterns estimated using real urban data. The model was evaluated on a case study on 218 zones of Seattle, USA. Results achieved good accessibility: locating 20 charging station the walking distance was 1.1 km (average) and 3 km (maximum), whereas almost 80% of the demand was fulfilled.

Cavadas et al. [4] proposed a MIP model for EV-CSL to maximize the satisfied demand subject to a maximum budget constraint, considering the activity patterns of travelers. A multi-period formulation was introduced to model time intervals within a day. The model was evaluated in a small real scenario in Coimbra, Portugal, with just nine stations and four charging points each, to be installed on 129 candidate locations. Accurate solutions were computed, improving over the real configuration of EV charging stations installed in the city. Brandstätter et al. [2] proposed an ILP model for EV-CSL to maximize economic benefits in a car-sharing system, considering stochastic demands. The model was validated on medium-size synthetic scenarios and real world instances from Vienna (up to 693 potential locations). For Vienna, the exact approach was only able to solve instances for eight central districts of the city, whereas an heuristic method was applied for larger problem instances. Solutions confirmed the economic viability of implementing a electric car-sharing system.

Çalik and Fortz [3] proposed a MILP formulation for EV-CSL to maximize the profit of a public one-way electric cars system. The model and two relaxations were studied for 63 instances in New York, USA, with 85 potential locations for installing non-identical charging stations. The impact of cost changes in the number of stations was studied. Bian et al. [1] proposed a GIS-based approach for EV-CSL to maximize the profit. GIS was applied to determine the probability for users to charge their EV in different areas, using relevant traffic information. The model was evaluated in a small case study in Västerås, Sweden, with 268 square zones. Two scenarios were studied, adding three and ten new charging stations to 40 already installed in the city. When adding three stations, the best option was selecting fast chargers in commercial areas, whereas slow chargers installed in residential areas were better when including ten stations.

Lin et al. [12] proposed MILP model based on Geographic Information System (GIS) to optimally select the location and the size EVCS in urban scenarios. The MILP model is defined to maximize the economical profits of installing new charging stations, which are computed according to the charging demand based on the traffic flow data, charging profiles, and city land-use classification. In order to compute the charging demand, the authors generated an aggregated charging demand profile of the EVs based on the real-world travel data in National Household Travel Survey and charging behaviors. These daily charging behaviors, for each charging type of location, are represented by 24 hourly charging demands. GIS is employed to calculate the charging demand in different locations by taking into account traffic flow and land-use classifications (e.g., residential with villa, residential with apartment, working, etc.). In this study, it is assumed that a charging station will only serve the demands in specific given area. In turn, there is defined an acceptable walking distance from the charging station (parking lot) to the destination of the user. The researchers take into account the costs of a new station (which could include fast and slow chargers). Thus, the costs of a station consist of an aggregation of the economical costs of the equipment, installation, rent, maintenance and operation, and electricity consumption, which depend on the number and the type of chargers installed chargers. The optimization problem objective (the economical profits of deploying the new stations) is computed by subtracting the costs of locating the new charging station to the revenues of charging EVs. The proposed approach was evaluated over an area of 67 km$^{2}$ of Västerås, Sweden. Västerås had a population of 119 372 people, there were 44 192 personal cars, and the city had 324 plug-in EVs charging stations. The authors defined 532 tentative charging stations. The experimental analyses evaluated only the proposed method over four scenarios: installing three, five, ten, and 15 new charging stations. The results show that the proposed approach was able to provide charging station locations that provided competitive profits.

The EV-CSL problem and related variants have been also solved using metaheuristic approaches, due to the inherent complexity of specific variants using complex formulations or even simulations for solution evaluation.

In this line of work, this article contributes with an exact solution to EV-CSL, taking advantage of our expertise on location problems in the context of smart cities, including roadside infrastructure for vehicular networks [14], stations for public bicycles [6], bus stops [8], and waste bins [16], among other relevant problems. Our research demonstrates that a simple MILP formulation of EV-CSL can be solved with an exact method for medium-sized instances, and we solve a real-life scenario modeling the current reality in the city of Málaga.

4 The Proposed Optimization Approach

This section elaborates upon the developments implemented to solve variants of the EV-CSL. The previous approach to solve this problem relied on metaheuristics to find good-quality solutions for real-world instances [7]. Conversely, this work presents how exact methods have proven to be successful to solve the Mathematical Programming formulation for the previously studied instances, as well as over many others of such size.

A couple of tools were used along the development process. The optimization toolkit of MATLAB (release R2015a-8.5.0) was used in early stages of the work, mainly to validate the general formulation over a manually crafted test-set with relatively few variables. However, real-world instances solved in this article are far beyond capabilities of these tools. The number of $x_{cs}$ variables could be as high as $M\times N,$ which in some instances (e.g. $D_c=$ 8000 m) reaches almost six and a half million integer variables.

To cope with the size of instances for the application case, IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.6.3.0 was used as the optimization tool. The total time to optimal required by this solver to find solution was always below two hours. As we see later in this document, total times were quite below that value in general. It is worth mentioning that by optimal we mean: within the default GAP tolerance, which is set to the default value for the MIP solver (i.e. 0.01%). The GAP corresponds to the relative difference between the best integer solution found and the best upper bound estimated up to that moment, namely $(f(x)-bestBound)/f(x)$, where x is a feasible solution, f(x) is its objective function value, and bestBound is the higher lowest bound found for the optimum value. For the interface between the large instance data-sets and the solver, we developed a C++ program to read data and convert them to CPLEX LP-format. Afterwards, those LP files were launched in computing resources of the National Supercomputing Center, Uruguay (Cluster-UY) [15].

5 Experimental Validation

This section reports the experimental evaluation of the proposed exact approach for solving the EV-CSL problem over realistic instances in Málaga, Spain.

5.1 Methodology

The methodology applied in the experimental validation of the proposed exact methods is described next.

Analysis. Three relevant analysis are developed. First, the relaxed problem variant flexible (without including constraints defined by Eqs. (1e) and (1f)) is evaluated for a set of realistic instances, varying the maximum number of charging points to be deployed, $M_s$. Then, for the relaxed problem variant, results are compared with the corresponding previous EA applied to the problem [7]. Finally, the full (more realistic) problem variant, including the constraints that model the supply of the electrical grid (defined by Eqs. (1e) and (1f)) is studied.

Metrics. Relevant metrics are considered in the evaluation of the computed solutions. On the one hand, the objective function values account for the per-customer combined distance between clusters and their nearest charging point. On the other hand, other relevant QoS-related metrics are considered, such as the average and maximum distance a customer must travel for charging. In turn, the installation cost of the electric charging stations is also evaluated, according to a simplified cost model developed for the analysis. The cost model is based on real infrastructure installation costs (including the cost of the charger, civil infrastructure works, electrical installation, signaling, security, and legalization). A semi-rapid charger is considered, with a power of 22 kW and a cost of 10 500 €. In addition, the cost of the connection from the charging point to the corresponding electrical substation is added.

For the comparison with the previous EA for the problem, the GAP metric is used to evaluate the differences in the computed objective function values.

Fig. 1.

Potential locations for charging stations in Málaga (Color figure online)

Problem Instances. Two set of instances are considered in the evaluation of the proposed exact approach for EV-CSL:

• For the evaluation of the exact approach on both the relaxed and full versions, a constant threshold distance of $D_c$ = 2500 m is used, assumed as a reasonable distance citizens are willing to travel to charge their electric vehicles. Setting $D_c$ fixes in turn the set of variables of the problem. The value of $M_s$ varies from 20 to 80. Whenever Eqs. (1e) and (1f) are dismissed from the full version (Eqs. (1a)–(1g)), a relaxation is obtained, no matter what the dataset is. However, along the sequence of problem instances previously introduced and since $D_c$ is fixed along them, as $M_s$ increases, either version of the problem is in turn a relaxation of the previous problem instance. This is because the only difference between any instance and the following is on the right-hand side of Eq. (1d), which is exactly one unit larger than the previous. Hence, as $M_s$ increases, the optimal objective can only decrease, and whatever solution for any prior instance previously tackled could be used as an initial feasible solution for the current, a property that whether used helps to improve the performance of the solver.

• For the comparison with results computed using the previous EA, instances reported in our previous work [7] are used. In these instances, both the values of $M_s$ and $D_c$ vary simultaneously, so no nesting exists among problems.

Regarding geographical information, both sets of instances were built considering real data for the city of Málaga. A total number of $M_s$ = 33.550 potential locations for charging points are considered. In turn, 363 clusters and 14 electric substations are considered. Figure 1 presents the potential locations over the map of Málaga (green dots) and the electric substation location (blue squares).

Numerical Results. This section, discusses the results of the proposed exact approach for EV-CSL on the relaxed version and compares them against the results obtained by the previous EA [7]. Then, it presents the results provided by the proposed exact approach on the full version of the problem.

Tables 1 and 3 reports the results for the relaxed and full versions of the problem, Reported values are: the total distance between clusters and charging points ($f_{\text {BEST}}$), the economical cost of deploying that solution in euros (cost), and the actual distance in meters between the clusters and the charging points in terms of average ($d_{\text {AVG}}$) and maximum ($d_{\text {MAX}}$) for each $M_s$.

Table 1. Experimental results for the relaxed version of the problem.

Results in Table 1 show that as the number of charging points increases ($M_s$) the combined distance between clusters and charging points ($f_{\text {BEST}}$) decreases, as expected. $d_{\text {MAX}}$ is slightly below 2500 m in all cases, so, optimal solutions tend to assign some clusters very close to the distance threshold.

Fig. 2.

Distance and the economical cost on the relaxed variation. (Color figure online)

The reduction in the calculated $f_{\text {BEST}}$ values when increasing $M_s$ implies that citizens generally travel shorter distances to charge their cars. Values of $d_{\text {AVG}}$ and $d_{\text {MAX}}$ in Table 1 show that the average distances decrease as the number of charging points increases. However, not all citizens benefit when adding only one charging point. For this reason, the maximum distance values do not improve in the same way as the average (it is always close to threshold distance of $D_c$ = 2500 m). This is illustrated in Fig. 3 that shows the distribution of the charging points through the real map of Málaga for different values of $M_s$. Even though the exact method distributes the charging points through the whole map as $M_s$ increases, there are areas of the city that are not targeted because they have low population densities. This is mainly the objective to be optimized defined in Sect. 2 is the combined distance (see Eq. (1a)) that takes into account the population density of the clusters, and therefore, the method prioritizes the areas of the city with higher population densities.

Fig. 3.

Solutions computed by the proposed exact approach for the relaxed version of the problem over map of Málaga for different $M_s$.

Regarding the economical cost of deploying the solutions, Fig. 2 illustrates $f_{\text {BEST}}$ values, i.e., the combined distance, given the economical cost as blue circles. This figure can be seen as a Pareto Front of an optimization problem in which the combined distance and the economical costs are two objectives to be minimized. Thus, the points close to the red row represent the solutions with the best trade-off between these two objectives. The figure shows that for solutions with fewer charging points (left side of the figure), a smaller economical investment gets a higher improvement in the QoS metric than when there are already a considerable number of stations (right side of the figure).

Even though the considered economical cost model takes into account the cost of the infrastructure of the charging point and the cost of wiring the charging point the cost behaves as a linear monotonic function increasing with respect to $M_s$ because the cost of the infrastructure is significantly higher than the wiring cost and contributes much more to the cost of the proposed solution.

Table 2. GAP between the proposed exact approach and the EA.

Results computed by the exact method are compared against the previous EA, for $M_s = \{10, 20, 30, 40, 50\}$ [7]. Table 2 reports the mean GAP between the exact solution and all computed solutions by the EA for the same $M_s$, and the best GAP, regarding the best EA solution. According to results in Table 2, the exact approach is better than the EA. The GAPs are always positive and they increase as $M_s$ increases, takes advantage of installing more charging points.

Exact solutions are the same for the full version and the relaxed version of the problem for $M_s$ from 20 to 59, because they fulfill the constraints. However, solutions found for the greater of values of $M_s$ get slightly higher $f_{\text {BEST}}$, i.e., less competitive QoS. This behavior is because when the number of charging points in the instance does not exceed a given threshold (i.e., $M_s<$ 60), the exact approach is able to locate the charging points in any place (as in the relaxed version of the problem), without exceeding power station limits. However, as $M_s$ grows the exact approach distributes in a different way the charging points, because solutions for the relaxed version of the problem are not feasible (they do not fulfill the power stations limit). Thus, the exact method in the full version locates the charging points in the way they are close to the high population areas but also the charging points are wired to different electric substations.

Table 3. Experimental results for the full version of the problem. Solutions when $M_s<60$ always match those reported in Table 1.

Figure 4 shows the solutions deployed through the city for $M_s=$ 60 and $M_s=$ 80. These two solutions distribute more the charging points over the city in comparison with the solutions computed for the flexible version of the problem (which concentrate most of the charging points in the same Downtown locations).

Fig. 4.

Solutions computed by the exact approach for the full version of the problem over map of Málaga for different $M_s$.

Figure 5 plots ($f_{\text {BEST}}$) and economical cost results. Blue circles illustrate identical solutions for both versions of the problem, while gray squares represent different solutions. Whenever solutions in both versions do not match, that of the full version must be higher since the other is its relaxation. Those differences exist for $60 \le M_s\le 80$ only, but they are relatively negligible, and in fact, it is necessary to zoom into that range to notice any difference as is in Fig. 6.

Fig. 5.

Distance and the economical cost on restricted variation. (Color figure online)

Fig. 6.

Solutions of both problem variations (60 $\le$ $M_s$ $\le$ 80).

6 Conclusions and Future Work

Proposing efficient and effective networks of EV charging points has become a must in modern urban areas to allow easy adoption of sustainable mobility based on EVs. This article presented an exact optimization approach for solving a new variant of the EV-CSL problem defined on a real city, Málaga. This new variant is more realistic because it explicitly models the actual energy supply constraints and it takes them into account to compute the solutions.

Results of the experimental evaluation on a set of real-world instances of Málaga show that the proposed approach is competitive to address EV-CSL for the constrained and the flexible versions of the problem. The exact optimization approach based on ILP is able to automatically distribute the charging points along the city taking into account the real distribution of the tentative EV users, while optimizing the QoS of the whole charging points network.

Besides, the proposed exact approach has shown being more competitive than a GA proposed in previous research ta address EV-CSL. It is able to improve the QoS by 17,74% in instances with 50 charging points.

The main lines for future work are related to improve the realism of the model by considering general citizen’s mobility behavior, the location of points of interest, and aspects related to the installation costs; to the definition of the EV-CSL problem by taking into account other objectives rather than QoS, such as installation costs; and to the definition of real instances over other cities.