Say I have some errands to run. For example, this afternoon, I need to visit any Wells Fargo branch, and then I want to visit any Safeway for some groceries, and on my way home I want to pick up some KFC. Each of those businesses has at least 2 locations and then some in my area, in different directions from my house. I don’t care which of the locations I go to; I just want the most efficient route starting and ending at my home. Is there a way to make Google calculate that route or some other map site or app that can do it?
Google Maps lets you search for the nearest chain location to given starting point. And it calculates the shortest path for multi-stop trips. So it has the capability make the itinerary for you, but I don’t think it actually has that feature. You’d have to do it manually yourself. For example, you can see which Safeway is closest to your house, and then find which Wells Fargo is closest to that Safeway. Or try it vice versa and see if the total trip time differs. Then you could set up a multi-stop trip in Google Maps to calculate the shortest route to those destinations. So I think you can get the result you’re looking for, it just takes more work on your part than it really should.
Note that there’s an exponentially growing number of paths to consider as more franchises are added to the search list. But is the exponential inherent, in some sense? Yes.
There’s a simple reduction from the Hamiltonian Path problem to this*. Hence the problem is NP-Hard. (I.e., there is no known efficient solution and many believe that there cannot be one.)
So, here be dragons.
But, you might know about heuristics and wonder if there is an efficient approximately optimal solution. E.g., Bin Packing is NP-hard but there are quite simple heuristics to get solutions that are within a guaranteed small percentage of optimal.
Again, there’s a gotcha. This problem is incredibly sensitive to initial conditions. A small change in location of one place and a significantly different path is selected.
E.g., the town is just a “Y” and you’re driving up the base towards the fork. The two branches are identical in relative layout of all the franchises you want to visit except one. Which is located just a bit up one branch. So that’s clearly the best one. But move that franchise slightly to up the other branch and your best route changes completely.
When small changes like this result in big changes in results, heuristics don’t generally do at all well.
- Note that you can make the map/graph fairly mundane. Planar, two-way streets, 3-way intersections, etc. There’s nothing really bizarre about them.
My first thought was also that this is similar to the Traveling Salesman problem and is therefore NP-hard. But probably most real-world examples would be something like the OP, where the total number of nodes is on the order of 10 or so, so an exhaustive search would be feasible even if it wouldn’t be in the case of a hundred or more nodes.
Right, even an NP-hard problem can be fairly easy, if n is small.