Opened 8 years ago

Closed 4 years ago

Last modified 4 years ago

#456 closed defect/bug (invalid)

route >80km is not calculated

Reported by: arne.anka Owned by: KaZeR
Priority: critical Milestone: version 0.2.1
Component: core Version: git master
Severity: Keywords: navit, core, routing, navigation, international, distance, uk, ireland, serbia,
Cc: flabrosse, fred@…, http://wiki.navit-project.org/index.php/user:stabarinde, http://wiki.navit-project.org/index.php/user:nioui, arnaud.lemeur@…, heinold@…, michael@…

Description

navit is from debian/unstable (0.1.1.0+dfsg.1-1, no idea what svn version that correspondends to). using either an europe or sweden map from cloudmade or an europe map from osm (fetched via the osm bbox ulr listed in the wiki), calculating aroute bigger than approx 80km results in a completely wrong calculation: i started with a route from trelleborg to ulricehamn, that's about 400km. the route resulted in a blue dot inside central trelleborg. next attempt resulted in an l-shaped blue covering about 5km and ending about 1km in the sea. several attempst result in several different shapes (i expected it to be at least always the same shape), none longer that approx 5km.

trying a shorter route instead, trelleborg - malmö (40km) works. trying another with about 60km works too, and one with ca 80km. the next one with 97km (according to google) results in the above error again.

is there any parameter to make navit put out more instructive informations about what happens (and make it _not_ display those constant "vehicle_gpsd:vehicle_gpsd_try_open:gps_open failed for 'gpsd://localhost'. Retrying in 10 seconds. Have you started gpsd?" messages)?

Attachments (3)

route.c.diff (784 bytes) - added by kapiteined 8 years ago.
patch for route.c
route_harder.patch (2.4 KB) - added by nioui 7 years ago.
If routing fails, try again with more roads included.
detailed_route_map.diff (417 bytes) - added by tegzed 6 years ago.
use more detailed map for routing

Download all attachments as: .zip

Change History (80)

comment:1 Changed 8 years ago by arne.anka

true for svn2490, too.

comment:2 Changed 8 years ago by arne.anka

some investigation later ... the newer navit.xml includes 4 predefined vehicles, all of them both enabled and active. setting all except Car to inactive allows to calculate longer routes. didn't test the other, but i guess, having more than one active vehicle confuses navit.

route trelleborg -- urlricehamn still doesn't work, but reverse -- ulricehamn -- trelleborg. i got the impression, that navit does not exactly cling to the highway, in particulay around malmö, but routes somewhere into the city and doesn't find a way out. if that's the case i think, the algorithm should try to stick to the highway in this case, resp to return to it, forgetting about the last part from the highway to the city.

anyway, it would probably be helpful, if the route's fragements are shown and maybe where no route is found a straight line is shown between the last known good point and the next one -- in extremis that would mean one straight line between trelleborg and ulricehamn, which imo is better than the current behaviour.

comment:3 Changed 8 years ago by arne.anka

