An (parallel) insertion-style heuristic as described in:
Potvin, Jean-Yves, and Jean-Marc Rousseau. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows." European Journal of Operational Research 66.3 (1993): 331-340.
is quite popular and can work in O(N^3) time following careful implementation:
Campbell, Ann Melissa, and Martin Savelsbergh. "Efficient insertion heuristics for vehicle routing and scheduling problems." Transportation science 38.3 (2004): 369-378.
With N=5000; N^3=125.000.000.000, this 10s eval should be feasible to achieve given todays hardware, especially when exploiting SIMD (harder; but fits the implementation of the 2nd citation well) and multi-core (easier).
Edit: 10s might be a bit hard...
An implementation of above will be memory-bound, as the calculations are trivial but z=125.000.000.000 evals will touch at least z * 4bytes * 10(values) in bytes: 5.000.000.000.000. (i have chosen the 10 arbritrary but it can be deduced from the papers algorithm -> how many values to read for each evaluation)
As a modern server-cpu (more mem-channels) will have a max mem-bandwith of ~ 300.000.000.000 (300GB/s) we have an lower-bound of 17 seconds.
A GPU would have 10x the bandwith and would fit more. In theory. In practice i also think it's one of the few use-cases in combinatorial-optimization where i would assume a GPU implementation will actually work out (but i never tried it).
Note on memory-bandwith estimations
Often code is cpu-bound (lots of complex calculations) but when algorithms are optimized heavily, often those implementations become memory-bound: you are slowed down by reading from memory and your calculations are starving!.
A popular example is dense matrix-multiplication. In gaming/AI there are more examples which explain why GPUs have much more memory-bandwith than CPUs!
The 2nd-resource algorithm will be memory-bound! It's a simple calculation but we need to read from large distance-matrices with little chance of caching (steps are not that local).
If we already now it's memory-bound, we can quickly estimate how much memory we will need to read during the execution of the whole algorithm.
If we know we will need to read X bytes, we can compare it to the theoretical maximum memory-bandwith our hardware provides to obtain a lower-bound!
Caveats:
- In practice, mem-bandwith will be lower
- The lower-bound is only relevant if mem-bandwith is the bottleneck
- I would argue it's never the case without using low-level programming languages
- For scripting-languages (python) or probably even Java, all of this is probably too optimistic
- I would argue it's never the case without using low-level programming languages