A very short description of the FleetEngine method is
- Creating an initial solution (in short time)
- Improving it step by step (in much longer time).
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 to the right, 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 and TeleAtlas 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 differencies in hardware used, the street network and several other details unknown to us.
For a customer we have compiled RW Net 2 with FreePascal WinCE compiler and tested it on a couple of smart devices (HP iPAQ, HTC Touch HD) with Windows Mobile 6.1. Works very well. Expect to find it in next version RW Net 2.43 Pro.
Generating large and detailed drivetime isochrones has always been a RAM demanding process in RW Net 2. As part of looking closer at supporting Win64 (using FreePascal compiler), we had to update certain parts of the source code, using pointers. This also made us test various settings for the memory allocation routine. This gave us a ~10-15% improvement in both speed and memory use on win32 platform. But when compiling for Win64 we don’t see quite the same improvement, since the same pointers now require 8 bytes, instead of 4 bytes.
All in all we can now calculate larger isochrones on true Win64 with 8 GB RAM than with Win32 applications on the same pc. But not that much bigger.
If you have a maintained license for RW Net 2 and want to test it with FreePascal, drop us a line.
When the isochrone generation gets implemented in RW Net 4, we shall of course reuse these results and possibly improve them further (we still have ideas for improvements….)
Welcome to our blog.
We expect to tell about plans, technical issues, experiments we do and a lot more.
The design is still, hmm, you could say missing or just “default”. But one day we will find time to do something more nice. For now, just focus on the content
In the long run, the blog may also replace the newsletter sent out by e-mail, we’ll see how that works out as we move along.