Did You Hear the One About the Salesman Who Traveled Better?

[R. A. Hettinga]

<http://online.wsj.com/article_print/0,,SB108266481426590961,00.html>

The Wall Street Journal

      April 23, 2004

 SCIENCE JOURNAL
 By SHARON BEGLEY



Did You Hear the One
 About the Salesman
 Who Traveled Better?
April 23, 2004

Traveling salesmen star in more jokes than almost any other occupation, but
William Cook doesn't let that distract him.

A mathematician at Georgia Institute of Technology, Atlanta, Prof. Cook is
one of hundreds of researchers who, since the 1930s, have wracked their
brains over the puzzle known as the traveling-salesman problem. It asks:
What's the shortest itinerary a salesman can follow to visit all the stops
on his route?

If our Willy Loman has to make only three or four stops, the optimal route
is easy to figure out. But once he adds a few dozen, the number of possible
sequences grows exponentially, and the computer time it would take to
calculate every possibility grows into the decades. As a result, after
three mathematicians solved the problem for 49 cities in 1954, it took
until 1971 to solve it for only 15 more. But Prof. Cook and three
colleagues broke the problem wide open in the 1990s, solving it for 13,509
cities in 1998 and for 24,978 a few weeks ago. That feat took 67 computer
years. (You can see the optimal paths at
www.math.princeton.edu/tsp/vlsi/index.html1.)

While not even the busiest salesman has a route that big, the problem has
become a boldface celebrity in the business world because all manner of
practical problems involve the basic question, what is the best way to do
something? Applications range from scheduling cable-TV service calls and
routing parcel-delivery trucks to drilling holes in a circuit board, where
you want to minimize how far the drill, like the salesman, must travel.

Faster computers are still not fast enough for this task, because such
problems have zillions of possible combinations, notes Michael Trick of
Carnegie Mellon University, Pittsburgh. UPS, for one, has upward of 1,500
pick-up/delivery facilities and sorting centers. It would take millennia of
computer hours to solve its routing problems using the traditional
problem-solving methods. So, scientists in "operations research" (a hybrid
of math, engineering and computer science) now are exploiting what Prof.
Trick calls "profound insights into the mathematics of the problem." In
other words, they're figuring out clever shortcuts the computers can take.

These insights take the form of algorithms, a sort of mathematical recipe.
"We're developing algorithms that are 10,000 times faster than the ones we
used 15 years ago," says Irv Lustig, an operations researcher at ILOG Inc.,
Mountain View, Calif. "Now we can say, given the data, here is the
probably-best answer."

An algorithm he developed for ILOG, which sells algorithm-packed custom
software, tackled the National Football League's 2004 schedule. He had to
juggle 256 games among 32 teams, subject to multiple constraints. There had
to be a nationally appealing game every Monday night and at least one
must-see match-up every Sunday, for example, and he couldn't send a team on
the road for weeks at a time.

Dr. Lustig's algorithm created thousands of schedules that fit these
constraints in a fraction of the time it took by trial-and-error computing.
Even better, it can tweak a schedule in less than a day if, say, the NFL
decides that a Giants-Redskins game simply won't do for Week 8 (it's Week
2). In the past, making that change would produce a domino effect taking
days to fix.

Many of the new algorithms emerged from advances in a relatively young
field of math called linear programming. Despite its name, linear
programming is not a kind of software-writing. Instead, it's a way to solve
optimization problems. Among the most powerful algorithms in linear
programming is one that could use some help from a branding consultant, but
for now is called the "interior-point method."

Imagine that every possible solution to a problem is represented as a point
on the surface of a million-faceted diamond. The best solution is the one
at the top. The challenge is to reach it. Traditionally, you'd do that by
climbing (mathematically) from point to higher point along the outside of
the diamond. The interior-point method lets you zoom up the inside.
Depending on the number of facets on the diamond, that may let you find the
solution more quickly.

Thanks to abstruse breakthroughs like this, operations research (OR) has
scored in more than the NFL. To eliminate backtracking and overlapping
routes, Waste Management Inc. solved what you might call a traveling
garbage-truck problem. Using an optimization algorithm to reroute its
fleet, WMI eliminated 761 trucks, saved $91 million in annual operating
costs and still hauled the trash on time.

So-called fractional-fleet services needed a similar mathematical rescue.
These companies promise customers who own, say, one-quarter of a business
jet that they can depart from anywhere within four hours. The easiest way
to do that is to have a plane at every airport their customers use. But
that is a good way to bleed cash. With operations research, Bombardier
Flexjet was able to cut crew levels by 20%, while getting 10% more daily
flights out of each of its aircraft.

Bombardier and WMI are among the finalists in a competition run by Informs,
the professional group for operations research. The winner will be
announced next week.

-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'