Efficient movement of units to different points with different speeds

Question

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.

Answer 1

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.