This is a bonus project. We look at finding the optimal restoration process. An interesting thing to note is that we have two networks to work with: the electrical network and the travel network. The interaction between these systems is best illustrated by an example.

Example

Consider the electrical system below. The feeder is numbered as bus 0 and is the root of the tree. Note that we assume the topology of the network is given and it will always be a tree. In practice, the network always operate as a tree but there are switches. That makes the problem too complicated and we won’t look switching in this class. The weights on the nodes represents how “important” that load is, and larger means more important.

distribution system with a feeder and 3 buses

Note the tree topology defines a partial ordering of the buses. We say bus $i$ to be an ancestor of bus $j$ if the path from the root (bus $0$) to bus $j$ contains bus $i$. In the figure above, bus 2 is an ancestor of bus 3. The bus $j$ can only be energized if all of its ancestors are energized.

In addition to the electrical network, we have a travel network that defines the time it takes for an repair crew to get from one bus to another bus. We typically do not include the feeder in this network, since we assume that the feeder is already energized. Since one could travel directly from any bus to any other bus, we have a complete graph:

3 bus complete graph with weights on the edges

Here the weights on the edges denote the travel time between two buses.

Our goal is to find a sequence of buses that a crew should visit. To make things simple, we assume that a bus is repaired instantaneously once a crew get there. Given such a sequence, we define a metric called harm (H) as:

\[H=\sum_i \text{time bus i is not repaired} \cdot w_i\]

and we want to minimize $H$.

For the example above, let’s compare two repair sequences, $s_1={1, 3, 2}$ and $s_2={2,3,1}$. The harm associated with $s_1$ is $H_1=0\cdot 1+(0.1+0.5)\cdot (10+5)=9$ (note that bus 3 cannot be energized until bus 2 is repaired). The harm associated with $s_2$ is $H_2=0\cdot 5+0.5\cdot 10 + 0.6 \cdot 1=5.6$, which is quite a bit smaller than $H_1$. Therefore $s_2$ is the better repair sequence.

Questions

Consider the following electrical network and travel networks:

enter image description here

enter image description here

  1. Find two repair sequences, where one is bad and one is good. Note it is very difficult to show that a sequence is optimal (it is a NP-hard problem). So often we show that a solution is pretty good. To do this, we can find a baseline solution, for example, picking a random sequence, and show that a more carefully chosen sequence has lower harm.
  2. What happens when you have two crews? How much better can you do?