We have added a new method for Steiner Tree’s, which deals with the problem of connecting points on a network with the shortest possible set of links, so there is a path between all points. Like when you install pipelines along roads for various purposes.
Finding the optimum solution is an NP-complete problem, so our algorithm only finds an approximation – although a good one. If you inspect the sample below closely, you will also see that it had been slightly more efficient if node 7 rather than node 20 had been connected to the line between 6 and 16.
We have just implemented a number of low-level performance improvements of the simple isochrones (method DriveTimeSimpleDyn), so they are generated faster, particularly in large networks and when they have multiple steps. This is done by using the spatial index as part of the calculations and avoiding too many of the same conversion from degree to radians.
Here is a first view of the next major release of RouteFinder. It is based upon RW Net 4 and is for 64-bit MapInfo. Follow the roadmap for expected release.
We have come a long way with adding alpha shapes as one more way of doing polygon isochrones in RW Net 4. The example below shows a 5 km isochrone, based upon OpenStreetMap data:
Pitney Bowes has released an alpha version of their upcoming 64-bit version of MapInfo Professional. We decided to test it with the 64-bit version of RW Net 4 DLL and performed two runs:
MapInfo 12.0 > test.mbx > rwnet4.dll (32-bit)
MapInfo 12.5 > test.mbx > rwnet4.dll (64-bit)
It was the exact same mapbasic application and we got the exact same results (distance matrices, isochrones etc.). Success !!
The 64-bit version of RW Net 4 DLL shall be included in the next release of RW Net.
There is also the option of calling the RW Net 4 .NET assembly from MapBasic 12.5. According to the documentation this has been extended a lot, so it is possible to call constructors etc. This means support for objects, rather than only static methods. But that is an area we haven’t tested yet.
After several low-level fixes and changes, we have now managed to get RW Net 4 running on an Android device.
It is the exact same .NET assembly that you also use with Visual Studio and Windows.
The application below was developed with Xamarin and Mono/Android:
Now it is up to you to find out, where you can benefit from off-line route calculations in the field – requiring no expensive data connection !!
To be part of RW Net 4.17, which shall very soon be released.
For the municipality of Næstved we have calculated drive time isochrones showing the effect of the Fixed link at Femern Belt, scheduled to open in 2021 and connecting Germany and Eastern Denmark. Calculations were done with RW Net 4, OpenStreetMap data and this coastline dataset. Almost one hour is expected to be saved on drive time, making Berlin reachable in 5 hours.
The fully detailed OSM has been used in the calculations, while only motorways and trunk roads are shown.
Maps has been created with MapInfo Professional.
2013 network with ferry
2021 network with tunnel
We have been making experiments on calculating alternative routes, as can be seen on the map below:
Here we have 4 routes, the fastest (green) and then 3 alternatives. 1, 2 and 3 are mostly overlapping.
It will be included in a future version of RW Net 4, as soon as we have decided for an easy way of accessing the functionality.
A spatial index is key to the routing calculations, since it allows us to convert from real-world coordinates to the internal nodes and links of the street network. Many data structures have been developed for spatial indices and for RW Net 4 we have chosen a quad tree, where we are storing a mix of nodes and partial links in the cells. This makes it very fast to generate and query. Storing partial links mean we don’t have to test every section of even very long roads, but can focus on the relevant part (within the grid cell).
Index generation wasn’t as fast as we would like it to be, so we have just improved it with reduced memory foot print and calculation time as a result. Testing it on USA+Canada (35 million links) showed an improvement from 30 min to just 5 min. Loading the spatial index is also faster and uses 25-30% less RAM, while the speed of searches has improved, but no big difference. With typical GPS data a search takes just a couple of msec on the same network.
Below is an example of a spatial index with max 50 nodes in every cell:
We have added a minimum spanning tree (MST) algorithm to RW Net 4. This can for instance be used when putting telecommunication cables in the ground, under a road.
See an example output below (blue lines are the tree):