Slow route (re) calculation

[bitboy85]

On long distances the route calculation is slow. This wouldn't be a problem but if a road is closed it seems to take the same amount of time to recalculate the route. In my case this was about 10 minutes. Maybe you miss the next possible route because of this.

Maybe both issues can be fixed if you assume that you usually use motorways on long distances so keeping the route after the motorway link and just recalculate the route to the link. On first calculation it might be possible to start navigation after finding a route to the next motorway link. the rest of the route could be calculated in background.

[scaidermern]

I noticed the same issue. A small deviation from the route results in a complete re-calculation which shouldn't be necessary. I don't know the current routing algorithm implementation. But I imagine a recalculation should be able to keep the previous route in mind while calculating a new one. At some point the new route might lead onto the old route, resulting in a combination of both routes and the recalculation process can be stopped early. Not sure if this is possible with the current implementation, though.

[vshcherb]

Current routing algorithm tries to use previous route for 3 times before running full recalculation. It has a threshold of 20km, so first 20km are always recalculated

[bumbaras]

I have the same issues with 2.8.2 and many earlier versions. Yesterday I have checked 250km distance and after 11 minutes the navigation was still calculating the route. It is unbearable and make this app totally useless now. And it wasn't so bad at the end of 2015 year (one, two minutes and route has been calculated). That is i have trashed 2.8.2, and will try to do some tests on versions 2.2 and 2.3 sideloaded. If it won't help, i will trash the app completely. Current online navigation mechanisms binded with OsmAnd are not acceptable as well because they are not respecting any navigation settings made in app.

Of course, official statement of developer is that my device is just too slow. I am aware that Android 4.1.2, qct msm8627 mtp and 1GB Ram are not attributes of speed demon, but well, I think that my old Lark and Mio485 have worse hardware but works much, much better (i know, they are dedicated devices and not on Android).

[bitboy85]

i don't think it is a hardware related issue. This happens also on my cars head unit which has an octa core and 2gb ram. Another thing where an unexpected long recalculation takes place is when you visit a rest area next to the motorway. Sometimes it takes minutes.

[bumbaras]

2.3.5 - the same map data as 2.8.2, the same destination, the same source point. Default settings. Route calculated in about 4-5 minutes. 2.8.2 couldn't finish it in 12 minutes. I got to home from work so i didn't wait anymore over that 12 minutes. Still too long as You ask me, but much better.

[sonora]

Possibly similar to #5030? Can you check if you also observe an order of magnitude faster pedestrian than car routing these days?

[bumbaras]

Don't think so that this is the same issue. On short routes, for example 30-50kms the calculation is quite fast, as far as i remember. I would need to check this again because it was quite long ago (yes, versions 2.2 and 2.3). Besides, i didn't put any results from my latest tests which might put support in wrong here. Returning to my previous post, I was happy that older 2.3.5 was able to calculate 250-300km distance in about 5 minutes, much short than 2.8.2. But the navigation is still unusable - older version may calculate route faster but if i choose the other way than navigation proposed, OsmAnd starts to recalculating route again and it takes next 4-5 minutes. And when calculation is over then it appears that new route still differs from my route and then calculation start again for next 4-5 minutes. So I am in fact driving without any navigation. I have gave up with OsmAnd for now. I will try other application, AutoMapa, which is alternative (not free) to check how it will work on Sony Xperia M.

[cgogolin]

I am currently using OSMAND on a long trip through Europe and route calculation over several hundred kilometers is painful slow to the extent that that is almost unusable, even on quite fast/recent hardware. I mostly use OSMAND for pedestrian navigation and always love it, but this is a problem that is rather seriously limiting its usefulness for longer trips.

