OsmAnd and others: Calculation: Speed vs. accuracy, distance vs. accuracy => feature request

[Harry van der Wolf]

Hi,

Sorry to disturb the new OsmAnd routing functionality with this request, but I think it is necessary.

I tried OsmAnd (OA) versus BeOnRoad (BOR) and Mapfactor Navigator Free (MNF). Latter two are closed source, closed maps but free and based on OSM. BOR maps are old. MNF maps are very small but lack details the OA maps do have which is particularly useful for cycling and hiking.

To start with: OsmAnd is by far the most versatile planner in all conditions and supports the most options.
==
Short distance calculations, e.g. in a city or between two cities near each other.
fastest: MNF, slowest: OA.
best accuracy: OA, worst accuracy: MNF

Within a city or between two nearby cities the speed difference is noticable but not worth mentioning. They are all fast enough. So OsmAnd is the winner.
Within a city, especially one you don't know, it is nice to get the most accurate route, even though they all bring you where you want to go.

==
Long distance (200 km):
fastest: MNF, slowest: OA.
best accuracy: OA, worst accuracy: MNF (my interpretation: Harder to judge as factors of traffic light penalties, faster/slower roads, average speeds for roads between apps, etc. play an important role).

Here the speed difference becomes a real pain in the back side. Besides: travelling 200 km will save you a few kilometers and a few minutes. So: who cares. Traffic density and traffic jams determine your average speed and travel time far more.

==
Very long distances (600-800 km):
This forces me to create wayspoints in OsmAnd. This is a real nuissance. Why should I find/determine my own route because my route planner can't do this? This is THE reason to use a route planning app: to find a route for me. If I need to determine it myself it has no use.
All apps create the routes where MNF is again the fastest and OA the slowest (by far).

On a 600+ km tour what does accuracy really mean? Saving you 10 kilometers or 10 minutes (fastest route)? And that is only theoretically. I do think OA calculates the best route, but how do I know for sure? I need to create waypoints which might have a negative effect on the "shortest path". And OA takes so extremely long to calculate! Saving 10 minutes or 10 kilometers are only theoretically. In Germany (wintersports) I sometimes take a 35 km longer road because I know it is faster as there is less traffic (or at least I think so :) ).

Feature request:
Based on the distance between starting point and destination before calculating the route:
- Use the new accurate routing for routes up to 50-60 km (or something like that).
- Move back to the previous (<=1.6.5) calculation algorithm for longer routes.
- Optionally: Give the user the choice what algorithm to use.

I have filed this as a feature request (https://code.google.com/p/osmand/issues/detail?id=2301) but I also like to know what others think of this.

Harry

[Arndt]

Am Sonntag, 13. April 2014 16:47:35 UTC+2 schrieb Harry van der Wolf:

 

 but I also like to know what others think of this.

Hi Harry,

we two had a similar discussion last August and your point at this time was the same, namely that speed is everything and solving the path-finding problem correctly does not matter. I still do not share this point of view:

https://groups.google.com/d/msg/osmand/paCDL5_xHkk/bUchpBjPAzAJ

However, in these last 8 months I did most of the homework that I described there regarding "brouter", espacially I implemented "carsubset" routing files and "timeout free recalculations" (and I open-sourced it, added a download manager and put in on play..). Though this is still not a usable car-router (travel-time calculations, turn-restrictions and network-generated voice hints are missing), it's a proof of concept that it could be a usable solution for cars as well (currently the focus is still bikes).

I'm not willing to compare with closed source solutions that all do some dirty trick, let it be precalculated shortcuts (killing flexibilty) or dirty heuristics (killing corectness), but maybe you can give it a second try to judge where it stands in your comparison?

regards, Arndt

[Harry van der Wolf]

Hi Arndt,

This is going to be a long reply.

2014-04-14 9:33 GMT+02:00 Arndt <abre...@googlemail.com>:

Am Sonntag, 13. April 2014 16:47:35 UTC+2 schrieb Harry van der Wolf:

 

 but I also like to know what others think of this.

Hi Harry,

we two had a similar discussion last August and your point at this time was the same, namely that speed is everything and solving the path-finding problem correctly does not matter. I still do not share this point of view:

https://groups.google.com/d/msg/osmand/paCDL5_xHkk/bUchpBjPAzAJ

The discussion of August is related to this one, but not entirely. I will focus on this new discussion.

"namely that speed is everything and solving the path-finding problem correctly does not matter"

This is not what I said: not at all actually!! You really twist my words and put them in another perspective.

I compared 3 apps and mentioned that on shorter distances OsmAnd is the slowest but does the best calculation and OsmAnd is to me the clear winner. I did some routing in situations where the A* normal algorithm might fail. Routing around building blocks (can be right route or left route and which the is the fastest/shortest/best), or accessing a city where you can take the circular way around the city clock-wise or counter clockwise to reach your destination in the city, and which is the fastest/shortest/best).

