Solving an Average Cost per Stage Problem for Resource Management in Electricity Networks

Samuel Zürcher, Term Project, Autumn 2008

Supervisors: Michael Guarisco, Marco Laumanns

The regulation schemes for grid fees in liberalized electricity markets such as price or revenue cap regulation give strong incentives to grid operators for cost reduction. As the attempt to reduce operating costs may have negative effects on the quality of supply, regulators impose quality standards. Accordingly, grid operators try to find an optimal balance between costs and quality of supply. One main aspect of the quality of supply concerns the availability of electricity to customers, which is usually measured by duration, extent and frequency of supply interruptions. The restoration process after incidents depends on the availability of resources. For incidents with an interruption of supply, a temporary non-availability of resources delays the restoration and thus directly influences the quality of supply. Incidents without an interruption of supply reduce the redundancy in the power grid and a delay in the repair directly affects the duration of the grid being in a status of risk. Additional incidents might eventually lead to a (large) interruption of supply.

In this project, we analyze the relation between a given configuration of resources and the corresponding quality of supply by a stochastic dynamic optimization model, namely by an average cost per stage problem. The cost in this setting is intended to measure the quality of supply and is defined as the energy not supplied. We consider a power supply system consisting of a power grid (power supply lines, transformers, generators, etc.), consumers/loads, and (human) resources. The electrical energy is generated and supplied by the power grid and spent by the consumers. Due to technical failures or external causes, the electrical equipment can fail and thus has to be repaired by the resources (according to some policy). In our model, the power grid and the loads are represented by a finite number of components. Each component is either running or has failed and requires a given time to be repaired. The components/nodes are connected by edges ("roads") with given travel times on which the resources are allowed to travel. The state of the system at a given point in time is defined by the state of each component and the allocation of the resources on the nodes. The system is assumed to be stationary and is considered in discrete time steps over an infinite time horizon. For a given number of resources, the aim of the model is to find a policy with minimum average cost (i.e., expected energy not supplied) per stage. The optimal cost and the corresponding policies for different numbers of resources may be used to support strategic decisions concerning an "optimal" configuration of resources.

There are several methods to solve this type of problem based on value iteration, policy iteration, or linear programming. However, the validity of these methods may depend on structural assumptions on the underlying Markov chains. One main difficulty of the described model is that the number of states is very large (e.g. exponential in the number of components) and hence approximate solution methods are needed. The aim of this work was to analyze and compare different solution methods to solve the average cost per stage problem in the above framework.

First, the properties of the different solution methods were investigated and contrasted with respect to their applicability in the given setting. Based on this analysis, two methods were selected, a modified version of the value iteration method and the linear programming approach. For the modified value iteration - an iterative procedure which yields an approximate optimal cost and a corresponding policy - the error bounds on the optimal cost were studied. To assure the theoretical results, (sufficient) conditions on the set of policies were formulated. These conditions e.g. imply that the optimal average cost is independent of the starting state. Finally, the two selected methods were implemented and tested on small examples. To explore a result which relates optimal basic feasible solutions of the linear program to optimal stationary policies, the simplex algorithm was used to solve the linear program. The results of both methods, i.e. the optimal cost and the corresponding policies, were validated and interpreted.