Let's say I want to plot a navigation route from San Francisco to New York. There are about a thousand services that can do this for free. There are also many services that can solve the Traveling Salesman Problem and compute a route through 6 cities, figuring out the optimal order. These are all solved problems.
Now let's say I want to plot a course from SF to NY, stopping at EV chargers from a database along the way.
This is more difficult than just a bunch of waypoints, because I don't need to stop at every one. I just need to limit my route to hop from one to the next.
How might I go about figuring this out? Is there an algorithm that I can use to simplify this? Or perhaps I could use OSRM (https://github.com/Project-OSRM/osrm-backend) to help me somehow, instead of relying on the public APIs. We could brute-force this and just keep calculating routes until we find the shortest one that works, but I could see that falling apart pretty quickly.
Construct a directed graph. The waypoints are the nodes, and you put a directed weighted edge from waypoint A to waypoint B if the distance can be covered by a fully charged car. Then you need to find the shortest path in a weighted directed graph.