Comment by gregkerzhner | Hacker News Reader

Comment by gregkerzhner | Hacker News Reader

Parent Full thread

Interesting article. One challenge though is that there are a lot more gray areas in cycling than in driving. Driving is black and white - you want the fastest route thats legally possible. With cycling, everyone's tolerance for what is a good cycling road is different, and you are constantly making trade offs between road quality and scenery, and distance.

The cycling directions in my town, for example, are great in the sense that they take you on only bike paths with little cars. However, they are often 25% longer than just taking the roads which also have bike lanes. I am comfortable biking on the roads so I prefer the roads, but others might not be. Which set of directions do you present? I guess you could have options for both like "most scenic" and "most direct". However, there will always be people complaining about routes being too roundabout or not safe enough because of preference differences.

I think with cycling sometimes its best to just use the bike directions as a starting off point and then explore from there. Hopefully you can be in a place for long enough to discover the routes that fit you best and stick to them. For me, thats actually a fun part of the activity.

Most map apps allow some choices like 'avoid tolls', or 'avoid highways'. Biking should/could be similar. Prefer bike paths vs bike lanes. To be fair, it is hard for the Google Street view car to go down the bike lanes. Going to need to rig up a bike with the camera rig. They've done it for hiking trails, so why not?

> choices like 'avoid tolls', or 'avoid highways'

Those choices are insanely expensive for Google to provide.

Every unique configuration of options has to be hosted by hundreds of servers in each region. The cost of running the routing service is proportional to 2 ^ (the number of options). It's because everything has to be precomputed for fast lookups, and the lookup tables for one set of options aren't valid for another. See [1].

This is why Google hasn't added any more options in ~a decade. Even then, some combinations of options use various approximations and in some cases don't return the mathematically best result, or take longer to do so.

[1]: https://bib.irb.hr/datoteka/644571.MaueSandersMatijevic.pdf

That paper is old and definitely not what Google Maps actually uses. Techniques which people actually use (mostly Contraction hierarchies and CRP) are much more compact than what you describe. Routing isn't just a table lookup.

Google Maps' offline maps also include routing information. The downloads are pretty small, which definitely excludes the more space-intensive algorithms.

To be fair, contraction hierarchies are inflexible for exactly the reasons OP described. CRP (aka multi-level dijkstra) is more flexible, but there's always a trade off between query speed, pre-process/weight-update speed, and route quality. These services are very expensive to run at global scale if you need multi-modal or live congestion support.

Customizable Contraction Hierarchies go a long way towards solving that, they're quite similar to CRP with regards to both customization and query time. Also, route quality isn't part of the trade-off: all of these methods are exact.

I would argue that updating the routing algorithm's data structure isn't the expensive part of reacting to live traffic. Getting and processing the raw data sounds a lot harder than re-running the customization phase of routing preprocessing.

> which definitely excludes the more space-intensive algorithms

No. A small area means a small download.

I'd be very concerned if download size wouldn't scale with the size of the map, so I'm not quite sure what your point is. Nobody uses lookup tables for routing (that would require quadratic space to store). If you really want to use something that could be described as lookup tables (even though "set intersection" would be more accurate), have a look at hub labeling. But that still requires a lot of space and isn't particularly suitable for traffic updates, so it's clearly not what any of the maps services use, online or offline.

”It's because everything has to be precomputed for fast lookups”

I don’t see how that can be true. With, conservatively, 50 million destinations, that would mean 25E14 different precomputed routes (edit, that’s exactly what the paper you reference argues: An extreme way to accelerate queries is to precompute all shortest path distances d(s, t). However, this is impractical for large graphs since it requires quadratic space and preprocessing time.)

Also, the average GPS without any internet connectivity can compute routes. Surely, those don’t store those precomputed routes.

What likely is true is that it may be a bit harder to do a bicycle route planner. Slightly simplifying, a planner for cars, given two places A and B relatively far apart, ‘just’ needs to find the best route from A to any on-ramp to a highway, from any highway to B, and a route only on highways between the on- and off-ramps.

On the other hand, bike routes that have to be planned typically will be a bit shorter.

Together, that means it isn’t that hard to compute routes on the fly. https://routeplanner.fietsersbond.nl/ does exactly that, giving you options such as “shortest route”, “fewest interruptions”, “racing”, “fewer cars”, or “recreational”.

It's kind of true. Routing algorithms like Contraction Hierarchies and Transit Node Routing don't precompute every possible A-B pair, but they do store so many "shortcuts" (i.e. the best route between common As and Bs) that a route lookup will quickly converge on one of these precomputed routes for all but its first and last sections.

It's similar to the way that we intuitively navigate by car - if you drive from (say) London to Glasgow, you don't bother weighing up the many options: rather, you take whatever local roads get you to the M1 fastest, then follow M1, M6, M74, and then whatever local roads get you to your exact destination.

Would it be cheaper to download the bike route data to the device and simply do the processing there?

Generally bicyclists have a fixed starting point so you could cache the results and improve them over time. (Obviously cross-country would require further work to support efficiently.)

I’m all for “anything can be done in the cloud” but if the cloud can’t efficiently handle this, I still have a couple of supercomputers laying around that I’d be happy to let puzzle over my bicycling needs for a few minutes (or overnight, or for a few weeks when charging) if that helped me find a more scenic route someday that isn’t much slower than the direct one.

