5 ms·

I would love to learn how the routing algorithm works. This is probably one of a few opensource-but-in-production implementation of such kind of algorithms. her

I would love to learn how the routing algorithm works. This is probably one of a few opensource-but-in-production implementation of such kind of algorithms. here seems no doc in the repo unfortunately. Still, it's very exciting to see they started from a "Helicoptor Router" [1] five years ago! The author clearly knew what they were doing. [1] https://github.com/organicmaps/organicmaps/commit/7123f71eeccbc4f92bc72fef6f37e0b97c55f863 https://github.com/organicmaps/organicmaps/commit/7123f71eec...

erzapp 5y ago
There are some interesting resources available on the BRouter algorithm: https://brouter.de/brouter/index.html https://brouter.de/brouter/index.html The source code is here: https://github.com/abrensch/brouter https://github.com/abrensch/brouter
et-al 5y ago
Valhalla is also open source and in production: https://github.com/valhalla/valhalla https://github.com/valhalla/valhalla
- flakiness 5y ago
  It's used (or even built) by Mapbox? Very cool! Thanks for the pointer! Leaving a couple of google results for interested folks like me: * https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4f * https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41611
  - neolog 5y ago
    Copied links - https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4f https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4... - https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41611 https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41...
  - andrewljohnson 5y ago
    MapBox hired the Valhalla team after Mapzen went out of business.
- dagw 5y ago
  Valhalla is fantastic, especially since it can run completely offline. I had a project where I had to calculate isochrones of different radii around 10s of thousands of points. Using an online API would have taken several hours to run and cost a non-trivial amount of money. By downloading the OSM data and running Valhalla locally I could process the data in minutes completely for free
Doctor_Fegg 5y ago
I halfheartedly maintain a list of interesting open source routing implementations: https://gist.github.com/systemed/be2d6bb242d2fa497b5d93dcafe85f0c https://gist.github.com/systemed/be2d6bb242d2fa497b5d93dcafe...
- durkie 5y ago
  hey systemed! thanks so much for tilemaker! it's incredibly useful.
  - Doctor_Fegg 5y ago
    No problem! It's come on in leaps and bounds this year thanks to a great new contributor.
jxf 5y ago
What is a "helicopter router" (helicopter routing?)? That's the first time I've heard that term and it sounds interesting.
- flakiness 5y ago
  It's a straight line ;-)
  - raffraffraff 5y ago
    "crow" would have been a more obvious reference
    - kortilla 5y ago
      You can’t ride a crow.
      - bufferoverflow 5y ago
        With a large enough flock you can.
      - jhgb 5y ago
        Gwaihir routing, then.
  - jxf 5y ago
    Ha, got it. Thanks for enlightening me — that helicopter flew right over my head.
aasasd 5y ago
OsmAnd also has good routing on phones. Possibly uses the algo from GraphHopper or OSRM, which are afaik go-to solutions for OSM routing. You might be interested in links from https://wiki.openstreetmap.org/wiki/Routing https://wiki.openstreetmap.org/wiki/Routing
- karussell 5y ago
  OsmAnd has a separate routing algorithm to my knowledge (was one of the first). It is definitely not GraphHopper as I created it later and prefer the routes it creates ;) but you can study our documentation to get a rough understanding how it all works: https://github.com/graphhopper/graphhopper/blob/master/docs/index.md#technical https://github.com/graphhopper/graphhopper/blob/master/docs/... and reach out in our forum for more details. The algorithm from maps.me / Organicmaps is ported from OSRM to Android and iOS. The CTO of maps.me that did this port left maps.me in 2017 but now seems to work on Organicmaps again: https://github.com/biodranik https://github.com/biodranik
  - petre 5y ago
    GraphHopper is anazing. Thank you! I also prefer the routes it creates and use it for bicycle routing.
- flakiness 5y ago
  This wiki is amazing! Thanks for the pointer!
biodranik 5y ago
It's a modified A*. Our code is open, you may learn and improve it :)

erzapp 5y ago

There are some interesting resources available on the BRouter algorithm: https://brouter.de/brouter/index.html https://brouter.de/brouter/index.html The source code is here: https://github.com/abrensch/brouter https://github.com/abrensch/brouter

et-al 5y ago

Valhalla is also open source and in production: https://github.com/valhalla/valhalla https://github.com/valhalla/valhalla

flakiness 5y ago
It's used (or even built) by Mapbox? Very cool! Thanks for the pointer! Leaving a couple of google results for interested folks like me: * https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4f * https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41611
- neolog 5y ago
  Copied links - https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4f https://blog.mapbox.com/mapbox-%EF%B8%8F-valhalla-1fdda95ac4... - https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41611 https://blog.mapbox.com/valhalla-is-live-on-mapbox-d868e8d41...
- andrewljohnson 5y ago
  MapBox hired the Valhalla team after Mapzen went out of business.
dagw 5y ago
Valhalla is fantastic, especially since it can run completely offline. I had a project where I had to calculate isochrones of different radii around 10s of thousands of points. Using an online API would have taken several hours to run and cost a non-trivial amount of money. By downloading the OSM data and running Valhalla locally I could process the data in minutes completely for free

Doctor_Fegg 5y ago

I halfheartedly maintain a list of interesting open source routing implementations: https://gist.github.com/systemed/be2d6bb242d2fa497b5d93dcafe85f0c https://gist.github.com/systemed/be2d6bb242d2fa497b5d93dcafe...

durkie 5y ago
hey systemed! thanks so much for tilemaker! it's incredibly useful.
- Doctor_Fegg 5y ago
  No problem! It's come on in leaps and bounds this year thanks to a great new contributor.

jxf 5y ago

What is a "helicopter router" (helicopter routing?)? That's the first time I've heard that term and it sounds interesting.

flakiness 5y ago
It's a straight line ;-)
- raffraffraff 5y ago
  "crow" would have been a more obvious reference
  - kortilla 5y ago
    You can’t ride a crow.
    - bufferoverflow 5y ago
      With a large enough flock you can.
    - jhgb 5y ago
      Gwaihir routing, then.
- jxf 5y ago
  Ha, got it. Thanks for enlightening me — that helicopter flew right over my head.

aasasd 5y ago

OsmAnd also has good routing on phones. Possibly uses the algo from GraphHopper or OSRM, which are afaik go-to solutions for OSM routing. You might be interested in links from https://wiki.openstreetmap.org/wiki/Routing https://wiki.openstreetmap.org/wiki/Routing

karussell 5y ago
OsmAnd has a separate routing algorithm to my knowledge (was one of the first). It is definitely not GraphHopper as I created it later and prefer the routes it creates ;) but you can study our documentation to get a rough understanding how it all works: https://github.com/graphhopper/graphhopper/blob/master/docs/index.md#technical https://github.com/graphhopper/graphhopper/blob/master/docs/... and reach out in our forum for more details. The algorithm from maps.me / Organicmaps is ported from OSRM to Android and iOS. The CTO of maps.me that did this port left maps.me in 2017 but now seems to work on Organicmaps again: https://github.com/biodranik https://github.com/biodranik
- petre 5y ago
  GraphHopper is anazing. Thank you! I also prefer the routes it creates and use it for bicycle routing.
flakiness 5y ago
This wiki is amazing! Thanks for the pointer!

biodranik 5y ago

It's a modified A*. Our code is open, you may learn and improve it :)