GraphHopper.com | Forum | GitHub | Maps | Blog

algorithm.searchSolutions() not maxing out CPU


#1

Hi!

We’re running jsprit on an 8-core server. I’ve noticed that during the searchSolutions() phase, our CPUs are only ever used at between 10-50%. Is there anything we can do to have the solution search phase run at 100% CPU usage?

Thanks,
Luke


#2

Hello Luke,

check out Using multiple threads to run algorithm

Basically, you need to do something like:

VehicleRoutingProblem.Builder problemBuilder = VehicleRoutingProblem.Builder.newInstance();
// Create your problem using problemBuilder
// ...
VehicleRoutingProblem vrpProblem = problemBuilder.build();
Jsprit.Builder algorithmBuilder = Jsprit.Builder.newInstance(vrpProblem);
algorithmBuilder.setProperty(Jsprit.Parameter.THREADS, "4");

Please note that specifying a number of threads will only max out your CPUs if there are multiple routes in your solution, otherwise the multi-threaded version might become slower than single-threaded! Read more about this here: Why Multi Threading slower than sequential?


#3

Hi, thanks for your reply.

We are indeed already setting the THREADS param.

We set it using Runtime.getRuntime().availableProcessors() so whatever machine we host it, it should use all available threads.

During our tests, we’ve been using 20 or so vehicles, and 1000+ jobs. I’m assuming there’s multiple routes!

What we’re seeing is that it the searchSolutions() phase does indeed use all the available cores, but they’re only utilised to about 10-50%.

I’m wondering if there’s something we’re doing wrong that’s holding that method back from using 100% of the available cores.

Thanks,
Luke


#4

Hi Luke,

I’m not a Java expert, but I think that your problem has nothing to do with jsprit: it’s cause lies in the way JVM handles multi-threading (via ExecutorService, as this is the common way to spawn threads, used also by jsprit).

Check this out: https://stackoverflow.com/questions/2867278/why-does-this-java-code-not-utilize-all-cpu-cores

BTW, I’m curious: how many routes do you get, on average, with 20 or so vehicles and 1000+ jobs and how long does it take to compute it?


#5

Thanks I’ll test that out, that’s helpful. I’m not a Java expert either which is probably why I’m stuck!

BTW, I’m curious: how many routes do you get, on average, with 20 or so vehicles and 1000+ jobs and how long does it take to compute it?

Our solution will end up a route per vehicle, but yeah it has to query millions of possible routes to determine the solution. The length of time comes down to how many iterations we do, and we’ve found that we need a LOT of iterations for really large problems like that, like 10,000 iterations or so, which with that many jobs takes a few hours.

I did some benchmarking on our 8-core (not sure what size) AWS instance with job numbers vs iterations (Note: using the smaller 1500 iterations, just to get a sense of the correlation of jobs to length of time), and in case it’s of interest these were the results:

60 Job / 1500 iteration / 18 worker
Took 1 minute

200 Job / 1500 iteration / 18 worker 
Took 4 minutes

1000 Job / 1500 iteration / 18 worker
Took 17 minutes

1700 jobs / 1500 iteration / 18 worker
Took 40 minutes

In general, we’ve found that it’s hard to get good results for problems with more than 300-400 jobs … even with high iterations.

This problem was talked about here:

And the first link in Stefan’s post sounded pretty interesting. The idea was to partition large job problems into different problems, by clustering jobs nearby each other somehow and then sending those clusters off to be solved separately, then joining the problem back together.

We haven’t tried to do that (yet) and it doesn’t look like anyone has with jsprit just yet.