Show HN: Configurable Route Planning – Avoid left turns, areas and more

https://discuss.graphhopper.com/t/5190

by karussell • 6 years ago

143 44 6 years ago

discuss.graphhopper.com

karussell7• 6 years ago

Let me know if you have questions or want to try it out on your own. This work will be likely in version 1.0 of our open source routing engine:

https://github.com/graphhopper/graphhopper

toomuchtodo• 6 years ago

How does this compare to Valhalla?

avinassh• 6 years ago

what is a routing engine?

IshKebab2• 6 years ago

An engine that calculates routes.

IshKebab2• 6 years ago

An engine (i.e. some code) that calculates good routes from A to B.

hinkley2• 6 years ago

Friends and I have discussed many times that we want to be able to downvote certain intersections. Lines of sight, incorrect information about left turns or one ways, idiot pedestrians, accidents, blinding light at sunset, your ex’s house. Tons of reasons.

kick3• 6 years ago

your ex’s house

In this case, wouldn't you want to upvote it? More people going on it means they have to suffer from more noise.

icebraining• 6 years ago

Not everyone hates their ex, you know; it just might be emotionally difficult to be reminded of the loss.

caconym_• 6 years ago

The decisions Google Maps (and competitors) make in the vicinity of my house are baffling and dangerous. It's almost like it's intentionally looking for left turns out across busy roads with blind corners and crests. Usually there's a light a block or two over, but no, let's see if we can get ourselves killed to maybe shave a few dubious seconds off our trip.

karussell7• 6 years ago

You can contribute to the OpenStreetMap project to fix the data, which is an an outstanding project. Even without registration you can leave notes and contributors will pick them up: https://www.openstreetmap.org

MayeulC• 6 years ago

That looks awesome! I quite like GraphHopper and OSM for directions, however when on the go I mostly use OSMand.

Does OSMand use GraphHopper internally? One of its downsides is the time it takes to compute a route when offline. I read in multiple places that it could use a server for doing so. Is there any documentation for self-hosting it? I didn't find anything on the topic. Is it then possible to leverage a graphhopper instance?

Also, I saw on the README that graphhopper uses djikstra and A*. Wouldn't RRT/ACO be faster to find solutions, to some extent?

karussell7• 6 years ago

OSMAnd is an independent software. For OSMAnd I have not much knowledge, but GraphHopper you can surely host on your own.

BTW: you can use locus maps with our routing service or our own mobile app demo for Android: https://github.com/graphhopper/graphhopper-navigation-exampl...

Wouldn't RRT/ACO be faster to find solutions, to some extent?

Did you try our demo and think it is slow :) ? https://graphhopper.com/maps/?point=Madrid&point=Moscow

We not only support Dijkstra and A* but also landmark (A* variant) and contraction hierarchies which makes routing very fast additionally to our optimized data structures.

quickthrower2• 6 years ago

Yeah I hate the routes google maps concocts with horrible and sometimes illegal turns.

Bearing in mind the no turn between 7-9am mon-fri signs etc.

Another one is the on-off tolls. I want “I’ll pay a toll if it’s 10 minutes or more quicker”

h2odragon• 6 years ago

That's nifty.

I've got one for you. Rural route mail carries aren't supposed to reverse more than 50ft, among other rules. They also have routes that should be derivable from the walk sort data the post office hosts for bulk mail discounts.

The majority of them who are less technical would be deeply grateful for all they help they could get in this arena. The more technical would be even more appreciative.

joncrane• 6 years ago

This reminded me that my uncle was a rural mail carrier. Interesting job. There was a lot more to it than delivering mail. He used his own personal vehicle. He also served as kind of a scout for all kinds of things. Reporting that a road has washed out and the road needed repair and that kind of thing. For many of the families he visited, he was one of the few humans from the outside they would talk to. Receiving and passing on news verbally. He even helped name some of the roads as civilization matured. Apparently he was part of a political machine where these jobs were sought after and getting the job was a form of political patronage. When election time came around, my uncle had kind words for certain candidates. (Note he's dead and long retired so I'm not sure how it works these days)

Never thought about how the traveling salesman problem applied to him, though. However I did get the impression that it was a pretty cushy job and there wasn't much incentive to optimize anything. He spent the time to get to know a lot of people.

Taniwha• 6 years ago

While optimizing for left turns don't forget that about 1/3 of the world's population would rather you optimize for right turns (so please make it configurable)

karussell7• 6 years ago

Sure, it already is configurable, you can even avoid going straight and force a turn on every junction :)

see the gif

laurencei2• 6 years ago

