Support for turn restrictions and costs about graphhopper HOT 30 CLOSED

Turn restrictions are on the roadmap and very important. But I won't get the time in the next couple of months. Lots of things to do :)

from graphhopper.

I am interested in this feature, together with adding speed (in order to deal with traffic conditions). Could you point me in the right direction so that I could contribute?

from graphhopper.

Turn restrictions are relative easy for a normal Dijkstra. Gets a bit more complicated for a bidirectional Dijkstra and harder for the contraction hierarchies case: http://algo2.iti.kit.edu/download/turn_ch.pdf

together with adding speed (in order to deal with traffic conditions)

What do you mean here? Live traffic conditions or fixed speed limits? (Feel free to create the different issues -> update: #32 )

from graphhopper.

We can try an experiment ... you can 'vote' for this issue here and the more backers there are the faster&better I'll concentrate on it.

from graphhopper.

Ok, I'll play along :-) Just added a $50 bounty to get the ball rolling.
Btw, great job so far with Graphhopper!

from graphhopper.

I will play along too. I am keen on the upgraded walking and turns. I am also looking for public transport, but I think I will land up with OTP for this part because it is quite a large effort.

On 30 Apr 2013, at 10:12 PM, Mats Norén wrote:

Ok, I'll play along :-) Just added a $50 bounty to get the ball rolling.
Btw, great job so far with Graphhopper!

—
Reply to this email directly or view it on GitHub.

from graphhopper.

@matsjg + @quintona Thanks! As I eagerly anticipate yet another contribution from the community I've also placed a $50 bounty :) !

from graphhopper.

I would not limit on turn restrictions only, but also consider turn costs. E.g. left-turns are generally more expensive than right-turns.

Do you already have ideas/concepts, especially for data structures the routing algorithms could use for calculating turn costs? I flew over the paper and the idea of using cost tables on each node seems to be promising. Would be great if you can describe your ideas, some problems you see, and maybe what you want or what you do not want.

from graphhopper.

Yes, cost tables instead of modeling an edge based graph is my preferred solution.

The main problem I see is with CH, the normal algorithms should be straight forward (ok, the bidirectional ones need a bit more attention).

For CH the query will degrade by a factor of 3 according to some paper (for C++). So, I have the fear that it could be even worse for Java or needs a lot of work and attention to get it right, especially on Android. Also the preparation time (which I could improve recently by a factor of 2) will suffer IMO. As the normal Dijkstra will be called a lot. Several millions - even for smaller areas, but probably there is still room for improvement even without turn restructions.

but also consider turn costs

We should have an eye on this of course, but I've the experience that making step by step progress is better than getting overwhelmed by the necessary things to do and get stuck or super slowish.

so probably:

1. turn restriction for all algos except CH
2. turn restriction for CH
3. performance improvements
4. turn costs

The question is after which step should/could the bounty be paid :) ?

from graphhopper.

I implemented a first prototype for supporting turn restrictions on all algorithms except those which use CH.
Feel free to ask and maybe you can give me advises/hints/tipps/whatever.

fork+commit: https://github.com/khuebner/graphhopper.git
details: https://github.com/khuebner/graphhopper/wiki/Turn-Restrictions

PS: it's my very first contribution on an open source project. :)

from graphhopper.

Thanks + nice! Keep coding - this looks good!

Regardaring OSMids: yes they shouldn't stay in the storage, but you're already saying that you'll eliminate them...

Regarding unit tests: I'm adding unit tests before coding :) because afterwards they are sometimes hard but at least not really fun to add. E.g. define the future turn restriction API (storage.limitNode(a, b) => check if edges of a is only {b} etc) with your unit test and then go ahead implementing it. So, no need to deploy something to a device or web service to view and verify it. For me unit tests speeds up working a lot. Try it :) ! BTW: If some of the turn restriction tests go into AbstractRoutingAlgorithm you see automatically if they work for all algorithms :). (The main tests should go into GraphStorageTest)

Regarding CH: If turn restrictions work for DijkstraOneToMany there is not much more work to make them working for CH as the preparation routine already has the restrictions in mind and adds only correct shortcuts. But speed etc will need improvements + probably other stuff.

