Computer Scientist Solves Old Salesman Problem

Now a computer scientist at Washington University in St. Louis has developed and tested an algorithm that might at least have made Loman's road traveled a little easier.

Weixiong Zhang, Ph. D., associate professor of computer science at Washington University, has developed an algorithm that attacks an old problem in the computing and business worlds known as the Traveling Salesman Problem (TSP). An algorithm is the backbone of computer operations; it is a step-wise mathematical formula, similar to a recipe, that solves a problem or reaches an otherwise desired end. The Traveling Salesman Problem is actually an umbrella term for a whole host of planning and scheduling problems, often involving routes; a classic one being a postman's route, for instance.

Zhang currently is working with an AT&T Bell Labs collaborator David S. Johnson, Ph.D., a pioneer and widely acknowledged leading expert in the area of computational complexity. They have applied the algorithm bearing Zhang's name to ten theoretical Traveling Salesman Problems and found it to be the best solution for half the problems, including one the AT&T Bell Labs is focusing on. The Zhang algorithm can be applied to a host of real-life problems.

One of the problems that AT&T Bell Labs is concerned with is one that involves the routes of payphone coin collectors. Zhang's algorithm, in the case of payphone coin collectors, maps a route through these different phone booths enabling the service person to avoid backtracking, one-way streets, or visiting the same booth twice, getting him back to the office at a reasonable time. In the business world, this saves a company time and expense.

Zhang and his collaborator tested his algorithm on four different classes of coin collecting routes, with routes of 100, 316, 1,000, and 3,162 different payphones. Compared with six other algorithms tested, the Zhang algorithm found the shortest, most efficient, or cost-effective route in each case. The algorithm is scalable and robust; it can compute for up to half million "nodes," in this case payphones, and it computed some routes in a matter of seconds.

Beyond the phone booth problem, the Zhang algorithm and the otherswere tested on a category called "No-wait flowshop problems." Picture an automobile paint shop with multiple stations for painting different portions of a car. The algorithm maps the most efficient route from start-to-finish. Also computed were routes for tiny disk drive readers inside a computer and routes for moving heavy oil-drilling equipment on a large field. In the case of the disk drive reader, a short route must be chosen to minimize the distances that the reader must "travel" to speed up data access operations. In the case of the drilling equipment, a short route means a short "travel" distance for the equipment. The algorithm also can be applied to what is called very large scale integration (VLSI). For such a problem, a route is needed that will connect all the minuscule components on a computer chip so that they can interface and function together.

Each of the TSPs tested are considered asymmetrical, which takes into account that the distance from place A to place B is not the same as that from B to A. Asymmetrical problems more closely reflect real-world situations. For instance, traveling on a freeway, you might be able to get on and reach a destination without paying a toll, but on the way back you might have to cross a bridge that has a toll. Thus, the cost in one direction is not the same as that going back. The Zhang algorithm factors in these real-life asymmetries. The results of the research were presented Jan. 5, 2001, at the Third Workshop on Algorithm Engineering and Experiments (Alenex 01), held at Washington, D.C. Some of the results also will be included as a chapter in a forthcoming book on the Traveling Salesman Problem. The work is partially funded by the National Science Foundation. "The Traveling Salesman Problem is one of the first computer science problems to be approached in the past century, and it is one of the first problems shown to be in the class called NP-Complete," saidZhang.

Loosely speaking, NP-Complete is a class of problems that are believed unsolvable within a reasonable amount of time in the worst case. Thus, approximation algorithms are very important for solving real-world problems such as the payphone coin collector problem. Zhang’s algorithm is considered to be one of the two best approximation algorithms for the Asymmetric Traveling Salesman Problem. The other is what is called the Kanellakis-Papdimitrious local search algorithm, named after two noted computer scientists.

Algorithms such as Zhang's are memory-efficient and meant to be embedded in hardware as a small but essential part of what's called mechanical electronic manufactured systems (MEMs). Zhang currently is working on algorithms that are meant to run on smart devices, with very small memory and limited power.

"Memory is a very big issue today," Zhang said. "With MEMs, you bundle the software so it's very tightly integrated with the hardware and each smart device, with just a few thousand bits of memory and small amounts of data, all connect with each other to build and run a larger application. Running time-and space-efficient algorithms, you build a big system out of these small smart devices." Zhang also is working on efficient search algorithms for analyzing biological data such as DNA, RNA and protein sequences. He is particularly interested in applying his skills in computer science and artificial intelligence to a relatively new but very active area called computational biology, or bioinformatics.

"If we say that information and computer technology were the leaders in the technology world in the last century, then biology will be the leader of this century," said Zhang. "The combination of information technology and biology will not only provide us the knowledge of life science, but also help to cure diseases and make our lives wonderful to live."