3 ms·

I don't really buy this argument: each pre-computed route could be tagged `{toll: false, highway: true, elevation: 15, scenic: 0.9}` and such, making it almost

• karussell 6y ago
  The expensive part is not the filtering. Actually you can do hundred of thousands of road segments per second (maybe 10x less on a phone). The expensive part is the visited nodes from Dijkstra vs. the much less nodes from the query of a precomputed request. The speed difference can be 50x or 200x, depending on the route length.
  • lorenzhs 6y ago
    I don't think you understand how these routing algorithms work. Contraction Hierarchies, Customizable Route Planning, Transit Node Routing, etc are all guaranteed to give you the same result as a Dijkstra search. They just exploit properties of road networks to do so much faster. The secret sauce of routing is not in the algorithms (those are publicly known), it's computing the edge weights (including things like turn costs). Effectively, the edge weight has to be the desirability of driving/riding/walking along that particular stretch of road. A big factor of this is obviously travel time. This whole discussion is centered around the observation that whatever metric Google uses for bicycle routing, it doesn't result in routes that users perceive as good.
  • ulucs 6y ago
    I'm not sure I fully understand this. Is the speed difference caused by the options limiting the use of pre-computed nodes? As in, looking for guarded bike roads limits the search for pre-computed nodes' lengths and the search has to be deeper as a result of thay.