splitting the route t'borg -- u'hamn in parts (t'borg -- malmö, malmö -- göteborg, g'borg -- u'hamn) produces valid routes.

comment:4 Changed 8 years ago by flabrosse

  • Cc flabrosse added

I may have the same problem, although the outcome is different. When calculating a route in the UK from 52.4141 -4.0859 to approx 51.8025 -3.0081 (on the A4042) I do get a route. If I go a bit further south (away from current position) along the same road, I don't get a road and navit outputs in the console: "navit:route_path_new:no route found, pos blocked".

This is using yesterday's svn and a recent openstreetmap map of Europe from cloudmade. I checked in OSM and the road is indeed a single item (not cut).

comment:5 Changed 8 years ago by drlizau

I have a similar problem but have not checked the error messages which are generated. I did describe this on the navit-user list. I can make a route up to about 250km in length. If I set a destination more than that distance away navit can calculate a route when I get close to 250km from the destination. That route has "town-avoidance-behaviour" which tries to send me on a very long detour. I've tried this with a few versions and different maps, and triple checked that the route is joined on OSM. I also tried with setting maxspeed on roads involved which did not have maxspeed to test if that improved the routing, with no success. https://sourceforge.net/mailarchive/forum.php?thread_name=200911210654.26359.edodd%40billiau.net&forum_name=navit-users

Changed 8 years ago by kapiteined

patch for route.c

comment:6 Changed 8 years ago by kapiteined

I ran into the same problem, when routing along a large part "non highway"

i worked around this by applying the attached patch to route.c
I don't know what else this will break, so use at your own risk [[BR]]

comment:7 Changed 7 years ago by www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m

I am having the same issue as reported in #579 which looks like a duplicate of this bug. I've applied the patch, but the routing performance was poor.

The patch had changed the function route_calc_selection. route_calc_selection uses function route_rect to assemble a one way linked list which defines rectangle selections. These rectangles are used to reduce the size of the map data that are used for routing. The patch extends the areas for these rectangles and thus it gets more CPU/memory intensive.

On a PC the calculation delay cause by the patch becomes obvious, which means it is not satisfactory solution for the embedded platforms like nokia N810, or supported cell phones.

Can we get martin-s (the name associated with svn blame on these functions) to comment on this?

comment:8 follow-up: Changed 7 years ago by www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

comment:9 Changed 7 years ago by www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc

  • Cc fred@… added

comment:10 in reply to: ↑ 8 ; follow-up: Changed 7 years ago by www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m

Replying to https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc:

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

Please post the France coordinates you have used successfully. I would like to see the topology of the underlying map and which rectangles were selected. Yesterday I've inquired on the irc channel, and it seems nobody is working on this issue at the moment.

comment:11 in reply to: ↑ 10 Changed 7 years ago by www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc

Replying to https://www.google.com/accounts/o8/id?id=aitoawmkw7qh8zqo5rtszg0qlehp5t_zvpfgz3m:

Replying to https://www.google.com/accounts/o8/id?id=aitoawke3ydqlxkrjxetvkpfmrt3bhza4xqucwc:

This doesn't explain why I don't seem to have any problem in France but can't plan a long route in the UK.

I can't try the patch because I use Maemo packages on a N800.

Please post the France coordinates you have used successfully. I would like to see the topology of the underlying map and which rectangles were selected. Yesterday I've inquired on the irc channel, and it seems nobody is working on this issue at the moment.

Everything I've tried in the past has worked I think (although see below).

For example, from 4825.8453N 00157.7273E to Saumur works and is about 277.9km. From 5101.2593N 00211.8706E to again Saumur (624.2km) works fine and to Nantes, Avenue des Églantiers (684.4km) also works fine (however, to Nantes alone (no street) seems to fail).

In the UK, everything I have tried above roughly 100km has failed.

comment:12 Changed 7 years ago by kazer

  • Milestone set to version 0.2.0

comment:13 Changed 7 years ago by stabarinde

  • Cc http://wiki.navit-project.org/index.php/user:stabarinde added
  • Keywords navit core routing navigation international distance uk ireland serbia added
  • Priority changed from major to critical
  • Summary changed from route >80km is not calculated correctly to route >80km is not calculated

So, let me get this straight;

  • This issue has been known for 11 months.
  • There is a kludgey fix, which has been around for 4 months.
  • The scope of affected countries is either unknown or undeclared.
  • The root cause is either unknown or undeclared.
  • Any progress on root causing the issue or applying a fix is undeclared.
  • Target date for the fix is undeclared.

So, what's going on? Basically, Navit works for a small selection of countries in the world. This means it *doesn't work*. The product cannot be a little bit broken. It's either broken or it isn't.

And yet, on the wiki page and the main page it says nothing about Navit not working in a number of countries.

I think the general populace can take a product that works but requires some in depth configuration, but a product that needs to be recompiled with a patch applied that they have to dig in a mailing list for is beyond most people.

I would imagine that this issue is getting all the priority the developers can muster. A glance at the current bug-list shows a lot of issues that effect unreleased builds or are minor UI quirks, but really route plotting is core functionality - without that you may as well be just looking at google maps offline. Objectively speaking, this is a stopper. It also effects a larger proportion of users, since it's in the wild (my version came down the pipe via the Ubuntu Lucid 10.04 LTS repos).

So, while you guys are working hard to fix the problem, here's what needs to happen;

  • Update the front page, so that the issue is roundly addressed;
    • Explain the issue
    • List the countries affected
    • Offer a patched build to download for those affected.
    • Give step by step instructions on applying the patch for those who need to build it.
    • Give a target date for fixing the problem.
    • Use your news feed to give status updates.

This allows the average user to assess whether they want to spend the hours configuring a product that, at the end of the day, may not work for them. It tells them that if the answer to the previous question is no, then they can come back at a specific future date and get a better option. It also tells the more adventurous how to do something they might never have done before (i.e. compile software) - for example, even if you have route.c.diff, there are *two* route.c files in the SVN source. Most importantly, it tells them that the issue is being actively pursued, and that the developers are serious about this product.

For my part, I can confirm that the issue is present in Ireland as well. I used Cloudmade, the navit planet extractor and OSM maps converted using the maptool application (again from the Ubuntu Lucid repos), and in all cases no route was plotted, throwing the same error listed by the submitter.

comment:14 Changed 7 years ago by nioui

  • Cc http://wiki.navit-project.org/index.php/user:nioui added

As far as I can tell there is no bug or unexpected behavior here as such, it's only due to the way Navit looks for a route.

Basically, computing a route in a graph with n point costs O(n×log n). So you don't want to route in a huge graph. Apparently, navit address this by restricting the map to a smaller area, and ignoring smaller road in the middle. More precisely, when routing from A to B, the following roads are considered:

  • Major road in rectangle area around A and B.
  • Intermediate roads in a square around A, and a square around B (40 km).
  • Small roads in a small square around A, and a small square around B (10 km).

In most case, this should work correctly: you will use a major road between A and B, and small roads to go from A to the major road, and from the major road to B. It also works well for small distances, because everything fits in the small squares.

However, it fails if you travel long distance (more than 80km) and no major roads are available in the middle. A good example would be going from Santa Maria, CA to Bakersfield, CA (note that a major road is actually available, but it does not fit in the first rectangle containing A and B).

The patch proposed by kapiteined address this by expanding the areas around A and B where smaller road are considered (to respectively 100km and 400km). It should work correctly, but result in a much longer routing time, probably unacceptable for handheld devices.

I'm attaching a patch that tries to solve this issue in a slightly different way. Instead of changing the parameters for all the routings, I only try with enlarged parameters when the first routing fails with standard parameters. I decided to change the parameters by including intermediate roads in the rectangle containing A and B, because it seems to address the main cause of problem: if there is no major road between A and B, we allow smaller ones.

This patch seems to work well for me, but I'm not sure I'm doing everything correctly, and it is quite possible that some structures get corrupted in some cases. I'd be glad if someone could review it...

Changed 7 years ago by nioui

If routing fails, try again with more roads included.

comment:15 Changed 7 years ago by flabrosse

I initially reported that I had no problem in France. This is wrong. I have used navit a lot up to Friday evening in France and the UK. I had similar problems in France too. However, that seemed to be over much longer distances.

I think the idea of the 3 stage route planning is broken. One can specify weights for the different types of roads one wants to take. Not wanting to take any motorways, I tried to disable them all together. That doesn't work. Also, if there is a motorway in the vicinity, then navit will want you to take it, even if that implies a large detour. That has occurred to me over and over again. As stabarinde was saying, this makes navit not really usable because you can't trust it to:

  • find a route, or
  • that the route indeed makes sense.

Not long ago, somebody suggested to use the A* search method. Maybe that would be much better.

comment:16 follow-up: Changed 7 years ago by number6

I was probably that someone!

The current algorithm, Dijkstra, is inefficient. Well, that's a lie.

The current algorithm is actually very good at finding all possible routes, but it's slow and memory hungry - not something we want.

A* is far far faster, often an order of magnitude and would hopefully not be so CPU and memory hungry.

Sure, changing the "sel->next=route_rect" line in route.c to a higher number, or applying the Route Harder Patch fixes the problem, but the fact remains that Dijkstra is a slow algorithm.

comment:17 Changed 7 years ago by tegzed

I also suggested A* some 2 month ago in a forum topic:

http://sourceforge.net/projects/navit/forums/forum/512959/topic/3746837 Perhaps I posted it to the wrong place.

Maybe one problem is to handle the case when the vehicle leaves area with roads that are flooded. In this case additional flooding should be done which can hurt performance during navigation. Current solution may have more control over the flooded area. In a previous irc discussion Cp15 told that performance of creating the graph is more problematic than flooding itself. Maybe some benchmarks would be useful and improve graph creation if its possible.

comment:18 Changed 7 years ago by number6

May I get your A* patch for testing purposes?

comment:19 Changed 7 years ago by tegzed

Hello Number6,

It's not a patch for navit, just a test program. Just parsed some OSM xml data with my simple separate commandline c++ program and run routing with dijkstra and A* on the data. If you are interested I can send you the program, however you may find better (and more readable) examples on these algorithms on the net.

comment:20 in reply to: ↑ 16 Changed 7 years ago by flabrosse

Replying to http://wiki.navit-project.org/index.php/user:number6:

The current algorithm is actually very good at finding all possible routes, but it's slow and memory hungry - not something we want.

A* is far far faster, often an order of magnitude and would hopefully not be so CPU and memory hungry.

Sure, changing the "sel->next=route_rect" line in route.c to a higher number, or applying the Route Harder Patch fixes the problem, but the fact remains that Dijkstra is a slow algorithm.

I would not say it's very good. If I understand it well, it relies on either having a motorway close enough to the current position and destination or on the the destination and current position to be close enough. The "close enough" is a threshold that is a compromise rather arbitrarily set (and I understand that recently a patch was introduced that changes it if no route was found).

However, there are places in the world where motorways are sparse and far away. Where I live (Wales) is one of them. So either the threshold is set to a long distance (and the routing is not that efficient) or I fail to have a route.

There is another failure of the approach: I cannot get a route that avoid motorways if there is one around. In fact, in some cases I've seen routes being planned that were just plain wrong, simply because there was a motorway close enough (that was with a weight for motorways as low as it could go to not fail (1)).

In fact, if you've ever played with a "proper" sat nav system, it can take these several minutes to plan a long route. I appreciate how fast navit is at planning the same route, but in many cases it fails, making it not so useful. Somehow I would prefer something that takes a long time but succeeds to something that simply fails.

Just my view ;-)

comment:21 Changed 7 years ago by number6

I should have clarified. From a mathematical standpoint, Dijkstra is a very good algorithm - albeit slow. Poor implementation, non-complete data and limited resources will easily affect the way it works.

I'm in the same situation as you, flabrosse. I am rather far from a motorway and "regional" roads in Ireland range from very very good (near "National" roads) to the down right impassible - that's a completely different matter though!

As an aside, I would happily wait 5 mintues for the "best" initial routing to my destination.

I am still of the belief that A* would be a better algorithm.

comment:22 follow-up: Changed 7 years ago by flabrosse

