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.