How could I compute a map route that goes from a starting point to a destination through optional waypoints?

1
votes

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.

1
algorithmgoogle-mapsosrm
from each waypoint calculate distance to next point, if distance is greater tahn current charge, dynamically add a new waypoint for the closest charger... - I wrestled a bear once.
So that was my first thought, but sometimes you have to go a roundabout way along a route you wouldn't normally take. I don't think just searching for the nearest charger would work for all situations, especially if there isn't a charger nearby. - Cory Imdieke
It's unclear how many of these "optional" waypoints are actually necessary: you give an upper bound ("I don't need to stop at every one") but no lower bound. So why not skip them all? They're optional, after all. - j_random_hacker
Well the actual definitions are much more complex, it's not just a distance or number thing, but it's affected by elevation, speed, vehicle weight, etc. One set of circumstances might need a route where each leg can be 250 miles, and another set of circumstances might require each leg can only be 80 miles long (and may not have a valid route because of this). - Cory Imdieke
Well, those actual definitions, or some simple approximation of them, need to be in your question, otherwise my trivial answer answers it! - j_random_hacker

1 Answers

3
votes

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.