Can long distance calculations not be done on a much simplified graph of just motorways and their rough intersections? Other navigation apps take only a split second for the same route for which OSMAND takes >10min :-(

[bumbaras]

You have to compare other offline product. Of course, if You take some offline mio product and compare it, the mio will be the speed beast in calculating routes even if the hardware is much worse than what You have in Your android device. The algorithm in the Osmand is probably to complex now and use too much details from maps and this is the result. The most painful thing is not that it takes so much time to calculate route but when You take the other road Osmand had proposed then the calculation starts from the beginning and takes another 10 (or longer) minutes - in this time You are still driving/moving so i don't have to say what will be the result of this calculation? Osmand doesn't have own online mechanism, and these online what have been implemented are really useless - for example the most useful online one in Osmand advices You to turn left or right on elevated highway (because highway is crossing some local road which runs below, and there is no direct connection).

[pss34]

As I can see, route calculated on one core of my 8. It makes osmand be equally slow on all devices. Is it algorithm flaw?

[naoliv]

I am seeing this problem even with short routes (from one side of the city to the other one): if I miss a street, it starts to recalculate the route.

But then it gives a solution/instruction to turn on a street which I just passed (since it took some time to calculate); and again, it starts a new route recalculation with the same type of problem, always giving a solution to a street which is now behind me.

It's just not fast enough to properly calculate a route for an approaching exit/street.

[scaidermern]

But then it gives a solution/instruction to turn on a street which I just passed (since it took some time to calculate); and again, it starts a new route recalculation with the same type of problem, always giving a solution to a street which is now behind me.

I think this is a more generic problem faced by all routers if you don't already drive on the route towards your destination.

Maybe if OsmAnd detects that you are moving it should not start calculating a route from your current position but instead from a position a few hundred meters ahead? How do other routers handle this problem?

[bitboy85]

From what i've seen on other routers the recalculation time is much smaller (only few seconds) so getting a solution you just passed cannot happen or it is very rare. Of course the algo should use multithreading to be much faster on multicore devices.

[bumbaras]

Do You think MIO S485 (from 2012) has better performance, better inside than decent smartphones? I understand, that there weren't so many details, but missing given route make the device to reroute in a dozen seconds which is acceptable. If the details are a problem in OsmAnd maybe this is just overloaded of bs which are not needed for a driver? This MIO was always offline and has POI as well. Rerouting route for 10 minutes is just unacceptable and makes such navigation a garbage.

[TheCapsLock]

You have to compare other offline product.

I tried another offline product (but proprietary) : Sygic : Sygic gets your way in a few seconds, blazing fast compared to osmand.

Today, it is difficult to me to convince people to use osmand because of this and also because of extremely slow and irrelevant search results compared to other products (Photon may be an answer for the latter one)

[wehkah]

Can long distance calculations not be done on a much simplified graph of just motorways and their rough intersections?

I am a driver who has passed a certain age, and I can tell you, this is exactly the way how long distance trips were "calculated" back in "the good old days", when maps were made out of paper and electronic guidance was something that only the army used for their tanks and rockets. ;)

In those "pre-electronic age", when you had to make a trip from A to B, you took a look at a large scaled map, you mentally connected the places by a straight line, and you simply looked for the most convenient and fastest roads that were the closest to this line. Then you memorized all the places along that road that you had to parse by or drive through, and then your trip started! Once on the road, you just followed the signs that told you how to drive from one way stop to the next. And just before you left or passed the last way stop, you took a look at a detailed city map and only then you would have looked up the proper way to your destination.

No one in those days would have started a trip of more than 200km by writing down each and every single street and little dirt road, that would have summed up to the shortest way, needing 10 different detailed maps and taking 5 hours to calculate that route.

Osmand is unbeatable when it comes to finding addresses and guiding you through a city that is not your home town. And I highly appreciate that and all the work that is being put into this project! I really love it! :)

But on the other hand: do you really need a navigation software, Osmand or other, to calculate a trip that consists of 490km on a highway and 10 km city traffic? I'd say: no! And, no offence meant, but any one who can't drive from edge of a country to the other without the use of a navigation software, should ask themselves, if taking a train wouldn't be the better solution...

Maybe this old-school routing mechanism, that cgogolin mentioned and that I described above, could be a solution for Osmand's "long distance problem": connect the starting point and the destination by a straight line, then look for the best paved roads and fastest lanes along side this line, and off you go! And once you're within 50km of the final destination, Osmand can calculate the exact route.

[bumbaras]

Well, the long time calculation for start is lesser problem than the fact that after changing on fly the route (for example route is closed due to accident) osmand start calculating it the same way which took the same time again. I can understand that google maps do this in blink of eye because it has strong servers behind. But why some offline Mio Spirit from 2012 is doing the same in few seconds? Its hardware is much behind current tablets. And Mio also can point You exact street and exact number. Maybe datas which Osmand is using as a basis to calculating routes is just too much complex or code is too much not optimized?

[jkufner]

I wonder why long-distance trips are so slow to calculate. When traveling long distances we always use highways (or similar fast roads*). Therefore, there is no need for Osmand to bother with low-grade roads and paths. The highway network is much less dense and navigation should take a second. Just find all nearby highways around current location and the destination, then plan route from the set of source highway points to a set of the destination highway points. Once such a route is computed, just connect the three fragments of the route — from current position to the source highway point, then the highway portion, and finally from the destination highway point to the destination.

