Dynamic weights to avoid repetition in routes

openrouteservice
1

Hello,

I’m working on a running route builder that favours greenery & nature over distance, and can also automatically generate routes for you of a target distance. An early version is available on trailrouter.com.

It uses Openrouteservice at its core (which is fantastic!), and I use the green routing feature quite heavily. I believe this means I rely entirely on dynamic weights.

A common use case is creating a “round-trip route”, whereby you start at X, run 20km, and finish back at X. Often, these round-trip routes are automatically plotted along a hiking trail or coastline, which are generally very long lines. So the algorithm often ends up giving you a 10km out-and-back approach. This is technically fine, but some people (including me) prefer to avoid the repetition and would rather have a different route back even if it’s slightly less optimal.

My idea for doing this would be to do something like the following:

  1. Calculate the 10km route from the start point X out to the turnaround point (as I currently do).
  2. Add all edges traversed in step 1 to a penalty list, such that if they are used again then they will get a penalty weight
  3. Calculate the route back to the start point X, utilising the additional weights produced in step 2

Does this seem a reasonable approach? Any pointers to where I should look in the code to achieve this?

Thanks,

Sam

2

Semi-answering my own question: I think the use of AvoidEdgesWeighting in https://github.com/graphhopper/graphhopper/blob/d992b901d223ab0ad10741f014b1e47aacd01669/core/src/main/java/com/graphhopper/routing/template/RoundTripRoutingTemplate.java#L118 is a good example of what I had in mind. I’ll try to follow a similar approach here.

3

Hi @samcrawford,
with the next release (next week if all goes well this time) round trip routing will be in the openrouteservice. That feature is still relatively “beta” though as there are a number of issues relating to how GraphHopper implement it that means it doesn’t always work too well (e.g. it struggles near coastlines, and smaller distance round trips tend to get overestimated, so when you request 10km, you might end up with 12km or more)

4

Thanks for the reply. I’m familiar with GH’s round-trip routing approach, and it’s not really what I was looking for, so I’ve implemented something else instead (which takes into account trails and features in the vicinity - the GH one does not, it just plots points starting from some bearing).

I’ll try the AvoidEdgesWeighting idea I found earlier, I think that will do what I want.

Good luck with the release - I look forward to reading about it and incorporating the update!