  This paper presents a computation-efficient stochastic dynamic programming
algorithm for solving energy storage price arbitrage considering variable
charge and discharge efficiencies. We formulate the price arbitrage problem
using stochastic dynamic programming and model real-time prices as a Markov
process. Then we propose an analytical solution algorithm using a piecewise
linear approximation of the value-to-go function. Our solution algorithm
achieves extreme computation performance and solves the proposed arbitrage
problem for one operating day in less than one second on a personal computer.
We demonstrate our approach using historical price data from four price zones
in New York Independent System Operator, with case studies comparing the
performance of different stochastic models and storage settings. Our results
show that the proposed method captures 50% to 90% of arbitrage profit compared
to perfect price forecasts. In particular, our method captures more than 80% of
arbitrage profit in three out of the four price zones when considering
batteries with more than two-hour duration and realistic degradation cost.
