Coalitional control for charging electric vehicles in smart grids

DYMASOS EV Charging 1_USEThe renewed interest in electric vehicles (EV) during the last decade can be mainly addressed to the flexibility provided by the employ of electrical energy, which can be generated from sources of different nature. Moreover, the EV population is regarded as a unique opportunity for the exploitation of renewable energy for their storage capacity. The growing popularity of EVs induces the need of a novel infrastructure capable of efficiently supplying the associated energy demanded. A significant portion of EVs’ daily trip will exceed the range of the fully charged battery, thus requiring a recharge during daytime operation of the vehicle [1]. It is expected that drivers will be uncomfortable with peculiar aspects of EVs such as monitoring the state of charge and best locating one of the few available charging stations (CS).

The choice of the charging station by EV drivers is a highly complex problem: the demand is expected to be mutable, closely related to the user’s schedule, driving and travel patterns as well as the availability of CSs [4],[11]. Besides the natural dependence of the demand from the energy prices, the long time required for battery recharge (about 15 min with fast DC chargers) produces a significant coupling between the decisions of different drivers, unlike gas stations.

DYMASOS EV Charging 2_USEThe EV recharging infrastructure will likely encompass advanced communication and control technologies. Indeed, intelligent transportation systems (ITS) strongly support such development, as vehicles and infrastructures are capable of exchanging traffic data in real-time. The work of [1] brings out the concept of quality of service (QoS) for charging stations. In order to address the long delays caused by the fairly large charging time for EVs (compared with that of conventional gasoline vehicles), a price admission mechanism is proposed, with the aim of improving the QoS provided to customers. In this way, drivers are incentivized through price signals to recharge at less busy stations. Results of recent investigation show that updated information about the estimated waiting time at each CS can be effectively employed for rerouting, providing significant improvement in the quality of service (QoS) experienced by the users [2],[3].

While most works assume that vehicles obey a rigid (often monodimensional) trajectory, a number of methods have been proposed for the prediction of the EV load based on driving patterns, possibly obtained from data of real commuting habits [6]. Nevertheless, if on one hand the information about light duty vehicles is limited, on the other hand it is arguable to expect that such data can be directly translated on EVs. The micro simulation environment employed in the present work was developed in cooperation with AYESA, which provided insights on the problem and data from the real EV benchmark Zem2All [7].

The main goals of the work carried out at the intersection of DYMASOS WP3 and WP5 by USE are: (i) develop a model of the variation of the energy demand for EV recharge operations in a urban setting, according to the spot prices, and (ii) use such model to design a control strategy to let each CS maximize its own economical benefit by either operating on its own or according to a joint planning derived through strategic coalitions.

It is widely acknowledged that dynamic pricing policies offer the best performance in terms of efficient use of the infrastructures, since price variations allow to adjust the demand in real-time according to the system capacity. However, implementation of such pricing mechanisms is not straightforward, as it requires expensive real time monitoring. Hence, static (e.g., flat rates) or myopic mechanisms (e.g., congestion pricing) are the most eligible candidates for the application. Characterized by a reduced computational complexity, the prediction model presented is oriented at the implementation of complex dynamical pricing strategies for an enhanced management of EV charging stations.

In order to facilitate the analysis, the problem has been so far approached in the literature through essential schemes, characterized by restrictions on the action space of both parties: simplifications may range from a unique price applied by all charging stations to neglecting the coupling between EV drivers’ decisions [8]. In this work, the price optimization problem is formulated from the CS manager standpoint. Motivated by the fact that demand at each CS is strongly correlated with its location as well as the location of the other CSs, and with the dominant traffic pattern, we identified the sensitivity of the aggregate demand to recharge price variations on a microscopic traffic simulator.  We assume that the EV drivers rationally select the CS according to a function expressing their individual utility, defined by a trade-off between minimizing the charging cost and getting the service as soon as possible.  The open microsimulator SUMO has been employed as a base for the study [9].