On the other hand, A*, IIRC, will not give you the best route, only a good one (it is a greedy search, isn't it?). In practice, I don't think this is a big inconvenience.

I agree that the quality of the roads is another issue (and to some extent a problem with the data). However, the reliance on motorways in the 3 tier routing is the issue of the thread. And A* might solve that problem.

comment:23 in reply to: ↑ 22 Changed 7 years ago by drlizau

Replying to http://wiki.navit-project.org/index.php/user:flabrosse:

My problem may be the same or may be different, but it also relates to calculating the route. There is a current default in the route calculation which avoids towns. In Australia roads join towns rather than divert around them, so eventually a long route fails because there is not a logical solution without going through a town. Sometimes a route can be found to a point past the town, but the diversion may be of the order of hundreds of kilometers. Example: Find route between Wollongong (-34.425529 150.890967) and Griffith (-34.288559 146.047760). This fails on progressive extension of the route at Stockinbingal (-34.501841 147.889103). Routing through Stockinbingal is refused by the navigation engine, and no route around Stockinbingal can be found. navit:route_path_new:no route found, pos blocked.

A previous irc discussion mentioned that towns were avoided in the current code, but this was not always the case. I am thinking of restoring the old code as an option which can be set in navit.xml so that routing through towns can be available.

comment:24 follow-up: Changed 7 years ago by flabrosse

While looking through a recent default config file, I discovered the option destination_distance. I tried to look for an explanation for it and couldn't. However, the name and the default value (50) made me think that this was the size of the area outside of which only major roads were used for the route planning. All excited by that, I tried a long route that normally fails, and it failed. I then changed the value from 50 to 500 which should have been plenty for the route I was looking for, and it still failed.

My questions are:

  • what is this option and has it got anything to do with that?
  • has anything been done on that problem?

Cheers

comment:25 in reply to: ↑ 24 Changed 7 years ago by korrosa

Replying to http://wiki.navit-project.org/index.php/user:flabrosse:

While looking through a recent default config file, I discovered the option destination_distance. <snip>

My questions are:

  • what is this option and has it got anything to do with that?
  • has anything been done on that problem?

From route.c:

int destination_distance;	/**< Distance to the destination at which the destination is considered "reached" */

So, unfortunately not a solution for this ticket!

comment:26 follow-up: Changed 7 years ago by ziaou

The patch submitted by nioui seems to be the most easy solution to keep a fast route calculation, and to guarantee that a route will always be found to destination. In most cases, the calculation time will not be increased.

Without any modification of route calculation method, some towns like Brest (in France) are unreachable because too far from a motorway.

I have tested this modification on a eeepc 901 (800MHz) to go from Toulouse to Brest and I think that the calculation time could be acceptable.

The most important thing is to have a functional software first.

comment:27 in reply to: ↑ 26 ; follow-up: Changed 7 years ago by flabrosse

Replying to https://wiki.navit-project.org/index.php/user:ziaou:

The most important thing is to have a functional software first.

I could not agree more with that.

However, this is not the solution because it still forces routes to use motorways for the middle section for trips that are longer than the 2 * 50km threshold. This is annoying because:

  • you cannot not use motorways (something that all satnav systems offer)
  • if your ideal route is just above the threshold and there is a motorway in sight, the selected route will use it even if that makes a huge detour (I came across an example like that last summer which I could try to find again if anyone can use the example to improve things).

comment:28 in reply to: ↑ 27 ; follow-up: Changed 7 years ago by ziaou

Replying to https://wiki.navit-project.org/index.php/user:flabrosse:

However, this is not the solution because it still forces routes to use motorways for the middle section for trips that are longer than the 2 * 50km threshold

I agree with you.

Perhaps it's possible to enable major ways (motorway, trunk, primary) instead of only motorway for the middle section. As I understand, it is what is done in the patch when the route is not found at the first try. It will take more calculation time but the result could be best.

comment:29 in reply to: ↑ 28 ; follow-up: Changed 7 years ago by flabrosse

Replying to https://wiki.navit-project.org/index.php/user:ziaou:

Perhaps it's possible to enable major ways (motorway, trunk, primary) instead of only motorway for the middle section. As I understand, it is what is done in the patch when the route is not found at the first try. It will take more calculation time but the result could be best.

If that is indeed what the patch does, why isn't it included? This seems like a sensible solution.

comment:30 in reply to: ↑ 29 Changed 7 years ago by ziaou

Replying to https://wiki.navit-project.org/index.php/user:flabrosse:

If that is indeed what the patch does, why isn't it included? This seems like a sensible solution.

What the patch does :

  • first try : only motorway in the middle section
    • advantage : fast calculation
    • drawback : no route found if point is to far from motorway, always use motorways
  • second try if first failed : enable other ways in the middle section
    • advantage : always find a route, could propose route without motorway in some cases
    • drawback : slow calculation, could be too heavy for handset

In my configuration, I have patched route.c to use only use the second try. It take more time to calculate route but the result is pretty good.

It could be interesting to test this configuration on a handset. Perhaps this patch is not applicable on it because of too many node to take in account for calculation.

comment:31 Changed 7 years ago by tegzed

Hello,

Woglinde (on #navit irc channel) has plans to pluginize the routing engine and fit it to the existing plugin infrastructure. I think this would be a good direction, in this way anybody could choose her/his best routing strategy and parameters of the routing engine (like routing numbers, the used road types etc.) in config time. Of course presets for typical scenarios can be offered to the user who then can choose from them.

comment:32 Changed 6 years ago by arnaud le meur

  • Cc arnaud.lemeur@… added

comment:33 Changed 6 years ago by woglinde

  • Cc heinold@… added

comment:34 Changed 6 years ago by tryagain.myopenid.com

http://trac.navit-project.org/ticket/876 has a patch with different approach to the problem. It's scientifically based!

comment:35 follow-up: Changed 6 years ago by mvglasow (2)

I recently had the same problem when trying to route from Vienna to Vilnius: no route was found until I was about 200 km from my destination.

Reproducing the problem at home, showing the route graph, I found that the nodes assigned a weight were all within 200 km from Vilnius; all the others were empty.

Reasons: from Vilnius to the Polish border, the roads are partly motorways, the rest are trunk roads. The whole way through Poland (several hundred km) are almost completely primary roads, with only a few pieces of motorway or trunk roads. Nothing is found because apparently primary roads are not considered for long-distance navigation.

As far as I know, OSM uses highway=primary for roads of national importance which don't meet motorway or trunk criteria. Some countries do not have a dense network of the latter two roads and long-distance traffic needs to use primary roads.

For this reason, I believe these three categories of roads (motorway, trunk, primary) should always be considered for long-distance routing. It will increase the size of the route graph (more roads, hence more edges and vertices), but due to cost differences, highways will quickly "win" where they are available and a feasible alternative.

comment:36 Changed 6 years ago by mvglasow (2)

As for Dijkstra versus A*: A* is basically a modified Dijkstra algorithm. It operates on the same graphs, and flooding a graph completely (examining every node) will give the exact same results with either algorithm.

This means nothing is saved in terms of memory requirements for the route graph.

The improvement of A* is that it selects the next node to examine by different criteria: Dijkstra chooses the node with the lowest cost. A* chooses the cost where the sum of its cost and a heuristic (lowest possible cost to destination) is lowest. Because of this, the destination node tends to get examined sooner than with Dijkstra.

As I understand it, Navit calculates the cost of a way segment as an estimate of the time needed to travel from one end to the other, based on its length, a speed estimate (configured in navit.xml) plus some penalties for traffic congestion etc.

A valid heuristic would thus be to take the distance between the node and the route destination, divided by the highest speed defined for any way type, and not taking into account any penalties.

It would require some code changes: we would still need to store the cost for each node, for nodes on the open list we would also need to store their cost+heuristic. This means nodes on the open list will take up some more memory. Also, we'd need to calculate the heuristic for each node we put on the open list. It would probably take some tests to find out how much of a difference that makes (the time gain most likely varies from route to route).

comment:37 in reply to: ↑ 35 Changed 6 years ago by tryagain

Replying to http://wiki.navit-project.org/index.php/user:mvglasow:

Reasons: from Vilnius to the Polish border, the roads are partly motorways, the rest are trunk roads. The whole way through Poland (several hundred km) are almost completely primary roads, with only a few pieces of motorway or trunk roads. Nothing is found because apparently primary roads are not considered for long-distance navigation.

As far as I know, OSM uses highway=primary for roads of national importance which don't meet motorway or trunk criteria. Some countries do not have a dense network of the latter two roads and long-distance traffic needs to use primary roads.

At #876 there was described a similar problem, and my first patch made highway=primary roads eligible for distant routing. But that patch was partially reverted back because of performance problems found by cp15. So now we have least significant roads for distant routing being highway=trunk.

BTW, highway=trunk definition at http://wiki.openstreetmap.org/wiki/Tag:highway%3Dtrunk seems to allow to tag it on any important road. But country-wide [bad] practices sometimes add more requirements to roads it is placed on. For example, I don't know why in Czech Republic and Denmark one should use this tag only for roads that in other countries are tagged as higway=<anything> and motorroad=yes (http://wiki.openstreetmap.org/wiki/Tag:motorroad%3Dyes). There's no highway=trunk specifics described for Poland.

The definition of highway=primary at http://wiki.openstreetmap.org/wiki/Tag:highway%3Dprimary doesn't give any clue if that road should or can be used for distant routing. It's just "a major highway linking large towns".

Comparing two above definitions I'd say it's better to place higway=trunk tags on all roads you name and don't touch the navit code.

But having that country-dependent tag usage practices we probably have to use some sophisticated logic to decide if given highway=primary is eligible for distant routing or not. That decision can be done on country-by-country basis, or adaptive, by checking if highway=primary density (number of such roads per square km) is less than some value.

comment:38 Changed 6 years ago by mvglasow (2)

  • Cc michael@… added

Well, changing common tagging practice is not an easy task either, nor do I want to start edit wars on OSM. Also, I'm wondering if that's maybe even a borderline case of tagging for the renderer.

In some countries (Italy I know for sure) there is a clear-cut difference between primary and trunk, which has to do with traffic regulations, including speed limits, and thus also has an impact on routing. So having this distinction is even beneficial for routing. Btw, this exists also for Poland, look here: http://wiki.openstreetmap.org/wiki/Key:highway#International_equivalence

Also, the definition of primary may not specify it as being of national importance, but many national tagging schemes (e.g. Austria, France, Germany, Italy, Poland, Sweden; see above link) map "primary" to road categories which do effectively fall into this category.

If making primary roads eligible for long-distance routing induces performance problems, then I would suggest looking at two things:

  • In the route graph I sometimes see a couple of nodes in the middle of a road. The correspond to OSM nodes (because the road is curved) but they are not junctions, hence they are not needed for the graph (the graph needs nodes only where two paths split or join). It seems the graph is not optimized in that respect, which would lead to generic performance issues. With this optimization, we might get enough "elbow room" for primaries. It would require pre-processing at some point but would decrease the number of nodes in the graph, reducing both memory consumption and execution time.
  • Adaptive inclusion/exclusion of primaries, as you suggested. We can either include primaries by default and drop them if the graph gets too large, or exclude them by default and include them only if the network of higher-rated roads is not dense enough.

comment:39 Changed 6 years ago by linesoff.myopenid.com

Before I knew about this ticket, I spend a lot of time wondering, why navit delivered routes, which make great detours (or delivered no route). Now this is clear.

But I'd like to emphasize, that the two step approach mentioned above will not be a solution for those cases, when Navit makes a great detour using a motormay, because the second step is not performed. I found several starts+destinations (in the area of D-A-CH), where the Navit-route starts in the opposite direction of a realistic route. At the moment the routing for long trips is not for practical use.

But I hope, a suitable solution for long trips will be found. ( Soon ? )

Changed 6 years ago by tegzed

use more detailed map for routing

comment:40 Changed 6 years ago by tegzed

Hello, I attached a one-liner patch that I use for routing (detailed_route_map.diff). Routing uses map extracts as described here: http://wiki.navit-project.org/index.php/Routing. This patch increases the detail level(from 4 to 6) of the outer most rectangle.(the one that does include the position and destination point with an additional 25% at the ends). (The route_harder patch increases the detail to 8 for this rectangle in the second step) This one-liner is a version of the two-step patch that starts with the detailed version(avoiding the above problems). This works quickly and correctly on my android device (motorola defy). I could do routing from Hungary to Stuttgart without problems. I think the best solution would be to let the user select presets about the detail and range of he route map rectangles from navit.xml, so navit can be configured for low memory devices and more advanced hardwares too without recompilation. The constants (or some similar quantities derived from the constants) used in route.c between lines 958 and 965 should be made configurable from xml.

Last edited 6 years ago by tegzed (previous) (diff)

comment:41 Changed 6 years ago by mvglasow (2)

would that include primary roads in routing, then? (What order/detail level would a highway=primary have? where is the mapping between these two done?)

comment:42 Changed 6 years ago by tegzed

If I'm understanding the code well, the order depends on the "length" (or more precisely the quadtree level) of the way not the osm tags(which is mapped to navit item type). The longer the way the lower the quadtree level (it can only fit in a bigger quadtree tile). So the patch allows shorter ways (that have higher order value) to be used.

Last edited 6 years ago by tegzed (previous) (diff)

comment:43 Changed 6 years ago by tryagain

phase34_process_file() of navit/maptool/misc.c assigns maximum item order (tile depth) based on its navit type. So, for example, shortest items of type ramp will have order=8. Order may become lower for lengthy items.

OSM attribute to item type correspondence is given by attrmap array of navit/maptool/osm.c.

So there's no central place where mapping between order and OSM type is done, but it's quite simple to deduct that correspondence.

comment:44 Changed 5 years ago by ceelvain

If the memory cost of A* is too high, there are variations of this algorithm which uses a bounded amount of memory.

IDA* for instance only keep one path in memory at the cost of a heavier computation. http://en.wikipedia.org/wiki/IDA*

SMA* uses all the memory you want it to use and is thus (IMO) the best compromise between memory and CPU consuption. http://en.wikipedia.org/wiki/SMA* (The algorithm on wikipedia is not really clear, the paper linked is better I think.)

I think some benchmarks would be welcome to compare these algorithms.

Last edited 5 years ago by ceelvain (previous) (diff)

comment:45 Changed 5 years ago by fred labrosse

I'm not sure what the status of this is, but given that navit was able to create routes in Wales without motorways or using motorways when they are available, I thought it had been solved. However, it is still not solved. I am just back from a holiday in France where I tried to travel between 2 places (Saumur and Brehal), the obvious, shortest route between the two being off motorways, but going across a few. navit was giving me a zigzag type route that was using the motorways, despite making the route much longer. I tried the "car_shortest" vehicle and that gave me an even longer route (with the initial and final sections shorter, but using even more motorway. I created a new vehicle with a weight of 1 for motorways and I got a route that was wrong too. The same with the avoid toll roads vehicle.

So I guess the idea of having a motorway section of the route is still there then, despite clearly not being the best one when motorways are not appropriate.

Any idea of what the status is?

comment:46 Changed 5 years ago by tryagain

labrosse, I have no France map handy so can't reproduce your problem.

Can you please verify if Navit route differs from one given by other OSM roting engines, for example online one at http://maps.cloudmade.com . That could help verifying that osm data is not the cause of the problem.

And, obvious routes are not always that fast as they seem.

comment:47 Changed 5 years ago by chaoscrawler

hello. i can confirm bug exists, i've hit it many times in Poland - i use navit for bicycle routing and it's very apparent when used in such purpose.

i've often tried to split the route in smaller parts , and verified if OSM data is correct. it all looks fine.

example : try routing from 52.1'35, 15,6'30 to 50,44'16, 15,0'39

the border place where it works is 51,36'23N 14,46'55E , 51,40'11N 15,48'12E - does not. you can easily click inbetween this point to see how it breaks, change vehicleprofiles, etc.

btw. i think 1) usage of motorways should be defined in navit.xml - i.e. for bicycle routing this actually produces LONGER time of computation. some 'preffered way type for fast route mode' setting should be added.

2) if route fails, fallback routing algo should be used - may be slow. would be nice if it would be define-able in navit.xml aswell as some '2nd resort routing algo' as it will be clearly different for i.e. bicycle, horse, pedestrian, motorcycle and boat...

