Hacker News new | past | comments | ask | show | jobs | submit login
Show HN: Configurable Route Planning – Avoid left turns, areas and more (graphhopper.com)
143 points by karussell 4 months ago | hide | past | web | favorite | 44 comments



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...


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...


> 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).


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...


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


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.


which country was this?


Netherlands. As far as I know the emergency services here are government run, so I guess they bought this for all of them at once.


In The Netherlands there are Veiligheidsregio's ("Safety regions", areas where the emergency services work together) which make changes to OSM to improve the routing for emergency services. For example, Veiligheidsregio Twente is quite active.


So they've built / bought a custom system based on OSM data?


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”


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


How does this compare to Valhalla?


what is a routing engine?


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


An engine that calculates routes.


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.


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.


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


> 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.


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


What would be the point in downvoting in the first place, then? I assumed it was a joke.


I understood it as a private, personal, downvote. Meaning to tell the system to avoid that route as much as it's possible


Yes. I didn’t mean it as a social filtering thing like HN. I meant it more like most of us interact with Netflix (stop showing me movies like this, it was awful).

That said, if everyone hates an intersection, the mapping people should investigate why. Use it as a priority queue for audits, for instance.


Of course, if it's really about avoiding your ex, why would you want the makers to know at all? You'd really want the preference to be on-device only with an option to contribute it to everyone else.


Ah, I see! That makes sense.


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.


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.


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?


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.


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.


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?


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.


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


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).


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


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)


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.



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.


„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.


I would definitely use this feature.


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)


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

see the gif




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: