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