The general idea for this project is to calculate routes that stop at charge stations as needed for EVs to complete long trips in mainland North America. Currently, the start and end points must be charge stations, and user inputted coordinates are snapped to the nearest charge stations before any calculations are done. After this, the route which minimizes total drive time is found and the EV's battery level is simulated. All backend code is written in Python.
Data for this project is retrieved from 2 places.
- US Dept. of Energy's Electric Vehicle Charging Station Locations via CSV download1
Routing an EV trip that is longer than the EV's range involves stopping at 1 or more charge stations during the trip to recharge the EV's battery. To limit API calls needed when routing an EV trip, a "charge network" is initially created as a local offline cache of possible routes. More specifically, a charge network is a weighted graph where the vertices are charge stations and the edges are possible legs between charge stations weighted by drive time.
To limit the complexity of the charge network without drastically changing its functionality, charge stations are clustered into groups contained within a certain diameter2 and then replaced by each group's most central charge station. This is implemented recursively using a divisive hierarchical clustering tree.
| Initial Charge Network (n=3606) | Clustered Charge Network (n=942) |
|---|---|
 |
 |
| Clusters in Initial Charge Network Zoomed | Clustered Charge Network Zoomed |
|---|---|
 |
 |
A possible leg is defined as a leg which has a road distance less than the max supported EV range of the charge network3. To initially populate the charge network with all possible legs, an API call must be made for each leg to compare road distance to the max supported EV range of the charge network. Using great circle distance between two charge stations as a heuristic makes the number of API calls needed feasible; an API call is only needed if the great circle distance is less than the max supported EV range of the charge network since the road distance is certainly greater than the great circle distance.
| Completed Charge Network |
|---|
 |
Given that the charge network represents all possible legs for the EV, routing from one charge station to another simplifies to the single-pair shortest path problem. This is solved using the A* search algorithm with great circle distance heuristic implemented using a fringe priority queue and hash set for constant time membership checking at the expense of space complexity.
After a route has been found, the start battery of the EV is initialized based on the user input. Battery depletion is simulated linearly with road distance. Battery charging is simulated following a non-linear regression of current battery technology where the charge rate diminishes as the battery approaches fully charged4. With this in mind, at each charge station, the EV is only simulated to charge just enough to make it to the next charge station as charging more than that will be at an unoptimal charge rate.
The Python logic in the backend retrieves user input and serves output to the web app using the Flask framework, along with Jinja interpolated HTML, and static JavaScript. Flask is also used to store user input as a cookie on form submission. Three Google Maps API endpoints are used. All 3 are rate limited via "quotas". The Directions endpoint is only called on the backend and is further restricted by IP. The Places endpoint is also only called on the backend, but since it is billed by token sessions, the "quota" rate limit is not helpful. Thus, an SQLite database is used for token and session logic to enforce request limits via the API wrapper routes of this Flask app. It is also restricted by IP. Finally, the JavaScript Maps endpoint is called by the frontend and is both stored in unicode code points to avoid it being scraped from GitHub and restricted by HTTP referrer.
This project is deployed on an OCI Ampere A1 Flex VM running Oracle Linux 85. The Flask app is run in a Python 3.12 venv using the WSGI HTTP server Gunicorn which is run behind Nginx configured as a HTTP reverse proxy server (recommended by Gunicorn). SSL certificates are created and renewed using Certbot in its own venv.
The following commands were used (with sudo redacted for readability).
dnf install git python3.12 nginxfirewall-cmd --add-service=http --permanent
firewall-cmd --add-service=https --permanent
firewall-cmd --reload
setsebool -P httpd_can_network_connect 1cat > /etc/nginx/conf.d/main.conf << "EOF"
server {
server_name www.evsim.ca evsim.ca;
location / {
proxy_pass http://127.0.0.1:5000;
}
}
EOF
systemctl start nginxpython3.12 -m venv /opt/certbot/
/opt/certbot/bin/pip install certbot certbot-nginx
ln -s /opt/certbot/bin/certbot /usr/bin/certbot
certbot --nginx
echo "0 0,12 * * * root /opt/certbot/bin/python -c 'import random; import time; time.sleep(random.random() * 3600)' && sudo certbot renew -q" | sudo tee -a /etc/crontab > /dev/nullgit clone https://github.com/skrukwa/evsim.git
cd evsim/src
python3.12 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
gunicorn --bind 127.0.0.1:5000 app:app