Divide and Conquer
One approach that many fleet companies take is to divide the stops into smaller groups and then build routes for the groups separately. Street networks often subdivide into regions naturally and that makes dividing up the stops easier. For example, a river, canyon, or highway may divide a city so roads cross over it at only a few places. It would usually be inefficient to make a route that jumps back and forth across the divide, so it probably makes sense to divide the stops into two groups, one for each side of the obstacle, and then plan routes for the groups separately.
Many companies carefully plan out delivery areas and then assign all the stops in a particular area to a single driver. That not only lets them plan routes one area at a time, but it also gives drivers time to become familiar with an area so they learn the shortcuts and don't get lost as often.
While dividing stops into delivery areas helps, it still leaves you short of a full solution. Suppose delivery people drive four-hour shifts and can deliver about four packages per hour. Because that's 16 packages per shift, it would be nice if you could solve at least 16-stop TSP problems. Even with the super computer described earlier flashing through 1 billion solutions per second, it would take you almost 6 hours to solve this problem exhaustively.
This still isn't good enough, particularly if deliveries are faster than four per hour. Dividing the stops helps but you need more heuristics to avoid an exhaustive search.
The Random Approach
A very straightforward approach to solving TSP is to simply pick a bunch of random orderings for the stops and then see which one is best. This may seem like a stupid approach. After all, the chances of guessing the best solution for a 30-stop TSP are almost indistinguishable from zeroalmost as bad as those of winning the lottery. However, picking random solutions is very quick and easy. If you examine a few thousand random solutions, you almost certainly won't find the best solution but you may find one that's pretty good.
|Figure 1. Random Route Strategy: Testing random routes is quick but doesn't always lead to great solutions.|
Testing random solutions is quick and easy but it's, well, random. There's no notion of working towards a better solution. You just make a bunch of haphazard guesses and see which one is best.
Figure 1 shows the downloadable TSP example program that accompanies this article (in both Visual Basic and C# versions) displaying a randomly generated solution to a 35-stop TSP. The program generated 10,000 random routes and picked the one shown in Figure 1 as the best. It's not a great solutionafter a few minutes with pencil and paper, you could probably improve on this route considerably.
Instead of just making a bunch of random solutions, you improve this algorithm significantly if you try to improve the random solution. Rather than testing a random guess and moving on to the next one, you try making small changes to the random guess to see if such changes improve it.
There are several ways you can try to improve a solution. One of the easiest is to randomly pick two stops, swap them, and see if that made the route better. If the route is better, you keep the change and try to make other improvements. If the swap didn't improve the solution, you move the stops back to their original positions and try again with two other stops.
|Figure 2. Improved Random Strategy: Improved random solutions often give better results than purely random solutions.|
You can continue trying random improvements for either a certain number of trials or until you've tried some reasonable number of random swaps without generating any improvement. For example, you might try random swaps until you make 100 swaps in a row without any improvement. At that point it's getting hard to find improvements, so you can record the best solution so far and move on.
Figure 2 shows a solution to a 35-stop TSP that uses the technique of improving random solutions. It generated a single random solution and then tried to improve it until it failed to make any improvements 10,000 times in a row.
The result shown in Figure 2 is much better than the one shown in Figure 1, although you can probably spot a few places for improvement.
The problem with this approach is that it sometimes gets stuck with a route that is not perfect but that cannot be improved by simply swapping two stops. The program might need to rearrange three, four, or even more stops to find any improvement.
One way to make this approach more robust is to repeat it many times. Pick a random solution and improve it for a while. Then start over with another random solution and improve it. Repeat the process, picking and improving a few thousand random solutions, until you decide you've found a good enough solution.
Another approach is to specifically try other kinds of improvement. Instead of just swapping two stops, you can try other operations for improving the initial random solution.