Skip to content

Find optimal path for electric vehicle using spatial information.

License

Notifications You must be signed in to change notification settings

ar8372/EV-Enrouting

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

64 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

EV-Enrouting

Find optimal path for electric vehicle using spatial information.

Preprocessing :-

Our algorithm solves 3 main problems:

  • Finding Best Route
  • Finding Optimal Location to setup a Charging Station
  • Dealing with Overhead on Charging Stations

Below we will see demo of these:-

1.Finding Best Route:

a) Base problem

Our algorithm gives us the best route which will take the shortest path out of all the available charging stations.

b) Now with traffic data

The benefit of this grid approach over graph approach is that we can very easily put layers of information on top and our algorithm will work fine. Like here we have added traffic information on top of it.

c) With remaining battery

We can also pass the information about available battery power and it will tell us if there is any charging station within our battery limit. We have given remaining battery of 100 minutes and now we see that many times it is not showing us any path because it is out of range of 100 minutes.

Let's look at details of how it is working:-

2.Finding Optimal Location to setup a Charging Station:

Finding the optimal location to set up a charging station is very tricky and we have to look at various factors, like where there is more demand and which is geographically the most feasible location from all places.

So to solve this we applied three approaches.

  • a) Brute force approach
  • b) Sliding Window Technique
  • c) Subblocks Technique

a) In brute force approach we calculated total return by putting CS at each point of grid (50*50) and the point corresponding to maximum total return is the optimal point.
b) In sliding window we took a window of 10*10 and moved over this 50*50 matrix.
c) In Sub-blocks Technique we divided our whole grid into 4 sub grids (upper left, upper right, lower left, lower right). Then we calculated the return of the median point for each sub grid. We repeat the same for subgrid with max total return.
[Optimality]

Brute Force Approach >> Sliding Window Technique >> Sub-blocks method

[Speed]

Sub-blocks method >> Sliding Window Technique >> Brute Force Approach

(So there is tradeoff between Speed and Optimality)

Sliding Window Techniqe

Sliding Window with traffic


note: we see that due to traffic the optimal charging station position has changed, which makes sense.

3.Overhead on Charging stations:

For this I have defined two types of overhead on the charging stations.

  • a) Dynamic overhead
  • b) Static Overhead

Dynamic Overhead tells how many cars are there in the queue, i.e. if we reach the Charging station now then after how much time we will get the turn.
Static Overhead tells about on an average when a vehicle is plugged in for charging how much time it takes to get fully charged.
Together these two help us find a charging station which is best for us at that current moment.
[case1] : only Static Overhead
Charging Station Static Overhead travel time total time
Cs1 50 20 70
Cs2 10 28 38
Cs3 5 38 43

So our algorithm will choose Cs2 >> Cs3 >> Cs1
Let’s verify below.


[case2] : both Dynamic and Static Overhead

Charging Station Dynamic Overhead travel time remaining overhead:- max(0, Dynamic_overhead-travel_time) Static Overhead Total Overhead:- rem_overhead + static_overhead Total time (total_overhead + travel_time
Cs1 40 20 20 50 70 90
Cs2 48 28 20 10 30 58
Cs3 27 38 0 5 5 43

So our algorithm will choose Cs3 >> Cs2 >> Cs1 [ In this I have applied greedy search which allows us to find optimal CS without the need of calculating travel_time of each and every CS] note: Greedy Search in our case gives optimal solution, details of this method can be found in the report

Theory

Theory Notebook link: https://colab.research.google.com/drive/1zSd24UZs3tKTVcDbJ61VH8CpsZ8QZA8d?usp=sharing