On longer distances (200 km) I still consider OsmAnd the best but it takes long and I question the absolute accuracy.

On very long distances (600+ km) OsmAnd is not usable without doing some tricks (waypoints) otherwise you run into memory issues above 300-350 km (on my phone with 512MB memory), and it is very slow.

I want an app that "simply" calculates the route to my wintersport destination (800-950 km) or to my summer holiday destination (600-950 km) without crashing and without having to add waypoints.

Adding waypoints influences your 100% accurate calculation. It might no longer be 100% accurate over the total trajectum. It is only 100% accurate between the waypoints. So then what is this 100% accuracy worth?
I only want/need waypoints if I want to deviate from the route to see something special, find a hotel, a camping or for whatever reason. I don't want to create waypoints because my application can't calculate the entire route.

That's why I don't care about 100% accuracy over such a long distance. It's a 1 day travel anyway and maybe 10 minutes or 10-20 kilometers shorter than using a less accurate routing algorithm, but it doesn't take 6 minutes to calculate (or most of the time crash).

I still have my old Navigon device as well and this one is extremely fast in calculation and brings me at the same point with distance difference within 2-3%. I very well know that distance itself is not the measure. Max. speeds on roads, speed penalties due to crossings, cities, and yes: distance, determines the best route.

 

However, in these last 8 months I did most of the homework that I described there regarding "brouter", espacially I implemented "carsubset" routing files and "timeout free recalculations" (and I open-sourced it, added a download manager and put in on play..). Though this is still not a usable car-router (travel-time calculations, turn-restrictions and network-generated voice hints are missing), it's a proof of concept that it could be a usable solution for cars as well (currently the focus is still bikes).

I will have a look at it and I will try it.

 

I'm not willing to compare with closed source solutions that all do some dirty trick, let it be precalculated shortcuts (killing flexibilty) or dirty heuristics (killing corectness), but maybe you can give it a second try to judge where it stands in your comparison?

I certainly will try it. I support Open Source already since 1993, I am release manager of another OS project and have created a few OS programs myself and some of them are still available and one is under active development: I really like, support and create Open Source.
I also consider myself an active contributor to the OsmAnd app and really try to help it get better (IMHO). I simply can't program in java and I actually don't want to learn yet another language (being already a bit older I have seen and used over 10 programming languages by now. That also makes that I can "read" java. but creating code is something completely different).
I only made the comparison with closed source apps due to the fact that OsmAnd simply can't calculate longer routes anymore.
I also consider the fact that you don't want to compare open source with closed source as a flaw. When Open Source does better some OS guys/girls shout it from the roofs. When it compares worse they don't want to compare. That is not fair.
A few OsmAnd versions ago I could create routes up to 1200-1500 km (depending on the road density) by setting the java heap space to its maximum. Now I can calculate routes up to 350 km, max. 400 km. I don't call that an improvement.

That's why I would like to see a balance between 100% accuracy for shorter distances and less (but still very good accuracy) on longer distances.

Harry

[Harry van der Wolf]

2014-04-14 11:12 GMT+02:00 Harry van der Wolf <hvd...@gmail.com>:

That's why I would like to see a balance between 100% accuracy for shorter distances and less (but still very good accuracy) on longer distances.

Harry

