take into account expense of doing a u-turn when routing

[grenzdebil@…]

When the user intentionally leaves the route, navit will always give the instruction to make a 180-degree-turn and return to the route, even when it would be less time-consuming in real life to go on and take a slightly different route than the one originally computed by navit. (to turn around, you first have to find a suitable place to do it, stop, let opposite traffic pass, etc.)

For example: you drive down(up in the ascii example) a main road (A) and navit wants you to turn right at the junction of A and B to get to the target. But you decide - no matter why (maybe because of traffic jam on A) - to turn right at the junction of A and C, go down C, turn, follow D and turn right at the junction of D and B.

+----B-----+------>target
|          |
|          D
+----C-----+
|
A
|
^
start

When on C, navit will urge you to turn around and follow A again.

I am no expert in routing algorithms, but I think if there was some value added to the total "expense" of a route when it involves doing a u-turn on a "one-lane-two-directions-road", better results could be archieved in most of these cases.

Of course the direction of movement has to be known.

[KaZeR]

I personally also vote for this. Turning around is often impossible, and almost always dangerous.

[mvglasow]

How about a configuration setting "avoid U-turns"?

[elhaard]

Today, I saw another reason to vote for this:

    ---+----B---+--------------------->target
       |        | (no right turn)
       D        A
       |        |
       +---C----+
                |
                |
                ^
              Start

Near me, there is a situation like above. There is a turn restriction (no right turn) from A to B.

If you are driving on A and go right on B, then the best thing to do is to turn left into C, right into D and then right into B.

But today, Navit (svn version 4418) insisted that I should just turn left on B and make a U-turn instead. As B is rather congested, making a U-turn is not easy at all.

This type of problems would also be fixed by adding to the cost of making a U-turn.

[usul]

Sounds reasonable to me.
IMHO we need to create some wiki page to list the routing priorities, to avoid conflicts and to setup testcases, to make sure that new routing goals don't destroy old ones.

As it doesn't seem to be a very essential problem (as navit isn't wrong in routing), I schedule it to the next major release.

[kazer]

Actually I have been considering this. There are different use cases where it would help (because in a city it's no big deal to miss a turn you can still turn a bit later down the road.)

Usul has a valid point about test cases. We need to define a comprehensive list of them to be able to make this kind of changes more easily without fear of breaking another feature.

[http://wiki.navit-project.org/index.php/user:jkoan]

It's a feature, we target 0.6.0 now.