  Energy markets with retail choice enable customers to switch energy plans
among competitive retail suppliers. Despite the promising benefits of more
affordable prices and better savings to customers, there appears subsided
participation in energy retail markets from residential customers. One major
reason is the complex online decision-making process for selecting the best
energy plan from a multitude of options that hinders average consumers. In this
paper, we shed light on the online energy plan selection problem by providing
effective competitive online algorithms. We first formulate the online energy
plan selection problem as a metrical task system problem with temporally
dependent switching costs. For the case of constant cancellation fee, we
present a 3-competitive deterministic online algorithm and a 2-competitive
randomized online algorithm for solving the energy plan selection problem. We
show that the two competitive ratios are the best possible among deterministic
and randomized online algorithms, respectively. We further extend our online
algorithms to the case where the cancellation fee is linearly proportional to
the residual contract duration. Through empirical evaluations using real-world
household and energy plan data, we show that our deterministic online algorithm
can produce on average 14.6% cost saving, as compared to 16.2% by the offline
optimal algorithm, while our randomized online algorithm can further improve
cost saving by up to 0.5%.
