The traveling salesman problem

Companies use a problem known as the travelling salesman problem (TSP) to find the most efficient route to deliver mail, reduce fuel usage, and save money.

The problem describes a salesman that must make it to a set of points in the most efficient fashion. Solving this problem is NP-hard (computationally difficult) and is very taxing for smaller companies that do not have the necessary computational power. Oftentimes, instead of finding exact solutions, close approximations are used that cut down the computational time dramatically.

Dr. Cole Smith, Professor of Industrial and Systems Engineering at the University of Florida, and some of his students used an approximation technique to solve the “Close Enough Traveling Salesman Problem,” called such because they use circles instead of points.

In the classic problem, the salesman must visit every point in his route. In the modified problem, the salesman must only approach each point to a minimum distance. This changes the problem so that going to one area can actually put the salesman “close enough” to several points, making a visit to that area much more efficient than visiting each point individually.

The algorithm Smith developed uses an integer-programming based approach that splits the computation into 2 stages – order of points and then shortest paths between those points. By taking away some restrictions and letting the person move freely along the arc of each circle, the computational time is cut down dramatically and provides very close approximations. In tests, his algorithm had a higher bound and lower bound that where both approximately 1% off. Furthermore, tests showed that computational time was cut down by a factor of 10.

Different exact algorithms exist, but most of them require lots of CPU power. Oftentimes calculations involving 1,000 points or more can take about 20 years on a 500 MHz processor. The brute force method, which finds all possibilities, becomes inefficient at just 20 points. Other methods include: Branch and Bound (good for 40-60 points) and progressive improvement (up to 200 points).

As CPUs become more powerful and faster they will eventually be able to solve the TSP fairly quickly, but, for now, Smith’s algorithm is useful while limited by computational resources.