Return to Answer

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 with 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

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

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

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 with 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

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)

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