comment:48 Changed 5 years ago by fred labrosse

tryagain, I understand what you are saying. However... The route created by navit is different from the one made by the cloudmade ones and forces the use of even more motorway: navit does Saumur->Anger->Le Mans->Rennes->Brehal, Cloudmade takes a shortcut after Le Mans, not going as far as Rennes, which results in a much better route. I don't seem to be able to post screen shots so can't really show the results. I'll try to put them on some server, unless knows how to post images (tried the image tag but that does not seem to work).

The other point is that navit's shortest was even longer than the fastest because, I think, was shortening the distances to the motorways and therefore using a different motorway that made the route longer. I can't replicate that anymore because it seems that any vehicle other that the fastest only works with a real GPS, not a manually set position, and I am not there any more.

Fred

comment:49 follow-up: Changed 5 years ago by tryagain

Hi!

With r5216 I made car_pedantic profile which uses full map depth (order=18) in the 25% enlarged rectangle built around the waypoints plus 40km around each waypoint. So it shouldnt miss any routable segment in the area which were considered before, but at different detail levels.

This is made possible because vehicleprofile now have route_depth attribute, which allows to tune per vehicleprofile route parameters discussed earlier.

route_depth attribute consists of subarea parameter tuples separated by commas. Each tuple itself is represented by two numbers, separated by colon, and describes a part of the map selection used to build the route.