Note also that on (very) long distances the route is mostly going over motorways, trunks and primary roads. All applications do that fine. It is in the beginning and the end where the accuracy is needed. And the driving time is not in the end or the beginning, which is normally 2 times 5-15 minutes compared to the 1 day travel "in the middle" where evey app takes almost the same route.
Again: That's when I want an algorithm that "simply" works.

Harry

[Marek Tyburec]

I am not an Osmand developer nor don't know Java, but I love Osmand. Just have few comments regarding new navigation system. 

I agree that for shorter distances it makes sense. It may also make sense for longer distances when preparing really the best route from home before driving. However imagine this situation: driving to 500km far destination and in the city there is a short detour not mentioned in OSM. What osmand does is route recalculation which will take really long - and in that time you lose all the instructions (maybe not so good example but the point is sometimes new route is needed relatively soon). That is where fast algorithms shloud (have to) be used.

I know that heuristics may lead to best/good/not so good/wrong results. However it should give you the point how it may be good to travel, at least good direction. Why not calculate route fastly (using heuristics) and in the backgroud optimize the route more precisely?

Secondly I agree with Harry that user should not have to create waypoints. If the calculation algorithm can't calculate so long routes, it should create them automatically (according to some sort of "intelligence") or at least warn user that the destination is further than the device can calculate -> "Please, create waypoints." I think that the depandance of possible calculation distance and available RAM may be easilly found.

[Cristián Serpell]

I know that heuristics may lead to best/good/not so good/wrong results. However it should give you the point how it may be good to travel, at least good direction. Why not calculate route fastly (using heuristics) and in the backgroud optimize the route more precisely?

I totally agree with that feature. Maybe developers already had this discussion? I am also not an OsmAnd developer, but I would love to help.

[Harry van der Wolf]

2014-04-14 16:46 GMT+02:00 Marek Tyburec <marek....@gmail.com>:

I am not an Osmand developer nor don't know Java, but I love Osmand. Just have few comments regarding new navigation system. 

I agree that for shorter distances it makes sense. It may also make sense for longer distances when preparing really the best route from home before driving. However imagine this situation: driving to 500km far destination and in the city there is a short detour not mentioned in OSM. What osmand does is route recalculation which will take really long - and in that time you lose all the instructions (maybe not so good example but the point is sometimes new route is needed relatively soon). That is where fast algorithms shloud (have to) be used.

+1
 

Secondly I agree with Harry that user should not have to create waypoints. If the calculation algorithm can't calculate so long routes, it should create them automatically (according to some sort of "intelligence") or at least warn user that the destination is further than the device can calculate -> "Please, create waypoints." I think that the depandance of possible calculation distance and available RAM may be easilly found.

OsmAnd already warns you if you try to calculate a route longer then 200 km. It does not create waypoints automatically (how should it? It is investigating possible paths.). That's exactly why I used the 200km distance in my experiments/mail.

The memory dependency is also related to road density. In Nordhrein-Westfalen you have a huge road-density which make a lot of paths to estimate, requiring a lot of memory. In northern Sweden, Norway and you name it, you can easily calculate longer routes.

Harry

[Marek Tyburec]

OsmAnd already warns you if you try to calculate a route longer then 200 km. It does not create waypoints automatically (how should it? It is investigating possible paths.).

But how should user know? Customly places waypoint will always have an effect on the solution (even though user chooses  them).

If I understand it correctly, world-basemap contains only higher-level roads, which could possibly be used as a first step of route calcullation - because when travelling for longer distances, people usually take them. This way, however, it will not be possible to connect always current position and final destination but again, would give possible parts of route and possible waypoints. By possible I mean there may be eg. two or three good-looking solutions and according to the lower-level roads navigation system would choose. But yes, it is ceartainly not globally-optimal sollution.

But again, I am not familiar with Osmand source code, so this is possibly an useless comment.

[sympa]

Shortcuts in the calculation do sometimes lead to not finding the correct route at all, but a very big detour. That is not desirable. Not a matter of "5% longer" but of "100% longer 5% of the time".

