Why sales reps pose a hard problem: What is the shortest route for travelling sales reps to visit all their clients? Mathematicians had hoped to find a complete solution, but they may have to settle for less
- 12 December 1992
- From New Scientist Print Edition. Subscribe and get 4 free issues.
What do a manufacturer of printed circuit boards, a scientist studying the structure of crystals and a sales representative have in common? The scientist has to move the crystal into thousands of different orientations to measure the intensity of X-ray diffraction. The manufacturer has to move a drill around the board to make thousands of holes. And the sales rep has to visit scores of cities. If they want to do these things in the most economical way, all three have to solve a puzzle known to mathematicians as the travelling salesman problem.
The problem first appeared in the US during the 1930s in the newly born discipline - later called operations research - which uses mathematical analysis to solve problems of optimisation. The original version is about a sales rep who has to visit a number of cities. If the rep begins at one city and visits each of the others once before returning to the starting point, in which order should the cities be visited so that the total distance travelled is as short as possible? In the manufacture of a circuit board, the cities represent the holes to be drilled. In measuring X-ray diffraction, the cities correspond to the orientations of the crystal, and the distances correspond to the times needed to reposition the diffractometer between two measurements.
The problem may be simple to pose but it has turned out to be very difficult to solve. Despite the efforts of several generations of mathematicians and computer scientists, no one has found a complete solution. The distinction between a theoretical and a practical solution is crucial here, as is the difference between solving the whole problem and solving an instance of the problem. For example,
How about adding the city-to-city distances for each possible tour and then picking the tour with the smallest length? This method will do when there are only a few cities, but it quickly becomes useless as the number of cities increases. With 30 cities, for example, the number of possible tours is approximately 2 x 10
So the challenge is to construct an explicit set of step-by-step procedures, an algorithm, that will always give an answer for however many cities are specified. And it has to be 'efficient' - meaning that there must be a reasonable relationship between the number of cities and the time the computer takes to find a solution to the problem.
In 1954, three mathematicians at Rand Corporation in Santa Monica, California, solved the first large-scale travelling salesman problem. George Dantzig, Delbert Fulkerson and Selmer Johnson applied techniques and algorithms borrowed from the new discipline of linear programming - a technique of mathematical modelling used to help in making quantitative decisions. The Rand mathematicians represented each possible tour of 49 real cities (Washington DC and 48 other large American cities) as a different vertex of a multidimensional polygon. Then the problem of finding the shortest tour became that of finding the vertex where a linear function (the 'tour length' function) reaches its minimum value.
Into four-figure problems
Building on this initial success, other mathematicians developed improved algorithms for the travelling salesman problem. In 1980, Manfred Padberg of the Leonard N. Stern School of Business at New York University and Harlan Crowder of IBM's Thomas J. Watson Research Center in Yorktown Heights, New York, employed linear programming techniques to solve several travelling salesman problems, the largest of which involved a tour of 318 cities.
Six years later, Padberg and Giovanni Rinaldi of the Institute for Systems Analysis, part of the Italian National Research Organisation in Rome, succeeded in solving a 2392-city problem for the electronics company Tektronics, which wanted to optimise the manufacture of a printed circuit board. This time the researchers used an algorithm based on a mathematical theory developed in the 1970s by the German mathematician Martin Grotschel and by Padberg himself. A Control Data Cyber-205 computer initially took 27 hours to solve the problem, but Padberg and Rinaldi improved the algorithm and reduced the running time to less than 3 hours. However, the same computer using the same algorithm took twice as long to solve a problem involving only 532 cities - an indication that running time depends on the distribution as well as the number of cities.
In April this year, a team of American mathematicians took the lead with an optimal solution for a tour of 3038 cities (see New Scientist, Science, 27 June). David Applegate of AT&T Bell Laboratories in New Jersey, Robert Bixby of Rice University, Vasek Chvatal of Rutgers University and William Cook of Bellcore in New Jersey used parallel computing on 30 Sparc2 stations to work out the route and to prove that it is indeed optimal. The program was run mostly at night when the computers would otherwise have been idle. An estimated 18 months of computer time was needed to complete the calculation.
Padberg sees no barrier to the size of real-life travelling salesman problems that can be solved, other than the limitations of current technology. 'Parallelisation and vectorisation of the computation,' he claims, 'are the most obvious avenues to take if one wants to increase solvable problem size.' Nevertheless, a practical solution to the whole problem remains elusive.
One of the attractions of the travelling salesman problem to mathematicians is that it is typical of a large class of difficult, and as yet unsolved, optimisation problems. They hope that if they can construct an efficient algorithm for the travelling salesman problem, they could apply it to other problems in the class. Central to this is a new branch of mathematics known as complexity theory, which studies not just algorithms but also how efficient they are.
EASY IS QUICK TO SOLVE
Mathematicians use the performance of algorithms to distinguish between 'easy' and 'hard' problems. To see whether a problem is easy or hard, mathematicians look at the formula which relates the time an algorithm takes to the number of objects in the problem to be solved. In general, the larger the number (n) of objects, the longer the time the algorithm will take to find the solution.
If running time grows as a constant multiple of a fixed power of n, such as
A HARD CASE
Mathematicians classify all problems that can be solved by a polynomial-time algorithm as class P. There are good reasons, both theoretical and empirical, for choosing a polynomial-time algorithm as the mathematical equivalent of a practical algorithm - that is, one that gives an answer in a reasonable time.
The travelling salesman problem is hard because no one has found an algorithm that computes the shortest tour of n cities in polynomial time. The running times for the best algorithms known for solving the travelling salesman and other hard optimisation problems usually grow exponentially, and are therefore useless for all practical purposes. If the solution of a problem of size
A second class of problems in complexity theory is called nondeterministic polynomial, or NP. These are problems that can be solved by a nondeterministic algorithm in polynomial time. Normally, the term algorithm refers to a deterministic algorithm; one that consists of a sequence of steps, so that computation proceeds in a linear fashion. In nondeterministic algorithms, instructions can take the form 'Go to both A and B', and as a result the computation will branch like a tree into a number of parallel computations. A nondeterministic algorithm can be thought of as operating in two stages. In the first, the algorithm 'guesses' a possible answer to the problem; the second stage then serves to verify whether the guess is a solution.
The NP class contains all the problems in P because a deterministic algorithm in effect simply bypasses the guessing stage. The central question is whether there is anything in NP that is not in P. In other words, no one knows whether P
Strictly speaking, the labels P and NP apply only to decision problems, or problems requiring a yes or no answer. But almost any problem may be expressed as a decision problem, so the distinction is often blurred. In NP, the hard problems may be loosely described as those whose solutions may be hard to find but are easy to check. For example, the travelling salesman problem is in NP because we can ask 'Is there a tour of length less than k?' If the answer is yes and a particular tour t is offered as evidence, it is then easy to check that the length of t is indeed less than k.
In 1971, Stephen Cook of the University of Toronto showed that a particular decision problem in formal logic, known as the satisfiability problem, could qualify as the 'hardest' problem in the class NP. This is because the satisfiability problem has the property that for any problem X in NP, there is a polynomial-time algorithm that transforms X into a special case of the satisfiability problem S. Problems such as S are called 'NP-complete', and Cook's finding implies that any polynomial-time solution of S can be converted into a polynomial-time solution of X. In other words, if S is in class P, so is every other problem in NP and there are no hard problems at all. Since then, many well-known hard problems in the class NP have been proved to be NP-complete including - you guessed it - the travelling salesman problem. The bottom line is that if there are such things as hard problems, the travelling salesman puzzle must be one of them.
TAKING THE APPROXIMATE ROUTE
In the meanwhile, the record-breaking algorithm that produced a solution for 3038 cities is still a long way away from the needs of chip manufacturers, where applications may require the drilling of as many as 1.2 million holes. In many practical applications of the travelling salesman problem, however, a tour that is nearly optimal may be as good as an exact solution. In certain processes, for instance, where a laser must move to 100 000 different points on a chip, a near-optimal path can significantly reduce expensive processing time. Cost may be another factor in opting for approximate solutions.
According to David Johnson, a mathematician at Bell Labs: 'Five hours on a multimillion dollar computer for an optimal solution may not be cost-effective if one can get within a few per cent in seconds on a PC.' Johnson and his colleague Jon Bentley have become experts in the art of finding approximate solutions for the travelling salesman problem. They firmly believe that finding optimal tours for large instances is just not feasible. Their approach involves designing and experimenting with heuristics: strategies or sets of rules designed to find near-optimal tours rather than exact solutions.
Some of these heuristics gradually build up a tour out of shorter paths. A simple example is the nearest-neighbour heuristic: start at an arbitrarily chosen city; choose as the second city the one closest to the first; choose as the third city the one closest to the second and not already visited, and so on. Finally, when you have visited every city, complete the tour by returning to the initial city.
A popular type of heuristic, called 'local optimisation', repeatedly improves an approximate solution by making local changes to a previously constructed tour. An example of this technique is the 2-Opt heuristic. Figure 2 illustrates a single 2-Opt swap where replacing the edges AB and CD by AC and BD produces a shorter tour. The 2-Opt heuristic applies such swaps to a tour until no further swaps can be made that would reduce the tour's length. For example, in the 32-city tour shown in Figure 3, the 2-Optimal tour is obtained after six swaps.
A much more sophisticated approach, known as the Lin-Kernighan algorithm, is the basis of a program created by Bentley and Johnson in collaboration with Lyne McGeoch of Amherst College in Massachusetts. The program can compute very good approximations in a relatively short time. When run on a fast processor with 256 megabytes of main memory, it takes less than 3 hours to give an answer that is within 1.5 per cent of the shortest tour of one million 'cities' - actually points on the unit square that the computer has randomly generated.
Physics and biology serve as models for two variants of local optimisation that have been tried on the travelling salesman problem (see 'Natural solutions give their best', New Scientist, 14 April 1990). The technique called simulated annealing is reasonably effective but slow. Inspired by the behaviour of crystals forming in a cooling metal, it involves exchanging two randomly chosen links in the tour to improve an approximate solution. Genetic algorithms are based on a kind of 'mating' of solutions selected from a population of possible solutions. The process is repeated for many 'generations' in a way that mimics natural selection, with randomness once more being a key element. Again, the technique gives mixed results.
Then there are neural networks. These are systems that model the massive interconnections of neurons in the human brain and have the ability to modify themselves by a process similar to learning. Artificial neural networks can be simulated by a computer program or actually built into, for example, a silicon chip. Could this branch of artificial intelligence hold the key to the solution of the travelling salesman problem?
Johnson says that he has never seen an impressive application of neural networks to the travelling salesman problem, or to any of the other hard optimisation problems. 'The hardware requirements increase rapidly,' he adds, 'and neural network models do not scale very well. As problems get bigger, they typically do not produce feasible solutions, much less good ones.' Johnson does not expect performance to improve even with the development of neural computers, where the networks are built into the hardware and not just simulated.
HARD PROBLEMS STAY HARD
Mathematicians will not consider the travelling salesman problem as solved until they find an efficient algorithm that can calculate the optimal tour for instances of arbitrary large size. But for practical applications of the problem, an approximate solution is the next best thing. For some hard problems (such as the bin packing problem of how best to fit objects into bins given their respective sizes), it is possible to construct polynomial-time algorithms that provide approximate solutions to any degree of accuracy desired. But a few months ago, Sanjeev Arora and Madhu Sudan of the University of California at Berkeley, Rajeev Motwani of Stanford University, and Carsten Lund and Mario Szegedy of Bell Labs found a powerful property of the class NP that had an unexpected connection with the travelling salesman and other difficult problems. Their result implies that if P
There is much empirical evidence but no conclusive proof that the travelling salesman problem is intractable. Mathematicians may still cling to the hope of finding an efficient solution - or accept the fact that their algorithms cannot help all travelling reps find the most economical route.
Arturo Sangalli is in the department of mathematics at Champlain Regional College, Lennoxville, Quebec.
Further reading: The Traveling Salesman Problem, edited by E. L. Lawler et al, John Wiley & Sons, 1985.