Because the roads are (mostly) planar, the each set of highway points should form a polygon around the source/destination location. The highway routing needs to support multiple starting and ending points, but we can do that for any routing algorithm by replacing the path between source/destination position to a given highway point with a single edge.

* By "highway" here I mean various main roads: highways, motorways, 1st class roads, etc. Those roads that stay visible when you zoom out a little.

[wehkah]

That's exactly what I meant in my posting. There should be an option in Osmand, to always take the most convenient / the best build / the road with the highest speed limit / the most sophisticated road, or whatever you call it, as long as possible, and use city road only, if absolutely necessary. That is, for example, the last few kilometres when you need to go to an address within the city.

It really doesn't make sense to always use the shortest way, when the shortest way leads you through dozens of towns and cities, with a million traffic lights and very sloooooow traffic, while most likely there's a bypass road, a highway, a motorway or an autobahn nearby available, which elongates your trip just a couple of km, but safes you from getting mad because of urban traffic.

[scaidermern]

That's exactly what I meant in my posting. There should be an option in Osmand, to always take the most convenient / the best build / the road with the highest speed limit / the most sophisticated road, or whatever you call it, as long as possible, and use city road only, if absolutely necessary.

This is already the default. Unless you selected to take the shortest route, not the fastest.

[jkufner]

@scaidermern The question is how it is implemented. Investigates the routing algorithm all roads or the highways only? The routing speed sugests it investigates all routes and rejects them as too slow. There should be a very effective optimization available.

[wehkah]

Yes, you're right. But in many cases I have not seen a great difference in routing according to this setting. There are differences, yes, but still the option "fastest route" does not use all possible resources of bypass roads. I can not give you an adhoc example right now, but my experience is that Osmand prefers to go straight through a city instead of driving around it.

[pebogufi]

If you think route calculation is slow, read the discussion about changed heuristic coefficient (search for "heuristic" in forum) and test the recommandation of Harry van der Wolf. I like it, it is fast !

[scaidermern]

The question is how it is implemented. Investigates the routing algorithm all roads or the highways only? The routing speed sugests it investigates all routes and rejects them as too slow. There should be a very effective optimization available.

You have to consider all roads for finding the optimal route. Some locations are very far away from large roads. And sometimes you have to leave the motorway and enter it again at a later point in time to take the fastest route.

Approaches like contraction hierarchies would be an option but makes routing less flexible because it doesn't support configurable routing parameters. Howerever they could still be an option, for example by supporting the three most common routing parameter combinations.

[bitboy85]

I'm still wondering how very old devices could calculate a route quite fast. Without knowledge of how its implemented right now its hard to say what could be optimised. Maybe there are some unessessary checks. I guess we could assume that highways have best available surface and highest speed limit so there is no need to check this on every single piece of it.

As i said in the first post, main problem is not that it takes initially long to calculate. It just annoying it takes so long if something unforseen happend like a closed route and as also mentioned before, it happened to me if i visited an rest area next to the main road. I cannot understand why it takes minutes just to get back to the main road from the rest area even its the only possible way.

[jkufner]

You have to consider all roads for finding the optimal route.

Theoretically, yes. Practically, not really. When traveling across Europe there is no point in checking every possible road. Just get on highway and next few hundred km is planned. There may be a shortcut we miss (example – the bridge may get ignored), but if the length of a suboptimal route is similar to straight distance, it does not matter. If the found route is suspiciously longer, we may want to check for shortcuts and consider lower-grade roads.

Some locations are very far away from large roads.

The distance does not matter. If we can construct a polygon made of highways around the destination, we can ignore low-grade roads when searching a route to the polygon. Once we get inside, we need to consider the low-grade roads again.

And sometimes you have to leave the motorway and enter it again at a later point in time to take the fastest route.

By "highway" I mean various main roads. Zoom out on a map and those main roads stay visible when highways are visible. The point is that these roads form a network dense enough to find a reasonable route, but sparse enough to calculate the route in few seconds.

[wehkah]

I'm still wondering how very old devices could calculate a route quite fast. Without knowledge of how its implemented right now its hard to say what could be optimised.

I am no expert neither, but I my guess would be that pure navigation devices, even "old" ones, consist of optimized hardware that doesn't do any thing else but calculating routes. Those devices don't have to deal with things like operating systems, hardware drivers to be loaded, sharing the memory with other applications, and all those things that smart phones and tablets do.

[bitboy85]

