algorithmsimulationgraph-theoryphysics

Electric circuit with redundancies (power distribution) simulation


I need to simulate at basic level an electric circuit with redundancies, for example like this:

enter image description here

We have two generators, a couple of power distributors and the devices. I am trying to simulate the electric current on each branch, starting from device power requirements (e.g., Device 1 need 5 Ampere, Device 2 15, Device 3 ..., )

My trial was by implementing a simple graph:

  • We start from the last-level children and they ask their parent the current they need to work
  • Each parent check if it received request from each children, if not just wait
  • All other parents sum up the current requested from each child and will ask to its own parent
  • Do this until we have no parents anymore Now we distribute the power:
  • last set of parents from algorithm above are the power supply (generators in this case)
  • each power supply knows how much current it was asked, it simply split it available power (or current) proportionally to each child (it may be enough or even not if overloaded, that's fine)
  • each child do the same until we reach the bottom

Now the problem which brought me to a stop: Some devices (power distributors) can take power from multiple parents. In such a case the normal solution would be to split the power request evenly among parents BUT, if one of the parent cannot provide it (smaller generator or supplying to much devices) than the distributor will ask more to the other parent(s). It seems to me impossible to know it in advance if this is the case, since the above algorithm need to be run fully to know if a generator is overloaded or not, and to do that I must select in advance if the distributor will ask to its parents 50/50 or 30/70 or ... .

The only solution I could think of is iterative: applying the algorithm once with a 50/50. If one generator can pro provide just let's say 30% I take note of that and simulate again, asking for 70% to the other one, fine. Maybe not... the other generator now cannot provide enough power to the other distributor so I have to simulate again changing the 50/50 percentage of the other distributor as well. I am afraid this can be overcomplicated and that the algorithm will never converge to a good result. I never faced this kind of problems and after many days sleeping over it I still cannot find the best solution. I would like to avoid bad practices and using good software design. Does anyone has a common solution for this kind of problem to point me to?

Thank you everyone

PS: Language is not a problem (it's an algorithm issue) but if relevant I'm writing it in C++


Solution

  • This is a flow problem.

    Here is the algorithm to calculate the flow problem:

    • Find a path from a source to a destination, using the Dijkstra algorithm

    • Find minimum capacity of any link on the path

    • Reduce capacity of all links on path by minimum capacity

    • Remove any link that now has zero capacity

    • Repeat above steps until no more paths can be found.

    To make this work you will need to:

    • set the capacity of an output links from each generator to the maximum power it can generate

    • connect the generator output link to an additional node that splits the flow to the different devices and distributors that are connected to the generator

    • set the capacity of the input links to the devices to be the power demand of the devices.

    • connect an output link from each device to an additional node that acts as a common sink

    • set the capacity of all links that have not been specified by the above steps to a very large number, greater than any total flow expected, so that they do not limit the flow in any way.

    Here is some C++ code that implements this https://github.com/JamesBremner/PathFinder/blob/7b98a412398e1aea8934a8002822e1ccef9b888a/src/GraphTheory.cpp#L755-L859. The documentation for this is at https://github.com/JamesBremner/PathFinder/wiki/Flows and the complete application at https://github.com/JamesBremner/PathFinder

    Here is your problem specified in the format expected by the PathFinder application

    format multiflows
    g 1 0
    l gen1 gen1split 100
    l gen1split dev1 5
    l gen1split dist1 1000
    l gen1split dist2 1000
    l gen2 gen2split 100
    l gen2split dist1 1000
    l gen2split dist2 1000
    l dist1 dev2 15
    l dist1 dev3 3
    l dist2 dev4 4
    l dist2 dev5 5
    l dist2 dev6 6
    l dev1 sink 1000
    l dev2 sink 1000
    l dev3 sink 1000
    l dev4 sink 1000
    l dev5 sink 1000
    l dev6 sink 1000
    s gen1
    s gen2
    e sink
    

    The code linked to above only works correctly for a single source ( generator ). Here is the code to calculate the flow from multiple sources

    double multiflows(sGraphData &gd)
            {
                // total flow on each link from all sources
                std::vector<int> vMultiFlow(gd.g.edgeCount());
    
                // flow on each link from current source
                std::vector<int> vEdgeFlow(gd.g.edgeCount());
    
                // working copy of graph
                sGraphData work = gd;
    
                // loop over sources
                for (auto &s : gd.multiStart)
                {
                    // reduce link capacities by flow from previous generator
                    for (int k = 0; k < vEdgeFlow.size(); k++)
                        work.edgeWeight[k] -= vEdgeFlow[k];
    
                    // calculate flow from this generator
                    vEdgeFlow.clear();
                    work.startName = s;
                    flows(
                        work,
                        vEdgeFlow);
    
                    // add to total flow
                    for (int k = 0; k < vEdgeFlow.size(); k++)
                        vMultiFlow[k] += vEdgeFlow[k];
                }
    
                // display total flow through each link
                for (int k = 0; k < vMultiFlow.size(); k++)
                {
                    std::cout << gd.g.userName(gd.g.src(k))
                              << " -> " << gd.g.userName(gd.g.dest(k))
                              << " " << vMultiFlow[k] << "\n";
                }
                return 0;
            }
    

    For your problem, the output is

    gen1 -> gen1split 20
    gen1split -> dev1 5
    gen1split -> dist1 3
    gen1split -> dist2 12
    gen2 -> gen2split 18
    gen2split -> dist1 15
    gen2split -> dist2 3
    dist1 -> dev2 15
    dist1 -> dev3 3
    dist2 -> dev4 4
    dist2 -> dev5 5
    dist2 -> dev6 6
    dev1 -> sink 5
    dev2 -> sink 15
    dev3 -> sink 3
    dev4 -> sink 4
    dev5 -> sink 5
    dev6 -> sink 6