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.html.)

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.

- You can e-mail me at sciencejournal@wsj.com.