0

I apologize if people feel like this stuff have already been explained plenty of times. But after an extensive search I am still not sure exactly what is what, or which information is still correct.

Essentially I have been trying to figure out what solver VRP uses and how I might optimize or parallelize it. (I know that the conventional wisdom is to decompose the problem into smaller problems, and I will also do that, but in the end I still need to solve the VRP problem for something like 500-2000 deliveries ideally.)

My first question is, which solver does or-tools vrp use?

https://github.com/google/or-tools/issues/1867 already asked this question, and was directed to: https://developers.google.com/optimization/routing/routing_options#first_sol_options

However, there also seem to be something about original CP solver, and the new CP-SAT solver. If I look at: https://developers.google.com/optimization/routing/original_cp_solver I can see that the original CP solver seems to have been replaced by the CP-SAT solver. However, it isn't explicitly stated that this is also the case for VRP problems?, but it is placed under the routing problem section.

Is there any command for getting/seeing the underlying solver being used?

How to parallelize?

Assuming that it is CP-SAT that is used as the solver, then the question is how to actually parallelize it. From what I understand CP-SAT is designed to used with multiple workers https://github.com/google/or-tools/blob/stable/ortools/sat/docs/troubleshooting.md#improving-performance-with-multiple-workers However it does not actually give me the command to set the number of workers?

It should be noted that I am using the python API if that makes a difference.

How to optimize?

I haven't found much information on this

There is talk about trying all the various solver strategies in parallel https://developers.google.com/optimization/routing/routing_options

There is this thread, where it is suggested to set the max callback cache size: https://groups.google.com/g/or-tools-discuss/c/yWdZm6nJLxI/m/qaiJMF5EAAAJ

What performance should I expect?

For my particular problem I have the following runtimes (using 1 core), if I do not use GUIDED_LOCAL_SEARCH:

n_deliveries/n_vehicles/runtime (s)
50/25/6
100/50/30
200/100/177
300/150/311

If I enable GUIDED_LOCAL_SEARCH, I get the following times for 100 searches:

n_deliveries/n_vehicles/runtime (s)
50/25/12
100/50/5.3
200/100/13
300/150/12
500/250/41

The above problems, were run on 1 core out of 10 on my laptop, and uses negligble amounts of memory. (Multi-Capacitated, Pick and delivery, with dynamic start and end points, time-windows VRP.)

Improve this question
1
  • Please read the site you link to: it is explicitly writen: Note that the original CP solver is the foundation of the routing library, and its API may be necessary to customize a routing model. Commented Jun 7, 2024 at 11:30

1 Answer 1

Reset to default
2
  1. The routing library is based on the original CP solver.
  2. CP-SAT is used as a subroutine
  3. The routing library is not designed to run in parallel.
  4. The best approach to speed up and parallelize solving is to decompose the set of visits into multiple sub-problems and solve them independently.
Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

The problem has already been decomposed as much as seem sensible. So now I am down to a single problem with maybe 500-1000 pickups and deliveries, and I would like to throw 20 CPU cores at that problem. I'm guessing OR-tools is non-deterministic, so one approach is of course to just rerun the same simulation on all 20 cores and take the best solution, but is that really the recommended way?
I'm guessing that the CP-SAT subroutine is also not able to use multiple threads? Or is it not doing the heavy lifting?
You can look in the code. It is used as a single thread solver.
Let us try to make the CP-SAT a thread parallel solver.
Following this, given that 1. am suggested by ortools to use CP-SAT solver instead of the original CP solver for solving a CP model. 2. the routing library is based on the original CP solver. So can we conjecture that the performance of routing library will improve to some extent if we replace the underlying original cp-solver with the new cp-sat solver?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.