First number of the tuple is order used to query the map. 18 is maximum depth, is allows the smallest map items to be visible, 4 is used to be the value to query the big rectangle around all waypoints.

If the last number of tuple is followed by percent sign, that tuple describes rectangle built around all points and enlarged by that percentage. Otherwise, It defines size of squares built around each waypoint.

So previous algorithm parameters can be coded as route_depth="4:25%,8:40000,18:10000", brand new "pedantic" vehicle profile - as route_depth="18:25%,18:40000".

Also I can suggest using route_depth="4:25%,4:40000" route profile to debug routing problems around some known point of failure.

Please note that with car_pedantic or pedestrian/bike/horse profiles, small devices will run out of memory or build the route forever when route graph is too big.

Last edited 5 years ago by tryagain (previous) (diff)

comment:50 follow-up: Changed 5 years ago by chaoscrawler

hello. thanx for your patch. 18:25% settings seem too cpu intensive to calculate even short routes on my mobile device (400mhz, 64M of ram) so i rather used 12:10% and 9:15%

there is another problem though, even with 'default' settings (8:25%) , since your patch navit calculates car routes via footways, and other car-disallowed routes... any idea what went wrong?

comment:51 in reply to: ↑ 50 Changed 5 years ago by tryagain

Replying to chaoscrawler:

there is another problem though, even with 'default' settings (8:25%) , since your patch navit calculates car routes via footways, and other car-disallowed routes... any idea what went wrong?

Hmm. Currently no idea... Will recheck that. But can you please give some samples (OSM IDS of ways in question)? I have not seen this behavior during testing and really have no idea what change made the problem. I suspect there's rather some problem with osm tags on those footways so them are considered as routable, and were roiutable before, though rarely visible to route engine.

comment:52 Changed 5 years ago by chaoscrawler

try routing from 50,44'33"N 15,0'33"E to 50,44'38"N 15,0'20"E those are hiking paths and cycleways. just example, try just any footway.

comment:53 Changed 5 years ago by tryagain

If you mean, for example, http://www.openstreetmap.org/browse/way/42042656, then I'd say highway=track were routable by car since ages and are mapped to track_gravel in navit. If you consider this behavior buggy, please open another ticket for that.

Btw picture at http://wiki.openstreetmap.org/wiki/Track looks like a car can drive there. So you have just to place appropriate flags to roadprofile to have such roads lower priority than usual highways.

Or, maybe, that road is just wrongly mapped.

I hope you cant route by car on http://www.openstreetmap.org/browse/way/42043693 which is indeed tagged as highway=footway.

Last edited 5 years ago by tryagain (previous) (diff)

comment:54 Changed 5 years ago by chaoscrawler

how about 50,46'34"N 15,3'34E to 50,46'29"N 15,3'37"E , i get route straight through park... maybe off-road routing kicks in somehow, i'll try to recheck that asap

comment:55 Changed 5 years ago by chaoscrawler

switching route_mode to 1 solves problem :)

comment:56 follow-up: Changed 5 years ago by dominizer77

Thank you very much for this feature.

Is there any list, that tells us, which roads are linked to a certain route_depth value? I think i remember to have seen something like that before, but can't find it anymore.

So I just started some trial and error experiments with my "car avoid motorways" profile, that was mainly created to go around traffic jam. But I found out that it it works pretty good as a testing profile for a situation where no motorway is around. It's just a simple copy of the default car profile with highway_land, highway_city and land_n_lanes deleted.

What I found out is, that a good route_depth value for my personal needs is

8 for a car and

10 for a bicycle

Personal needs means here that I live in germany (central Europe) which is a very crowded area. I don't think there's a spot on the map, that would be more than 10 kilometers away from a paved road. Let me know, if you find one. Might be different in more agricultural areas.

What did I do?

I started with the default setting and tested a no motorway car on distance of about 500 km (several destinations)

4:25%,8:40000,18:10000 route not built ... increasing long route depth

5:25%,8:40000,18:10000 route not built

6:25%,8:40000,18:10000 route built but a long way round

7:25%,8:40000,18:10000 route built but still detour

8:25%,8:40000,18:10000 route built a sinuous line

Hooray! Well a 8:25%,8:40000 setup doesn't make sense, less does a 9:25%,8:40000 so I decided to go on with

9:25%,12:10000,18:3000 nearly the same route as before but 4 times more calculation time

10:25%,12:10000,18:3000 pretty straight but calculating for several minutes

up to 18:25% ... no big differece

there seems to be no need to have a normal car profile (with increasing route_weight) depthed to more than level 8. So something like 8:25%,10:10000,18:3000 should be working. This is still memory hungry and takes few minutes of calculating for a 1000 km route without major roads on a 2GB RAM machine with swap space. Don't know how it works on a small handheld device. But it's a lot better than an 18/18/18 setup.

I tested car_shortest and bike profiles the same way. As track_gravelled is out at route_depth 9 and in at route_depth 10, I have a bike_10 profile that creates nearly the same routes as the bike_18. And i have a car_shortest_8 profile which creates drivable routes (allthough not the shortest ;) and a car_rat_run_18 where you have to expect private ways and barriers en route.

comment:57 in reply to: ↑ 49 Changed 5 years ago by fred labrosse

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

Hi!

With r5216 I made car_pedantic profile which uses full map depth (order=18) in the 25% enlarged rectangle built around the waypoints plus 40km around each waypoint. So it shouldnt miss any routable segment in the area which were considered before, but at different detail levels.

This is made possible because vehicleprofile now have route_depth attribute, which allows to tune per vehicleprofile route parameters discussed earlier.

route_depth attribute consists of subarea parameter tuples separated by commas. Each tuple itself is represented by two numbers, separated by colon, and describes a part of the map selection used to build the route.

First number of the tuple is order used to query the map. 18 is maximum depth, is allows the smallest map items to be visible, 4 is used to be the value to query the big rectangle around all waypoints.

If the last number of tuple is followed by percent sign, that tuple describes rectangle built around all points and enlarged by that percentage. Otherwise, It defines size of squares built around each waypoint.

So previous algorithm parameters can be coded as route_depth="4:25%,8:40000,18:10000", brand new "pedantic" vehicle profile - as route_depth="18:25%,18:40000".

Also I can suggest using route_depth="4:25%,4:40000" route profile to debug routing problems around some known point of failure.

Please note that with car_pedantic or pedestrian/bike/horse profiles, small devices will run out of memory or build the route forever when route graph is too big.

This works! Thanks. The pedantic setting gives me more or less what I would have done by hand, but does take a while. I'll play with the depth a bit more.

One question though. I was not sure to understand why the "normal" setting has 3 tuples while the pedantic one has only 2. In other words, I wasn't quite sure what they correspond to.

