Digital Marketplaces Unleashed

by Claudia Linnhoff-Popien

  68. A Generic Model for Coordinating the Individual Energy Demand of Electric Vehicles: Optimizing the Coordination Problem Between Electric Vehicles and Charging Points with the Implementation of a Genetic Algorithm

  Malte Zuch1 , Arne Koschel1 and Andreas Hausotter1

  (1)University of Applied Sciences and Arts in Hanover, Hanover, Germany

  Malte Zuch (Corresponding author)

  Email: malte.zuch@hs-hannover.de

  Arne Koschel

  Email: arne.koschel@hs-hannover.de

  Andreas Hausotter

  Email: andreas.hausotter@hs-hannover.de

  68.1 Introduction

  The market of electric vehicles is globally growing. Just for Germany [1, p. 10] the German government expects one million electric (and plug in hybrid) vehicles for the year 2020 in Germany. Worldwide, the market will grow to about 20 million electric vehicles by 2020 [2, p. 9]. Modern vehicles embed several sensors and communication technologies and are able to share data. So finally, even vehicles become digitalized. Their digitalization offers the possibility to add even more value to the product “electric vehicle”. The direct integration of advanced services into vehicles, like collaborative traffic management services, will lead to a new experience of mobility. This is provided by sharing information amongst the vehicles. Especially the growing market of electric vehicles will lead to new “e‐mobility data scenarios”. Electric vehicles have to be recharged frequently with electric power. This could be done at home or at public charging points.

  Depending on the vehicle’s actual location, the driver will look for unoccupied charging points in the near environment. If a large number of drivers of electric vehicles will look up on their own for unoccupied charging points, this will lead to mutual blocking between the drivers. To reduce the risk of driving to occupied charging points, a collaborative coordination system is required, which is able to handle individual charging requests and consider individual constraints. Therefore, a generic approach of handling such demands will be introduced and a genetic algorithm will be applied exemplary to optimize the general coordination problem between vehicles and charging points to reduce overall waiting times.

  But especially for Germany, the current generation of vehicles is still restricted concerning their digitalization. The possibilities to integrate additional digital services with or into such vehicles, for example, real‐time information services about charging points including prices or utilization, are still limited.

  The vehicle manufacturers are still restricting the board systems of the vehicles. Only some board systems have already integrated such charging point finding services. But those services are still limited by the manufacturer. They are not showing the whole market data with all charging points to the drivers and the resulting limited information is often out of date.

  So today, drivers of vehicles have to use smartphone apps to integrate additional services, which are based on data with a better quality. These restrictions are motivating to investigate the benefit of collaborative coordination systems within this work.

  For the near future, there is a noticeable trend within the automotive industry to become more open, concerning the integration of additional third party digital services like such a collaborative coordination system. Most of the leading companies of the automotive industry have already announced to integrate standardized platforms, known and established from the smartphone market.

  The car manufacturer Daimler will integrate the Apple Carplay platform into their vehicles [3]. Volkswagen, Audi, and BMW are offering the possibility to integrate both leading platforms, Apple Carplay and Android Auto, into their vehicles [4–6].

  Summing up, more vehicles will become digitalized. This ongoing digitalization offers options to share and receive data while driving. So more vehicles will be able to share their positions and the state of charge of their batteries. Such data can be optimized in a collaborative manner.

  Today, drivers of electric vehicles simply do not have collaborative information about other drivers and do not know where other drivers could probably charge. This missing information amongst the drivers will lead to mutual blocking at already occupied charging points and will cause avoidable waiting times. Utilizing a collaborative coordination service could reduce waiting times to a significant degree.

  Within this work, such a collaborative coordination service will be presented. It will be compared to the default charging behavior of nowadays typical drivers, who are always driving to the nearest charging point in range. This behavior serves as general benchmark scenario, which will be compared with the scenario of a collaborative coordination. The latter is based on a genetic algorithm and uses the (now) shared information of the electric vehicles (position and state of charge). With this additional information, the genetic algorithm is utilized to recommend better charging points to the drivers with less occupation and waiting times. This optimization should lead to an improved situation of charging for all drivers, which is more efficient than the benchmark scenario.

  The next section presents the related work concerning this topic. Afterwards, the approach of the data model is explained, followed by the discussion of the general coordination problem and the approach to solve this problem with a genetic algorithm. The results of the genetic algorithm will be presented and discussed followed by a final conclusion.

  68.2 Prior and Related Work

  In prior work, the general architecture of a charging point information system as well as initial data partitioning methods have been described [7, p. 5]. The discussion about the potential risk of volatile loads in traffic coordination system during rush hour motivated to follow a matrix based calculation approach within this work. This approach allows to divide and distribute the data over several systems to compute the data in parallel.

  A coordination approach for plug‐in electric vehicles during their search for parking spaces and the resulting effect on smart grids is presented in [8, pp. 9, 10]. The resulting effect was considered within a simulation. It shows that there is a potential to stabilize smart grids by coordinating the energy demand of electric vehicles. Another work has also shown that loads in smart grids and general waiting times at charging points could be reduced up to 50% with the approach of “swarm intelligence (SI)” [9, pp. 9, 21]. Also the pricing of charging points could be adapted to gain efficiency within electro mobile coordination scenarios [10, pp. 88, 89].

  A dynamic pricing model for charging points shows the effects of adapting to different behaviors of drivers [11, p. 2]. Drivers of electric vehicles were separated into two groups, cooperative and selfish drivers with respect to dynamic prices of charging points. The coordination of those groups increased the profit of charging points by about 18% and has shown further potential of coordination systems [11, p. 2]. Another approach for PHEV‐vehicles (plug in hybrid electric vehicle) shows how to save 10% of energy and extend the driving range by a coordination system with route optimization [12, pp. 41, 42].

  Within long range scenarios, a further coordination approach for electric vehicles has been described including a route assistance system [13, p. 139]. The point of view of data partitioning is based on a static perimeter around the different charging points. Electric vehicles within this perimeter are considered as standard partition. Building of dynamic partitions is not considered, because the primary focus of this work is the dynamic rerouting over several charging points for long range routes. So, the mentioned related work focuses more on specific scenarios. None of this work attempts to describe a general approach with genetic algorithms, various and flexible preferences of the drivers and their individual behavior while searching for charging points and motivates to offer such a (basic) model within this work.

  In general, the whole market of communicating vehicles will produce a continuous data strea