Regarding turn restriction table: I'm not sure what exactly the authors in the paper mean with the table. But I thought it is rather a very limited list instead of one entry per node (keep in mind that the world wide graph has over 80mio nodes!). Now assume a three edge crossing, there could be only the following restrictions A to B and C, A only to B or A only to C + a combination for B and C restrictions which make 3*3 => 9 restrictions. The same is true for a 4 edge crossing etc. Now one only needs to point from the node to the index of the concrete restriction. But we can change/experiment with this later very easy and if there are enough unit tests we can be sure that everything is still working.

Also feel free to add you as the author to existing source files!

from graphhopper.

Really nice place to start then. Well done!

On 01 May 2013, at 11:27 PM, khuebner wrote:

I implemented a first prototype for supporting turn restrictions on all algorithms except those which use CH.
Feel free to ask and maybe you can give me advises/hints/tipps/whatever.

fork+commit: https://github.com/khuebner/graphhopper.git
details: https://github.com/khuebner/graphhopper/wiki/Turn-Restrictions

PS: it's my very first contribution on an open source project. :)

—
Reply to this email directly or view it on GitHub.

from graphhopper.

Thanks so far! I will continue my work next week, at least I hope to!

Regarding OSMids: I will store them in an additional storage instead of edge/node storage, which can be deleted after parsing the osm file.

Regarding unit tests: I just discovered that your test suite is well written and easy to extend, so before I continue my work I will write some new test cases for turn restrictions. Kudos!

Regarding CH: I saw that I forgot to extend DijkstraOneToMany to consider turn restrictions. But maybe reading the paper with a little bit more attention would help me to understand what's happening there.

Regarding turn restriction table: It's not really a table, and its not a entry for each node. Every node points to a node cost entry, if, and only if, it is in relation with a turn restriction. If it don't have any restrictions, the pointer is empty and no entry in the node cost table will be made. Since every node has a pointer (which points to an node cost entry or is empty) the node storage will extended by 4 byte per node (which would mean +300MB when you have 80mio nodes, which is okay for server environment, but not for mobile). Another idea could be (regarding the paper) to create an identifier out of (edgeFrom,nodeVia,edgeTo) which would be 12 bytes long. This can be used as an key within a map which holds the turn costs as values. But as you said, I would face this as improvements later.

Fun fact: Currently even pedestrians will consider turn restrictions. 🐢

from graphhopper.

Fun fact: Currently even pedestrians will consider turn restrictions. 🐢

oh, yes. I didn't thought of that as well! Did the unit test discover that? At least now they should ;) !

Regarding OSMids: I will store them in an additional storage instead of edge/node storage,
which can be deleted after parsing the osm file.

I would like to move it to the OSMReader part, as they are not related to the graph and only exist for the import time. See e.g. OSMReaderHelperDoubleParse where I store pillarLats/Lons and osmIdToIndexMap only for the reading part. The cleanup happens in the finishedReading method.

node storage will extended by 4 byte per node

Yes, that is not a problem. And yes crossings with no turn restrictions would not have an entry but still I think this can be improved ... but as you said this is probably better done later.

from graphhopper.

I would like to move it to the OSMReader part, as they are not related to the graph and only exist for the import time.

I removed any osmids from the node and edge storage. While reading the osm file there now is an osmIdToEdgeIndexMap which maps osm ids to edge ids.

oh, yes. I didn't thought of that as well! Did the unit test discover that? At least now they should ;) !

I added some tests to AbstractRoutingAlgorithmTester to test if car/bike routes consider turn restrictions and if foot routes ignore turn restrictions. Some tests for special cases will be added later.

