I’ve asked a similar question trying to optimize the creation of a cost matrix but no one ever responds here. I guess it is due to it being a paid feature of graphhopper, the answer anyhows.
I’ve produced a 1000+ point matrix file in about 5 minutes through brute forcing it. This is by removing any unnecessary processing like hints etc from graphhopper.
The other thought I had was to split the task into individual threads in java to process the task simultaneously. I haven’t had time to try this though.
There are online comments around caching each result and checking the cache before calculating, but in my head I’m not sure how that works if you are doing a “One to all” matrix.
I wonder if graphhopper caches each individual instruction instead of “complete paths”. I’m unsure how to implement something like that.
Keen to hear if you have any insight or solutions of how to do this efficiently.
Open door logistics completes the task somewhat quickly for a 1000 point problem using forwards / backwards searching.
On a similar note, I also though that rejecting some results from the matrix might simplify the possible connections when solving the Travelling Salesman Problem.
Unsure if JSprit automatically rejects these but I thought might as well reject it before hand.
This was a semi recent attempt,
For 1021 delivery points;
Total connections 1021*1021 = 1,042,441
Execution time in seconds : 443.59357
Used < 150m : 37,686
Used >= 150m, < 200m : 19,014
Used >= 200m, < 250m : 24,022
Used >= 250m, < 300m : 28,406
Rejected >= 300m : 933,313
My points are quite clustered and I wouldn’t expect to use any returned distances =>300m from graphhopper.
Hiya, @rocawabe
I had some time to do some work on this and here are my results;
Single thread : Execution time in seconds : 443.59357
4 threads : Execution time in seconds : 159.257072847
example;
int section = (int)Math.ceil(vrpBuilder.getAddedJobs().size() / 4);
//int lastSection = vrpBuilder.getAddedJobs().size() - section * 3; You don't need to know the last section
Thread one = new Thread(new Runnable() {
@Override
public void run() {
// Create your loop of the first section
}
});
//Then create another thread to process next section
// start threads
one.start();
two.start();
three.start();
four.start();
// Wait for threads above to finish
try{
one.join();
two.join();
three.join();
four.join();
}
catch (InterruptedException e)
{
System.out.println("Interrupt Occurred");
e.printStackTrace();
}