It might be useful if OsmAnd would place some hidden waypoints on longer routes. If a recalculation is needed, it could recalculate to a fairly nearby waypoint (maybe 5 or 10 km ahead). This would give a 'bring me back to the route' recalculation that would be pretty fast. When that has run, and the user has guidance again, calculate to the original (final) destination for the optimal solution. With a big penalty for making an immediate U-turn...

[Harry van der Wolf]

2014-04-14 22:24 GMT+02:00 sympa <echte...@gmail.com>:

Shortcuts in the calculation do sometimes lead to not finding the correct route at all, but a very big detour. That is not desirable. Not a matter of "5% longer" but of "100% longer 5% of the time".

It might be useful if OsmAnd would place some hidden waypoints on longer routes. If a recalculation is needed, it could recalculate to a fairly nearby waypoint (maybe 5 or 10 km ahead). This would give a 'bring me back to the route' recalculation that would be pretty fast. When that has run, and the user has guidance again, calculate to the original (final) destination for the optimal solution. With a big penalty for making an immediate U-turn...

That's a really nice idea. I don't know if it is workable but I think it should work as it stores the route you are going to take, and it recalculates if you deviate, from point to point.

Harry

[Greg Troxel]

It's a good idea, and from experience I suspect Garmin does this. But I
think there needs to be the longer calculation in the background.
Something that often happens to me is that a route is calculated, and
it's one of 4 reasonable ways to go, and the right way of those 4
depends on traffic. I go a different one, and get directed back for
longer than I think I should, with some stickiness.

So I'd modify the suggestion by saying (I realize this is all not
consistent):

place waypoints more like 20km ahead - just close enough that the
recalculate time is ok.

choose waypoints by using higher-tier roads

if on a motorway, choose not only on the motorway, but at least one
exit and 10 km farther along, so that a route that chooses a different
entrance can succeed

After calculating a route like this, calculate using the full
algorithm in the background, and flip if it's better.

[Arndt]

Am Montag, 14. April 2014 22:36:31 UTC+2 schrieb Harry van der Wolf:

2014-04-14 22:24 GMT+02:00 sympa <echte...@gmail.com>:

It might be useful if OsmAnd would place some hidden waypoints on longer routes. If a recalculation is needed, it could recalculate to a fairly nearby waypoint (maybe 5 or 10 km ahead). This would give a 'bring me back to the route' recalculation that would be pretty fast. When that has run, and the user has guidance again, calculate to the original (final) destination for the optimal solution.

That's a really nice idea. I don't know if it is workable..

It's an old nice idea:

https://groups.google.com/d/msg/osmand/CTwTvlKSHKQ/Bz98kmpxxD0J

and I'm sure that it's workable, because I implemented something very similar in the "BRouter" routing engine. You can try it, it works!

I say "similar" and not exactly sympa's proposal because I do not use a distance limit (5 or 10km), but a calculation time limit of 60s, and I do not use "some" waypoints along the old track, but consider every node on the old track as such. I also do not finish the recalculation in the background after the 60s timeout, but just return a merged track from the old and the new calculation.

To get an initial track for a long distance journey, it may be neccessary to calculate one outside OsmAnd, using the BRouter-App, but once you have a track, recalculating from within OsmAnd works fine.

[Arndt]

Am Sonntag, 13. April 2014 16:47:35 UTC+2 schrieb Harry van der Wolf:

 

Long distance (200 km):
fastest: MNF, slowest: OA.
best accuracy: OA, worst accuracy: MNF (my interpretation: Harder to judge as factors of traffic light penalties, faster/slower roads, average speeds for roads between apps, etc. play an important role).

