Traveling salesman problem
The Traveling Salesman Problem (TSP) is a classic optimization challenge where a salesperson aims to visit a set number of cities, starting and ending at their hometown, while minimizing travel time. The problem becomes increasingly complex with a growing number of cities, as the potential routes increase exponentially, making a brute-force approach impractical. For example, with 30 cities, the number of possible routes is staggering, leading to impossibly long computation times—even surpassing the age of the universe for exhaustive searches.
The TSP serves as a foundational model for various real-world applications, such as optimizing garbage truck routes, sequencing robot motions, and arranging genetic markers. It is categorized as an NP-hard problem, meaning there is currently no known polynomial-time solution that works efficiently for all instances of the problem. Although researchers have developed algorithms that outperform brute force methods and have solved instances with up to 85,900 cities, the quest for a universally efficient algorithm continues. Additionally, approximation algorithms have been created to provide near-optimal solutions within a reasonable timeframe, highlighting the TSP's significance in computer science and operations research.
Traveling salesman problem
Summary: The traveling salesman problem is a notable applied mathematics problem that is simply constructed and may be unsolvable.
Imagine a salesperson that needs to travel to 30 cities. The salesperson wants to begin in his or her hometown, visit every city exactly once, and return to the hometown. In what sequence should the salesperson visit the cities in order to minimize the total amount of traveling time on the road between cities? The significance of the traveling salesman problem (TSP) lies in the fact that many other problems can be translated into a traveling salesman formulation and that a brute force check-all-the-possibilities approach will take prohibitively long—even for moderately sized problems (like the example) and with the use of fast computers.
Many problems can be translated to the TSP. The travel time between cities can be replaced by distance, cost, or other measures. Hence, in essence, this problem captures many sequencing problems where a number of tasks have to be sequenced and the costs can be modeled appropriately. Problems as diverse as optimizing the routes of garbage trucks, planning the sequence of motions performed by a robot, and ordering genetic markers on a chromosome have been modeled by the TSP.
Solving the TSP
Why is solving the TSP hard? If one decides to solve the problem by checking all the possibilities and then choosing the best one, then the sheer number of possibilities will make the problem impossible to solve. For example, with 30 cities and starting at a hometown, initially there are 29 cities to choose as a first destination. Regardless of the first choice, there are 28 cities to choose from next and so on. The total number of possible ways to start from a hometown, traverse each of the 30 cities exactly once and return to the hometown is
possibilities.
Even if a computer checked a million possibilities per second, checking all the possibilities would take more than 200,000,000,000,000,000 years—much longer than the age of the universe. Making the computer twice or 10 times faster still will not be enough to make the problem worth attempting.
Solution Through Algorithms
Could there be clever algorithms that solve the TSP faster? The TSP is among the problems that computer scientists call NP-hard. Given any algorithm for solving the TSP, certainly the number of steps needed by the algorithm grows as the size of the problem—namely the number of the cities—grows. If the number of steps in an algorithm as a function of the size of the problem is a polynomial, then it is generally believed that the problem is tractable. In other words, if there is one such polynomial time algorithm, then one can hope to find other more efficient ones and be able to solve even large-sized problems efficiently. At the start of the twenty-first century, it is not known whether the TSP has such a polynomial time algorithm. But it is known that if there is such an algorithm, then there is also efficient algorithms for a host of other problems of interest to computer scientists. For many years, researchers have looked for such algorithms and have not been able to find one, and the strong prevailing opinion is that no such algorithm exists (this is the famous P≠NP problem).
Even though the TSP is a difficult problem to solve in general, progress has been made in developing algorithms that do much better than the brute force method. In fact, very large instances—for example, one with 85,900 cities—of the TSP have been solved exactly. On another front, many approximation algorithms have been devised. These algorithms do not aim to find the absolute best solution but rather find a solution that is close to the best one. A simple approximation algorithm using minimum spanning trees, for example, can find a solution that is guaranteed to be no worse than twice the optimal solution. More sophisticated algorithms can find a solution within a few percentages of the optimal solution for a problem with the number of cities in the millions.
Bibliography
Applegate, David L., Robert E. Bixby, Va ek Chvátal, and William J. Cook. The Traveling Salesman Problem: A Computational Study. Princeton, NJ: Princeton University Press, 2006.
Gutin, Gregory, and Abraham P. Punnen. The Traveling Salesman Problem and its Variations. Dordrecht, The Netherlands: Kluwer Academic Publishers, 2002.