Keywords

1 Introduction

With increasing pressures on the environment and shortages of resources, energy saving has become of ever-increasing importance and concern. Electric vehicles (EV) have consequently come into focus of governments and enterprises, because they have the characteristics of energy saving and environmental protection. It is so much more energy efficient, for example, to use biogas in electric power plants rather than as vehicle fuel. Thus, to varying degrees, governments are promoting EVs across by providing a range of subsidies and other benefits, both on the demand and supply side. Reducing emissions is one of the key reasons, but other considerations, for instance, improving road environment such as noise level also play a role. However, despite this governmental support and, in many circumstances, a host of positive local market conditions (high capacity of electricity system and grids, environmentally aware citizens, etc.), the adoption rates of EVs have fallen short of initial goals. EV sales are lower than environmental awareness would predict. User preferences, their unwillingness to pay for an EV, and range anxiety are the most import reasons for this. A recent study has found that travel range, cost, and charging infrastructure are the three main concerns for potential electric vehicle buyers [13].

Users of EVs expect high quality and high service level. In this context, service level and quality are defined in terms of battery capacity, energy price, battery cost, charging delay, and the impact of the charging method on the battery performance [21]. Acceptance of EVs will depend to a large extent on how well these vehicles meet user expectations. One main shortcoming of EVs today is their limited range, which is around 100 miles [21]. In order to overcome this limitation, power supply stations (PSs) are needed to extend the driving range and comfort the users. Consequently, providing adequate infrastructure becomes a necessity for increasing the adaptation rate of EVs. Providing high-quality infrastructure leads to decreasing the user’s range anxiety, increasing thus the public motivation for this technology. In [21], the charging deployment station together with mobility modeling were identified as the most critical task for the widespread adoption of the EVs. Previous studies have shown that for EV the user confidence rises due to the sole presence of charging stations, as it causes users to be significantly less concerned about reaching their destinations with a limited range car [4, 14].

There are two basic technologies for providing EVs with electric supply infrastructure. The first includes charging stations, slow or fast, at which users park their EVs for a time interval of several minutes to few hours in order to recharge their batteries. While it is not difficult to park the EVs at work place, home, or other public charging points for a few hours or overnight, it is impractical to station the car for a recharge in the middle of a long trip. The second technology is based on battery-swapping stations and aims to overcome this time obstacle. In a battery-swapping facility, users swap batteries during their trips without even getting out of their vehicles in less than 5 min. The depleted batteries are then recharged at the stations and later swapped for depleted batteries in other arriving EVs. Both methods require an important investment and, therefore, it is important to assist private and public entities to locate charging infrastructure efficiently.

How to optimize the power supply stations for EVs becomes one of the problems that enterprises and authorities at both national and local level should be focusing on. The present paper presents the same recent developments in the field and discusses some challenges that the decision makers should address.

2 Demand Forecasting

In order to maximize the usability and minimize the relevant operating cost, it is mandatory to design a plant where the charging stations can serve the commuters’ demand. Mismatch of demand and infrastructure can lead to underutilized facilities. Knowledge of the day-ahead demand is critical for the system to be able to prevent faults in the network and stability issues. The accuracy of demand forecasting is important to the planning and operational decisions taken by utility companies. Unreliable demand prediction has adverse effects both to the proper utilization of the capabilities of the network and the robustness of the system.

In the early literature, there have been proposed various demand estimation methodologies which in general can be categorized into three broader categories.

The literature that belongs to the first category utilizes users’ preferences such as parking behaviour, distance traveled, and point of charging in order to estimate demand for charging. The basic assumption that underlies the research works which use the parking behaviour of the drivers is that users usually tend to charge when parking due to the significantly long charging time. Chen et al. [6] employed a regression model that predicts parking demand as en estimation of demand for charging. Parking demand is also used to simulate demand of charging in [51] and [48].

The second category assumes that the demand is mainly influenced by the traffic flow produced by regional EVs and the comprehensive distance from candidate station to every main road. In the related literature, a number of methods have been proposed for the prediction of the EV load. Lp et al. [37] propose a two-step model that quantifies traffic information into data points and subsequently converge these data points into demand clusters over an urban area. This hierarchical cluster analysis is concluded with an optimization in order to maximize the usability and minimize the relevant operating costs while considering various constraints and cost factors. In [25, 29], EVs power demand is predicted based on the driving patterns from the Danish National Travel Survey while in [26] driving patterns from travel survey of Finland are also used for modeling the EVs demand.

The third category assumes that the characteristics of the vehicles affect the demand for charging. Authors in [5] consider the characteristics of vehicles and user driving, and adopt a Monte Carlo method to simulate the daily charging demand of different places and penetration and calculate the distribution system design parameters.