Hi Harry,

 I re-checked if MNF is usable in the meantime (since my last test more than year ago but I was disappointed again:

• for car-routing, it's obiuos that MNF aggressivily tries to reach the next "logical network level", just like I expect that for a "simplified" routing algorithm that does the long-distance calculation on roads only. Attached an example where it is going south just to leave a residential area as quickly as possible to reach a road heading north. I do not want a navigation which sends me on detours just because of routing-simplifications. OsmAnd Offline does it right here.
• for bike routing still a complete desaster. You frequently see glitches from access=no/private + bicycle=yes. This is bicylce allowed, but for MNF (and I think for OsmAnd Offline as well?) this is bicylce not allowed. Just wrong. But the most severe glitch I see when calculating a bike route from South of Darmstadt to e.g. Bad Soden(Taunus). It calculates complete nonsense. a route that is far too long and includes motorways (see attachment) Looks like an integer overflow or some other very basic software bug. And I re-checked that with the MNF installation on another Phone more than year old: old software, old map, same bug. So it's very obvious that there's no testing at all for bike routing mith MNF.

regards, Aarndt

[Arndt]

Am Samstag, 26. April 2014 13:01:34 UTC+2 schrieb Arndt:

for car-routing, it's obiuos that MNF aggressivily tries to reach the next "logical network level", just like I expect that for a "simplified" routing algorithm that does the long-distance calculation on roads only.

If you still don't believe that MNF is doing such a dirty trick: add a road-block ("deactivate connection") in a village of a route you just calculated and then re-caclulate: it will make a big detour avoiding this village completely, instead of just bypassing the road-block on residentials. So it's  just not able to find a route with residentials in the middle.

[Harry van der Wolf]

I do believe that MNF is doing such dirty tricks. I also concluded that it is the most inaccurate one. I used it to compare and tried it 2-3 times in real life and didn't use it anymore (also because the Dutch voice is horrible, but that's a matter of personal taste).

I also mentioned it to compare it with a.o. OsmAnd and to mention that, even though it is innacurate, it could easily calculate routes of over 600 km.

And if you drive 815 or 831 kilometers, or 1018 or 1028 kilometers, it doesn't matter anymore if you start from the same starting point and end up at the same destination. All apps lead you there.

That's each time what I try to say. Below 200 kilometers I want (absolute?) accuracy. Above that distance it is less important. Above 200 kilometers (and for OsmAnd that is above 300-400 kilometers) I simply want to have a route calculated.
The driving time is more determined by traffic conditions (or how long you have to wait for a toilet in a road restaurant) then 15 or 20 kilometers less or extra. And more accurate is not always the shortest distance. It can also be a longer distance due to the fact that the route is faster.

If I drive a full day, 1½ day or 2 days, what do I care about 15-30 kilometers?

If it could be absolutely correct, it would be the best solution. If it can't calculate the full route it is an inferior product.

That's why I want/like OsmAnd to use absolute accuracy up to 200 kilometers, and above that "some" algorithm that can calculate a full route.

I use OsmAnd about 2-3 times a week and it is the only program I use (unless in comparisons), but it annoys me already for 1½ years or so (as long as I use it) that it can't caluclate longer routes. And that got even worse now.

As said before: What is absolute accuracy if you can't use it? And absolute accuracy is worth nothing if I need to set waypoints to be able to calculate a longer route. (And even for longer routes I use OsmAnd even though the waypoint necessity annoys me enormously).

Harry

--
You received this message because you are subscribed to the Google Groups "Osmand" group.
To unsubscribe from this group and stop receiving emails from it, send an email to osmand+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Harold Blount]

Just a thought .. maybe it has been suggested .. but why not use a quick and dirty algorithm for a first-cut on a long route and then place hidden way points on this route at 200km (or less) increments and do incremental very accurate routing through these waypoints?

I agree that Garmin likely does incremental routing on the fly. I notice often turn directions only pop up as you get closer to an intersection if it is a slight left/right jog in close detail that from a distance looks like a straight line.

As cyclists planning tours I am more interest in creating a route that takes me through the waypoints and scenic roads I have selected rather than optimizing time. .. except when I jump in a car and want to get to my recreation point asap!

HB

[JeCh]

I have been using the desktop version of MNF for many years as my navigation. For cars it works perfectly. With the default settings, it tries to get you on a main road as quickly as possible, which doesn't make muc sense. But if you tune it to your preferences and needs it does a perfect job especially in cities. If Osmand would be able to navigate my car as good and as quickly as MNF I would be absolutely satisfied.