Fred

comment:58 in reply to: ↑ 56 Changed 5 years ago by fred labrosse

Replying to dominizer77:

So I just started some trial and error experiments with my "car avoid motorways" profile, that was mainly created to go around traffic jam. But I found out that it it works pretty good as a testing profile for a situation where no motorway is around. It's just a simple copy of the default car profile with highway_land, highway_city and land_n_lanes deleted.

This is interesting. I have been trying, and failing, to produce a no_motorway profile for a while (I don't have any motorways around here so trying it for real is often difficult). What I did was set the weight of the highway_land to a low value. In the past, 0 was making navit fail, so never tried it again. However, with this recent change, I'll try again. But maybe deleting these from the profile works better?

Also, part of my failure might have been that I kept the highway_city as normal. I can't remove land_n_lanes because around here, all roads are like that (not sure why).

Cheers,

Fred

comment:59 Changed 5 years ago by mvglasow (2)

This does open up another issue, though: the route graph does get quite huge, causing Navit to run out of memory on longer routes. The 512 MB on the Nexus S are insufficient to create a route from Munich to Vilnius with a route_depth of 6:25%,...

We'll need to reduce memory consumption of the route graph, one thing we should do is reduce redundant nodes from the graph (see #1066).

@dominizer77: For route depth, have a look at http://wiki.navit-project.org/index.php/Navit%27s_binary_map_driver#How_An_object_Is_placed_in_a_tile.

Basically, the whole planet is flattened, then divided into a 2×2 grid of top-level tiles. The next level is obtained by again dividing each of these tiles in the same way. This continues 18 levels deep.

The "depth" of an object is the lowest tile level at which it can fit into a single tile. This tends to place longer objects into higher-level tiles, as well as objects that are near a tile border. (As an extreme example, objects that cross the equator would always end up in the topmost tile level, regardless of their length.)

There are some limitations:

  • motorway, trunk and *_link can have a maximum depth of 8.
  • primary can have a maximum depth of 10.
  • secondary can have a maximum level of 12.

This is done so that fewer tiles have to be searched in order to find "important" objects (labels of large/prominent places or roads likely to be used for long-distance routing).

@fre labrosse: For the route_depth syntax, see http://wiki.navit-project.org/index.php/Configuring_Navit/Full_list_of_options and http://wiki.navit-project.org/index.php/Routing.

comment:60 follow-up: Changed 5 years ago by chaoscrawler

ad mem consumption - my device is 64M "lark" - with the increased depth it crawls to a stop when calculating longer routes, but i've found out i can play with the % and square size and then it quite saves the day.

my current settings are 12:10%,18:10000 and those quite work for distances ~80-100km (bicycle profile). not sure how much those affect accuracy of routes - sometimes it seems choice of i.e. cycleways, or footways is still not optimal (i.e. navit prefeers to take normal road , sometimes 10x longer around i.e. 100m footway short )

comment:61 Changed 5 years ago by chaoscrawler

i still have some issues with navit trying to route car via cycleways, i.e. : 51,6'36"N 14,58'41"E one

any ideas why such behaviour ? it's definitelly not motor-car drive-able, and it's just plain cycleway in OSM

comment:62 follow-up: Changed 5 years ago by antenna

A value of 18:25%,18:40000 causes navit to lag minutes! behind real time on my netbook (Intel Atom 1.6Ghz and 2Gb RAM) after some time. When I removed the entry from navit.xml it worked just fine again.

@dominizer77: I'm looking for a profile to bypass a complete closure (autobahn), as well. Before I added your value ( 8:25%,10:10000,18:3000) to the edited profile (weight of highway set to 40) I actually got a bypass route - not one, you would choose personally, but it led me back on the freeway after around 30km (just because it couldn't find a suitable ordinary road) . By adding your value, however, I really got an effective avoidance of freeways, which on the other hand doesn't serve my purpose to bypass a complete closure. Is it possible to play with the value to bypass a complete closure and return to a freeway after some km? Unfortunately, I can't tell right now, whether I will experience lag with your depth, too.

Last edited 5 years ago by antenna (previous) (diff)

comment:63 in reply to: ↑ 62 ; follow-up: Changed 5 years ago by dominizer77

Replying to http://wiki.navit-project.org/index.php/user:mvglasow:

@dominizer77: For route depth, have a look at http://wiki.navit-project.org/index.php/Navit%27s_binary_map_driver#How_An_object_Is_placed_in_a_tile.

Basically, the whole planet is flattened, then divided into a 2×2 grid of top-level tiles. The next level is obtained by again dividing each of these tiles in the same way. This continues 18 levels deep.

Thank you for this information.

So the route_depth is not about how "big" a certain way is (like highway vs footway), but how "long" it is. Which often looks like the same, as highways are usually longer than footways. But if we had a footway of 10.000 km length, that one would be pretty high leveled.

I'm slowly getting behind how it works. So what is the whole planet tile of 40.000 km in square?

Depth 0 or depth 1? I'm trying to figure out, how big the tile is, when i define route_depth = 8 for example.

Replying to fre labrosse:

This is interesting. I have been trying, and failing, to produce a no_motorway profile for a while (I don't have any motorways around here so trying it for real is often difficult). What I did was set the weight of the highway_land to a low value. In the past, 0 was making navit fail, so never tried it again. However, with this recent change, I'll try again. But maybe deleting these from the profile works better?

I never tried a route_weight=0, but I know that a zero in a config file is allways a nasty thing for programmers. Every computer-program is a set of methematical calculations and a devision-by-zero might crash it.

So deleting might be the better choice. Or open another ticket "route_weight=0 causes crash" something like that.

Also, part of my failure might have been that I kept the highway_city as normal. I can't remove land_n_lanes because around here, all roads are like that (not sure why).

If so, your area seems to be mapped badly. No street_4_land around? street_3_land?

Replying to chaoscrawler:

i still have some issues with navit trying to route car via cycleways, i.e. : 51,6'36"N 14,58'41"E one

any ideas why such behaviour ? it's definitelly not motor-car drive-able, and it's just plain cycleway in OSM

Do you have a cycleway defined in your "car" vehicle-profile? Or maybe there is something wrong with the flags.

For example, one of my vehicle-profiles looks like this:

<vehicleprofile name="car_shortest" 	route_depth="8:25%,10:10000,18:3000" 		flags="0x4000000" 	flags_forward_mask="0x4000002" 	flags_reverse_mask="0x4000001" 	maxspeed_handling="0" route_mode="0" static_speed="5" static_distance="25">
	<roadprofile item_types="street_0,street_1_city,living_street,street_service,track_gravelled,track_unpaved" speed="10" route_weight="10"/>
	<roadprofile item_types="street_2_city,track_paved" speed="30" route_weight="20"/>
	<roadprofile item_types="street_3_city" speed="40" route_weight="40"/>
	<roadprofile item_types="street_4_city" speed="50" route_weight="40"/>
	<roadprofile item_types="highway_city" speed="80" route_weight="40"/>
	<roadprofile item_types="street_1_land" speed="60" route_weight="40"/>
	<roadprofile item_types="street_2_land" speed="65" route_weight="40"/>
	<roadprofile item_types="street_3_land" speed="70" route_weight="40"/>
	<roadprofile item_types="street_4_land" speed="80" route_weight="40"/>
	<roadprofile item_types="street_n_lanes" speed="120" route_weight="20"/>
	<roadprofile item_types="highway_land" speed="120" route_weight="10"/>
	<roadprofile item_types="ramp" speed="40" route_weight="10"/>
	<roadprofile item_types="roundabout" speed="10" route_weight="20"/>
	<roadprofile item_types="ferry" speed="40" route_weight="20"/>
</vehicleprofile>

there is simply no item_types="cycleway" in there. If you find a cycleway on your route, it must be defined in your vehicle-profile.

Replying to chaoscrawler:

ad mem consumption - my device is 64M "lark" - with the increased depth it crawls to a stop when calculating longer routes, but i've found out i can play with the % and square size and then it quite saves the day. my current settings are 12:10%,18:10000 and those quite work for distances ~80-100km (bicycle profile). not sure how much those affect accuracy of routes - sometimes it seems choice of i.e. cycleways, or footways is still not optimal (i.e. navit prefeers to take normal road , sometimes 10x longer around i.e. 100m footway short )

Did you try to decrease the lvl 18 square? Maybe like 18:1000 or 18:500? On short distances this might help. And if you have lvl 12 around anyway...

Another question is: How is the Rectangle around all waypoints calculated? Let us say all waypoints have same longitude. How is this zero mutiplicated?

Replying to fre labrosse:

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

One question though. I was not sure to understand why the "normal" setting has 3 tuples while the pedantic one has only 2. In other words, I wasn't quite sure what they correspond to.

Good Question.

A tuple by default has no dimension. So something like route_depth="18:20%" should be enough. But I guess that we need at least 2 dimensions. Otherwise it would not make sense to define something like 4:25%,4:40000.

So what about

route_depth="12:15%"

route_depth="4:25%,8:12%"

route_depth="4:25%,8:1%,18:100000"

route_depth="4:100%,6:1%,8:64000,10:32000,12:16000,14:8000,16:4000,18:2000"

gonna try out those...

Replying to http://wiki.navit-project.org/index.php/user:antenna:

A value of 18:25%,18:40000 causes navit to lag minutes! behind real time on my netbook (Intel Atom 1.6Ghz and 2Gb RAM) after some time. When I removed the entry from navit.xml it worked just fine again.

@dominizer77: I'm looking for a profile to bypass a complete closure (autobahn), as well. Before I added your value ( 8:25%,10:10000,18:3000) to the edited profile (weight of highway set to 40) I actually got a bypass route - not one, you would choose personally, but it led me back on the freeway after around 30km (just because it couldn't find a suitable ordinary road) . By adding your value, however, I really got an effective avoidance of freeways, which on the other hand doesn't serve my purpose to bypass a complete closure. Is it possible to play with the value to bypass a complete closure and return to a freeway after some km? Unfortunately, I can't tell right now, whether I will experience lag with your depth, too.