i own a very old navigon / transonic with ARM chip. Its just a device having winCE 5(?) and the software installed, so no, i don't think theres something special built into it to do route calculation.

[wehkah]

Interesting... I'm curious: is there any way you can get information out of that system, like memory usage, CPU usage, etc?

Two ideas crossed my mind:

1. Leaving a route because of traffic jam, accidents or construction sites is something that really needs to be taken care of in Osmand. I think one good solution to this problem would be a button on the screen, that makes Osmand stop calculating a new route and keep the already calculated route. Once you're done with following the diversion signs and you're back to your original road, Osmand can reuse the old route without having to recalculate it.

The distance does not matter. If we can construct a polygon made of highways around the destination, we can ignore low-grade roads when searching a route to the polygon. Once we get inside, we need to consider the low-grade roads again.

I'd call that a really good idea! But is that really necessary? I am not familiar with programming, and I have no idea about Osmand and its techniques. But wouldn't it be enough to give the user a new option to give much more priority to fast roads and to low rate (thus ignoring) roads that lead through towns or country side roads?

[naoliv]

Wasn't Smart route recalculation supposed to mitigate this problem?

Maybe the code should be profiled to spot the slow paths and then find some possible optimizations.

[jkufner]

@wehkah Ignoring lower-grade roads when routing to the polygon is not something user will see. It is under-the-hood optimization.

The whole point is, that there is a lot of low-grade roads, but relatively small number of highways (and other main roads). If there are like 10 low-grade roads for each highway, then if we consider 1 000 highways when routing, we can ignore 10 000 low-grade roads. That is approx. 90% faster calculation.

[jkufner]

Leaving a route because of traffic jam, accidents or construction sites is something that really needs to be taken care of in Osmand. I think one good solution to this problem would be a button on the screen, that makes Osmand stop calculating a new route and keep the already calculated route.

User should not be bothered with such thing. Osmand should keep partial routing results cached and reuse them when calculating a new route. Then the recalculation should take less than a second, when we take a wrong turn and next street leads back to the original route.

[wehkah]

That would be the ideal case. But how should Osmand decide whether you are leaving the calculated route on purpose, e.g. because you want to have lunch, or if you are forced to leave the route because of road works, or if you simply missed the right exit? And how should Osmand decide if its supposed to calculate a new route or not?

Even if Osmand keeps the original route cached, which would be a very good thing to do indeed, how do you keep it from starting to calculate a new route, as soon as you leave this route, just because you want to have dinner or you need to fill up your car? This automatic re-calculating of a new route simply takes too long, and if you're moving and taking turns while the calculating takes place, this procedure takes even longer, because the device always tries to re-re-re-calculate a new route, taking into account all the turns that you took or that you did not take since you left the original route.

I don't think that this is something that can be taken care of automatically, as long as calculating a route takes longer than reaching the next turn or exit.

[jkufner]

It does not matter whether you leave the route on purpose or not. The task is the same — calculate route to the destination.

Thing about routing and path-finding in general is, that you don't really calculate the route. The road map is a graph of nodes and edges and the algorithm checks a subset of hopefully relevant nodes and edges whether they lead in the right direction. The algorithm also calculates partial distances between start and the currently investigated node (or distance from the destination if run backwards). So when the algorithm finishes, you get a data structure which contains distances from the start to the each point on the route and also to many other suboptimal partially computed routes around the found route. If you take a wrong turn (on purpose or not), there is a pretty good chance that the new route is already calculated, all you need to do is to collect the data and render it.

The trick is that we must not stop the algorithm (and discard the temporary data structures) once the route is found. We must pause the algorithm in the current state and restart it when the current location leaves the calculated area. Then we get instant route recalculation for free.

Another trick is to calculate the route backwards. When the algorithm calculates distance from the start and the start moves, the calculated data become obsolete. But the destination does not move. So we can calculate route from the destination to the current position, and if the current position moves, the algorithm will simply run a little bit longer to check few extra nodes in the end. It is the same case as when recalculating route after taking a wrong turn.

