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][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:
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]):
no_swaps_occurred = false
In the end,
plan contains the proposed optimal travel plan for all units.