Actually Osmand gives worse results for ~200km roads then MNF. Try to search how to get from Plzeň, CZ to Passau, DE. The are basically to 2 choices: use the shortest 166km long road with no highways. It is short but quite slow. The second option is to go direction Cham, DE and join a highway from Regensburg to Passau by Deggendorf. This is by far the fastest route according to my experiences. And it is the route which MNF calculates. But OsmAnd will send you all the way to Regensburg making the trip almost 300km long. I would expect this result if I selected "prefer motorways". But it is the longest of all three both in terms of speed and distance.

In the summary. I don't care which dirty tricks Mapfactor uses as long as it takes me to my destination faster using the same source data as Osmand.

For me Osmand is great for walking and biking (mainly thanks to Arndt's BRouter)  but still unusable for car navigation.

[Harry van der Wolf]

Hi JeCh,

With regard to MNF: I know that for longer routes it indeed tries to get you on a main road as soon as possible. They call it the "transit network".

It is actually the same as a "major roads" map used (internally) by many commercial products as well. It is not the same as the roads_only maps from OsmAnd because these contain all roads.

So, for distances to approx. 250 km use OsmAnds accurate routing.

For distances above 250 km, I would like OsmAnd to do the same as many other map products. Get me on the main big road a.s.a.p. en then: "Disable" all smaller roads. It would reduce the number of possibilities in a huge way and thereby decrease memory use and increase performance = speed of calculation.

And for the last 30-50 (?) km, use the absolute accurate routing again.

When you get close(r) to your destination, OsmAnd could even recalculate in the background to probably find a more optimized route.

Now OsmAnd does a 2-step routing as well and Victor explained it once in an extensive mail to the group, but I forgot, can't find that mail back and theferore currently still don't understand the concepts.

Note also: Some 1-1½ year ago I created major_roads maps for OsmAnd for e.g. France, UK, Germany, Spain, Belgium, Netherlands and a few others (using omsconvert, osmfilter and OsmAndMapCreator). To get me to my destination from Nederland through Belgium and France to Bretagne (1028 km), I used the France major_roads map and Bretagne. That also allowed me to calculate a full route and do it reasonably fast.

Same for my wintersport destination from Nederland, through (major_maps) Germany to Austria (815 km). OsmAnd could calculate a full route and do it fast.

I did not even think of that this year :)

Harry

[Harry van der Wolf]

And Bretagne is Brittany in France. Forgot to translate.

Harry

[Marek Tyburec]

A little off topic - is it possible to switch between more vector maps of eg. the same country?

Dne pondělí, 28. dubna 2014 17:08:33 UTC+2 Harry van der Wolf napsal(a):

When you get close(r) to your destination, OsmAnd could even recalculate in the background to probably find a more optimized route.

Harry

Agree with what you wrote except one little thing - the final-part-of-route optimization should be done as soon as possible to avoid (in extreme situation) forcing to make a U-turn when approaching to exact distance.

[Harry van der Wolf]

Hi,

2014-04-28 17:45 GMT+02:00 Marek Tyburec <marek....@gmail.com>:

A little off topic - is it possible to switch between more vector maps of eg. the same country?

When you say "to switch between" I assume you mean "to use at the same time".
Yes, that's possible but normally not advisable.
The point is that every map that contains routing information is taken into account for the route calculation. This means also (from my example) that he major_roads map of France, when going into Brittany (Bretagne) contains the same major roads information as the "full" Brittany map has (next to the minor roads information).

It means that OsmAnd calculates everything twice for that part. It doesn't see that motorway 1 in the major roads map is the same as motorway 1 in the detailed map.

So do not simply mix a roads_only map with all the detailed maps of. e.g. Germany or France.

 

Dne pondělí, 28. dubna 2014 17:08:33 UTC+2 Harry van der Wolf napsal(a):

When you get close(r) to your destination, OsmAnd could even recalculate in the background to probably find a more optimized route.

Harry

Agree with what you wrote except one little thing - the final-part-of-route optimization should be done as soon as possible to avoid (in extreme situation) forcing to make a U-turn when approaching to exact distance.

That's why I mentioned to switch to accurate routing again in the final 30-50 km.

Harry

[JeCh]

Hi Harry van der Wolf,

