Featured Research

from universities, journals, and other organizations

Computer Scientist Solves Old Salesman Problem

Date:
January 16, 2001
Source:
Washington University In St. Louis
Summary:
It was a combination of things, physical and metaphysical, that killed Arthur Miller's traveling salesman Willie Loman. 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.

It was a combination of things, physical and metaphysical, that killed Arthur Miller's traveling salesman Willie Loman.

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."


Story Source:

The above story is based on materials provided by Washington University In St. Louis. Note: Materials may be edited for content and length.


Cite This Page:

Washington University In St. Louis. "Computer Scientist Solves Old Salesman Problem." ScienceDaily. ScienceDaily, 16 January 2001. <www.sciencedaily.com/releases/2001/01/010116075125.htm>.
Washington University In St. Louis. (2001, January 16). Computer Scientist Solves Old Salesman Problem. ScienceDaily. Retrieved October 1, 2014 from www.sciencedaily.com/releases/2001/01/010116075125.htm
Washington University In St. Louis. "Computer Scientist Solves Old Salesman Problem." ScienceDaily. www.sciencedaily.com/releases/2001/01/010116075125.htm (accessed October 1, 2014).

Share This



More Computers & Math News

Wednesday, October 1, 2014

Featured Research

from universities, journals, and other organizations


Featured Videos

from AP, Reuters, AFP, and other news services

Mozilla Bets On Software To Sell Its Chromecast Competitor

Mozilla Bets On Software To Sell Its Chromecast Competitor

Newsy (Oct. 1, 2014) Mozilla's Matchstick streaming device is entering a crowded market. The company is banking on open-source software to rise above the competition. Video provided by Newsy
Powered by NewsLook.com
App Teaches Kindergarteners to Code

App Teaches Kindergarteners to Code

AP (Oct. 1, 2014) They can't all read yet, but soon kindergarteners may be able to create basic computer code. Researchers in Massachusetts developed an app that teaches young kids a simple computer programming language. (Oct. 1) Video provided by AP
Powered by NewsLook.com
Microsoft Goes For Familiarity Over Novelty In Windows 10

Microsoft Goes For Familiarity Over Novelty In Windows 10

Newsy (Sep. 30, 2014) At a special event in San Francisco, Microsoft introduced its latest operating system, Windows 10, which combines key features from earlier versions. Video provided by Newsy
Powered by NewsLook.com
French Apple Fans Discover the Apple Watch

French Apple Fans Discover the Apple Watch

AFP (Sep. 30, 2014) Apple fans in France discover the latest toy, the Apple Watch. The watch comes in two sizes and an array of interchangeable, fashionable wrist straps. Duration: 00:42 Video provided by AFP
Powered by NewsLook.com

Search ScienceDaily

Number of stories in archives: 140,361

Find with keyword(s):
Enter a keyword or phrase to search ScienceDaily for related topics and research stories.

Save/Print:
Share:

Breaking News:

Strange & Offbeat Stories


Space & Time

Matter & Energy

Computers & Math

In Other News

... from NewsDaily.com

Science News

Health News

Environment News

Technology News



Save/Print:
Share:

Free Subscriptions


Get the latest science news with ScienceDaily's free email newsletters, updated daily and weekly. Or view hourly updated newsfeeds in your RSS reader:

Get Social & Mobile


Keep up to date with the latest news from ScienceDaily via social networks and mobile apps:

Have Feedback?


Tell us what you think of ScienceDaily -- we welcome both positive and negative comments. Have any problems using the site? Questions?
Mobile: iPhone Android Web
Follow: Facebook Twitter Google+
Subscribe: RSS Feeds Email Newsletters
Latest Headlines Health & Medicine Mind & Brain Space & Time Matter & Energy Computers & Math Plants & Animals Earth & Climate Fossils & Ruins