Making Smarter Improvements
|Figure 3. Two-opt Strategy: The Two-opt heuristic looks for improvements by swapping pairs of links.|
The random improvement heuristic picks two stops in the route and swaps them to see if it can make an improvement. The Two-opt heuristic randomly picks two links between stops. It removes those links and replaces them with others that keep the route connected and checks whether the change is an improvement.
shows an initial route and an improved version found by Two-opt. The 2-6
links in red on the left have been removed and replaced by the 2-3
links in blue on the right. Notice also that the path 6-5-4-3
on the left was reversed to 3-4-5-6
on the right to keep the route valid.
|Figure 4. Comparing Strategies: Different heuristics may produce dramatically different results.|
You can make other heuristics that consider rearranging three, four, or more stops or links but the more complicated the heuristic is, the harder it is to implement and debug. Often it's just about as effective to run more trials starting from different random solutions as it is to build a much more complex heuristic.
shows the TSP example program displaying results for several different heuristics on a 35-stop TSP. The Random heuristic tested 10,000 random solutions in about 0.09 seconds and found one where the total length of the links in the solution was 3,345.
The Random Improvement heuristic generated a single solution and tried to improve it by making random swaps until it found no improvements in 10,000 trials in a row. This example took 0.02 seconds and examined 13,917 possible improvements. This test examined almost 40 percent more possible solutions than the Random heuristic did but in only about a quarter as much time. It was faster because it did not need to pick a completely new solution each time it looked for improvements. Instead it just swapped two stops on the route and checked the result.
The Four-opt heuristic does almost the same thing that Random Improvement does. It picks two stops and considers swapping them. But rather than actually performing the swap and then calculating the new solution's cost, this program determines how much it would change the route's cost to rearrange the four links leading into and out of the two stops, then actually makes the swap only if it will be profitable. In this test, Random Improvement found a slightly better solution than Four-opt did in about the same amount of time. In general these algorithms are pretty similar, although Four-opt may save some time in large problems because it doesn't need to recalculate the whole solution's cost at each step.
The Two-opt heuristic tries swapping links as described earlier. In this example it found a solution that is significantly better than the ones found by the previous methods.
Finally, the Mix heuristic uses the Four-opt and Two-opt heuristics many times until neither technique can find an improvement in 100 trials. You can see that this technique performed a lot more trials (more than 2 million versus around 10,000) and took longer, although it did find a slightly better solution.
|Figure 5. Brute Force: Exhaustive search finds the best possible result but can be very slow.|
How good is this solution? I don't know and I never will. It seems like a pretty good solution but the only way to be certain is to perform an exhaustive search. Until quantum computers appear, or some other science-fiction-like technology comes along, the sun would be a cold dark cinder before my
computer could check all of the possible solutions.
shows one final example displaying the results of an exhaustive search for a 10-stop TSP. The exhaustive search took about .3 seconds to examine 3.6 million possible solutions. If you look closely, you'll see that the more advanced heuristics produced increasingly better results. In this example, the Mix heuristic found the best possible solution, although in general any one of the heuristics might get lucky and find a perfect solutionor might be unlucky and always find bad solutions.
How long you let a heuristic run is for you to decide. You could let the heuristic run indefinitely, constantly displaying the best result it has found so far, until you decide you need to actually drive the route and get some work done. It might be nice to wait for the perfect solution, but if your boss is anything like mine, you won't be able to wait billions of years for a solution.
Even if you don't own a huge fleet, these savings can add up. I drive about 15,000 miles per year. If I can reduce this by 10 percent by using shorter routes, then I can save about 1,500 miles. If I get 30 miles per gallon (and most people don't do that well), that would save about 50 gallons per year. At today's prices that's nothing to sneeze at.