Consider amenities when routing (weighting)

Open Source Routing Engine
1

Do you think it would be possible to consider amenities when routing? I’d like to implement routing that would prefer route via certain types of amenities (drinking water, restrooms, fuel stops).

I was thinking this could be achieved with the use of virtual nodes like in QueryGraph.

I’m new to graphhopper and still learning about it and what it is capable of. I haven’t seen anywhere any mention or use of amenities, only tags.

Any help is appreciated.

Regards, Mitja

2

Yes, this is possible. See e.g. how to avoid pubs :slight_smile: https://graphhopper.com/blog/2015/11/15/publess-routes-graphhopper-edition/

3

Thank you for your answer.

Definitely an option but I’m not sure this is what I was looking for. I don’t think I expressed my intentions clear enough :slight_smile:.

I’d like to make graphhoppeer suitable for planing a trip with electric vehicles where you NEED to stop on a charging station every X km/mi. That’s why I think virtual nodes with virtual edges would be more appropriate so the routing algorithm could visit particular node or not, and it would definitely not need to visit every stop along the route.

Another thing I plan to add is another weighing implementation that would prefer routes with lower energy consumption. That part is trivial.

I think I need more time looking at the code to figure how things can be done and what can be done (also what can not be done).

4

A problem like this requires usually OR (as you could easily get more constraints) and so it probably requires a software like jsprit.

One possibility to avoid additional software and for the more simpler requirements is to change the Dijkstra algorithm, limit the range and always extend the range once such a station is reached. You would have to store the range and number of charges in the SPTEntry - you can have a look in the pt branch where we do similar changes necessary to do public transit routing optimized regarding transfers etc.

1 Like
5

Oh … I misread @karussell to start with, and thought he meant something else. I now think we’re talking about the same thing = ) Oh well, I’ll post this anyway if it’s helpful.

…

I wonder if you can use a custom energy consumption weighting. This solves one of your problems (minimising energy consumption), and you can tweak it further to handle the main one (requiring stops at charging stations). To get round this, I’d look at tweaking the weighting/algorithm so that it also includes a (dynamic) ‘maximum consumption-distance until next charge’ (MCDUNC). Assuming you start fully charged, this might be e.g. 100kwh. So you start routing, and at each step, you

  • increment the consumption weight by Xkwh
  • decrement the MCDUNC by Xkwh
  • if MCDUNC goes below zero, stop
  • if you pass a charging station:
    • assume you stop at it - if you don’t make this assumption you’ll need to fork here and consider both possibilities (whether you charged or not) afterward which, I think, might get tricky.
    • add a penalty (as it takes time to wait and charge). This should be based on the charge left in the car (which you can get from the MCDUNC) as e.g. a full car takes longer to charge than a partially charged on.
    • assume you charge fully, and hence set MCDUNC to current consumption-distance + maximum car charge (e.g. 100kwh from above).

This should find you a route (or that none are available). The issue is that you’re stopping at every charging station, when you might not need to. To get round this, I’d simply post-process the final route to remove ‘unnecessary’ charging stations. (And it’s not a bad thing to have extra charging stations on your route which are unused - they’re a good back up e.g. if you take a detour.) I’m not sure, but I think this should get pretty close to a good solution - it should find feasible routes, and if multiple are available, it should find the ‘best’ one (which depends on your definition of ‘best’: charge more often, drive further, etc.).

Some other things:

  • you may need to keep multiple weights so you can e.g. balance consumption and time taken.
  • you could allow users to configure their own starting charge - e.g. I might be nearly empty when I start, so need to go to a charging station immediately.
  • it’s probably a more realistic solution than e.g. requiring a charge every Xkm (as X is not constant and depends on the route).
  • you could eventually add more constraints - e.g. allowing the user to fill only half-way at the last charging station if they’re in a rush, etc.
  • initially you could assume energy consumption only depends on distance, and hence just talk about range in km as opposed to kwh. It’d just simplify things and e.g. in flat cities, may be sufficient.