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.
Note: Got included in 4.39
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):
A very short description of the FleetEngine method is
We are currently working on adding several algorithms for the first step, in order to take advantage of the task structure, so simpler and faster algorithms are used for tasks without many restrictions.
This can be expected to give big benefits (many times faster depending upon task). Later on we shall look at doing something similar for the improvement step.
We have added a new function for calculating traffic flows in RW Net 4. Input is a list of traffic volumes between A to B. Task is to add up all these volumes and get a total flow on each link in the street network. Not so difficult doing on your own, if using node-2-node routing, but we have also added support for dynamic segmentation and keeping track of flow in both directions. This makes it an excellent tool for more simple situations, where you have decided an all-or-nothing approach is sufficient.
On the map all flows start at the red dot, and spread out in different directions like a tree.
More on this at Wikipedia.
In mathematical graph theory you work with vertices (nodes) and edges (links). An edge normally connects two different vertices or it becomes a loop.
RW Net has until now allowed loops. Since loops has several limitations in terms of lack of support for one-way restrictions etc. and also doesn’t fit with the “normal” algorithmic structure, we have decided to remove support for them in the route calculations. This means you can still use them in TNetwork and TSpatialSearch classes, but TCalc and TRouteCalc do not work at all, if there is just a single loop in the network.
Navteq (=HERE) and TeleAtlas (=TomTom) datasets hasn’t had any loops for a long time. With the release of our ITN converter from March 2011, you can now also avoid loops in ITN datasets.
Change to take place in RW Net 4 and FleetEngine after 1-1-2012.
After the release of Delphi XE2 and the included 64-bit compiler, we have upgraded RW Net 4 where needed and have had great success doing so: We are now able to create 64-bit applications and the route results are the same as before.
Main advantage of 64-bit are the possibility to work with larger street networks, while speed of calculations are not affected so much. It may even be slower for some operations. We shall get back to testing that detail at a later point.
Expect support for 64-bit in next release.
We have been doing some tests lately of OpenStreetMap (OSM). Inspired by a customer we realised that it had improved a lot since last time we looked at it. This time we checked out Denmark and Estonia. Conclusion is OSM topology is quite good for routing, but basic information such as oneway restrictions still lack in many places and the road classes (used for defining speed) is not always very strict. We have also noticed many roads are registrered as normal roads, even if they are closed for cars and only open to pedestrians / bicycles.
This means it is a good data source if you are not looking at creating driving directions, but is more interested in approximate drivetime and distance between locations not too close. Such as what you will typically use it for in FleetEngine at a regional / national level.
We have also developed a set of instructions and some applications for processing the OSM files, so they are easy to use in RouteWare products. If you want a copy, let us know.
Recently we did a test with a simple routing web service on behalf of a customer. Our aim was to find out how much time a request takes and how many requests can be processed per second. Input is two pairs of latitude-longitude coordinates and output should be approximate travel time. That is as basic as it gets.
The size of the street network was unknown, but in the range 1 – 2 million links. We decided for a rectangular area with 1.2 million links (West of New York) and generated random coordinates within that area, since the length of the routes was also unknown: A mix of short and long routes were expected.
We developed it in C# on top of RW Net 4, as a fully multi-threaded application.
Our result was app. 0.1 sec/route and we could generate 33 routes/sec on a quad core computer (Core i7-860). This included using the spatial index for converting the two coordinates to locations and finally calculating travel time between these, using dynamic segmentation.
The C# code shall be included in a later RW Net 4 Pro release as sample code.
Inspired by a recent post on MapInfo-L about the performance of a competing product, we decided to do a similar calculation with RW Net 4. Task is to create a distance matrix between 230,000 regions in the US. That is a very big calculation and just the output itself requires a lot of harddisk space. Even in a very compact format you would be looking at 200 GB (230,000^2 x 4 bytes).
We have free access to the TIGER database for the US and created random coordinates for the regions in order to have some input. First we imported the street network from MIF format. This took appr. 1 hour – not so bad. After all 4.7 GB of MIF file is a lot and the importer does more than just reading the file.
Next step was the actual calculations. We used the simple MatrixDynOut function in RW Net 4 with a smaller set of regions. After doing calculations for a while, we could extrapolate to the expected time for the full matrix: 60 days. A lot of time, but at least 8 times faster than the competing product, which had already spent appr. 15 months, divided between 5 computers, each working for 3 months. And still not finished……
There may of course be differences in hardware used, the street network and several other details unknown to us.
