You can get there from here
Research team finds record solution to classic math problem
From: Houston Chronicle, June 28, 1998
By Todd Ackerman, Staff
Every day during the school year in a rural county in upstate New York, 20 buses make roughly 800 stops
to pick up students and take them to school.
Allan Weaver, a retired engineer who does volunteer work for the Southern Cayuga Central School
District, says the intuition and experience that has determined the routes have worked pretty well over the
years.
"But I'm the type who's always looking for objective solutions," he says. So Weaver contacted a Rice
University math team that has come up with the world's best method of ascertaining the most economical
travel routes.
The Rice team is still waiting on school district data to provide the answer, but one thing it already can tell
school leaders might astound them: There are so many possible routes that the world's fastest computers
could never enumerate them all.
The bus-routing problem is an example of the "traveling salesman problem," a classic math problem of
such difficulty it is considered theoretically impossible to solve, although the Rice team has made
breakthrough after breakthrough to reach the point that it could solve 99 percent of such problems.
Simply put, the traveling salesman problem asks for the shortest tour around a number of cities. It's fairly
simple if there are only, say, four cities involved, in which case there would be 24 possible routes to check.
But increase the tour to, say, 12 cities and suddenly there are 20 million possible pathways.
A computer can calculate the most economical way a salesman can make the four-city tour in a fraction
of a second. But using the same method to figure the route for 100 cities could take billions of years.
But using algorithms, a kind of mathematical short-cut that saves computers from considering every
possibility, Rice University researchers Robert Bixby, David Applegate and William Cook and Rutgers
researcher Vaskek Chva-tal recently found the optimal route for touring a world-record 13,509 cities
(every U.S. city with 500 or more people). Just to print in tiny type the number of possible routes to tour
those cities would take up hundreds of pages.
"Because the routes explode so exponentially as you add cities, one great challenge about the traveling
salesman problem is making the numbers comprehensible," says Bixby. "In the school district problem, for
instance, the Earth will perish before computers could enumerate each possible bus route."
The traveling salesman problem actually predates 20th-century mathematics - long before it gained its
contemporary name, the same premise was found in famous 18th- and 19th-century puzzles - but it wasn't
until the advent of computers in the mid-1950s that it was solved for 49 cities (Washington, D.C., and a
city in each of the then 48 states).
The problem had been solved for 2,392 cities in 1988 when Bixby, Applegate, Cook and Chvatal began
working on it. In the following decade, they became the world's best at it - solving it for 3 ,038 cities, then
4,461, then 7,397 and now 13,509. In 1992, the 3 ,038-city achievement was chosen by Discover magazine
as one of its top 50 stories.
Now, for the first time, math observers are talking about the problem crumbling, about an algorithm being
developed that is so good it will produce excellent solutions to problems of the most calculated difficulty,
even it can't absolutely guarantee it's the best possible solution.
Algorithms are mathematical recipes whose computer-implementation codes tell computers how to find
the most economical routes without actually enumerating them all. Those short-cuts are based on patterns
detected by both the mathematicians working on the problem and the computers themselves.
In the real world, solutions to the traveling salesman problem simplify scheduling and routing in the
transportation industry - buses, airlines, delivery trucks and postal carriers. It also helps study biomolecular
pathways, route computer networks' parallel processing and advance code writing and deciphering.
"The real appeal of the traveling salesman problem isn't solving the problems," says Bixby. "It's what you
discover about the structure of a problem that makes it easier to solve other problems."
The Rice team is always looking for good examples to test their work. After reading a Wall Street Journal
article about the "Extra Miler Club," an eccentric group of travelers whose members seek to eat Big Macs
in every McDonald's in North America or visit every U.S. county, Cook offered to plan their trips based
on the Rice team's method.
But after 10 years of cyberspace traveling, the Rice team may be ready for a rest from setting records for
solving the traveling salesman problem. Members are now writing a book on the problem - complete with
algorithms and codes that should enable other mathematicians to set records without having to reinvent
what the Rice team learned.
Still, after investing a decade of their life on it, none of the researchers is ready to leave the traveling
salesman problem. All have future plans related to it.
"It's addictive," says Chvatal. "No matter how much progress you make, you always have the nagging
feeling that you still did not nail down a couple of hunches that could bring about another quantum leap."
|