Profit maximization with customer satisfaction control for electric vehicle charging in smart grids

Edwin Collado; Easton Li Xu; Hang Li; Shuguang Cui; Edwin Collado; Easton Li Xu; Hang Li; Shuguang Cui

doi:10.3934/energy.2017.3.529

AIMS Energy

2017, Volume 5, Issue 3: 529-556. doi: 10.3934/energy.2017.3.529

Previous Article Next Article

Research article Topical Sections

Profit maximization with customer satisfaction control for electric vehicle charging in smart grids

1.
Universidad Tecnológica de Panamá, Panamá
2.
Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USA
3.
Department of Electrical and Computer Engineering, University of California, Davis, CA 95616, USA

Received: 17 February 2017 Accepted: 18 May 2017 Published: 25 May 2017

As the market of electric vehicles is gaining popularity, large-scale commercialized or privately-operated charging stations are expected to play a key role as a technology enabler. In this paper, we study the problem of charging electric vehicles at stations with limited charging machines and power resources. The purpose of this study is to develop a novel profit maximization framework for station operation in both offline and online charging scenarios, under certain customer satisfaction constraints. The main goal is to maximize the profit obtained by the station owner and provide a satisfactory charging service to the customers. The framework includes not only the vehicle scheduling and charging power control, but also the managing of user satisfaction factors, which are defined as the percentages of finished charging targets. The profit maximization problem is proved to be NPcomplete in both scenarios (NP refers to “nondeterministic polynomial time”), for which two-stage charging strategies are proposed to obtain efficient suboptimal solutions. Competitive analysis is also provided to analyze the performance of the proposed online two-stage charging algorithm against the offline counterpart under non-congested and congested charging scenarios. Finally, the simulation results show that the proposed two-stage charging strategies achieve performance close to that with exhaustive search. Also, the proposed algorithms provide remarkable performance gains compared to the other conventional charging strategies with respect to not only the unified profit, but also other practical interests, such as the computational time, the user satisfaction factor, the power consumption, and the competitive ratio.
- Convex optimization,
- machine scheduling,
- electric vehicles charging,
- competitive ratio analysis,
- smart grid
Citation: Edwin Collado, Easton Li Xu, Hang Li, Shuguang Cui. Profit maximization with customer satisfaction control for electric vehicle charging in smart grids[J]. AIMS Energy, 2017, 5(3): 529-556. doi: 10.3934/energy.2017.3.529

Related Papers:

Abstract

As the market of electric vehicles is gaining popularity, large-scale commercialized or privately-operated charging stations are expected to play a key role as a technology enabler. In this paper, we study the problem of charging electric vehicles at stations with limited charging machines and power resources. The purpose of this study is to develop a novel profit maximization framework for station operation in both offline and online charging scenarios, under certain customer satisfaction constraints. The main goal is to maximize the profit obtained by the station owner and provide a satisfactory charging service to the customers. The framework includes not only the vehicle scheduling and charging power control, but also the managing of user satisfaction factors, which are defined as the percentages of finished charging targets. The profit maximization problem is proved to be NPcomplete in both scenarios (NP refers to “nondeterministic polynomial time”), for which two-stage charging strategies are proposed to obtain efficient suboptimal solutions. Competitive analysis is also provided to analyze the performance of the proposed online two-stage charging algorithm against the offline counterpart under non-congested and congested charging scenarios. Finally, the simulation results show that the proposed two-stage charging strategies achieve performance close to that with exhaustive search. Also, the proposed algorithms provide remarkable performance gains compared to the other conventional charging strategies with respect to not only the unified profit, but also other practical interests, such as the computational time, the user satisfaction factor, the power consumption, and the competitive ratio.

References