Aspects related to economical competition of CSs such as energy markets and dynamic pricing have already been considered in several works, involving as well the use of game theoretical tools [5]. The possibility of CSs cooperating in the joint planning of the pricing strategy is considered, so as to achieve a more efficient use of available charging infrastructures. This is done through the formulation of a coalitional game [12], allowing to derive a closed formulation of the benefit redistribution by the Shapley value [10].

At each turn, all possible coalitions among CSs are evaluated, and the organization into a given coalitional structure will be decided as the outcome of a best matching algorithm. This operation is carried out on the basis of an increase of individual economic benefit for each agent, derived from the Shapley allocation of the value of the coalition the agent is affiliate with. More specifically, coalition values are computed as the aggregate estimated profit of the members. It is worth to point out that this type of scenario can be modeled by a partition-function game [13]: here the value of a given coalition also depends on how the other players organize themselves. We addressed the problem by assigning the values resulting by the worst-case scenario for any given coalition. This way, the problem is approximated as a computationally approachable characteristic function game model. Finally, the prices relative to the resulting coalitional structure are applied to the system, and the profits by the energy sales shared among the agents, according to the Shapley values previously computed.

[1] I. Bayram, G. Michailidis, I. Papapanagiotou, and M. Devetsikiotis, “Decentralized control of electric vehicles in a network of fast charging stations,” in 2013 IEEE Global Communications Conference (GLOBECOM), Dec 2013, pp. 2785–2790.

[2] J. Johnson, M. Chowdhury, Y. He, and J. Taiber, “Utilizing real-time information transferring potentials to vehicles to improve the fast-charging process in electric vehicles,” Transportation Research Part C: Emerging Technologies, vol. 26, pp. 352 – 366, 2013.

[3] J. Escudero-Garzas and G. Seco-Granados, “Charging station selection optimization for plug-in electric vehicles: An oligopolistic game theoretic framework,” in Innovative Smart Grid Technologies (ISGT), 2012 IEEE PES, Jan 2012, pp. 1–8.

[4] X. Feixiang, H. Mei, Z. Weige, and L. Juan, “Research on electric vehicle charging station load forecasting,” in Advanced Power System Automation and Protection (APAP), 2011 International Conference on, vol. 3, Oct 2011, pp. 2055–2060.

[5] F. Malandrino, C. Casetti, C.-F. Chiasserini, and M. Reineri, “A game-theory analysis of charging stations selection by EV drivers,” Performance Evaluation, vol. 83–84, pp. 16–31, Jan 2015.

[6] E. Xydas, C. Marmaras, L. Cipcigan, A. Hassan, and N. Jenkins, “Forecasting electric vehicle charging demand using support vector machines,” in Power Engineering Conference (UPEC), 2013 48th International Universities’, Sept 2013, pp. 1–6.

[7] Zem2All project website, 2013. [Online]. Available: www.zem2all.com

[8] W. Yuan, J. Huang, and Y. Zhang, “Competitive charging station pricing for plug-in electric vehicles,” Smart Grid, IEEE Transactions on, vol. PP, no. 99, pp. 1–13, 2015.

[9] DLR – Institute of Transportation Systems, “Simulation of Urban MObility (SUMO),” 2016. [Online].  Available: www.dlr.de/ts/sumo/en/

[10] L. Shapley, “A value for n-person games,” Annals of Math. Studies, vol. 28, pp. 307–317, 1953.

[11] F. Fele, D. Cerero-Tejero, E. G. Debada,  and E. F. Camacho, “Coalition formation of charging stations in an EV population scenario”, submitted to the 55th IEEE Conference on Decision and Control (CDC 2016)

[12] F. Fele, E. G. Debada,  J.M. Maestre, M. A. Ridao and E. F. Camacho, “DYMASOS D3.4: Final report on policies for coalition formation in SoS”, ETSI, Universidad de Sevilla, Seville, Spain, Tech. Rep., March 2016. [Online]. Available: www.dymasos.eu/outcomes/deliverables/

[13] G. Chalkiadakis, E. Elkind, and M. Wooldridge, Computational aspects of cooperative game theory. USA: Morgan & Claypool, 2012.