[OSRM-talk] Electric vehicle planner

Francis Giraldeau francis.giraldeau at gmail.com
Thu Jun 16 15:08:18 UTC 2016

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:


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.

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 waypoints are inserted
when the marker is moved and released.

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

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.

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

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.



[1] https://github.com/giraldeau/evnav
[2] https://github.com/giraldeau/osrm-frontend-v2/tree/evnav
[3] http://sparkev.blogspot.ca/2016/05/regenerative-braking-efficiency.html
[4] http://openchargemap.org/site/

Francis Giraldeau
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160616/d53c2ae3/attachment.html>

More information about the OSRM-talk mailing list