If you own a Tesla and are planning a road trip, you can program in a start point and an end point for your journey and your car will inform you where the best places are to charge your battery along the way. But if you don’t own a Tesla and are planning to use public chargers for your journey, the potential route and charging options could run into the millions.
There are so many factors to consider — the state of charge of your battery when you begin, how far your car can drive given weather, traffic, and elevation changes, and the availability of chargers along your route are all important considerations. Then there are individual preferences such as whether you want to enjoy a meal while your car is charging or sit by a waterfall and commune with nature for a while.
In a blog post this week, Google says it has devised a new Maps feature that uses “graph theory” to sort through all the permutations and give drivers accurate information about how to drive and charge along the way. In the three graphics below, the new feature shows the fastest route from Berlin to Paris in a gasoline powered car, in an electric car with 400 kilometers of range, and in an electric car with 200 kilometers of range. All three routes vary significantly.
“Today, we present a new approach for routing of EVs integrated into the latest release of Google Maps built into your car for participating EVs that reduces range anxiety by integrating recharging stations into the navigational route,” Google says in its blog post. But as The Verge points out, at the present time the only two cars with Android Automotive baked in are the Polestar 2 and Volvo XC40 Recharge, although more models are on the way.
“Now when you enter a destination that requires two or more recharge stops, algorithms in Maps will search and filter through tens to thousands of public charging stations to find the most efficient route — all in less than 10 seconds. You can see how long each charge will take and your updated total trip time, so your final ETA will never again be a mystery,” the blog post says.
“Based on the battery level and the destination, Maps will recommend the charging stops and the corresponding charging levels that will minimize the total duration of the trip. To accomplish this we engineered a highly scalable solution for recommending efficient routes through charging stations, which optimizes the sum of the driving time and the charging time together.”
The blog post goes into great detail about how the new feature uses Dijkstra’s algorithm to find the shortest possible route and if you are an engineer or a math jock, you may enjoy reading up on that. For the rest of us, it is sufficient to know that our cars (if so equipped) will help alleviate some of the most common worries EV drivers face when they leave the local area — where will I charge if I need to and will I have enough range to get where I am going without incident?
“EV charging stations are not as commonly available as gas stations, which can cause range anxiety, the fear that the car will run out of power before reaching a charging station,” Google says. “This concern is common enough that it is considered one of the barriers to the widespread adoption of EVs. Second, charging an EV’s battery is a more decision-demanding task, because the charging time can be a significant fraction of the total travel time and can vary widely by station, vehicle model, and battery level. In addition, the charging time is non-linear — e.g., it takes longer to charge a battery from 90% to 100% than from 20% to 30%.”
This new feature will address both issues. “In this work we engineer a scalable solution for routing EVs on long trips to include access to charging stations through the use of graph sparsification and novel framing of standard routing algorithms. We are excited to put algorithmic ideas and techniques in the hands of Maps users and look forward to serving stress-free routes for EV drivers across the globe!” Anything that reduces the amount of stress EV drivers feel will help move the EV revolution forward faster — a good thing for all concerned.