I absolutely agree with your solution. I think that only main roads should be used for long distance routing. Then during your trip, every lets say 10km OsmAnd should try to recalculate the road to the next waypoint 50km away to check if there isn't a better option then the originally calculated route.

Of course sometimes even this will not be the best way but with the increasing processing power of smartphones a more precise algorithm could be an option. Also I think it should be possible for users to tune this parameters to make a good balance between precision and calculation speed.

Best regards,
Vladimir

[Areg]

Hi All

I agree with the part that Routing calculation should be improved much.

I have tried to calculate the route from Cambridge to Gatwick Airport (UK) which is about 90 miles and it took ages actually.

I gave up and left phone on side. It finally calculated but drained about 30% of battery.

It was necessary to switch the engine to YOURS to see the possible route, put the Waipoint in a middle and switch back to the OSMAND.

As already was mentioned this is not acceptable as the Navigator should suggest the way.

PS. I am using Samsung SGS2 and previous versions calculated route much more faster than latest version.

Regards,

Areg

[sympa]

A "transit network" and a "contraction hierarchy" are close together, conceptually. But the first is a dirty workarond while the seconds leads to the correct solution.

One could use a contraction hierarchy to find a quick and perfect solution, with the disadvantage of no fine tuning.

I have a feeling that avoiding roads and contraction hierarchies could work together. User blocks segment, if it is not in the CH path there is no problem (this needs mapping the blocked section upwards in the CH hierarchy - dunno if that is possible). If it is in the CH, then avoid this path in the CH and search for an alternate solution.

[Harry van der Wolf]

2014-04-29 23:01 GMT+02:00 sympa <echte...@gmail.com>:

A "transit network" and a "contraction hierarchy" are close together, conceptually. But the first is a dirty workarond while the seconds leads to the correct solution.

I know it is a dirty workaround. And on short distances it is sometimes a disaster. This has also been mentioned by Arndt.

I have noticed it myself if I use it inside a city. It is definitely not taking the optimal route.

On a long distance, say above 200 km, this is hardly an issue. Driving 200 km and another 2-5 in total at the beginning or end does not make a big difference.

And for caravan and motorhome drivers it might even be an advantage as they are on a big road as soon as possible, as that is what truck and caravan modes do as well in commercial products.

 

One could use a contraction hierarchy to find a quick and perfect solution, with the disadvantage of no fine tuning.

I have a feeling that avoiding roads and contraction hierarchies could work together. User blocks segment, if it is not in the CH path there is no problem (this needs mapping the blocked section upwards in the CH hierarchy - dunno if that is possible). If it is in the CH, then avoid this path in the CH and search for an alternate solution.

