<div dir="ltr">Traveling long distances with an electric car requires intermediate fast charging. I did a small prototype with OSRM to compute the optimal route including charging. Here is a demo with routes in Quebec and the public fast charging network Circuit Electrique:<div><br></div><div><a href="https://www.youtube.com/watch?v=zXEa5IlD1LQ" target="_blank">https://www.youtube.com/watch?v=zXEa5IlD1LQ</a><br></div><div><br></div><div>The algorithm is based on a simple Dijkstra shortest path. The graph is a complete digraph between all chargers, the source, and the destination. The edge weight includes the travel time, the charging time and a small overhead for the stop at the charger, which tends to minimize the total number of stops.</div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">The backend [1] is a web service written in Qt/C++ and linked to libosrm, where parameters are passed in the URL similar to OSRM, such as battery capacity, the state of charge and the average energy efficiency. The frontend [2] is the OSRM frontend where the charging</span><span style="line-height:1.5"> waypoints are inserted when the marker is moved and released.</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">The main problem is that complete digraph obviously don't scale well to thousands of chargers O(n^2). The inner graph edges are pre-computed to reduce request latency, but it requires a large startup time of the server. Maybe this can be done as a pre-processing, like osrm-prepare, but the graph will still be huge, so I'm not sure how to reduce the complexity of the graph. I tried to remove very small edges (chargers are mostly equivalent) are very large ones (not reachable with one charge), but it  reduces the number of edges by a factor 2, but is still O(n^2/2).</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Maybe the solution is to perform the computation within OSRM with the low-level street graph? We could stop the relaxation of an edge if its cumulative cost is greater than the range of the vehicle and reaching a charger would reset the range of the vehicle. The exact charging plan would be obtained once the shortest path is found.</span></div><div><span style="line-height:1.5"><br></span></div><div><span style="line-height:1.5">Also, I think it would make sense to have elevation data in OSRM. It is essential to validate energy required for the travel, we want to prevent a user from running out of juice in the middle of a steep hill. It's not possible to just assign this weight to the edge, because some of the energy is regenerated downhill (~75%) [3] and we have to validate the max energy usage at the top of the hill, not the average for the whole travel.</span><span style="line-height:1.5"> In the current situation, it would require to expand the compressed polyline and then sample the path elevation. I would rather do it at lower-level. I think that other projects require elevation data, such as hiking and biking routing, so even though it uses more memory, it could make sense to get elevation data for the path inside the routing algorithm as tuple (lon, lat, ele) or similar.</span></div><div><br></div><div><span style="line-height:1.5">There are other challenges, such as having an up-to-date source of chargers [maybe 4] and taking into account the weather conditions. Even though it's not production ready, I wanted to share the idea and have the feedback of the community. </span></div><div><br></div><div>Cheers!</div><div><br></div><div>Francis</div><div><br></div><div>[1] <a href="https://github.com/giraldeau/evnav" target="_blank">https://github.com/giraldeau/evnav</a></div><div>[2] <a href="https://github.com/giraldeau/osrm-frontend-v2/tree/evnav">https://github.com/giraldeau/osrm-frontend-v2/tree/evnav</a></div><div>[3] <a href="http://sparkev.blogspot.ca/2016/05/regenerative-braking-efficiency.html">http://sparkev.blogspot.ca/2016/05/regenerative-braking-efficiency.html</a></div><div><span style="line-height:1.5">[4] </span><a href="http://openchargemap.org/site/" target="_blank" style="line-height:1.5">http://openchargemap.org/site/</a><br></div><div><br></div></div><div dir="ltr">-- <br></div><div data-smartmail="gmail_signature"><div dir="ltr">Francis Giraldeau</div></div>