Optimize routing algorithm about graphhopper

[easbar]

Ok sure its probably also not a real problem. If some issues are auto-closed we can just re-open them. But do the commit hashes really stay the same even when porting the map-matching repo to here?

[karussell]

Yes. Or at least they did it with the method I used for the navigation pull request. See e.g. the first commit here: https://github.com/graphhopper/graphhopper/pull/2071/commits -> 6c03fdd -> graphhopper/graphhopper-navigation@6c03fdd

[karussell]

One can now preprocess the graph to create shortcuts (contraction hierarchy) - call OSMReader with osmreader.levelgraph=true and osmreader.chShortcuts=fastest. In addition to this you need to call new LevelGraphStorage with an MMapDirectory. This way it was possible for me today to successfully perform a 500km query on android with only ~15MB (32MB were allocated) within about a minute. Still this is improvable but the base is created. Keep in mind with contraction hierarchy we do not apply any heuristics to achieve this, 'just' clever shortcuts!

[karussell]

There is also beam search

[karussell]

Reopening in order to implement memory limitating algorithms. Also look at #104 for possible hard abort condition

[karussell]

Found an implementation of ID A* in Java and under Apache License https://github.com/citiususc/hipster/blob/development/hipster-core/src/main/java/es/usc/citius/hipster/algorithm/IDAStar.java

[karussell]

For none-CH requests one can now increase the heuristical nature and improve speed by a factor of at least 2. See #506

[easbar]

Almost eight years later issue #1 got closed 😄

[karussell]

Oh, why ... (ah, the commits of #2071 had a link to the issue #1 of the navigation repo ... )

[easbar]

Uh yeah there was a commit in the navigation repo that closed issue number 1 of the navigation repository:

and now we had this commit here it closed issue number 1 of this repository. Btw were there other issue references (in comments etc.) pointing to navigation issues? For map matching we should also check this and maybe change comments like

// this is a comment, see #6586

to

// this is a comment, see map-matching/#6586

[boldtrn]

Oh no, that's really unfortunate. I guess there will be multiple comments like this in the MapMatching Repo?

[easbar]

Yes, but in the navigation code there weren't any. For map-matching we should not forget about this. But actually we should be a bit careful because I think we decided not to squash the map-matching commits (to preserve history) and there might be some commits that auto-fix some issues :)

[karussell]

maybe change comments like

We cannot change commit messages without changing the history that could break other things.

[easbar]

We cannot change commit messages without changing the history that could break other things.

I meant we should change comments in the code. But even if there is something like fixes #256 in a commit message we could change the commit message when we are merging map-matching? It would not be possible in the map-matching repository, but when we merge it here its no problem to change the commits (they are just new commits for this repository, nothing existing is changed)?

[karussell]

I do not like rewriting history for map matching that much as e.g. we would not be able to easily find map matching commits in the graphhopper repo and maybe other disadvantages. E.g. when linking to commits like [here](graphhopper/map-matching#40 (comment) although this is rather rare (found 4 issues).