Contraction hierarchies have been mentioned more often but have no flexibility indeed, unless you build these hierarchies for multiple situations which take huge amounts of disk space. I tried it myself with osrm (http://project-osrm.org/).

So, "some" intermediate solution would indeed be the most optimal. I say most optimal, not the the best.

Harry

[sympa]

I think it is possible to re-expand a contraction hierarchy. CH adds shortcuts to a map. The CH is used for routing, but more detailed routing is used to 'expand' to the individual nodes.

The idea is like this:

1 - use the CH to find the route
2 - 'run the car through the route' and check if any actual road is slower than the the overlaid CH edges
3 - if there are delays, adjust the weight of the CH edges so they match the time found when 'running through' this piece of route
4 - use the adjusted CHs to find the route
5 - if this route is different than the previous one, go to step 2 to verify it
6 - the route is still optimal even with the delays, so this is the result

This might work well if there are some delays. But if all weights change a little, it might take too long.

[C K]

Hi
I just want to pick up this conversation.

I am working in th SW-industry for almost 30yrs and I have seen many discussions like this.

Experts tend to explain why only the 100% accurate solution is the only real solutions. Customers tend to have a usable solution no matter how it was done.

I fully appreciate the result of the development and the know how implementated in OsmAnd.

But if it's not useable it's worthless.

The whole life is a simplification and abstraction of very complex processes. Why isn't this possible here.

If I use a SW I would like to be supported by the most easiest way. I don't want ti think about algorithms how the software works or not. Whether "dirty tricks" or simplification gave me the quick an reliable result I don't want to care.

Is the route 2km shorter or 5min faster is an academic question but not relevant in every day use.

My proposal: Let the users decide. Useable fast solutions or almost unusable but very precise solutions.

Driving distances longer than 500km is very common in every days usage scenarios. Usually you don't need a navigation support for the every day way to the office. :-)

Just my two cents
Cheers

[Koen Rabaey]

Totally agree on this one

Users know best what they want to do (a 500km car drive with a few 5km+/- they don't care) or a 30km bike drive but they don't want to make a u-turn in the middle because of a forbidden road for bikes.

Best,

/koen

Op donderdag 29 mei 2014 12:38:56 UTC+2 schreef C K:

[Peter B]

Hi,

 

Ive been experimenting with sat navs recently on my phone, and like the look of OSMand since I have loaded you postcode file.

 

BUT - I feel OSMand really needs a third routing option, as in Navfree and Mapfactor.

 

When I tried NavFree (which unfortunately freezes on my phone, why I am looking for an alternative), I found the Fastest option sent me nearly back on myself - a long way round on main roads, and the shortest option used to many back roads.

The solution which solved the problem on Navfree was to set the routing to Economical (which I guess compares speed / road types wrt distance) - This made it come up with much better and more sensible routing.

 

Mapfactor has a similar option, 'Cheapest' which I assume does a similar thing. Unfortunately Mapfactor decided to try and send me completely off-track this morning whilst testing it on the way to work. 

On Sunday, 13 April 2014 15:47:35 UTC+1, Harry van der Wolf wrote:

Hi,

Sorry to disturb the new OsmAnd routing functionality with this request, but I think it is necessary.

I tried OsmAnd (OA) versus BeOnRoad (BOR) and Mapfactor Navigator Free (MNF). Latter two are closed source, closed maps but free and based on OSM. BOR maps are old. MNF maps are very small but lack details the OA maps do have which is particularly useful for cycling and hiking.

To start with: OsmAnd is by far the most versatile planner in all conditions and supports the most options.
==
Short distance calculations, e.g. in a city or between two cities near each other.

fastest: MNF, slowest: OA.
best accuracy: OA, worst accuracy: MNF

Within a city or between two nearby cities the speed difference is noticable but not worth mentioning. They are all fast enough. So OsmAnd is the winner.
Within a city, especially one you don't know, it is nice to get the most accurate route, even though they all bring you where you want to go.

==

Long distance (200 km):
fastest: MNF, slowest: OA.
best accuracy: OA, worst accuracy: MNF (my interpretation: Harder to judge as factors of traffic light penalties, faster/slower roads, average speeds for roads between apps, etc. play an important role).

Here the speed difference becomes a real pain in the back side. Besides: travelling 200 km will save you a few kilometers and a few minutes. So: who cares. Traffic density and traffic jams determine your average speed and travel time far more.

==
Very long distances (600-800 km):
This forces me to create wayspoints in OsmAnd. This is a real nuissance. Why should I find/determine my own route because my route planner can't do this? This is THE reason to use a route planning app: to find a route for me. If I need to determine it myself it has no use.
All apps create the routes where MNF is again the fastest and OA the slowest (by far).

On a 600+ km tour what does accuracy really mean? Saving you 10 kilometers or 10 minutes (fastest route)? And that is only theoretically. I do think OA calculates the best route, but how do I know for sure? I need to create waypoints which might have a negative effect on the "shortest path". And OA takes so extremely long to calculate! Saving 10 minutes or 10 kilometers are only theoretically. In Germany (wintersports) I sometimes take a 35 km longer road because I know it is faster as there is less traffic (or at least I think so :) ).

Feature request:
Based on the distance between starting point and destination before calculating the route:
- Use the new accurate routing for routes up to 50-60 km (or something like that).
- Move back to the previous (<=1.6.5) calculation algorithm for longer routes.
- Optionally: Give the user the choice what algorithm to use.

I have filed this as a feature request (https://code.google.com/p/osmand/issues/detail?id=2301) but I also like to know what others think of this.

Harry