This would be an interesting interview question. (/ducks)

Even small navigation company like Sygic can do it. While calculating on my phone.

So I don't think it is that expensive or insummortably difficult.

My 10 year old TomTom seems to manage OK and is pretty under-powered in most respects.

I'd speculate that most of that can be attributed to the TomTom's status a local device. I don't think the trouble is doing this for one person, but rather doing it for thousands to millions of people simultaneously. Also, the TomTom is probably operating on a pretty old set of static maps, rather than the constant updates that a service like Google Maps gets

>Those choices are insanely expensive for Google to provide.

That's a weak hill to die on with the money G makes. That's just the cost of doing business. People using maps need choices. If you as a map app choose not to provide an option, that's just an area a competitor can one up you. Once they do, you have to play catch up. That could be advantageous as you see what the competitor did that does/does not work allowing you to shortcut some of the R&D.

> That's just the cost of doing business.

It's not "doing business" if people using maps don't provide enough revenue back to the company either directly or through advertising. The reason Google makes so much money is that they are careful to implement features that are revenue positive.

Google isn't bottlenecked by money. Computers don't run on money. They are bottlenecked by getting datacenters online and staff ability to manage the complexity to keep systems running.

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 trivial to filter given options.

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.

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.

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.

Google has a Street View Trike to collect images from bike paths. It hasn't been widely used yet.

https://services.google.com/fb/forms/streetviewussuggestions...

Should/could be similar? It "is" similar! There is software that allows to configure your cycling speed as well as such preferences, one example I know of is OsmAnd.

It would be great if there was a more objective rating system to refer to (maybe something like this exists and I'm not aware of it?). Like an A bike rating would be a truly protected bike lane, physically separated from moving traffic as well as parked cars and loading curbs and anything else. B might be a dedicated bike lane, but not physically separated from road or parked cars so you might get a door opened on you.

Then you could look up map directions and maybe choose different routes based on the time estimate plus a breakdown of what percentage of the trip will be in different conditions, and you can choose your preferred route based on your safety tolerance.

As somewhat of an aside, I find the way you've explained your trade-offs here strange - as a matter of tolerance, and comfort being around cars vs desire for scenery. I've seen a lot of stories of very experienced, comfortable cyclists killed by cars every year. IMO this is very much not a learning curve or experience issue, it's an issue that biking on busy roads designed for cars and not bikes is genuinely dangerous in a way that is largely out of your control as a cyclist.

Luck certainly plays a factor but experience cycling on the roads is key.

When I cycle on roads I am hyper aware of my surroundings. I am scanning all around me, including behind me every few seconds. I’m also specifically looking at people’s faces and assume they don’t see me until we make eye contact. I also take space aggressively - if there is no bike lane I will bike in the middle of the car lane until I see a safe place for the car behind me to pass, and only then move over. This might piss off the cars behind me, but as long as they see me, its OK with me.

All these techniques make sure that I am seen by other cars and nothing surprising happens. This kind of riding takes years to build up experience. Anectodal, but through my 25 years of heavy commuting on a bicycle on roads shared with cars I’ve never had an accident - but I’ve certainly had several while driving a car. Ive also had several close calls on bike trails because those tend to be filled with pedestrians who aren't looking at all and don't follow any rules.

For sure I could go out biking tomorrow and get killed but freak accidents happen in all areas of life. Personally I don’t feel in danger on the roads - but everyone’s tolerance and experience is different and that’s one of the cruxes of giving good bike directions.

Yeah, there's a lot of factors to weigh.

How much car exhaust do I want to sniff? How much do I want to have to fight for space on a 'cycle lane' that's just a bunch of road markings directing me right down the middle of a lane of cars? What's the shade situation like? How well-maintained is the road? How sketchy are the neighborhoods I'm going through? Am I in a hurry, and how much do I wanna trade these other desires off for The Shortest Possible Route? Am I taking my time and feel like exploring?

At least I currently live in a very flat place so I don't need to worry about any hills to either detour around or sssssllllooooowwwwlllllyyyyy grind my way up.

Your preference may even change depending on where you're going. For my daily commuting and basic errands, I pretty much always take the most direct route. But then, I don't need an app for that, since it's the same every day. Even for recreational riding, I have a bunch of routes that I know well, and really only need to consult a map if I'm somewhere unfamiliar. And then it's usually not 'tell me how to get home' but 'get back to somewhere I know'. Usually a minute of scrolling around on the map will do that.

I would love a scenic option in driving instructions, much less biking instructions, but I think there’s a nuance that’s missed by that phrasing.

Imagine a slider between “Prefer protected bikeways” and “Prefer fastest routes”. You could show in UI the trip time for each extreme and a ‘middle’ choice.

Paired with a slider that says “Avoid uphill climbs” to “Prefer uphill climbs” and some checkboxes for scenic routes and paved-or-not and “fragile goods”/trailer-towing/etc, you’d have something pretty amazing.

That's my biggest problem with Google maps for cycling in London. They somehow always want to send me via Regent's Canal even if it's farther. I get that there are no cars and it's theoretically a nice route, but way too crowded to cycle during the day.

Reply on news.ycombinator.com