The Stochastic nature of the EV charging demand parameters dictates the use of advanced forecasting methods such as neural networks and support vector machines, which are able to decode all the patterns and produce an accurate estimation of the future EV charging demand. Lifestyle, age group, and socioeconomic circumstances play a major role on who has adopted or will adopt such vehicles, affecting where to plan locations for charging stations. Therefore, market surveys along with data mining techniques such as cluster analysis and classification are able to recognize all the patterns related to the drivers’ preferences and model their demand. In [49], the interpretive structural modeling (ISM) and the methodology of FMICMAC (fuzzy cross-impact matrix multiplication applied to classification) were employed in order to identify the influence factors, as well as the driving and dependence power of these factors, and to analyse the interactions among them. Moreover, rankings of the identified factors have also been obtained. The data used for the analysis were obtained by interviewing market experts. The study in [3] introduced a stochastic method to use driver-surveyed data from 76 vehicles in a one-year period to predict PEV charging profiles in different regions in the city of Winnipeg, Canada.

In [40], a demand forecast method based on big data technologies considering historical traffic data and weather data of South Korea is proposed. The forecasting processes include a cluster analysis to classify traffic patterns, a relational analysis to identify influential factors, and a decision tree to establish classification criteria. The prediction mechanism introduced in [35] combines classification methodologies and regression analysis along with the Bass diffusion model in order to provide a prediction mechanism for charging demand.

Artificial intelligence methodologies have been employed in the literature of charging demand forecasting. In [31], an Artificial Neural Network (ANN)-based model is proposed for predicting the charging profiles of EVs connected to a building. The ANN model considers the previous charging profiles, initial State of Charge (SOC), and final SOC for predicting the charging profile of the EV, while [52] establishes three types of daily load forecasting model, including BP neural network, RBF neural network, and GM(l, 1) model, based on data obtained based on the daily load data of Beijing Olympic Games EV Charging Station.

A short-term load forecast model using support vector machines has been developed in [53] to evaluate the accuracy of the method comparison with a Monte Carlo forecasting technique is performed, while in [7] the concept of Support Vector Regression (SVR) is used for the development of a forecasting model able to predict short-term demand, and time series reconstruction is used to restore the original features of the load in this method.

In [54], four different artificial intelligence algorithms, namely decision tables, decision trees, ANN, and SVM were used for predicting load demand. The corresponding models were tested using real data obtained by the ECOtality project, USA, and real charging data from public charging station in France. Authors in [38] proposed a framework for fast prediction of the EV load at the charging outlet level for cell phone application based on three different algorithms, K-Nearest Neighbour, Weighted k-Nearest Neighbour, and Lazy Learning. These algorithms were applied to data obtained from charging stations located on the UCLA campus. The results indicated that the k-Nearest Neighbour (kNN) algorithm with k = 1 had a better accuracy. The same dataset were used for prediction models based on algorithms such as Modified Pattern Sequence-based Forecasting (MPSF), SVR, and Random Forest in [39], where the authors concluded that selecting the appropriate algorithm for an application depends on the trade-off between accuracy and computational time. [7], using features such as nearby points of interest (PoI) (shopping malls, institutions, restaurants, hospitals, etc.) and traffic density at nearby road junction, presents a multiview learning-based regression framework for the charging demand prediction, which uses CCA in a supervised setting as a multivariate regression tool.

3 Optimal Location of Charging Stations

There are different approaches in the literature to determine the optimal power supply point locations for electric vehicles. Most of them are based on existing location models, while their solution approaches range from classical linear or no linear programming techniques to heuristic and metaheuristic methodologies such as genetic algorithms, particle swarm optimization, and ant colony optimization. It is in general accepted that EV charging station location belongs to the broader class of refueling-infrastructure problems. The existing literature on refueling-infrastructure problems can be categorized as using two modeling techniques: (a) point demand location models and (b) flow-capturing.

3.1 Point Demand Location Models

The basic assumption of these models is that the demand is located at distinct places, i.e. mall, parkings, etc., and the basic unit of the demand is a polygonal area-based spatial object in a geographical space [9]. Most of these approaches are based on the classical location problems (set covering problem, maximum covering problem, p-centre problem, and p-median problem [12]). The point demand location models have been applied for locating charging facilities under the assumption that the charging process takes place at destination.

In [15], the well-known maximum covering model [10] is used to locate a certain number of charging stations in the metropolitan area of Lisbon, Portugal. Zhang et al. [55] solved a set covering problem to minimize the number of CSs in California. The location problem considered in [2] is also a maximum covering problem. The authors presented a method for finding optimal regions for placing a predefined number of charging stations. The simple structure of the optimization problem allows an exact solution.

