Time complexity and speed up

[iedmrc]

Hi, I've several questions to understand more how to run the tool more effectively.

• What is the time complexity of this solver?

• Does it depend on the number of objective functions?

• And how is it related to Job and Vehicle counts?

• And how to increase speed?

• How much does increasing the thread pool affect?

• And what's the maximum limit of threads?

• How to choose a stopping point? What do you advise, and how to make choose the trade-off between time and optimal solution.

I know there are many questions here but to understand further, I wanted to open an issue. Maybe we can elaborate them later in a document or a post to light the way for after-comers.

[reinterpretcat]

What is the time complexity of this solver?

If you mean complexity in terms of big O notation, then I would say it is quite complex and depends on VRP variant. Internally, some custom metaheuristic is used to find a good solution quickly.

Does it depend on the number of objective functions?

It depends: some objective functions are using some extra functionality which is called pretty frequently.

And how is it related to Job and Vehicle counts?

It is simple: more jobs - more complexity. Amount of vehicle types is also affecting complexity of the problem.

And how to increase speed? How much does increasing the thread pool affect? And what's the maximum limit of threads?

Performance questions are hard. At the moment, I working on performance improvements and stability of the search (https://github.com/reinterpretcat/vrp/issues/60)

How to choose a stopping point? What do you advise, and how to make choose the trade-off between time and optimal solution.

That's also hard question. You can try to use combination of time/generations and premature termination by coefficient of variation.