Performance issue: Slow matrix calculation

[maarno]

Hello, I'm trying to solve a Travelling Salesman Problems with time windows and pickup/dropoff dependencies. I have an algorithm which needs the driving distance / time between all locations. I'm currently using the API to calculate the matrix:

router.CalculateWeight(Vehicle.Car.Fastest(), resolvedLocations, invalids);

It works fine, but it's very slow. A calculation with 5 locations takes about 2000ms on my Core i7-6700HQ@2.6Ghz with 16 GB running Windows 10. Is this considered normal? Since I have to work with about 20 locations, it doesn't work well for me. I profiled the calculation with dotTrace and got this result. Please don't mind the actually timings in ms, they are slower because of the profiling.

Any suggestions to speed things up are welcome :)

[xivk]

From your profiling I can see that you haven't contracted the graph. Make sure to add a contracted version for the profile you are calculating TSP's for, that should speedup things.

Use routerDb.AddContracted(Vehicle.Car.Fastest()), store the routerdb to disk and use that every time. More information is in the docs:

https://github.com/itinero/routing/wiki/RouterDb#contraction https://github.com/itinero/routing/wiki#start-to-build-real-world-applications

[maarno]

thank you for quick reply. Unfortunately the matrix calculation doesn't work when I use AddContracted.

Any idea what's wrong with this code? It works fine without the AddContracted.

// fails

[TestMethod]

    public void MatrixCalcuation_Contracted_Fastest()
    {
        // Arrange 
        RouterDb routerDb;
        using (var stream = new FileInfo(@"c:\temp\singapore.osm.pbf").OpenRead())
        {
            routerDb = new RouterDb();
            routerDb.LoadOsmData(stream, Vehicle.Car);
        }

        routerDb.AddContracted(Vehicle.Car.Fastest());

        var router = new Router(routerDb);
        var geoCoordinates = new Coordinate[]
        {
            new Coordinate
            {
                Latitude = 1.318115F,
                Longitude = 103.893715F
            },
            new Coordinate
            {
                Latitude = 1.298652F,
                Longitude = 103.846504F
            },
            new Coordinate
            {
                Latitude = 1.292534F,
                Longitude = 103.784882F
            },
            new Coordinate
            {
                Latitude = 1.245743F,
                Longitude = 103.827934F
            },
            new Coordinate
            {
                Latitude = 1.405317F,
                Longitude = 103.902763F
            }
        };

        // Act
        var resolvedLocations = router.Resolve(Vehicle.Car.Fastest(), geoCoordinates, 200);
        var invalids = new HashSet<int>();
        var weights = router.CalculateWeight(Vehicle.Car.Fastest(), resolvedLocations, invalids);

        // Assert
        Assert.AreEqual(0, invalids.Count, "Invalid locations"); // fails here
        Assert.IsTrue(weights.All(x => x.All(y => y < 9999999)), "Weights not correctly calculated");
    }

I did some more tests and they all fail when I use AddContracted

Might be related to this issue: https://github.com/itinero/routing/issues/114

edit: I did some further tests and while the matrix calculation is broken, the AddContracted speeds up the normal calculation a lot. Thank you!

[xivk]

Just to make sure before I look into this, what version are you using? As in what package did you install?

[xivk]

Can you give more details on the actual exception? Try doing AddContracted(profile, true)... it shouldn't be needed but it may solve your immidiate issue.

I'll try the tests as soon as I have some time. Feel free to send me the other failing tests too.

[maarno]

I'm using Itinero NuGet Version is 1.2.0.0

There's no exception. The invalids contain 5 elements and the weights are all infinite.

[maarno]

AddContracted(profile, true) doesn't change anything.

[xivk]

Ah ok, then they should be in the invalids set anyway.

Will check this out because there is definetly something wrong, have you seen this:

https://github.com/itinero/routing/wiki/Matrix-Calculations#error-handling => IGNORE this it's not up to date anymore:

• [x] Note to self, update matrix calc docs.

[maarno]

Yeah I have, but the Itinero.Algorithms.WeightMatrixAlgorithm class does not exist. Is it part of a different NuGet package?

[xivk]

@maarno This should be fixed now, let me know if you have any other issues.

Also opened this issue:

https://github.com/itinero/routing/issues/120