A very similar problem to the Traveling Salesperson problem is finding the best route. And this one you most likely have directly encountered.
Have you ever tried to find a way to a destination using more than one map finding software? Maybe you used Google Maps, MapQuest, and your car’s GPS, and they all gave you a different answer!
Determining the “best” path is an interesting form of search when you try to find a path, instead of a specific value. So why is a “best” path so hard to come up with? Let’s look at a couple of issues that might cause different devices/websites to provide different results.
First, they may not all know about the same roads. Some roads may be shown as closed, or not exist in one system, while they appear fine in another. Second, you need to know are you looking for faster route by posted speed, or by average speed (something not all systems would have info on), or are they assuming best posted speed.
Are you looking to avoid highways, tollroads, or rural roads? Or maybe these options are set as a default in some systems that you do not even know about. Does one system know about a recent accident that it’s trying to help you avoid, or maybe help you by only suggesting right hand turns because that’s more efficient in some cases? (I had a GPS that only liked right hand turns, even if it took you a mile out of the way to find the series of right turns to keep you from making a left turn.)
Even the order of which the roads are looked at will change the route you are presented, even if the total drive time and/or distance is the same.
As you can see, there are a lot of variables to consider, and how they are handled will potentially lead you to take different routes.
The Best vs. “Good Enough”
One of the considerations we must give to any algorithm is when is it good enough to work with the given results. What if, for example, we could have a route that would have two miles off a 1,000 mile trip, but it took us another 30 minutes to calculate? Would it be worth it?
Some researchers followed firefighters around to see how they made decisions. They assumed that the firefighters would always pick the best way to fight a given fire. What they found was that they found a way that worked, and then used it – sacrificing the “best” way for one that worked right now.
Sometimes we need to consider that with our solutions, and the Traveling Salesman is a perfect example. After so many iterations, after so many tries, at some point we have to assume that our answer is good enough and stop trying.
Stopping allows us to move into action with sending our sales person out on the road. It may not be the best method, but if you’ve got thousands of stops a year and tens of thousands of potential vertices to get there, at some point, you have to just go for it.
When and where that solution will be is unknown. Maybe it’s after you find the third path that doesn’t improve your time. Maybe it’s after running for 30 minutes. The criteria is up to you, but failing to track it can generate a system that seemingly never returns an answer as it always is searching and that does no one any good.
So know when good enough really is, and how to produce an answer. And if you can learn something from this algorithm, then maybe that is it.
Finding the Best Route was originally found on Access 2 Learn
