Search
Sites and Affiliations
Leadership
Research and Applications
Major Accomplishments
Frequently Asked Questions
Knowledge and Technology Transfer
Calendar
Education and Outreach
Media Resources
Technical Reports and Publications
Parallel Computing Research - Our Quarterly Newsletter
Contact Information
CRPC Home Page

UniGuide Featured Site

Salesman's world tour

From: London Financial Times, June 11, 1998

A traveling salesmen has to visit a specified number of cities. What is his shortest route?

This famous conundrum is typical of a class of mathematical problems that come up repeatedly in sentence, engineering and management. Examples range from drilling holes in printed circuit boards to routing helicopters around oil rigs.

The point is that the problem becomes increasingly difficult to solve as the number of cities increases, along with the number of possible routes. Computers find it particularly hard. If a computer had to calculate the lengths of all possible routes between 100 cities and find the shortest route it would take billions of years for it to complete the calculation.

But researchers at Rice University in the US are finding new ways to tackle the problem using mathematical models and high performance computing. They have recently found a solution to the traveling salesman problem for 13,509 cities - a big advance on their previous record of 7,397 cities. which was set in 1994.