Finding Groupings Of Points With A Additional Point Value

Question

So, as electrical engineers, one of the tasks we do is layout design. My task for the next month is doing Full Load Amps (FLA) design. Basily picking which motors should be connected to which electrical circuit. These motors should be close-ish together, and the whole circuit should not exceed 24 amps. I was able to pull the positional data and horsepower (amps) from our CAD drawings of each area. Example below.

Name, Xpos, Ypos, Amp
[U1000_MTR, 50,40,3 amp]
[U1010_MTR, 60,50,2.4 amp]
[U1100_MTR, 40,50,3 amp]
[U1110_MTR, 50,60,2.4 amp]
...........
[U1910_MTR, 90,40,2.4 amp]

Question: I have seen python clustering algorithms before (affinity propagation), but never one that would take the sum of an additional constant or weight (Make groupings of 25 amps or less Motors). Given the dataset I have, does anyone have any recommendations for an algorithm to look into?

What I am looking for are recommendations on what to look into, to accomplish this

post on using affinity propagation

https://scikit-learn.org/stable/auto_examples/cluster/plot_affinity_propagation.html#sphx-glr-auto-examples-cluster-plot-affinity-propagation-py

Something like this but taking the weight of the data point into account

Answer 1

I'd probably convert this into a graph problem then solve that, two engines (vertices) are connected by an edge if they a) Are not too far distance and b) Do not exceed 24 amps.

There are a ton of approaches you can use to solve this with graph theory. However, I'm pretty confident this is NP-Hard or NP-Complete, so you'll likely want to use a heuristic algorithm unless your data set is small (and doesn't look like it is).

A simple randomized algorithm to start you off (not the best solution, but it's a starting point):

1. Sum your amps and divide by 24 to get K. This gives you a lower bound on the number of clusters you need.
2. Take K random engines and use them to form the core of your clusters.
3. Randomly select an engine from the remaining engines.
4. Add that engine randomly to an a cluster where that engine would be within the allowed distance from the weighted center of the engines already within that cluster, and would not result in that cluster having more than 24. If there are none, create a new cluster and go through the previously added points to see if it would be good to move it elsewhere. For performance, keep data about whether a given point can be in the same cluster as another point (ignoring the 24 amp limit unless the two engines alone exceed 24 amps) in hash or something for easy lookup (will be very useful for step 6).
5. Repeat steps 3/4 until no engines remain.
6. Optimize the results by checking each point (perhaps even pair or triple) to see if there are clusters that would be more suitable for that point. Goal here is to try to reduce the number of clusters, as quite possible an excessive number has been created via step 4.