Create a table with distance (matrix)

Hi,
I need to create a table from 8000 places with lat/long coordinates displaying distance between them.

Is that possible with Graphhopper? I am not a developer but getting into a personal project before connecting with a team

Thanks. Any documentation would be great

2 Likes

Hi Rocawabe,

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.

I will post any idea on this direction. Thanks @Gregws!

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();
        }

Note that my work laptop CPU is utilized 100%

Hello,

If I understood you correctly, here’s how I’ve done it.

private VehicleRoutingTransportCostsMatrix buildCostMatrix(List<GHPoint> pointsList) {
    // True could improve performance but return worst solution
    VehicleRoutingTransportCostsMatrix.Builder builder = VehicleRoutingTransportCostsMatrix.Builder
                    .newInstance(false); 

    for (int fromIndex = 0; fromIndex < len; fromIndex++) {
        for (int toIndex = 0; toIndex < len; toIndex++) {
            // If same from -> to
            if (fromIndex == toIndex) {
                builder.addTransportDistance(String.valueOf(fromIndex), String.valueOf(toIndex), 0);
                builder.addTransportTime(String.valueOf(fromIndex), String.valueOf(toIndex), 0);
                continue;
            }

            GHRequest req = new GHRequest(pointsList.get(fromIndex), pointsList.get(toIndex))
                .setVehicle(vehicle);

            GHResponse resp = hopper.route(req);

            PathWrapper wrapper = resp.getBest();

             builder.addTransportDistance(String.valueOf(fromIndex), String.valueOf(toIndex),
                    (wrapper.getDistance() / 100) / 10f);
             builder.addTransportTime(String.valueOf(fromIndex), String.valueOf(toIndex),
                    wrapper.getTime() / 60000f);
        }
     }
}

Then you can use it like this:

 VehicleRoutingProblem vrp = 
 VehicleRoutingProblem.Builder.newInstance()
     .setFleetSize(FleetSize.FINITE)
     .setRoutingCost(costMatrix)
     .addVehicle(vehicle)
     .addAllJobs(services)
     .build();

Hope it helps!

Hi Imarcelocc,

How long does it take you to build a 1000 job matrix using this builder?

Hi,

I never did for 1k jobs. Also, I’m using this library on a phone.

But for 1k I imagine that it will take a lot of time, nothing like you give it a try.

A sábado, 18/04/2020, 02:47, Greg Schaaf via GraphHopper Forum discuss-management@graphhopper.com escreveu:

You can make this a bit faster when you disable instructions and points:

req.putHint("instructions", false);
req.putHint("calc_points", false);
1 Like

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.