Improve Oasis service

[CodeBear801]

We are near to finish implementing POC version of OASIS service, for next step, we want to expericing several strategy which might be helpful for production

• Charge station based routing
• Search charge stations along the route
• Remove dependencies on Telenav search for static charge station information

Charge station based routing

If Orig and Dest has some distance in between, let's say needs at least one charge time.
We could find all charge stations which could be reached for start point and all charge stations are needed to reach destination, if there are overlap in between, then we could end up with single charge station, otherwise, calculate the best route based on charge station network, node is charge station, edge is reachable charge station for each charge station.

• We could pre-process each charge stations, record all charge stations it could reached after charging in this charge station.
• We could experiment to record all charge stations could be reached if charging for two times. For example, station1 could reach station2 and station3, station2 could reach station1, station3, station4, and station 3 could reach station2, station1, station6
  we could create following table and recorded in db:

station name	charge times	reachable stations
station1	1	station 2, station3
	2	station2, station3, station4, station6

So let's say we limit this strategy to find charge strategy solution for at most 3 times charges, then we might just need db query and find whether there are duplicates in both query results.
The amount of results and db size is the concern, need experiments.

• If we pre-process charge stations using spatial engine like google-s2, then it could helps to find charge stations in certain radius easily:

Just based on spatial index we could find all cells for certain query polygon, just need retrieve data inside the polygon after query.

Search charge stations along the route

When we drive our EV follow the route, if charge station candidates near to the route could pop up smartly, then we don't need complex algorithm to pick optimized charge stations, just drove off current route and find a charge station when energy is low.

So how to search charge stations along the route?

Usually, search service works like given center point and bounding box, it could return all related data back. But in search along route's case, its hard to define center point. Most accurate representation is extend the route as a polygon, search all charge station inside that polygon.

For example, given route in blue, if we could find all charge stations just in green area then select charge station would be much easier.

Based on S2 or H3, we could achieve that easier:

• Collect all charge station data
• Build spatial index based on S2 or H3, for each charge station will assign a list of cells in different level(more info)
• During query time, generate polygon based on route, and query for all cells overlapped with that polygon, both H3 and S2 has such function
  • H3 and S2 has fixed size cells, more important, cells give a draft opinion about location
  • Different level of cells have different size, which represent different range

• Consider charge station location is not evenly distributed, based on logic, we might need to extend cell to higher level to search for charge station candidates
  
  • If we have enough energy, then might just continue.
  • Or, generate a search shape based on our logic and query at running time.

The steps of solving problem of searching for suitable charge stations could be:

• Calculate route between orig and destination. The route response should tell energy consumption for when reach each segment along the route
• Collect cells overlap with search along route's polygon
• Walk the route and accumulate energy cost, unbox the cells when need to look into charge station data. Might need to promote cell to upper level if no data found in current level. Always keep an eye on last cell with charge station data, in case when reach pre-defined energy threshold there is no charge station.

The drawback of this solution is, it assumes charge station could be found near to final route, which might not be the case, so I feel we could trigger charge station based route and search along route strategy at the same time and pick best result among them.

Tools

• Google S2

  • Build spatial index
  • https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/google_s2.md
  • https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/google_s2_cell.md

• Uber H3

  • Build spatial index
  • https://github.com/CodeBear801/tech_summary/blob/master/tech-summary/navigation/spatial_index/uber_h3.md

• BBolt DB

  • Embedded K/V engine
  • For given charge station point, retrieve all cells cover it(this might be feasible to calculate at running time)
  • Pre-processed station table

More info:
#231

[CodeBear801]

So let's say we limit this strategy to find charge strategy solution for at most 3 times charges, then we might just need db query and find whether there are duplicates in both query results.
The amount of results and db size is the concern, need experiments.

Instead of using exact charge stations, may be we could try record cellid instead. It could also support for checking overlap and also has less amount.

[CodeBear801]

Draft design for Charge Station Based Routing

Input

Electricity charge stations, expect input in JSON format follow OSM's tag definition about node and charging_station, example:

{
   "id": 12345,
   "lat": 51.5173639,
   "lon": -0.140043,
   "amenity": "charging_station",
   "operator": "NOFT",
   "fee": "yes",
   "capacity":4,
}

• Later could implement more input connector: pbf, csv, etc.

Pre-Processing

• For each charge station point, calculate its google s2 cellid, record result in bbolt

  • Make sure such function work: check whether a cell has charge stations or how many

• For each charge station point, take which as center and construct a circle whose radius is a hard code max drive range value(500km), query for all cells it could touch, only record the one contains charge stations

  • Make sure such function could work: give a cell id(not station id) could retrieve all cells it could reached by. We also need to distinguish the stations could be reached by charging how much of energy
  • Make sure exact distance between charge stations has been recorded in db
  • For production, circle should be replaced by reach range(or isoline, consider elevation, red/lights, energy pattern, etc)

• For each charge station point calculate all cells it could reached by 2 times charge

Query

• Given two points of orig/dest

• Check whether orig/dest is reachable by current energy

• If not start two strategy together: charge station based routing and search along route

• logic of charge station routing

  • For input, need using its current energy to filter all charge station it could reached
  • For Dest, check all charge station needed to reach destination
    • Check whether there is overlap between those two, if yes, then go to next step
    • For all reachable stations from start, generate a reachable cellids by combine each charge station's 1-time-charge reachable cells result, see whether there is any overlap with dest's stations(or cellids contain those stations), if yes, go to next step
    • For each reachable charge station of start, they have their unique value of arrival energy, this value need to be considered during calculating charge times, but the exist status of each charge station is fixed: such as charge to 60% of energy, 80% of energy, etc.
      * For all reachable stations from start, generate a reachable cellids by combine each charge station's 2-times-charge reachable cells result, see whether there is any overlap with dest's stations(or cellids contain those stations), if yes, go to next step
  • Construct graph to calculate most suitable charge stations
    * Except start and end, nodes are charge stations, edge is the connection between stations.
    * charge time value need to be assigned properly

• The algorithm used for calculating shortest path between two points in geo-graphical map still works here, just with some adjustment on node and edge's definition

  • nodes are charge stations, and each charge station might have several status: charge to 60%, charge to 80%, charge to 100% of total energy
  • edges' weight could be duration, payment or the combination. But charging time is the new information need to be considered
  • There could be multiple ways to reach a certain node, but we just record one with minimum weight, thus, the dynamic value of arrival energy is fixed due to the path and solution is fixed
  • More information could go to here: Document for charge strategy #208
  • May be we don't need bboltdb at running time at all :)
  • The graph is a dense graph, may be we could try with MLD to speed up