I also changed the API of turn costs a little bit. Now the turn costs are separated in two parts, the first part represents the costs for a turn regarding the distance, the second part represents the costs for a turn regarding the time. The idea behind this is, when we are searching for fastest routes we may want to consider other turn costs than for shortest routes, e.g. left turns will take much time and should be heavy when searching for fastest routes, but should be less heavy when searching for shortest path.
Both turn costs are hold in one integer, the first 2 bytes hold the costs for shortest route search (i.e. turn costs in terms of distance), and the last 2 bytes hold the costs for fastest route search (i.e. turn costs in terms of time. Additionally there is a state of this integer, which represents "restricted" for both parts.
I did this to avoid later re-factoring and to keep future tasks on this topic easier.
Anyhow, OSMReader only sets restrictions yet, no costs.

PS: I always try to merge your changes on the original master into my fork in hope that we won't have any bigger merge conflicts later.

from graphhopper.

I removed any osmids from the node and edge storage. While reading the osm file there
now is an osmIdToEdgeIndexMap which maps osm ids to edge ids.

perfect!

The idea behind this is

really nice catch + idea!

Anyhow, OSMReader only sets restrictions yet, no costs.

OSMReader is not important for now. But is it covered in some test? I think at least one test for every functionality is crucial. I often had the case where something was untested (as I e.g. struggled with removing it) and when I later wanted to try it then it was broken.

PS: I always try to merge your changes on the original master into my fork in hope that we
won't have any bigger merge conflicts later.

nice, thanks for your efforts! I'll have a closer look to all your work this or the next week (after finishing some problems with the new index ...)

One question: which turn restrictions are covered? http://wiki.openstreetmap.org/wiki/Relation:restriction

I mean are restrictions with one or more via points also covered? I'm not sure but I had in mind that this is important and occurs often for truck turn restrictions

from graphhopper.

One question: which turn restrictions are covered? http://wiki.openstreetmap.org/wiki/Relation:restriction

I mean are restrictions with one or more via points also covered? I'm not sure but I had in mind that this is important > and occurs often for truck turn restrictions

Unfortunately only simple edge-node-edge restrictions are currently supported. I currently don't have a concept for how to support edge-edge[-..edge]-edge restrictions in the routing algorithms and also for the storage of such types.

from graphhopper.

Ok, no problem. Just asked to understand the "restriction matter" a bit more :)

I think those restrictions are only easy to be modelled in edge based graphs ... but wait: one could explicitely add an edge from the first to the last node (with only one shortcut edge) ... but again: this is for later :)

from graphhopper.

Is it correct that when using CH I have to decide before graph preparation which vehicle encoder I want to use? Means, when I once prepared my graph for pedestrians I can not use it for cars? I have the same problem now for turn restrictions, i.e. when I set up my graph with turn restrictions, I can not later ignore turn costs.

from graphhopper.

Means, when I once prepared my graph for pedestrians I can not use it for cars?

Currently this is a limitation, yes. But one could extend the preparation and create shortcuts for all three types. but the preparation will be probably a bit complicated, not sure yet.

I have the same problem now for turn restrictions, i.e. when I set up my graph with turn restrictions
I can not later ignore turn costs.

What is the reason for that? Only for CH?

from graphhopper.

Yes, only CH. When considering turn restrictions during the preparation process edges with turn restrictions will probably not being used and a shortcut over other edges will be created instead. The both edges with the turn restriction are now on another level than the shortcut and will be either removed by the preparation process or skipped by LevelEdgeFilter while routing. At this point there's no possibility to route over the both edges which would be better when ignoring turn restrictions.

from graphhopper.

Yes, only CH.

ah, ok. Didn't know that you're already that far! nice! For CH there is no other solution IMO.

will be either removed by the preparation process or skipped by LevelEdgeFilter while routing

you already hacked deep into it :) ! One note while we are at it: disconnecting the edge has the advantage (over ignoring via LevelEdgeFilter) that the queries especially on Android are a lot faster. The big problem with disconnecting is that the edges are lost regardless of what we try. A better solution would be to put the 'disconnected' edges at the end of the edge list and implement a stop mechanism when reaching those disconnected edges. But if we need them, eg. for turn restriction (or for the new index this would be also nice) we can drop that stop criterion.

from graphhopper.

References kschrab#1 and #55

from graphhopper.

I will clean up the code and initiate a pull request the next few days.

from graphhopper.

Thanks!

from graphhopper.

The big pull request #55 is now closed and splitted into the listed issues here

from graphhopper.

Will be implemented in #238

from graphhopper.

Ah and regarding the bountysource money ($120) I think we can surely forward this all to @khuebner? I know it is not finished yet but as I now push it forward it will be for sure in the next weeks or months ;)

from graphhopper.

@karussell / @khuebner there's still a bounty waiting to be claimed! https://www.bountysource.com/issues/289889-support-for-turn-restrictions-and-costs/developers

from graphhopper.

Thanks for the reminder, I think this should go to @khuebner ! Please grab it ;) !

from graphhopper.