{"59990":{"#nid":"59990","#data":{"type":"news","title":"WSJ Feature: Did You Hear the One About the Salesman Who Traveled Better?","body":[{"value":"\u003Cp\u003ETraveling salesmen star in more jokes than almost any other occupation, but William Cook doesn\u0027t let that distract him.\n\u003C\/p\u003E\n\u003Cp\u003EA mathematician at Georgia Institute of Technology, Atlanta, \u003Ca href=\u0022http:\/\/www.isye.gatech.edu\/faculty-staff\/profile.php?entry=wc115\u0022\u003EProf. Cook\u003C\/a\u003E 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\u0027s the shortest itinerary a salesman can follow to visit all the stops on his route?\n\u003C\/p\u003E\n\u003Cp\u003EIf 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 \u003Ca href=\u0022http:\/\/www.math.princeton.edu\/tsp\/vlsi\/index.html\u0022\u003Ewww.math.princeton.edu\/tsp\/vlsi\/index.html.\u003C\/a\u003E)\n\u003C\/p\u003E\n\u003Cp\u003EWhile 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.\n\u003C\/p\u003E\n\u003Cp\u003EFaster 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 \u0022operations research\u0022 (a hybrid of math, engineering and computer science) now are exploiting what Prof. Trick calls \u0022profound insights into the mathematics of the problem.\u0022 In other words, they\u0027re figuring out clever shortcuts the computers can take.\n\u003C\/p\u003E\n\u003Cp\u003EThese insights take the form of algorithms, a sort of mathematical recipe. \u0022We\u0027re developing algorithms that are 10,000 times faster than the ones we used 15 years ago,\u0022 says Irv Lustig, an operations researcher at ILOG Inc., Mountain View, Calif. \u0022Now we can say, given the data, here is the probably-best answer.\u0022\n\u003C\/p\u003E\n\u003Cp\u003EAn algorithm he developed for ILOG, which sells algorithm-packed custom software, tackled the National Football League\u0027s 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\u0027t send a team on the road for weeks at a time.\n\u003C\/p\u003E\n\u003Cp\u003EDr. Lustig\u0027s 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\u0027t do for Week 8 (it\u0027s Week 2). In the past, making that change would produce a domino effect taking days to fix.\n\u003C\/p\u003E\n\u003Cp\u003EMany 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\u0027s 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 \u0022interior-point method.\u0022\n\u003C\/p\u003E\n\u003Cp\u003EImagine 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\u0027d 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.\n\u003C\/p\u003E\n\u003Cp\u003EThanks 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.\n\u003C\/p\u003E\n\u003Cp\u003ESo-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.\n\u003C\/p\u003E\n\u003Cp\u003EBombardier 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.\n\u003C\/p\u003E\n\u003Cp\u003E- You can e-mail me at \u003Ca href=\u0022mailto:sciencejournal@wsj.com\u0022\u003Esciencejournal@wsj.com\u003C\/a\u003E.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":"","uid":"27279","created_gmt":"2004-04-23 00:00:00","changed_gmt":"2016-10-08 03:07:08","author":"Barbara Christopher","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2004-04-23T00:00:00-04:00","iso_date":"2004-04-23T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"groups":[{"id":"1242","name":"School of Industrial and Systems Engineering (ISYE)"}],"categories":[{"id":"145","name":"Engineering"},{"id":"135","name":"Research"}],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cstrong\u003EBarbara Christopher\u003C\/strong\u003E\u003Cbr \/\u003EIndustrial and Systems Engineering\u003Cbr \/\u003E\u003Ca href=\u0022http:\/\/www.gatech.edu\/contact\/index.html?id=bt3\u0022\u003EContact Barbara Christopher\u003C\/a\u003E\u003Cbr \/\u003E\u003Cstrong\u003E404.385.3102\u003C\/strong\u003E","format":"limited_html"}],"email":["bchristopher@isye.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}