apersson850
02-11-2005, 07:46 AM
There's been a lot of discussions, over the year(s), about the quality of the calculated routes, why they differ from what you would expect and so on.
There are two things, limiting the possible quality of the routes: Time and memory.
To calculate the perfect route would take a very long time. Not an infinite time, since there aren't an infinite number of possible routes from A to B, given that we have to follow the roads on the map material in question. But there are many enough, to have a computer calculate routes all the way to the destination, without having figured out the best way to go there, even when we've found the way, using traditional methods.
So clearly, the routing algorithm has to clip off areas, which doesn't seem reasonable, to keep the number of possible ways small enough to handle.
When testing different routes, the computer has to keep data of the various possible ways to come forward in memory. Lets look at a very simple example:
........________
...__/_____......\__
_/...............\_____\__
...\__________/
.....\______/
The dots have no meaning, they are just placeholders.
As you can see, there are four possible ways from A to B, which are sensible. There are also stupid roads, leading back to where you came from, so the algorithm has to be able to figure out that they lead in the wrong way, or that they come back to where you've already been.
Also, after checking the routes in the lower half of the picture, the routes there, or at least the best of them, must be rememberd, while checking the routes in the top part of the picture. Otherwise, we can't compare which route is really the best.
In a real example, there are many more roads, thus many more alternatives to keep in memory.
Since memory is a limited resource, the algorithm sometimes has to discard a whole area, filled with small roads, and instead try to find a way around it, using larger roads. This will then be true, even if you set custom routing preferences (can't be done on the iQue, but the 3600a supports it) to favor minor roads, or if you set it to use the shortest road. The shortest may very well be along one of these small roads, but there simply isn't memory enough to figure out which way to go, along these roads. So the computer will have to use something that's easier to figure out, or run out of memory.
In the first releases of the iQue, a route too complex to calculate resulted in a crash, but now they display a message about the problem instead.
If you look at an area with many small roads, and you want to pass through it, then place a via somewhere inside that area. At a point that seems reasonable to pass, preferrably. Since the iQue (in this case, but the principles are general) then can calculate the entire route in two steps, the memory may be large enough to allow it to figure out where to go, along these small roads too.
This is also the explanation to why all these Avoids sometimes doesn't avoid anything. The alternate route, according to the users desire, may simply be too complex to calculate. So even if you set Avoid highways, or place an avoidance bar on a highway, or an area the highway passes through (possible on the 3600a), you may still be routed through there, if the alternatives have too many options to handle, within the existing memory constraints.
Once again, a strategically place via may solve the whole problem, since it allows the iQue to split it up in two halves.
I hope I've cleared up a few of the questions regarding this kind of algorithms in general, and the routing in the iQue in particular, with this post.
There are two things, limiting the possible quality of the routes: Time and memory.
To calculate the perfect route would take a very long time. Not an infinite time, since there aren't an infinite number of possible routes from A to B, given that we have to follow the roads on the map material in question. But there are many enough, to have a computer calculate routes all the way to the destination, without having figured out the best way to go there, even when we've found the way, using traditional methods.
So clearly, the routing algorithm has to clip off areas, which doesn't seem reasonable, to keep the number of possible ways small enough to handle.
When testing different routes, the computer has to keep data of the various possible ways to come forward in memory. Lets look at a very simple example:
........________
...__/_____......\__
_/...............\_____\__
...\__________/
.....\______/
The dots have no meaning, they are just placeholders.
As you can see, there are four possible ways from A to B, which are sensible. There are also stupid roads, leading back to where you came from, so the algorithm has to be able to figure out that they lead in the wrong way, or that they come back to where you've already been.
Also, after checking the routes in the lower half of the picture, the routes there, or at least the best of them, must be rememberd, while checking the routes in the top part of the picture. Otherwise, we can't compare which route is really the best.
In a real example, there are many more roads, thus many more alternatives to keep in memory.
Since memory is a limited resource, the algorithm sometimes has to discard a whole area, filled with small roads, and instead try to find a way around it, using larger roads. This will then be true, even if you set custom routing preferences (can't be done on the iQue, but the 3600a supports it) to favor minor roads, or if you set it to use the shortest road. The shortest may very well be along one of these small roads, but there simply isn't memory enough to figure out which way to go, along these roads. So the computer will have to use something that's easier to figure out, or run out of memory.
In the first releases of the iQue, a route too complex to calculate resulted in a crash, but now they display a message about the problem instead.
If you look at an area with many small roads, and you want to pass through it, then place a via somewhere inside that area. At a point that seems reasonable to pass, preferrably. Since the iQue (in this case, but the principles are general) then can calculate the entire route in two steps, the memory may be large enough to allow it to figure out where to go, along these small roads too.
This is also the explanation to why all these Avoids sometimes doesn't avoid anything. The alternate route, according to the users desire, may simply be too complex to calculate. So even if you set Avoid highways, or place an avoidance bar on a highway, or an area the highway passes through (possible on the 3600a), you may still be routed through there, if the alternatives have too many options to handle, within the existing memory constraints.
Once again, a strategically place via may solve the whole problem, since it allows the iQue to split it up in two halves.
I hope I've cleared up a few of the questions regarding this kind of algorithms in general, and the routing in the iQue in particular, with this post.