Sharma et al. [42] proposed a planning model of fast-charging stations based on the covering location principle. The aim of their model was to maximize the fast-charging serviceability subject to various constraints, i.e. the traffic service distance, the limit of waiting during the rush hour period, and the power distribution system. A novel hybrid artificial swarm optimization technique incorporating the beneficial characteristics of ant colony optimization and bees algorithm is developed to find the optimal locations of the stations.

In [28], the maximum set covering model is applied to identify electric taxi charging locations for the case of Seoul considering the current taxi travel patterns identified by taxi DTG data for the case of Seoul, while in [32] the maximum set covering model is used for locating fast-charging infrastructure for electric buses.

In [20], the set covering model, the maximal covering location model, and the p-median model were tested aiming to provide policymakers with a comprehensive analysis to better understand the effectiveness of these traditional models for locating EV charging facilities. The results show that the p-median solutions are more effective than the other two models in the sense that the charging stations are closer to the communities with higher EV demand, and, therefore, the majority of EV users have more convenient access to the charging facilities.

The p-centre location and allocation model is utilized in order to get the optimal site and size for both slow- and fast-charging stations in [23]. Applications of the p-media model can be found in [6, 24, 27].

Authors in [51] develop a simulation-optimization model that determines the optimal location of slow-charging stations to maximize their use by privately owned electric vehicles considering EV charging times. Assuming that the demand occurs at destination, the optimization model determines the chargers to place at each candidate location, with the objective of maximizing fleet-wide EV charging.

3.2 Flow Covering Models

The flow-based approach captures electric vehicle traffic by inserting recharging stations on traffic routes. Each traffic flow is defined by an origin–destination (OD) pair. They are based on the well-known Flow-Capturing Location-Allocation Model (FCLM), introduced by [22], which is actually an extension of the maximum covering problem to accommodate the demand of network flow. The objective of the model is to locate facilities to capture as much as possible of the flow. An important aspect of the FCLM is that the demand of any OD is captured by a single facility. FCLM was further extended by [30] in order to capture the limited driving range of alternative fuel vehicle the corresponding problem is the Flow Refueling Location Model (FRLM).

A flow-capturing model to minimize the total cost of locating stations is proposed in [47]. The authors in [11] presented two optimization models for location of fast-charging stations. The first model aims to maximize the public service provided by stations, while the second considers the incurred cost for providing it. Models’ effectiveness is illustrated in a case study of the City of Barcelona.

The FRLM has been applied to real-world network including locating scooter recharge stations [45], and battery exchange stations in the tourism transport [46]. In order to solve the problem in [1], a Benders decomposition approach is employed.

The model proposed in [41] presented a new mixed-integer formulation of the FRLM aiming at handling larger networks and they proved that this new formulation is able to obtain an optimal solution much faster than the previous original model. The reformulation of the problem presented in [44] was aiming at capturing the effects of the varying driving range into the optimal location of charging facilities.

The multiperiod optimal charging station location problem is presented in [8], and for the solution of the problem three different solution procedures were tested using real traffic flow data of the Korean Expressway network. The multipath refueling location model (MPRLM), in which users could utilize multiple deviation paths between all OD pairs on the network, is introduced in [34]. The authors developed also two greedy heuristics, the greedy-adding and greedy-adding with extension algorithm for the solution of the problem. These algorithms are shown to be efficient and effective to solve the model for the Sioux Falls network. The heuristics are also applied to locate electric vehicle charging stations in the state of South Carolina. A dynamic multiperiod multipath refueling-location model to optimize an EV charging network was proposed in [36]. The objective of the model is to minimize the cost of installing new stations and relocating existing stations focusing on intercity trips.

A game theoretical approach is adopted in [17] to investigate the interactions among availability of public charging opportunism, destination, and route choices of EVs. As a result, the paper presents an equilibrium framework capturing the interactions among the availability of public charging opportunities. A convex mathematical program is formulated to describe the equilibrium state. Built upon the proposed equilibrium analysis framework, the problem of optimally allocating public charging stations is formulated as a mathematical program with complementarity constraints and is solved by an active-set algorithm. Additionally, [18] presented the network equilibrium models for battery electric vehicles. The network equilibrium conditions are defined and formulated as a mathematical program. An iterative procedure is proposed to solve the program to find the equilibrium flow pattern. He et al. [19] present an equilibrium framework capturing the interactions among the availability of public charging opportunities, route choice, and price of electricity. This equilibrium-based framework is then used to determine the optimal allocation of public charging stations to maximize the social welfare.

