3
\$\begingroup\$

I have a series of units and have been given 2d points that they must go to. However they are free to go to what point they like as long as all the units get to all the points in the quickest time possible. Each unit has its own speed.

What is the best algorithm if I ignore unit collisions and terrain is perfectly flat with no obstacles.

\$\endgroup\$
7
  • \$\begingroup\$ Read up on Traveling Salesman problem - that's what you are asking about. \$\endgroup\$ Dec 28 '15 at 0:45
  • \$\begingroup\$ Thanks but there are not just 1 unit. I could loop over each point and unit again and again and get it at On (On-1) \$\endgroup\$ Dec 28 '15 at 0:48
  • \$\begingroup\$ If you ignore unit collisions the number of units and their different speeds is irrelevant. You solve the TSP for your set of points once, and calculate for each unit from which starting point and in which direction the resulting shortest path should be travelled. \$\endgroup\$
    – Eric
    Dec 28 '15 at 12:14
  • \$\begingroup\$ @Eric I also want the total time to be minimum. \$\endgroup\$ Dec 28 '15 at 17:22
  • \$\begingroup\$ That much is clear. However, I don't see why you think the shortest path from solving TSP won't give you the shortest time. Can you clarify? \$\endgroup\$
    – Eric
    Dec 29 '15 at 0:03
3
\$\begingroup\$

This appears to be an O(2ⁿ) problem, but I have an O(n³) algorithm that converges to a local optimum, which from my experiments is also usually the best solution (tested with random configurations of up to 10,000 units). Also it seems to actually run in O(n²log(n)) mean time but I am really too lazy to try to prove this.

Here is how it goes.

First, precompute all possible travel times in an N×N float array time, i.e. time[i][j] is the time it would get for unit i to go to point j.

Then populate an integer array plan of size N where plan[i] is the point that unit i should plan to reach. Using plan[i] = i or initialising randomly didn’t impact my tests, the algorithm always found the best solution.

Finally, apply the following algorithm:

repeat:
    no_swaps_occurred = true
    for a in 0…N:
        for b in i+1…N:
            if max(time[a][plan[a]], time[b][plan[b])
             > max(time[a][plan[b]], time[b][plan[a]):
                swap(plan[a], plan[b])
                no_swaps_occurred = false
until no_swaps_occurred

In the end, plan contains the proposed optimal travel plan for all units.

\$\endgroup\$

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.