That might be working for a certain route. How should navit know, which part of your route to bypass?

Let's say you have 300 km and you want 30 km over land. First 30? Last 30? Something in between? You would need to use waypoints and use different vehicle-profiles between them. Good idea, I have it on my wishlist for further development.

comment:64 in reply to: ↑ 63 Changed 5 years ago by antenna

Replying to dominizer77:

That might be working for a certain route. How should navit know, which part of your route to bypass?

Let's say you have 300 km and you want 30 km over land. First 30? Last 30? Something in between? You would need to use waypoints and use different vehicle-profiles between them. Good idea, I have it on my wishlist for further development.

Let's just say you use the standard car profile and get in a traffic jam caused by a complete closure due to a bridge repair or some serious accident. You listen to the news and hear that the offical bypass routes are crowded. So you decide to switch to the bypass profile and get a route that leads you around the traffic jam - not to close and not to far, comparable to one a capable passenger would choose - back to the freeway after ~ 30 km. One could choose the approximate point of re-entering the freeway with a waypoint.

comment:65 Changed 5 years ago by tryagain

dominizer77,

For "percent" tuples, longest rect side is used to calculate exact amount of expansion to be applied to each side. So enlarging 0x200 rect by 20%, you get 40x240 one (see also picture link below).

Your example of route_depth="4:100%,6:1%,8:64000,10:32000,12:16000,14:8000,16:4000,18:2000" will work. There's no arbitrary limit on number of tuples used, and no particular tuple ordering is needed.

Korrosa drawn nice sample during our chat, see logs

Chaoscrawler aka curious confirmed in irc that his troubles with car routing by cyleways were caused by wrong configuration file.

tryagain

comment:66 in reply to: ↑ 60 ; follow-up: Changed 5 years ago by dominizer77

Replying to http://wiki.navit-project.org/index.php/user:antenna:

Let's just say you use the standard car profile and get in a traffic jam caused by a complete closure due to a bridge repair or some serious accident. You listen to the news and hear that the offical bypass routes are crowded. So you decide to switch to the bypass profile and get a route that leads you around the traffic jam - not to close and not to far, comparable to one a capable passenger would choose - back to the freeway after ~ 30 km. One could choose the approximate point of re-entering the freeway with a waypoint.

That's exactly, what I'm here for. Atm it works pretty good for me. I have done some tests last week with my motorola defy android phone (512 MB Memory and CPU @ 1000 MHz). Not very long distances from 70km up to about 200. But I checked out, that the Defy can calculate routes > 500 km at a route_depth of 8:25%. Which is enough for me, as one should not drive such long distances without having a break, imho ;)

So what I did was plan some extra time, just in case something might go wrong, have a traffic-app on board to be informed about jams and major road works, start with the standard car-profile and try to go around everything that slows me down. It works. There is not even waypoint usage needed.

Example:

Right now I'm back from a trip Gelsenkirchen to Münster, Germany. The standard way is to join the Autobahn A42 at Gelsenkirchen Schalke and then join the A43 at Herne which will lead you right into Münster. Problem is, there is a major roadwork in the city of Gelsenkirchen which makes it hard to enter the A42 at Schalke. So I started with the car-shortest profile (modified version as posted above). After 10-15 minutes I switched to car-standard and got directed to the A42 and then to the A43. Everything went fine then until reaching Marl. There is another roadworks on the way. So 5 km before reaching Marl, I switched back to car-shortest. Navit called next out and directed me overland. Again 10-15 minutes and I decided to switch back to car-standard again. Back to the Autobahn and straight home.

As there was no closure or traffic jam along but only road works, it might have been better, just to go on with the standard-profile all the way. But if there was a jam, this would have spared 30 minutes or more, if there was a closure, I could still be there. I was 10 minutes after navit-calculated car-standard ETA.

I'm pretty shure this will work for 500 km distance travel, too. Allthough a field report has to be anticipated.

ATM I really use a lot of different vehicle profiles, and before starting the engine, I check all of them in birds eye view zoomed out to have the whole route at sight.

  • "car-standard" ("car" in the shipped navit.xml)
  • "car-shortest" (modified as above, very small and very big roads have a lowered route_weight)
  • "car-avoid-motorway" ("car" highways and land_n_lanes deleted)
  • "car-prefer-land" (like "car-avoid-motorway" but also city-steets lowered in route weight)

all of them in several route_depth settings.

Interestingly, changing the route_depth attribute has a much bigger effect on the route than route_weight has. You can create a far go-around with a low route_depth of 4 and a close-to-linear-distance with a high route_depth of 12.

I would like to post some of my favourites but first I have to check out this:

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

dominizer77,

For "percent" tuples, longest rect side is used to calculate exact amount of expansion to be applied to each side. So enlarging 0x200 rect by 20%, you get 40x240 one (see also picture link below).

Your example of route_depth="4:100%,6:1%,8:64000,10:32000,12:16000,14:8000,16:4000,18:2000" will work. There's no arbitrary limit on number of tuples used, and no particular tuple ordering is needed.

Thank you. So we have found a way to decrease memory consumption. As chaoscrawler said, it helps to decrease the high level rectangle size.

Replying to chaoscrawler:

ad mem consumption - my device is 64M "lark" - with the increased depth it crawls to a stop when calculating longer routes, but i've found out i can play with the % and square size and then it quite saves the day.

my current settings are 12:10%,18:10000 and those quite work for distances ~80-100km (bicycle profile). not sure how much those affect accuracy of routes - sometimes it seems choice of i.e. cycleways, or footways is still not optimal (i.e. navit prefeers to take normal road , sometimes 10x longer around i.e. 100m footway short )

So if 12:10% is ok on a 64M device, 12:1% would be even better. But maybe the rectangle is too small. So we say 8:10%,12:1% :) We can make as many rectangles as we want.