Does anyone know if anything like this, but for emergency vehicle responses? In some cases, routes that are not suitable for a normal car are exceptional quicker for an emergency vehicle to use (because perhaps they can do a right turn at an intersection that normal traffic cannot).

There would be restrictions, because you wouldnt want to go down a wrong way street etc, and some "no right turns" have physical reasons etc (such as median strip that would physically prevent you from crossing).

But there would definitely be a market for this to improve response times. In my country at least (Australia); most emergency service vehicles I know of use a standard GPS routing system that does not take this stuff into consideration...

t0mas883• 6 years ago

Yes this exists, I've been in an ambulance that had a navigation system aware of the "illegal" things they could do. It for example automatically took bus lanes as faster routes.

Didn't ask them what system it was, had other priorities at the time.

laurencei2• 6 years ago

which country was this?

punnerud• 6 years ago

In ArcGIS you can specify emergency vehicle, and can also calculate for distribution of multiple vehicles to multiple targets: https://developers.arcgis.com/labs/arcgisonline/route-multip...

Would love to see a free version of this. The closest I found is Optaplanner: https://docs.optaplanner.org/7.4.1.Final/optaplanner-docs/ht...

karussell7• 6 years ago

Would love to see a free version of this

See also one of our other projects https://github.com/graphhopper/jsprit

Please note that this is the chinese postman problem (visit every edge), which is different to the VRP - the vehicle routing problem (visit many nodes).

And VRP needs a routing engine to decide about the shortest distances between the nodes (usually with a distance matrix).

ge0ffrey• 6 years ago

In OptaPlanner you can grab the Vehicle Routing web application (called optaweb-vehicle-routing) and add any custom constraints that are specific to your use case such as emergency vehicles: https://www.optaplanner.org/learn/useCases/vehicleRoutingPro...

karussell7• 6 years ago

GraphHopper is already used for fire trucks and so called "isochrone calculations": https://github.com/graphhopper/graphhopper#for-analysis

viburnum• 6 years ago

I would definitely use this feature.

TACIXAT• 6 years ago

I feel like this in conjunction with highly configurable voice navigation would be great. I'd opt for a scenic route or a dirt road given some time trade off. In addition to that I am so sick of Google maps giving me four instructions each time I merge onto a new freeway (2 mile warning, immediately before, merge onto, continue on). Maybe even an assistant that can tell you the options and let you choose, and that understands when you say shut up about exit 217.

_-___________-_3• 6 years ago

What's the logic behind avoiding left (right in 1/3 of the world) turns? I assume that route planners already take into account that a "crossing the opposite flow" turn takes longer than a turn the other way, and I would expect them to only suggest that turn when it still shortens the overall travel time. Avoiding them entirely seems like it could only make routes worse.

dangerboysteve• 6 years ago

https://bigthink.com/robby-berman/the-science-behind-why-ups...

_-___________-_3• 6 years ago

Thanks! I guess it could be summarised by saying that turns across the opposite flow have an increased variance of delay, which reduces the accuracy of the routing engine's prediction of how long the turn will take, and they also have an increased risk of accidents.

senand• 6 years ago

„Avoid“ in this case means: increase weight, to make left turns less likely. And that could make a lot of sense, e.g. if you care about a more stress-free route.

_-___________-_3• 6 years ago

How difficult would it be to adapt GraphHopper for routing on things that are not roads/paths using things that are not cars/bikes/feet? For example, routing on canals using boats?

Doctor_Fegg• 6 years ago

Certainly doable, but OSM data for boating isn’t in a great state yet.

xnyhps2• 6 years ago

Last time I looked at it, none of the routers for OSM were good at routing over areas in OSM. For example, when planning a route on foot over a large square, the route often follows the outside edge. This becomes even harder when the area contains "holes" (i.e. a multipolygon). So for canals it could work, but if you need to cross a lake with an island you're in trouble.

sp8962• 6 years ago

See https://github.com/PlazaRoute for a preprocessing solution that is routing engine agnostic.

karussell7• 6 years ago

It already is adapted https://github.com/geofabrik/OpenRailRouting and I know also from a couple of services having it adapted to boats. But yes, routing on areas is still not properly possible (only via emulating paths on it).

nicois• 6 years ago

One of my friends spends quite a lot of time organising pedestrian routes to optimally deliver (local government) material to every house in a zone.

The goal is therefore to traverse every residential street twice, ignoring traffic flow rules, and potentially also identifying the ideal place to start/end.

Can you see this as a viable scenario for this tool to assist with? (This is in Australia, if it makes a difference)

Show HN: Configurable Route Planning – Avoid left turns, areas and more

Related Stories