# Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path.

For example,

Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E'

Gate 'B' will have to go to 'D'

Gate 'C' will have to go to 'A' and 'B'

Gate 'D' will have to go to 'E' - 'A' and 'B'

Gate 'E' will have to go to 'C' - 'E' and 'A'

Gate 'B' will have to go to 'D'

How can I find the optimal placement of the gates on the graph, such that it makes the least distance overall, computing all the paths to be made?

For 6 gates, we could search all possible placements by brute force. However, in my current project I have 42 gates to dispatch, thus it sounds too complicated to brute force.

The following is the function used to calculate the distance between the two gates (stocked in a Pandas DataFrame)

import math
def calculateDistance(df, gate_a, gate_b):
coord_a = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_a))][0] # GET COORDINATE OF GATE_A
coord_b = [(x, df.columns[y]) for x, y in zip(*np.where(df.values == gate_b))][0] # GET COORDINATE OF GATE_B
y1, x1 = coord_a[0], coord_a[1]
y2, x2 = coord_b[0], coord_b[1]
dist = math.sqrt((((x2 - x1) * scale_x) **2)  + ( ((y2 - y1) * scale_y) **2 ))
return dist

calculateDistance(df, "A", "C")

• I've added the way I calculate the distance between two gates, finding the gate's coordinates within the dataframe. Jul 25 at 15:13
• The least distance overall, computing all the paths to be made! Sorry if this is not clear Jul 25 at 15:21
• No, in my current project I have 42 gates to dispatch, thus it sounds too complicated to brute force Jul 25 at 15:34
• Travelling salesman problem is a very special case of your task. It is unlikely there is an algorithm in polynomial time of the number of gates. Jul 25 at 15:57
• Let me do my best attempt to rephrase the problem in CS terms: There's a metric space $X$, with $n$ points. Additionally, there is a collection of $n$ sequences of labels, where all labels are numbers in $\{1, \ldots, n\}$, and all sequences start with a different label. When the points are labeled in bijection to $\{1, \ldots, n\}$ then each sequence defines a path. The problem is to choose a bijective labeling of the nodes that minimizes the sum of the lengths of paths induced by the sequences? Is this a correct interpretation? If so your problem is clearly NP-hard as suggested by @JohnL. Jul 25 at 16:57

That said, 42 is a fairly small number, so there is some hope. I would suggest that you formulate this as an instance of integer linear programming (ILP). Add zero-or-one boolean variables $$x_{v,i}$$ for each vertex $$v$$ (i.e., point in the plane) and each gate $$i$$ (i.e., each index in $$\{1,2,\dots,n\}$$), where $$x_{v,i}=1$$ means that $$v$$ is associated with $$i$$. Add constraints to enforce that this is a bijective mapping, i.e., $$\sum_v x_{v,i}=1$$ for all $$i$$ and $$\sum_i x_{v,i}=1$$ for all $$v$$. Also, for each $$v,w,i,j$$ let $$y_{v,i,w,j} = x_{v,i} \land x_{w,j}$$, which can be enforced using linear inequalities as explained in Express boolean logic operations in zero-one integer linear programming (ILP). Finally, you now have an objective $$\Phi$$ defined as
$$\Phi = \sum_{i,j} \sum_v \sum_w d(v,w) y_{v,i,w,j}$$
where $$d(v,w)$$ is the distance between $$v$$ and $$w$$ (a constant), and you sum over all edges $$(i,j)$$ that appear in the input sequences, and you sum over all possible $$v$$ and $$w$$. This objective is a linear function, so you can use an ILP solver to find the solution that minimizes $$\Phi$$. You'll end up with an ILP instance with several million variables and tens of millions of inequalities, which might be small enough that an off-the-shelf ILP solver can solve it to find a decent solution.