(Btw, here is some general explanation of what's going on under the hood: https://www.youtube.com/watch?v=GazC3A4OQTE … for those who did not study this area in school.)

[wehkah]

It does not matter whether you leave the route on purpose or not. The task is the same — calculate route to the destination.

And I think that this is the problem: if Osmand could be kept from calculating a new route as soon as you leave the actual route, it could react much faster, once you finished following a detour, eg because of road works. While you're following such a detour, there is no need to recalculate a new route, because the detour will eventually return you to your previous road.

That's why I would welcome a possibility to manually stop Osmand from recalculating a new route.

Another trick is to calculate the route backwards.

When the algorithm calculates distance from the start and the start moves, the calculated data become obsolete.

Yes, that is sooo true: often it takes less time to reach and pass the next exit or turn, than it takes Osmand to finish the routing and telling you should have taken that exit. :(

[jkufner]

I took a brief look into Osmand's source code and I think that Osmand calculates the route, stores it and then navigates. To make recalculations fast, I think it would be better another aproach. Let the routing algorithm run in the background and let it update the route as the current position changes. The difference is in preserving all the temporary data generated during the calculation, because the routing algorithm is running the whole time (but not using CPU all the time, of course).

[wehkah]

Hm, I understand what you're telling, but I am still not 100% convinced. I know it's impossible, but the best solution I can think of would be to make Osmand "know" if a previous calculated route has been left because you missed the right turn, or if you were forced to leave it because of road works, to make it "know" if I want the route to be recalculated or if I don't want it, because I will return to the right track soon. In fact, it can be very disturbing if you start following an officially signposted diversion and Osmand tells you to "turn left" or "turn right" or "turn around" every few seconds.

Unnecessary navigation commands can be avoided easily, the muting button is you friend there. :) But the ongoing recalculation can be a very tough job for some hardware!

[jnr57]

Hello all, I was using occasionally 0smand using gpx tracks and some times for route navigation. Since the las update (3.4.8). I guess, its almost impossible to use the app for route calculation for 100 to 300 km long. Seems to work fine for short distances <50 km. For the same trip it takes 0.1 s with Googlemaps! and 3 s with MAPS.ME. So how Osmand is calculating the route ? As previous comments, I will stop using this app if this problem is not fixed. Thanks for any uddapte.

[bumbaras]

I have returned to OsmAnd since quite long break with Huawei P10 and it seems that calculation is done much faster now, it is probably due to more powerful smartphone. It still took about two minutes when i changed route, but strangely OsmAnd didn't seem to calculate new route - just showed i am out of route. It was 350km distance. Two things i couldn't find in current version - OsmAnd engine choice and Poland map only in autoroute version, not detailed one.

[scaidermern]

Two things i couldn't find in current version - OsmAnd engine choice and Poland map only in autoroute version, not detailed one.

Poland map has been split into several regions due to its size. Offtopic for this issue, though.

[bitboy85]

Anyone else who thinks it got even worse? I tried to get a routing for about 200km and after 40 minutes(!!) it says it wasn't possible. Tried reinstalling and using street-only maps instead of full featured maps. But it didn't help.

Its unusable in this state :(

[vshcherb]

I tried to get a routing for about 200km and after 40 minutes(

That's too long even for current routing engine. Please share coordinates and try to increase routing memory up to 256-512 MB.

[scaidermern]

I tried to get a routing for about 200km and after 40 minutes(

That's too long even for current routing engine. Please share coordinates and try to increase routing memory up to 256-512 MB.

Why is that, from a technical point of view? There are other offline routing engines, like brouter, which don't have this problem. Do they have a better data format? Or are more aggressive when cutting branches during routing graph calculation? Or do they user some other approximation to reduce the computational effort? Smartphones have become really powerful in recent years and should be able to handle this, if I'm not completely mistaken.

[vshcherb]

It really depends a lot on configuration, I think B-Router is also A* algorithm, so the end result should be comparable to OsmAnd (if routing configuration similar) i.e. B-Router could be 2 times faster due to optimized storage but unlikely 10 times faster.

[cgogolin]

In many cases B-router feels more like 20x faster. This is on a Galaxy S10e. -- Christian Gogolin http://www.cgogolin.de

[bitboy85]

How can i increase the memory? Are there other options or configurations that could be tweaked?

Coordinates was from Bitburg, Germany to Dortmund, Germany

[bitboy85]

Please reopen.

Meanwhile osmand version is 4.0.8; Kernel 3.4.39 Android 5.1.1 without any chance to upgrade.

During route calculation RAM usage from osmand is about 350-400MB while having an additional 1GB free.

It was able to finish the same route today after about 50 minutes....

[vshcherb]

Bitburg - Dortmund on my device (4.2 OsmAnd Android 11) takes 10-15 seconds and 230 km route.

[bitboy85]

Anything i can do to track down the issue? Are there Logfiles available? Debug mode?

Where is the setting for the memory?

[vshcherb]

It's not available in 4.0.8. Sorry 4.0 is outdated and no longer under support