Because the point-to-point is still the same problem, purely from a technical standpoint. How to find an optimal route between two nodes in an arbitrary graph. I merely noted this, somewhat whimsically, because an earlier post said it was a solved problem, when of course its famous as not have any known general NP solution. Then everyone got all excited, as people tend to do in forums I guess.
And of course, in practical terms, nav systems solve the problem by favoring different classes of roads, which vastly prunes the graph and allows it to find a nearly optimal route in very little time.
It is not the same problem, and the difference is what makes navigation systems that work quickly possible (most modern nav do not blow up when you enter a coast to coast tip).
TSP is defined: "
Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" Note that it ends where it starts, which kinda makes it not useful for navigation, but of course this can be worked around. This problem is what is called NP-complete which in worst case could mean exponentially increased compute time. Entering Los Angeles to Boston with an enormous graph of connecting road segments in between will not allow a route to be found using TSP! It doesn't even solve this problem.
Navigation problems, as encountered in journey planning, is related to the "shortest path problem" and this is NOT the same as the TSP. Computing an (optimal) path through a graph from one node to another (A to B) where optimal is defined in various ways (optimize speed, minimize distance, minimize elevation changes, avoid toll roads, what have you) is often done using the A* algorithm. This algorithm
is a "solved" problem.
Navigations systems almost always use the A* algorithm (or close variation) which applies a heuristic to drastically prune the search space and this speeds up the computation. It all centers on a somewhat accurate calculation of the cost of a segment between junctions, and the heuristic. Further optimizations consist when you notice that the only place to have route variations are intersections, and junctions (exits simply lead to these). The cost (time, speed, fuel) of each segment between junctions needs to be computed along all the road segments along the way (curves, segments with different speed etc.), but the A* itself only needs to be done from junction to junction.
Charging does not really complicate A to B planning because one can either reach B without charging or not. If one can, we're done. If not the heuristic in the A* algorithm needs to be adjusted so that any route choice that leads away from an SC before we have enough charge to reach B becomes prohibitively expensive. This is, however, a simplification as there may be multiple SC choices reasonable available between A and B.
The cost factor, in Tesla's case also involves estimate SoC on arrival (at SC and at B) and optimal charging durations based on SC characteristics and SoC. If there is a further destination C it may be that charging again, just before B (even though not needed to reach B, and not even to reach C) is better than a little while after B but before C. While this further complicates the search space (graph), the approach remains essentially the same.
Dynamic detours (traffic info) are basically the same problem. During the drive the cost is constantly computed. Segments with traffic problems become more expensive and alternatives might now be discovered...
Waypoints (points on the way), as most people regard them, are simply expressing a desire to visit C, D and E (in that order) after leaving A, but before reaching B. Other than effects on charging decisions, one can run the A* separately on A>C,C>D,D>E, and E>B. This is efficient and results in the way most people would use them. If users order A,C,D,E,B in some bizarre way, this approach will not hesitate to visit places or road segments twice if that makes sense. Although TSP does not solve this problem, it would not visit things twice.
The UI for entering/managing waypoints is a separate problem that has many solutions.
