Weixiong Zhang, Ph.D., associate professor of computer science, applied an algorithm to an old computing and business nemesis called the Traveling Salesman Problem. One of the TSPs involved finding the best route for pay phone coin collectors.
By Tony Fitzpatrick
It was a combination of things, physical and metaphysical, that killed Arthur Miller's traveling salesman, Willie Loman.
Now a University computer scientist has developed and tested an algorithm that might at least have made Loman's roads traveled a little easier. Weixiong Zhang, Ph.D., associate professor of computer science, has developed an algorithm that attacks an old problem in the computing and business worlds known as the Traveling Salesman Problem (TSP).
Weixiong Zhang, Ph.D., associate professor of computer science, applied an algorithm to an old computing and business nemesis called the Traveling Salesman Problem. One of the TSPs involved finding the best route for pay phone coin collectors. |
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. TSP 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 is currently working with AT&T Bell Labs collaborator David S. Johnson, Ph.D., a leading expert in the area of computational complexity. They have applied the algorithm bearing Zhang's name to 10 theoretical TSPs and found it to be the best solution for half.
One of the problems that AT&T Bell Labs is concerned with involves the routes of pay phone coin collectors. In this case, Zhang's algorithm maps a route through these different phone booths that enables the telephone service person to avoid backtracking, one-way streets, or visiting the same booth twice, and gets him back to the office at a reasonable time. In the business world, this saves a company time and money.
Beyond the phone booth problem, the Zhang algorithm and the others were 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.
Zhang and Johnson tested the algorithm on four different classes of flowshop routes, with routes of 100, 316, 1,000, and 3,162 different stations. Compared with six other algorithms tested, the Zhang algorithm found the shortest, most cost-effective route in each case. The algorithm is scalable and robust; it can compute for up to half-million "nodes," in this case stations, and it computed some routes in a matter of seconds.
Also computed were routes for tiny disk-drive readers inside a computer and routes for moving heavy drilling machines on a large oil 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 machines, 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 at the Third Workshop on Algorithm Engineering and Experiments (Alenex 01), held in Washington, D.C. Some of the results also will be included as a chapter in a forthcoming book on TSP. The work is partially funded by the National Science Foundation.
"The TSP 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," Zhang said.
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 pay phone coin collector puzzle. Zhang's algorithm is considered to be one of the two best approximation algorithms for the Asymmetric Traveling Salesman Problem. The other 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 is currently working on algorithms that are meant to run on smart devices, with very small memory and limited power.
"Memory is a 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 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," Zhang said.
| Medical News |
Washington People |
Calendar | More Campus News |
| WU Home Page |
Email Us! |
Record Staff |
Hilltop Jobs Medical Jobs |