Find Optimal Permutation/Positioning to Minimize the Total Distance for a Given Path

Question

Summary: A task for picking certain objects is given in the form of an ordered sequence (eg. to pick apple, banana, apple, apple, orange, order matters). The objects have to be preassigned to certain physical locations with all the pairwise distance being known and fixed. The question is how to efficiently find the best location assignment so that the total traveling distance is minimized.

What I Have Tried: I cannot map this problem to any other algos that I know. For example, Dijkstra is to find the path given the graph, Knapsack is to find the right combination which the order doesn't matter.

• I posted this question on Stackoverflow
• I wrote an article on my blog to describe the problem in more detail for your reference
• I wrote a script to demonstrate how to find the optimal position assignment in a brute force way for a small number of objects.

Right now, this is at a complexity I believe of O(n!) and will totally explode as we increase the number of different objects.

# task is a sequence of order picking 
task = '1212103' # means first pick up obj1, then obj2, then obj1, ..etc. 

result = []
for c in permutations(range(4), 4):
    # c contains the positions for all objects 
    # (1, 0, 2, 3) means obj0 stored at pos1, obj1 stored at pos0, etc.  
    res = 0

    for f,t in zip(task, task[1:]):
        pos_f = c[int(f)]
        pos_t = c[int(t)]
        # abs(...) is one oversimplief way to calculating distance between two positions 
        # in a 1d space for demonstration purpose 
        res += abs(pos_f - pos_t)
    result.append((c, res))

And the outputs are all the permutations and the total distance:

[((1, 2, 3, 0), 6),   # optimal position assignment #1 the yields the shortest distance 
((2, 1, 0, 3), 6),    # optimal position assignment #2 the yields the shortest distance 
((0, 2, 3, 1), 7),
((1, 3, 2, 0), 7),
((2, 0, 1, 3), 7),
((3, 1, 0, 2), 7),
((0, 1, 2, 3), 8),
((0, 3, 2, 1), 8),
((3, 0, 1, 2), 8),
((3, 2, 1, 0), 8),
((0, 2, 1, 3), 9),
((3, 1, 2, 0), 9),
((0, 1, 3, 2), 11),
((1, 0, 2, 3), 11),
((1, 2, 0, 3), 11),
((2, 1, 3, 0), 11),
((2, 3, 1, 0), 11),
((3, 2, 0, 1), 11),
((0, 3, 1, 2), 13),
((3, 0, 2, 1), 13),
((1, 0, 3, 2), 14),
((2, 3, 0, 1), 14),
((1, 3, 0, 2), 15),
((2, 0, 3, 1), 15)]

Answer 1

Let us call your problem as $TD$ (Total Distance problem). Now, we will show that there is a polynomial-time reduction from the $k$-clique problem to $TD$. Note that, the $k$-clique problem is $NP-hard$ and is defined as follow:

Given an undirected graph $G_{C} = (V_{C},E_{C})$. Does there exist a clique of size $k$ in $G_{C}$?

The reduction from $k$-Clique to $TD$ happens in the following way:

Define a complete weighted undirected graph $G = (V,E)$ such that $V = V_{C}$ and for an edge $(u,v) \in E$, the weight $w(u,v) = \infty$ if $(u,v) \notin E_{C}$, and $w(u,v) = 1$ if $(u,v) \in E_{C}$. Here, the vertex set $V$ represents the set of locations and weight on an edge represents the travelling cost between two locations. A $k$ size clique can be easily stated by some object sequence $S$. For example, suppose $k = 4$, then the object sequence would be: $S = (1,2,3,4,1,3,4,2)$. Similarly, for $k = 5$, the object sequence would be: $S = (1,2,3,4,5,1,3,5,2,4,1)$. Note that, we have $n$ number of distinct objects but only $k$ of them appears in the sequence. Now, the problem instance of $TD$ consists of the graph $G$ and sequence $S$. This completes the construction.

Now, suppose $A$ is an algorithm of $TD$ that returns a correct mapping of the objects to the locations such that the total traveling cost is minimized. Now, if the traveling cost of the mapping is $\infty$ then $G$ does not have a $k$ size clique. And, if the mapping gives the finite traveling cost then $G$ does have a $k$ size clique.

The above reduction implies that $TD$ is also $NP-hard$. So, we can not expect a polynomial-time running algorithm for $TD$.

---

Note that, in the reduction, instead of setting the edge weights of $G$ to be $\infty$, you can also use finite weights but with sufficiently large values such as $|V|^{|V|}$. That would also work.