[1]	Tanaka N (2011) Technology roadmap: electric and plug-in hybrid electric vehicles (EV/PHEV). Int Energy Agency, Tech Rep.
[2]	Ipakchi A, Albuyeh F (2009) Grid of the future. Power Energy Mag 7: 52-62. doi: 10.1109/MPE.2008.931384
[3]	US. Environmental Protection Agency, EPA in United Sates: All-electric vehicles. Available from: http://fueleconomy.gov/feg/evtech.shtml.
[4]	Emadi A, Lee YJ, Rajashekara K (2008) Power electronics and motor drives in electric, hybrid electric, and plug-in hybrid electric vehicles. IEEE Trans Ind Electron 55: 2237-2245. doi: 10.1109/TIE.2008.922768
[5]	Liu R, Dow L, Liu E (2011) A survey of PEV impacts on electric utilities. Proc IEEE PES ISGT 1-8.
[6]	Hadley SW (2006) Impact of plug-in hybrid vehicles on the electric grid. ORNL Report. Available from: http://apps.ornl.gov/pts/prod/pubs/ldoc3198-plug-in-paper-final.pdf.
[7]	Boulanger AG, Chu AC, Maxx S, et al. (2011) Vehicle electrification: status and issues. Proc IEEE 99: 1116-1138. doi: 10.1109/JPROC.2011.2112750
[8]	Qian K, Zhou C, Allan M, et al. (2011) Modeling of load demand due to EV battery charging in distribution systems. IEEE Trans Power Syst 26: 802-810. doi: 10.1109/TPWRS.2010.2057456
[9]	Yilmaz M, Krein PT (2013) Review of battery charger topologies, charging power levels, and infrastructure for plug-in electric and hybrid vehicles. IEEE Trans Power Electron 28: 2151-2169. doi: 10.1109/TPEL.2012.2212917
[10]	Richardson P, Flynn D, Keane A (2012) Optimal charging of electric vehicles in low-voltage distribution systems. IEEE Trans Power Syst 27: 268-279. doi: 10.1109/TPWRS.2011.2158247
[11]	Clement-Nyns K, Haesen E, Driesen J (2010) The impact of charging plug-in hybrid electric vehicles on a residential distribution grid. IEEE Trans Power Syst 25: 371-380. doi: 10.1109/TPWRS.2009.2036481
[12]	Mets K, Verschueren T, Haerick W, et al. (2010) Optimizing smart energy control strategies for plug-in hybrid electric vehicle charging. Proc 12th IEEE/IFIP NOMS, 293-299.
[13]	Zhong F (2012) A distributed demand response algorithm and its application to PHEV charging in smart grids. IEEE Trans Smart Grid 3: 1280-1290. doi: 10.1109/TSG.2012.2185075
[14]	Stein S, Gerding E, Robu V, et al. (2012) A model-based online mechanism with pre-commitment and its application to electric vehicle charging. Proc 11th AAMAS '12 2: 669-676.
[15]	Deilami S, Masoum AS, Moses PS, et al. (2011) Real-time coordination of plug-in electric vehicle charging in smart grids to minimize power losses and improve voltage profile. IEEE Trans Smart Grid 2: 456-467. doi: 10.1109/TSG.2011.2159816
[16]	Geng B, Mills J, Sun D (2013) Two-stage charging strategy for plug-in electric vehicles at the residential transformer level. IEEE Trans Smart Grid 4: 1442-1452. doi: 10.1109/TSG.2013.2246198
[17]	Fan Z (2012) A distributed demand response algorithm and its application to PHEV charging in smart grids. IEEE Trans Smart Grid 3: 1280-1290. doi: 10.1109/TSG.2012.2185075
[18]	Li Q, Cui T, Negi R, et al. (2011) On-line decentralized charging of plug-in electric vehicles in power systems. Available from: http://http://arxiv. org/abs/arXiv:1106.5063.
[19]	Gonzalez MV, G' oran A (2012) Centralized and decentralized approaches to smart charging of plug-in vehicles. Proc 2012 IEEE PES General Meeting.
[20]	Sundstrom O, Binding C (2012) Flexible charging optimization for electric vehicles considering distribution grid constraints. IEEE Trans Smart Grid 3: 26-37. doi: 10.1109/TSG.2011.2168431
[21]	Zheng Z, Shroff N (2014) Online welfare maximization for electric vehicle charging with electricity cost. Proc 5th Int Conf on Future Energy Syst, e-Energy '14, 253-263.
[22]	Papadopoulos P, Jenkins N, Cipcigan L, et al. (2013) Coordination of the charging of electric vehicles using a multi-agent system. IEEE Trans Smart Grid 4: 1802-1809. doi: 10.1109/TSG.2013.2274391
[23]	Su W, Chow M (2012) Performance evaluation of an EDA-based large-scale plug-in hybrid electric vehicle charging algorithm. IEEE Trans Smart Grid 3: 308-315. doi: 10.1109/TSG.2011.2151888
[24]	Woeginger G (1994) On-line scheduling of jobs with fixed start and end time. Theor Comput Sci 130: 5-16. doi: 10.1016/0304-3975(94)90150-3
[25]	Ding J, Zhang G (2006) Online scheduling with hard deadlines on parallel machines. Proc 2nd AAIM 4041: 32-42.
[26]	Arkin EM, Silverberg B (1987) Scheduling jobs with fixed start and end times. Disc Appl Math 18: 1-8. doi: 10.1016/0166-218X(87)90037-0
[27]	Clemente M, Fanti MP, Ukovich W (2014) Smart management of electric vehicles charging operations: the vehicle-to-charging station assignment problem. Proc 19th IFAC World Congr 19: 918-923.
[28]	Ming Z, Liu XY, Kong L, et al. (2014) The charging-scheduling problem for electric vehicle networks. Proc 2014 IEEE WCNC, 3178-3183.
[29]	Chen S, He T, Tong L (2011) Optimal deadline scheduling with commitment. Proc 49th Allerton Conf Commun, Control, and Comput.
[30]	Chen S, Ji Y, Tong L (2012) Large scale charging of electric vehicles. Proc 2012 IEEE PES, 1-9.
[31]	Li J, Yang B, Xu Y, et al. (2014) Scheduling of electric vehicle charging request and power allocation at charging stations with renewable energy. Proc 33rd China Control Conf 7066-7071.
[32]	Davis L (2014) How to generate good profit maximization problems. J Econ Educ 45: 183-190. doi: 10.1080/00220485.2014.917564
[33]	Agarwal T, Cui S (2012) Noncooperative games for autonomous consumer load balancing over smart grid. Available from: http://arxiv.org/abs/1104.3802.
[34]	Bouzina KI, Emmons H (1996) Interval scheduling on identical machines. J Global Optimization 9: 379-393. doi: 10.1007/BF00121680
[35]	Angelelli E, Bianchessi N, Filippi C (2014) Optimal interval scheduling with a resource constraint. Comput Oper Res 51: 268-281. doi: 10.1016/j.cor.2014.06.002
[36]	Bekki OB, AzizogluM (2008) Operational fixed interval scheduling problem on uniform parallel machines. Int J Production Econ 112: 756-768. doi: 10.1016/j.ijpe.2007.06.004
[37]	Darmann A, Pferschy U, Schauer J (2010) Resource allocation with time intervals. Theor Comput Sci 411: 4217-4234. doi: 10.1016/j.tcs.2010.08.028
[38]	Chen B, Hassin R, Tzur M (2002) Allocation of bandwidth and storage. IIE Trans 34: 501-507.
[39]	Bar-Noy A, Bar-Yehuda R, Freund A, et al. (2001) A unified approach to approximating resource allocation and scheduling. J ACM 48: 1069-1090. doi: 10.1145/502102.502107
[40]	Srivastav A (2001) Derandomization in combinatorial optimization. In Handbook of Randomized Computing (S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. D. P. Rolim, eds.), Kluwer Academic Publishers, Chapter 18, 731-842.
[41]	Bar-Noy A, Guha S, Naor J, et al. (2001) Approximating the throughput of multiple machines in real-time scheduling. SIAM J Comput 31: 331-352. doi: 10.1137/S0097539799354138
[42]	Bhatia R, Chuzhoy J, Freund A, et al. (2003) Algorithmic aspects of bandwidth trading. Proc 30th ICALP 2719: 751-766.
[43]	Andelman N, Mansour Y (2004) Auctions with budget constraints. Proc 9th Algor Theor-SWAT 3111: 26-38.
[44]	Mestre J (2006) Greedy in approximation algorithms. Proc 14th Algor ESA 4168: 528-539.
[45]	Jenkyns TA (1979) The greedy travelling salesman's problem. J Networks 9: 363-373. doi: 10.1002/net.3230090406
[46]	Boyd S, Vandenberghe L (2004) Convex optimization. Cambridge Univ. Press, Cambridge, UK: Cambridge University Press.
[47]	Pinedo M (2012) Scheduling: theory, algorithms, and systems. Springer Science and Business Media, New York, NY: Springer.
[48]	Grant M, Boyd S (2008) CVX: MATLAB software for disciplined convex programming (web page and software). Available from: http://www.stanford.edu/~boyd/cvx/.
[49]	Palm WJ (2004) Introduction to MATLAB 7 for Engineers. New York, NY: McGraw-Hill.
[50]	PR Newswire: Electric vehicle drivers enjoy charging on a "First Come, First Served" basis with ChargePoint's new waitlist feature. Available from: http://www.prnewswire.com/newsreleases/electric-vehicle-drivers-enjoy-charging-on-a-first-come-first-served-basis-withchargepoints-new-waitlist-feature-300332342.html.

Reader Comments

Your name:*

Email:*
© 2017 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)