m while asking a charging point information service for unoccupied charging points. Referring to those continuous data streams, a related “parallel complex event processing” model has been explained and realized a speedup factor by 14 × in [14, pp. 196, 200]. Such a model could also be used to support the handling of data within scenarios for the coordination of electric vehicles in parallel. Coordination approaches for electric vehicles could be seen as services, which support the drivers in finding (unoccupied) charging points. Those services can benefit from a uniform and generic representation and optimization of data within electro mobility traffic scenarios, which is part of this work.

  Therefore, the next section explains a general model to handle the data of electric vehicles in such a uniform and generic way in dependency of the actual states of charge and positions of the vehicles. This data model will be used to describe the general coordination problem. A genetic algorithm will be applied to optimize the coordination problem to recommend better vehicle‐charge‐point‐assignments to the drivers.

  68.3 The General Data Model of the Coordination Problem

  Electro mobility traffic scenarios are influenced by some elementary parameters. The number of electric vehicles and charging points, their locations, the state of charge and the average energy consumption of the vehicles: Number of electric vehicles:

  Number of charging points:

  State of charge in (kWh):

  Energy consumption of vehicles (kWh/km):

  Latitude of vehicles:

  Longitude of vehicles:

  Latitude of charging points:

  Longitude of charging points:

  The input parameters will be handled by matrices. Handling the data with matrices allows the representation of several vehicles and charging points in a uniform way. This uniform representation of data with matrices offers the possibility to divide the general vehicle coordination problem in sub‐matrices/partitions. So the general coordination problem of all vehicles over all cities could be separated with this matrix approach in sub‐matrices for single cities. Those sub‐matrices/partitions could be distributed over several computers to solve the general vehicle coordination problem in parallel for the individual cities. For example, solving the problem for New York and Moscow together makes no sense. The Atlantic Ocean prevents that electric vehicles in New York could build up a situation of competition with electric vehicles from Moscow during their search for unoccupied charging points. Dividing the problem for far away cities seems reasonable. But nearby cities will still interact with each other. So dividing the problem has to be done carefully and results in a tradeoff between gaining calculation speed and potentially cutting of additional information. Especially a matrix design offers the possibility to divide the problem easily. To solve this coordination problem, a general model is applied to process those input parameters within three steps. The first step prepares the latitude and longitude data for building matrices. The second step calculates with these matrices the distances between all vehicles and charging points. The third step summarizes the data in context of the actual states of charge of the electric vehicles and their remaining driving ranges. The resulting matrix includes the information, which charging points could be reached by which vehicles.

  This matrix is then utilized to optimize the vehicle coordination with a genetic algorithm. The matrix approach offers the possibility to integrate even more information for supporting such charging point coordination systems. For example, additional matrices with information of the prices of charging points or the behavior of the drivers and their individual preferences concerning energy prices and required charging power could be added. Those additional matrices could be integrated easily by overlaying the existing ones (explained in Sect. 68.3.2). This could achieve an even more accurate individual coordination of the vehicles. In the following, each of the aforementioned three steps is described in more detail.

  68.3.1 Step 1 – Preparing the Data in Matrix Form

  The one‐dimensional latitude and longitude vectors and will be expanded into two‐dimensional m × n matrices to calculate all possible combinations of distances at once. Therefore, the vehicle matrix is aligned vertically and the charging point matrix horizontally (s. Fig. 68.1).

  Fig. 68.1Preparation the data in matrix form

  The different horizontal and vertical alignment of the elements inside the matrices is necessary for the calculation of distances in step 2. By overlaying the horizontal and vertical aligned matrices, all combinations of distances between vehicles and charging points may be calculated at once (s. Fig. 68.2).

  Fig. 68.2Calculation of the distances between all electric vehicles and charging points

  With this design, even very large matrices might be divided and distributed easily over several computers to calculate huge amount of data quickly in parallel. Beside of the data preparation of the latitude and longitude vectors, a similar preparation is required for the vectors of the state of charge () and the individual energy consumption () of the electric vehicles. The actual state of charge of the batteries and the average energy consumption is leading to a limited driving range for all m electric vehicles:

  (68.1)

  All elements for all m vehicles will also be arranged into a m × n matrix by the following scheme for all n charging points:

  (68.2)

  This matrix R specifies the maximal driving range of all electric vehicles. It has the same dimensions as the aforementioned latitude and longitude matrices. The equality of dimensions allows an efficient calculation between the distance matrix D and the maximal driving range matrix R, explained in the next sections.

  68.3.2 Step 2 – Calculating the Distance Matrix

  With the data preparation in step 1, all possible distance combinations between all vehicles and charging points can be calculated at once with the single m × n matrix D (s. Fig. 68.2).

  This distance matrix D will be processed with the matrix of the maximal driving ranges R in the next section to identify the situation of competition and blocking amongst the vehicles, while they are searching for unoccupied charging points.

  68.3.3 Step 3 – Identifying the Potential of Blocking Amongst Vehicles

  The logical comparison between the matrices D and R from the previous sections will lead to the binary selection matrix Z. This matrix marks all possible combinations of vehicles and charging points, reachable with the actual state of charge of their batteries. Those combinations are building up the situation of competition and can cause blocking amongst the vehicles:

  (68.3)

  This competition matrix Z offers two main options to extract information. The extraction of row vectors contains the information which charging points are in range by a considered vehicle (row). The extraction of column vectors contains the information which vehicles are potentially demanding a considered charging point (column). Especially the extraction by column in combination with the distance matrix D could be used to identify possible situations of competition. If more than one driver is looking for the same charging point (column), only the driver with the shortest distance to the charging point will actually be able to charge right away, while all other drivers will be blocked by this firstly arriving vehicle (s. Fig. 68.3).

  Fig. 68.3Example of an electro mobile traffic situation of competition amongst vehicles

  The example in Fig. 68.3 shows a traffic situation with two vehicles F2 and F4 with a low state of charge and two vehicles F1 and F3 with a high state of charge. So, vehicle F1 and F3 have the option two choose between more than one charging point. Vehicle F2 and F4 have no choice concerning their low state of charge and have to charge at one particular charging point. If the vehicles won’t use a collaborative coordination service and if they would just drive to the nearest charging points in range, there would be a high risk of blocking between each oth
er.

  For this simple scenario, the calculated competition matrix Z is shown in Fig. 68.3 and includes all possible sets of competition. This matrix Z and the distance matrix D are the basic inputs for the coordination problem and will be used to optimize the coordination within the next section.

  68.4 Optimizing the Coordination Problem

  The general coordination problem was defined with the competition matrix Z and the distance matrix D in the last section. If drivers of electric vehicles are just driving to the nearest charging point in range, this could cause mutual blocking amongst the vehicles on arrival at the charging points.

  Alternatively, they could use a collaborative coordination service. Concerning their individual driving ranges, they could be guided by such a collaborative coordination service to alternative charging points in their individual range. This could minimize the blocking of other vehicles, which have less charging options reasoned by their low state of charge. This information is integrated in the competition matrix Z, which already includes the alternative charging options (rows) of the vehicles. The goal is to recommend optimized “vehicle‐to‐charge‐point‐assignments” to provide a better situation of charging for all drivers. These optimized recommendations of charging points are represented by the binary configuration matrix X. Within this matrix, the value “1” marks recommended charging points (columns) for the vehicles (rows). The specific configuration of this matrix will be optimized with a genetic algorithm to improve the situation of charging for all drivers: