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.