The stochastic nature of the flow is also considered in the literature of Flow Covering Models. Tan and Lin [43] assumed that customer demands, which are represented as the flows on the paths, change over time. In order to model the stochastic nature of the charging demand, they presented a stochastic mixed-integer two-stage model. Optimal locations of the charging stations are decided in the first stage before uncertain customer demands are included and treated as a set of possible scenarios in the second stage. The first stage contains only binary variables and the second stage is a linear problem with continuous variables.

The authors in [50] develop a model to optimize the location of public fast-charging stations for electric vehicles under the assumption of uncertain charging demand. A stochastic flow-capturing location model (SFCLM) is consequently formulated, and a sample-average approximation method and an averaged two-replication procedure are used to solve the problem and estimate the solution quality. The usability of the model is tested using a Central-Ohio-based case study.

The study in [33] proposes an optimization algorithm based on the extended FRLM with a probabilistic consideration of travel range referred as flow-refueling location model with an uncertain travel range (FRLMwU). The resulting mathematical formulation for FRLMwU is a mixed-integer non-linear programming (MINLP) problem. A Benders decomposition and column generation-based algorithm is then developed for the solution of the problem.

4 Challenges

The present chapter provided information on recent research trends and the most important issues in the design of optimization-based models for locating charging station. Having the chargers available in locations where people need to use them is going to be the key in the adoption of electric vehicles. For achieving this, the researchers are demanding to project the controllers for charging infrastructure, and numerous literature on the optimization-based location models were brought out. In this literature, although vast, there exist still some open questions that the researchers should find answers to:

Cooperation-collaboration between users and providers :

In the existing literature, the drivers (users) are treated separately from the providers (who install the infrastructure), so their behaviour is reactive rather than coordinative. The idea of cooperation in decision-making process arises due to its distributed nature, that is when its independent agents realize the benefits gained of through their collaboration. Consequently, the selection of the appropriate mechanism to coordinate these decision domains becomes a challenge. Such a mechanism could be able to induce self-interest agents to behave in ways that are best for the entire chain network. Usually, two issues arise in this context: the determination of binding agreements between members, and the incentives to make partners to actually share information. However, in these cooperative activities there are certain costs that partners have to incur to establish and maintain cooperation. The main challenge is to determine a framework to minimize the total cost and to allocate it to the agents such that none of them has the incentive to abort collaboration.

Robust Demand Prediction :

In order to maximize the usability and minimize the relevant operating cost, it is mandatory to design a plant where the charging stations can serve the commuters’ demand. Mismatch of demand and infrastructure can lead to underutilized facilities. Knowledge of the day-ahead demand is critical for the system to be able to prevent faults in the network and stability issues. The accuracy of demand forecasting is important to the planning and operational decisions taken by utility companies. Unreliable demand prediction has adverse effects both to the proper utilization of the capabilities of the network and the robustness of the system. Toward this direction, alternative approaches based on neural networks, support vector machines, and other concepts have been used to forecast charging demand. However, robust optimization provides an alternative approach. The problem of computing a robust parameter is usually formulated as a computationally intensive combinatorial optimization problem. Therefore, future demand prediction based on robust optimization will require the development of multistep approaches which involve the selection of an appropriate parametric function incorporating trends, seasonal fluctuations, and phase transition, fitting to the data using nonlinear regression and profit optimization in order to obtain the parameter models. The development of such approaches is a challenge that the researchers should be dealing with.

Modeling the effect of regional and governmental intervention :

The investigation of how such a decision process can be affected by regional and governmental intervention and policies as well as by marketing and improvement of services on the side of the enterprises is a subject that has received little attention in the literature. Investigating the effect of fiscal and regulatory changes on the decision-making process of the individual company is of utmost importance since transportation paradoxes may lead to results opposite to intended ones. The development of sophisticated game theoretic approaches will be a helpful instrument toward this direction. Game theory enters by influencing user choices through governmental incentives and policies as well as enterprise marketing. Investigation of the existences of optimality conditions and development of solution algorithms are questions that seek for an answer.

Use of renewable resources :

The increasing trend observed in the use of EVs increases the demand for electricity which in turn increases emissions due to fossil-generated electricity. However, EVs have been promoted as a mean to achieve a carbon-free transportation sector. Therefore, in order to improve the ability and the performance of the electric vehicles charging station, renewable energy resources should be integrated into their systems as well. This will also have the added benefit of making EV with greener credentials as their environmental impact depends on the primary source of energy. Thus, the proper integration of diverse renewable energy source for charging electric vehicles is the future of the charging stations optimization.