ELEKTROTEHNIŠKI VESTNIK 78(4): 205-210, 2011 ENGLISH EDITION Profit Optimization of Energy Supply of Electric Drive Vehicles Damir Imširović, Matej Rejc, Miloš Pantoš University of Ljubljana, Faculty of Electrical Engineering, Tržaška 25, 1000 Ljubljana, Slovenia E-mail: damir.imsirovic@fe.uni-lj.si, matej.rejc@fe.uni-lj.si, milos.pantos@fe.uni-lj.si Abstract. An increased electric drive vehicle (EDV) use is expected in the future due to the rapid development of new EDV technologies, increased environmental concerns, increasing petroleum-based fuel prices and the possibility of EDV participation on electricity markets. In this paper, an optimization algorithm for EDV charging and discharging for electricity-spot market participation is presented. The use of the presented algorithm would bring lower EDV driving costs for its users and a competitive advantage for the EDV electricity provider that would use the EDV batteries as a storage system in order to purchase and sell additionally stored energy on the electricity market. To simplify the optimization algorithm, individual EDVs are grouped into larger EDV fleets. The use of EDV fleets introduces a constant number of optimization variables in the optimization process. K- means the clustering algorithm is used to group individual EDVs into larger fleets. The optimization problem was approached deterministically and in future work, a probabilistic approach to the problem will be presented. Keywords: k-means clustering method, electricity-spot market, linear optimization 1 INTRODUCTION An increased electric drive vehicle (EDV) use is expected in the future due to the rapid development of new EDV technologies, increased environmental concerns, increasing petroleum-based fuel prices and the possibility of EDV participation on electricity markets. With an ever increasing number of EDVs, electric power systems (EPS) will be subjected to large technological changes, demands for new investments, such as the construction of new EDV charging stations and power system enhancements in transfer capabilities and voltage support. Also, additionally, EDV batteries are expected to be used on the electricity spot markets, where the EDV batteries could be used as an energy storage system [1]. In this paper, an optimization algorithm for EDV charging and discharging is presented with the goal of optimal electricity spot market participation. The presented algorithm enables the electricity providers to maximize the revenue from using additionally stored energy in EDV batteries on the electricity spot market. The EDV electricity providers are expected to be the already functioning distribution companies and electricity providers. This would allow lower driving costs for EDV users, which would attract more EDV users to allow their vehicles to be used in the electricity markets. To simplify the optimization algorithm, EDVs were merged into larger EDV fleets with similar driving needs. This enables the number of optimization variables to remain constant, even with the number of individual EDV changing. The change in the number of EDVs only affects the optimization algorithm as a change in the required power-demand curve for driving schedules. Therefore, a k-means clustering method is presented in this paper to group the various EDVs into fleets. This enables the presented algorithm to give optimal charging and discharging times for individual fleets with electricity spot market participation in mind. This enables the EDV electricity provider to purchase the required energy for EDV at times of lower electricity costs and sell the additionally stored energy at times of higher electricity costs. In the literature, various studies in the EDV charging impact on EPS have appeared [1-3]. The increased interest in EDV participation on electricity markets has been noted [4, 5]. In this paper, the basis for further EDV participation on electricity markets is presented, where probabilistic approach can be included as well as taking into account other electricity markets and various other economic, environmental and technical impacts of EDV. The paper is organized as follows. A short description of EDV and EDV electricity providers is given in Section 2. In Section 3, the developed optimization algorithm for EDV charging and discharging are presented and the k-means clustering method. In Section 4, results of the optimization algorithm for a test case are shown. Finally, in Section 5, the main findings of this paper are summarized. Received September 28, 2011 Accepted October 24, 2011 206 IMŠIROVIĆ, REJC, PANTOŠ 2 ELECTRIC VEHICLE AND ELECTRIC VEHICLE ELECTRICITY PROVIDER DESCRIPTION During the last few decades the development of new EDV technologies has led to a renewed interest in the electric transportation infrastructure. According to the Slovenian Green Paper for the National Energy Policy, EDV will amount to all the newly sold vehicles in 2030. The EDV advantages are their energy conversion efficiency from batteries (90 % efficiency as opposed to the 30 % efficiency of internal combustion vehicles from the stored fuel), locally lower emissions (CO2 emissions are expected to lower thrice [6]), and decreased foreign oil dependency. The disadvantages are currently numerous and are most commonly linked to the current batteries and EDV prices. The range of the current EDVs is approximately 150 km per charging, which is approximately three times less than internal combustion vehicles. The charging time of the current EDV batteries also has its disadvantages, as charging can take from 4 to 8 hours [7]. Additional environmental issues must be taken into account, as large amount of EDV batteries will have to be properly recycled. Increased investments in the EPS will also be required, new smart grid technologies will be mandatory and new regulatory rules for EDV electricity providers created. With the implementation of new smart grid technologies, EDV will be able to participate in electricity markets, aid in EPS frequency regulation and congestion management, participation in balancing markets, etc.. The basic idea is the use of EDV batteries as a storage system, and charging or discharging activated at optimal times during the day. This would enable the electricity provider to lower charging costs for EDV users, as the profits from participating on electricity markets would cover a certain amount of purchased electricity costs. This would bring competitive advantages to electricity providers participating in the above services. 3 OPTIMAL CHARGING AND DISCHARGING ALGORITHM FOR ELECTRICITY SPOT-MARKET PARTICIPATION The electricity provider will require an optimization algorithm to determine optimal charging and discharging times for EDV to optimally participate on the electricity spot market. This will allow the provider to reduce the costs of energy purchases required for EDV driving needs and lower the electricity prices for EDV users. This would result in a competitive advantage over other electricity providers not using such tool. To simplify the optimization problem, the EDV driving schedules were grouped into larger EDV fleets thus limiting the amount of optimization variables to a smaller constant value not changing with the change in the number of EDVs under contract with the electricity provider. As the driving schedules are mostly dependent on the EDV-user work habits, we used the k-means clustering method to group various EDVs into fleets with similar driving schedules (e.g. the EDV users driving to work at a specific time – early mornings, late evenings, during peak-traffic hours, etc.). In Subsection 3.1 we present various EDV driving schedules, reasons for grouping EDVs into fleets and the k-means clustering method. In Subsection 3.2, we describe on optimization algorithm for optimal charging and discharging times enabling electricity spot market participation. 3.1 Clustering of EDV driving schedules into EDV fleets EDV driving schedules of various users present a large uncertainty problem, as different users can drive at different times and require different amounts of energy for their driving needs. Moreover, optimizing charging and discharging times for individual EDVs is not recommended, as the large amount of EDVs in the optimization problem represented as optimization variables would cause serious problems to even the most capable optimization solvers. In this paper, we group individual EDVs into larger EDV fleets to limit the number of variables to a constant number, i.e. the number of fleets. The used k-means clustering algorithm creates representative clustered driving schedules for individual fleets to group individual EDV driving schedules into a fleet. As the number of EDVs changes, only the total battery capability in the fleet changes; the number of optimization variables remains unchanged. In this paper, the k-means clustering method [8] is used to group individual EDV driving schedules into fleets with representative driving patterns. The k-means clustering method uses an iterative refinement technique with the clustering algorithm aiming at minimizing the criterion (1) in order to group the individual EDV driving schedules into fleets. The method is a very popular clustering technique due to its simplicity. j k 2 j g g 1 g min J = ∈ = − ∑∑ d d μ , (1) j g j g g 1 , m ∈ = ∑ d μ d (2) where J is the criterion function, k is the number of EDV fleets, d j = [d j,1 , d j,2 ,…, d j,t ] is the driving schedule of the j-th EDV, (t = 24 hours). μ g = [μ g,1 , μ g,2 ,…, μ g,t ] is the arithmetic mean of all the driving schedules in the g- th EDV fleet, m g represents the number of EDVs in the g-th EDV fleet. The arithmetic mean represents the representative clustered driving schedule of the g-th EDV fleet, which is the goal of the k-means clustering method in this paper. PROFIT OPTIMIZATION OF ENERGY SUPPLY OF ELECTRIC DRIVE VEHICLES 207 The k-mean clustering method consists of four steps. The aim of the method is to iteratively define the arithmetic mean of the driving schedules of the k EDV fleets in order to reach the minimum of the criterion function (1). 1. In the first iteration, the number of EDV fleets is selected, i.e. k, where k