Using Matrix API for finding best EV route including Charging stations

Glued_Brain 2017-10-15 11:02:59 UTC #1

I came across this article on finding a best route for EV.

This, however, shows only a single station between the route. What if I want to have a route of around 2000kms and this would obviously have to include multiple charging stations. What should be the approach in this use case and how feasible is the usage of Matrix API in such use cases for production usage?

If it is not feasible what would the best approach?

karussell 2017-10-15 16:43:40 UTC #2

The best thing would be if our Route Optimization API supports optional locations. Currently this is not possible and you would calculate all distance of a few locations via the Matrix API and pick the best via a custom algorithm.

KaiSocrates 2017-10-15 17:06:51 UTC #3

Could you suggest some steps for this in case you have anything off the top of you mind?

Moreover I don’t think the matrix API would help for cases where the range of a vehicle is 100km. Then you would have to call the API atleast 20 times for the complete route plan?

Glued_Brain 2017-10-15 17:14:01 UTC #4

That was my question mate!

KaiSocrates 2017-10-16 01:28:44 UTC #5

I was working on a similar stuff and hence was curious about what would be the custom implementation. If you would want to implement you own algorithm completely, there are many papers written on this thing. For instance, this one here
http://drops.dagstuhl.de/opus/volltexte/2015/5455/pdf/6.pdf

But I’m interested if there would be any approach with what we have in Graphhopper?

karussell 2017-10-16 11:26:05 UTC #6

I have not much experience there nor read any paper yet, but the linked paper would break some algorithms like our speed up algorithm and so I would try to find a ‘less optimal’ solution that is practical. I think this is more a route optimization problem than a shortest path problem. So with our open source tools this is probably already solvable (I think). With our Directions API I would use a more heuristic approach using alternatives: calculate the route with some alternatives, fetch the charging stations ‘around’ those routes, now use the Matrix API to calculate all distances&times and with some heuristic you pick the stations and assign the sequence.

KaiSocrates 2017-10-21 10:59:33 UTC #7

Just realized there are EV cars whose range is like 90-100 miles. What if I want to calculate a trip of 2000 miles. I would have to call the matrix API atleast 20 times? How realistic will the performance be if that’s the case?