I would try something like this:

  • 4:25%,5:20%,6:15%,7:10%,8:5%,10:10000,12:5000,18:1000 or
  • 4:25%,6:10%,8:1%,18:1000

Korrosa drawn nice sample during our chat, see logs

So could we just leave the map-units tuples away and only use % ones? Don't think that would make sense, but was just wondering if it would work in theory.

Chaoscrawler aka curious confirmed in irc that his troubles with car routing by cyleways were caused by wrong configuration file.

Nice. Can't count the days in my life that have been sucked by a semicolon at wrong place ;)

tryagain

I do ;) dominizer

Last edited 5 years ago by dominizer77 (previous) (diff)

comment:67 in reply to: ↑ 66 Changed 5 years ago by tryagain

Replying to dominizer77:

So could we just leave the map-units tuples away and only use % ones? Don't think that would make sense, but was just wondering if it would work in theory.

It would work, but you will be unable to make a route if starting point and destination are on the opposite sides of 100m wide river and bridge is 1km away unless you specify percentage more than 900%. But then, if distance between endpoints would be 100 km, you'll try to search the route in a 1000x1000km rectangle, which is not a good idea.

tryagain

comment:68 Changed 5 years ago by mvglasow (2)

I've tried

route_depth="4:25%,6:1%,8:40000,18:10000"

successfully on my Nexus S. With that I could successfully calculate a route from Munich to Suwałki, which is about 1400 km and involves long stretches of primary roads. With the 512 MB of memory on my device, this seems to be the best balance between usable routing and memory efficiency. Devices with less memory may run into problems here, though.

Idea: can we make this setting the default and implement something to reduce the route depth if memory gets low?

comment:69 Changed 5 years ago by tryagain

  1. Changing routing strategy on the fly will give different routing results from run to run. In that case you will plan your route at home, doublecheck it, but at actual journey take a big detour because navit has a little less memory at the moment.
  1. Some platforms (Android) can give an application more memory by shutting down background tasks as needed. So amount of available memory can dramatically change during the run.
  1. When we already ran out of memory, it's too late to change strategy, because we'll have to redo graph building from scratch and require more time. This would be annoying on low-resource devices.
  1. Some countries do not require changing this setting to do long distance routing.

So I think primary way to fix this would be to move primary roads to upper level tiles in some countries, which do not have enough trunks to do distant routing.

Also, a good idea can be to have several route_depth variations coded in navit.xml so user can change them at runtime by name. A default for each vehicle profile can be choosen in dependence of device physical RAM amount and CPU speed.

tryagain

comment:70 Changed 5 years ago by mvglasow (2)

Hmmm... some thoughts here:

  • I'm not particularly fond of doing things "by country" as that would involve maintaining a list of countries (especially in the eastern EU the situation changes quite rapidly), and also the situation can be different in different parts of a country. How about the following: when at a certain level a tile does not contain any (or very few) trunk roads, then move primaries in the corresponding rectangle to that tile level. That way the map would auto-adapt itself to the road network in the region.
  • Also, changing route strategies would work for geeks like us, but it wouldn't be much help to less savvy users. I do like the idea of choosing the default based on device parameters (memory and possibly CPU) and I think that's the way to go.

As for memory, see also #1067 - it is mostly a game between route length, route depth and available memory, and this issue is just one of many cases.

comment:71 follow-up: Changed 5 years ago by tryagain

How about the following: when at a certain level a tile does not contain any (or very few) trunk roads, then move primaries in the corresponding rectangle to that tile level. That way the map would auto-adapt itself to the road network in the region.

I do not like to introduce things that require maintenance, but I'm afraid we can't filter the country specifics out that easy. An example: suppose country A have "trunks" for distant routing, while country B has "primaries" for that. A tile which includes A-B border might have enough trunks from the country A and will lack primaries from country B which are needed to cross the border.

Also, changing route strategies would work for geeks like us, but it wouldn't be much help to less savvy users.

Agree. I think we can introduce new attributes of navit object like system_cpuspeed, system_cpucores, system_ram and have that data analysed on navit startup by some script defined in navit.xml.

comment:72 in reply to: ↑ 71 Changed 5 years ago by ceelvain

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

I do not like to introduce things that require maintenance, but I'm afraid we can't filter the country specifics out that easy. An example: suppose country A have "trunks" for distant routing, while country B has "primaries" for that. A tile which includes A-B border might have enough trunks from the country A and will lack primaries from country B which are needed to cross the border.

What we need is a better algorithm that could take every level of road into account. We don't need the very-best route when dealing with roads. I'm pretty sure the 1000th best route on a 100km trip is less than 1 minute longer than the very best route. We only need "one of the best" routes.

I mean, Dikjstra is one of the worst routing algorithm for this kind of job. It is so bad we had to cut boxes around it and reduce the number of roads it take into account in order to make it work in a reasonable time.

I think there is a tradeoff "computation time / quality of the solution" to make.

comment:73 follow-up: Changed 5 years ago by tryagain

Dikjstra is good in that it actually computes all routes to destination from coverage area at the same time.

So if you go wrong way, you'll usually get navigation instructions at the same moment, not waiting for whole route recalculation. I was pretty annoyed when one commercial program were telling me "you went out of the route" and starting 5-minute route recalculation while I were driving in wrong direction on a ~700km route. I just had left a motel in direction I thought right before my gps got the fix. Navit in that situation worked well when I took my phone from the pocket, and let it calculate the route still driving in the direction i've choosen before. Commercial program gave me correct instructions only after I followed navit's command to turn back.

Also, some time-optimized algos may require precomputed info for each vehicleprofile. So you won't be able simply change some <vehicleprofile> settings and recalculate the route, you'll have to rebuild the whole map for that. And each supported vehicle profile would require some extra data on the map.

So there's really a tradeoff but it has more parameters than you have just named. I think we should come to the modulzrized routing algos at the some moment (as woglinde suggested before), so geeks can test different variations and suggest some default(s) for different usecases.

comment:74 in reply to: ↑ 73 Changed 5 years ago by ceelvain

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

Dikjstra is good in that it actually computes all routes to destination from coverage area at the same time.

That's what I acutally blame on Dijkstra. If the routing algorithm could compute a "good enough" route in less than 1 second on any device, you wouldn't need to flood the whole map. If you get out of the route, you would just compute another one on-the-fly without even noticing a lag.

Also, some time-optimized algos may require precomputed info for each vehicleprofile. So you won't be able simply change some <vehicleprofile> settings and recalculate the route, you'll have to rebuild the whole map for that. And each supported vehicle profile would require some extra data on the map.

Well, I was actually thinking about an algorithm that first find a dumb solution, and then improve it. Finding a path in a big graph is not an uncommon problem, I'm pretty sure there are plenty of algorithms for this on the net. ;)

So there's really a tradeoff but it has more parameters than you have just named. I think we should come to the modulzrized routing algos at the some moment (as woglinde suggested before), so geeks can test different variations and suggest some default(s) for different usecases.

I'm waiting for this. :)

comment:75 Changed 4 years ago by usul

  • Resolution set to invalid
  • Status changed from new to closed

(sorry I didn't read all the text)

I tried different routes in Germany with different ranges in car profile but the current SVN doesn't crash. If the bug persists, please reopen this bug. For cleanup reason, I set it to close. For related issues please open another ticket and link back to this one.

comment:76 Changed 4 years ago by sleske

I tried different routes in Germany with different ranges in car profile but the current SVN doesn't crash. If the bug persists, please reopen this bug.

It looks like you mixed up the close reason; this bug is not about a crash, but about incorrect routes.

Still, since the comments on this bug address so many different things, and since the original problem has apparently been solved in the meantime, closing this bug is probably best.

comment:77 Changed 4 years ago by usul

There is a post slightly related to the routing bugs: https://forum.navit-project.org/viewtopic.php?f=13&t=422 Would be great, if the devs who are familar with routing part of Navit could share their opinions, as I'm not that deep into the code :/

Note: See TracTickets for help on using tickets.