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).

(With more hardware being available, above can be made more robust by using parallel portfolios aka running the same with different parameters or seeding/initial-ordering)