1
$\begingroup$

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)]
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ I will need to do some homework to fully comprehend your answer. Meanwhile, what will be an efficient way of approximating the approximate a the optimal solution even if it can not be solved in polynomial time. Monte Carlo? or any smart way? Thanks. $\endgroup$ – user130037 Dec 26 '20 at 19:31
  • $\begingroup$ @user130037. Yes sure, take your time. Please let me know if you agree with the above reduction. I do not know if there is any approximation algorithm for your problem. We would have to search in the literature if some similar problem exist. $\endgroup$ – Inuyasha Yagami Dec 27 '20 at 10:16
  • $\begingroup$ @user130037 However, your problem can be reduced to the following problem: The given sequence of objects can be equivalently stated as a weighted graph $H$ where weight on an edge $(u,v)$ represents the number of times the objects $u$ and $v$ appears consecutively in the sequence. Now, finding a mapping of objects to the location graph $G$, with minimum traveling cost can be equivalently stated as finding a subgraph $H'$ of $G$ that is isomorphic to $H$ and has the minimum total weight. I do not know if such a problem is already studied or not. The problem does seems very meaningful. $\endgroup$ – Inuyasha Yagami Dec 27 '20 at 10:16
  • $\begingroup$ I am thinking about solving it using DP. For example, the first level is to assume object1 is in pos1, pos2, ... and the second level is to assume given object1's position, object2 is at pos1, pos2, ..etc. You can soon realize there are computations that are repeated:eg. obj1@pos1 and obj2@pos2 and obj3~n@pos(3~n) and obj2@pos1 and obj1@pos2 and obj3~n@pos(3~n). However, we cannot prune the tree in this scenario as all the subsequences containing obj1 or obj2 cannot be calculated until the rest of the positions are calculated. So I feel this can be improved from n! but what do I know :) $\endgroup$ – user130037 Dec 27 '20 at 15:18
  • $\begingroup$ @user130037 I agree that all the subsequences containing obj1 or obj2 cannot be calculated until the rest of the positions are known. However, once you fix the positions of some k objects, you need not recompute those subsequences that only contain these k objects. Therefore, your algorithm would be better than the brute force algorithm that you stated in your question. However, its complexity would be also $O(n!)$ $\endgroup$ – Inuyasha Yagami Dec 27 '20 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.