High level design for OASIS service

[CodeBear801]

Subtask of #120

POC Strategy description

1. Pass in destination and user's current energy level

2. Calculate route for given origin point and dest point

3. Pick segment gaps from route which is used for energy search

4. Query for search service for charge points

5. Query for table service for all distance&duration in each group. Ie, orig -> all charge points in the first segment gaps., all charge points in the first segment gaps to second gaps, ... , to destination

• Need to guarantee each range at least has one candidate has energy to reach next stage.
• Need to be aware that single charge station could exists in multiple stage's candidate.

6. A high level graph is generated, use Dynamic Programming to pick the best strategy

• Please note each charge station could have multiple charge time <-> energy level pair.

7. Generate result and make charge station candidates as way points.

Architecture

Component design

Corner cases

Parameter input

• Origin/Dest is not reachable
  • Origin/Dest don't have route in between
  • Origin/Dest's distance is large than POC's estimation
• Unreasonable initial energy level

Communication with OSRM

• OSRM server is down
• OSRM table service couldn't calculate route for given [O, D] pairs.
  • For example, given one point is never reachable, what will happen

Communication with Search

• Search service didn't response
• Search service respond very few charge stations

Integration

• Charge stations for this step is never reachable from previous step.

[CodeBear801]

Requirement:

• For given Oirg/Destination/current energy level/max energy level & charge stations, provide optimized charge station solution for user
• At start, user could have certain level of energy, represent by the value of curr_range(more info Oasis API design #128)
• When reach destination, user need to have certain level of energy, represent by a internal parameter dest_range(more info). Please note that dest_range is dynamic updated value, based on user's setting and distance to nearest charge station of destination.
  • For example, user set prefer_level = 32000(unit is meters, 20 miles), if nearest charge station is 10000 meters, then dest_range is 42000
  • For example, is user specify destination is chargeable and prefer_level = 32000, then dest_range is 32000

POC version

• Calc route for Orig/Dest, if no need charge then done

  • case 1: curr_range - (od_distance) > dest_range, no need any charge

• Special logic for start, find all charge station which is reachable based on user's curr_range(might need tune, too much charge stations)

  • Select charge stations along the route
    

• Special logic for destination, find all charge station which is needed based on user's dest_range(might need tune, too much charge stations)

  • Select charge stations along the route
    

• If same charge station exists in orig's range and also destination's range, then pick the one with minimum time

  • case 2(Need one charge stations): curr_range > (od_distance) & curr_range - (od_distance) > dest_range & same charge station exists in both OD's range

• Calculate charge station needed in the middle
  

  • Why need Distance for additional charge station selection: Avoid two charge station too near to each other. If we use following strategy
    
  • Such corner case exists: let's say max range is 300, but in middle the gap is about 350, which means when we charge at first place which could run for 300 but need another charge for 50 then come to next step. Instead, if we are certain we need 350's total energy then we could choose to charge two times at beginning which makes charge station exists more reasonably.
  • Please note, this solution might still miss the optimal solution .
    * original route might not be charge station friendly -> far away from charge station -> alternative route could help, version 2 could solve this
    * The strategy of picking search location ignores distance between charge station to original route. Its possible our search range ignores the charge station which is better. -> version 2 could solve this

• Evaluate result and find most optimal solution globally

  • Why need DP: avoid following case, two charge stations, one near to the route and another is far away, but the far away one is near to destination. If we choose the first one then we might need another additional charge.

More details

Want to divide functionality to 3 kind of situations:

• No charge station needed
  • Input is oasis request
  • Need query OSRM direction service
  • If fall into case 1's condition then generate response

`curr_range` - (od_distance) > `dest_range`

• Only 1 charge station needed
  • Input is oasis request
  • Need query search for charge station near orig and destination
    • For orig, will filter stations by curr_range, which means based on current energy, user must charge within curr_range
    • For dest, will filter stations by dest_range, which means user must charge within dest_range
  • If there is a match in 2 search result, which means we could use that charge station to complete the trip.
    • Use OSRM table service to calc(orig, charge stations), (charge stations, dest)
    • select topK result
    • Generate response
• Multiple charge station needed
  • Input is oasis request
  • Input is route response
  • Input is search result for orig&dest
  • Main logic is, calculate the place need to charge via route, query for nearest charge stations, using OSRM table service to calc distance/duration between each segment, pick topk
  • Need to query OSRM table service between different group of charge stations
  • Need to query search service for nearest charge stations
  • The calculation must be sequential

Version 2

• Charge station based search.
• During pre-processing, calculate all reachable charge station for each charge station
  
• For case 1, similar as POC strategy
• For case 2, similar as POC strategy
• If orig and dest is far away, then strategy go to charge station based routing. Which means we could forget original graph, and abstract a new layer of graph which only contains charge station as node and there distance/duration as edges. Routing based on this layer is much faster and could find most optimal solution.
  

[CodeBear801]

The design of StationFinderInterface:

type stationFinder interface {
       prepare()
       iterate()
       calcCost(another stationFinder)
}

There are several kind of stationFinder: origStationFinder, destStationFinder, midStationFinder

The target is, for client code should look like this:

stations := NewStationFinder()
                   .prepare()
                   .calcCost(anotherStationFinder)
for v, _ := range stations.iterate() {
         // do things
}