Facebook
Twitter
Pocket
Reddit
Email
When Bob Santilli, a senior project manager at UPS, was invited in 2009 to his daughter’s fifth grade class on Career Day, he struggled with how to describe exactly what he did for a living. Eventually, he decided he would show the class a travel optimization problem of the kind he worked on, and impress them with how fun and complex it was. The challenge was to choose the most efficient route among six different stops, in a typical suburban-errands itinerary. The class devised their respective routes, then began picking them over. But one girl thought past the question of efficiency. “She says, my mom would never go to the store and buy perishable things—she didn’t use the word perishable, I did—and leave it in the car the whole day at work,” Santilli tells me.
Her comment reflects a basic truth about the math that runs underneath the surface of nearly every modern transportation system, from bike-share rebalancing to airline crew scheduling to grocery delivery services. Modeling a simplified version of a transportation problem presents one set of challenges (and they can be significant). But modeling the real world, with constraints like melting ice cream and idiosyncratic human behavior, is often where the real challenge lies. As mathematicians, operations research specialists, and corporate executives set out to mathematize and optimize the transportation networks that interconnect our modern world, they are re-discovering some of our most human quirks and capabilities. They are finding that their job is as much to discover the world, as it is to change it.
The problem that Santilli posed to his daughter’s class is known as a traveling salesman problem. Algorithms solving this problem are among the most important and most commonly implemented in the transportation industry. Generally speaking, the traveling salesman problem asks: Given a list of stops, what is the most time-efficient way for a salesman to make all those stops? In 1962, for example, a Procter and Gamble advertisement tasked readers with such a challenge: To help “Toody and Muldoon,” co-stars of the Emmy-award-winning television show Car 54, Where Are You?, devise a 33-city trip across the continental United States. “You should plan a route for them from location to location,” went the instructions, “which will result in the shortest total mileage from Chicago, Illinois, back to Chicago, Illinois.”
A mathematician claimed the prize, and a regal $10,000. But the contest organizers could only verify that his solution was the shortest of those submitted, and not that it was the shortest possible route. That’s because solving a 33-city problem by calculating every route individually would require 28 trillion years—on the Department of Energy’s 129,000-core supercomputer Roadrunner (which is among the world’s fastest clusters). It’s for this reason that William J. Cook, in his book In Pursuit of the Traveling Salesman, calls the traveling salesman problem “the focal point of a larger debate on the nature of complexity and possible limits to human knowledge.” Its defining characteristic is how quickly the complexity scales. A six-city tour has only 720 possible paths, while a 20-city tour has—by Cook’s quick calculations on his Mac—more than 100 quadrillion possible paths.
Modeling the real world, with constraints like melting ice cream and idiosyncratic human behavior, is often where the real challenge lies.
There are answers to some traveling salesman problems. Cook himself has produced an iPhone app that will crack 100 cities, using relaxed linear programming and other algorithmic techniques. And every few years or so, teams armed with sophisticated hardware and programming approaches set the bar higher. In 2006, for example, an optimal tour was produced by a team led by Cook for a 85,900-city tour. It did not, of course, given the computing constraints mentioned above, involve checking each route individually. “There is no hope to actually list all the road trips between New York and Los Angeles,” he says. Instead, almost all of the computation went into proving that there is no tour shorter than the one his team found. In essence, there is an answer, but there is not a solution. “By solution,” writes Cook, “we mean an algorithm, that is a step-by-step recipe for producing an optimal tour for any example we may now throw at it.”
And that solution may never come. The traveling salesman problem is at the heart of an ongoing question—the question—in computer science: whether or not P equals NP. As summarized with blunt elegance by MIT’s news office, “roughly speaking, P is a set of relatively easy problems, NP is a set of incredibly hard problems, and if they’re equal, then a large number of computer science problems that seem to be incredibly hard are actually relatively easy.” The Clay Mathematics Institute offers a $1 million reward to a meta-problem hovering like a mothership over the Car 54 challenge and its ilk: proving that P does or does not equal NP.
By now it should be clear that we are not talking just about the routing needs of salesmen, for even the most trenchant of regional reps does not think about hitting 90,000 far-flung burghs on a call. But the Traveling Salesman Problem, and its intellectual cousins, are far from theoretical; indeed, they are at the invisible heart of our transportation networks. Every time you want to go somewhere, or you want something to get to you, the chances are someone is thinking at that very moment how to make that process more efficient. We are all of us traveling salesmen.
A position like Bob Santilli’s, performing optimization, didn’t always exist at UPS. Times used to be simpler. Until the early 1980s, UPS drivers used to have one simple goal: to get all the packages in their truck delivered by the end of the day. Those were the “ground” days. “The only thing we had was time sensitivity for commercial drivers,” notes Santilli. Jeff Winters, who heads operations research for UPS, says “everything was a human-scalable problem to solve.” And it had to be. “We had individual carload diagrams for drivers every day,” says Santilli (UPS calls its brown delivery vans “cars”). On paper. Routes were laid out via pushpins on a map. At the end of the day, everything was filed, and the process began again.
But then, in 1982, the world changed: Next-day air delivery was introduced. Suddenly, there were an increasing variety of time “commits”; packages had to be at one address by 10:30 a.m., another by 1:30 p.m., another by noon. There were new time constraints for package pickups as well. It was no longer just an optimal routing problem, but an optimal scheduling problem. And the one thing UPS suspected was that it was not doing things optimally. One imagines that within these walls there is no greater sin. Even the insides of vans are subjected to a kind of routing algorithm; the next time you get a package, look for a three-letter letter code, like “RDL.” That means “rear door left,” and it is so the driver has to take as few steps as possible to locate the package. In one typical aside, Santilli told me that when a driver stops the van, he “has nine seconds to select a package and get out of there.” His tone suggested he was talking about a member of a bomb disposal unit.
In 1986, UPS purchased Roadnet, a logistics company that created optimal routes for businesses like beer distributors. There was just one problem: the drivers that Roadnet worked with typically plied the same route every day or so, with few hard time constraints. And so UPS began what would become known as Project ORION (Onroad Integrated Optimization and Navigation), a project spanning many years and many millions of dollars, whose algorithmic efforts are just beginning to bear fruit in its fleet of nearly 58,000 trucks. At the core of ORION was the travelling salesman problem. Each UPS truck—which makes around 130 stops per day—is essentially a traveling salesman problem on wheels.
ORION’s promise was and is clear: For each mile saved, per driver, per year, UPS saves $30 million. The mathematics required to arrive at some solution to the traveling salesman problem, even if approximate, is also clear. But in trying to apply this mathematics to the real world of deliveries and drivers, UPS managers needed to learn that transportation is as much about people and the unique constraints they impose, as it is about negotiating intersections and time zones. As Jeff Winters put it to me, “on the surface, it should be very easy to come up with an optimized route and give it to the driver, and you’re done. We thought that would take a year.” That was a decade ago.
When a driver stops the van, he “has nine seconds to select a package and get out of there.”
For one thing, humans are irrational and prone to habit. When those habits are interrupted, interesting things happen. After the collapse of the I-35 bridge in Minnesota, for example, the number of travelers crossing the river, not surprisingly, dropped; but even after the bridge was restored, researcher David Levinson has noted, traffic levels never got near their previous levels again. Habits can be particularly troublesome for planning fixed travel routes for people, like public buses, as noted in a paper titled, “You Can Lead Travelers to the Bus Stop, But You Can’t Make Them Ride,” by Akshay Vij and Joan Walker of the University of California. “Traditional travel demand models assume that individuals are aware of the full range of alternatives at their disposal,” the paper reads, “and that a conscious choice is made based on a tradeoff between perceived costs and benefits.” But that is not necessarily so.
People are also emotional, and it turns out an unhappy truck driver can be trouble. Modern routing models incorporate whether a truck driver is happy or not—something he may not know about himself. For example, one major trucking company that declined to be named does “predictive analysis” on when drivers are at greater risk of being involved in a crash. Not only does the company have information on how the truck is being driven—speeding, hard-braking events, rapid lane changes—but on the life of the driver. “We actually have built into the model a number of indicators that could be surrogates for dissatisfaction,” said one employee familiar with the program.
This could be a change in a driver’s take-home pay, a life event like a death in the family or divorce, or something as subtle as a driver whose morning start time has been suddenly changed. The analysis takes into account everything the company’s engineers can think of, and then teases out which factors seem correlated to accident risk. Drivers who appear to be at highest risk are flagged. Then there are programs in place to ensure the driver’s manager will talk to a flagged driver.
In other words, the traveling salesman problem grows considerably more complex when you actually have to think about the happiness of the salesman. And, not only do you have to know when he’s unhappy, you have to know if your model might make him unhappy. Warren Powell, director of the Castle Laboratory at Princeton University’s Department of Operations Research and Financial Engineering, has optimized transportation companies from Netjets to Burlington Northern. He recalls how, at Yellow Freight company, “we were doing things with drivers—they said, you just can’t do that.” There were union rules, there was industry practice. Tractors can be stored anywhere, humans like to go home at night. “I said we’re going to need a file with 2,000 rules. Trucks are simple; drivers are complicated.”
At UPS, a program could come up with a great route, but if it violated, say, the Teamsters Union rules, it was worthless. For instance, time windows need to be built in for driver’s breaks and lunches. And while the filmed testimonials of drivers I saw at UPS were largely positive in their description of ORION, it is interesting to note that the latest contract between the company and the union included a provision that no driver would be “discharged based solely on information received from GPS or any successor system.”
Powell’s biggest revelation in considering the role of humans in algorithms, though, was that humans can do it better. “I would go down to Yellow, we were trying to solve these big deterministic problems. We weren’t even close. I would sit and look at the dispatch center and think, how are they doing it?” That’s when he noticed: They are not trying to solve the whole week’s schedule at once. They’re doing it in pieces. “We humans have funny ways of solving problems that no one’s been able to articulate,” he says. Operations research people just punt and call it a “heuristic approach.”
This innate human ability was at work in Santilli’s daughter’s class, too. The fifth graders got it about right. As James MacGregor and Thomas Ormerod note, “the task of the traveling salesman problem may happen to parallel what it is natural for the perceptual system to do in any case when presented with an array of dots.” Curiously, using this heuristic approach, they note, subjects in experiments were “exceptionally good at finding the optimum tours.” In other experiments, when subjects were shown images of optimal tours, they were thought to be more aesthetically pleasing than sub-optimal tours.
Modern routing models incorporate whether a truck driver is happy or not—something he may not know about himself.
Of course, even the human balks at understanding the behavior of other humans. Powell showed me a sample diagram he’ll sometimes give to a roomful of trucking executives. “I’ve got a load that has to be picked up. I’ve got a driver 60 miles away. All I have to do is dispatch him and it’s done. I’ve got another driver who, once he unloads, will be about 30 miles away—should be in around midafternoon.” Do you take the sure thing, even if it consumes more miles? Or do you take the risk on the shorter trip, which might get in later? When he asks for a show of hands which choice is better, the response is typically mixed. “Driver B saves me miles. But he hasn’t arrived yet, and what if he doesn’t?” he says, his voice dropping to a conspiratorial whisper. “Different people will answer it differently. They’ll say, ‘I know that driver, he’ll make it.’ Welcome to real-world decision making.”
In the end, the best approach turns out to be building on what people are already doing. When Powell consulted with Schneider trucking a decade ago, curiously, he did not model some über-efficient idealized vision of what Schneider could be. He essentially modeled Schneider as it was. “Our objective wasn’t to get the best solution,” says Ted Gifford, a longtime operations research specialist at Schneider. “Our objective was to try to simulate what the real world planners were really doing.” When I suggest to Gifford that he’s trying to understand the real world, mathematically, he concurs, but adds: “The word ‘understand’ is too strong—we are happy to get positive outcomes.”
At UPS, too, allowing for human behavior in a quantitative way was key. “In the old business rule,” says UPS’s Winters, “we held the drivers accountable for how closely they follow the trace”—UPS speak for route. Even worse, he says, drivers, while not being given guidance, were being penalized—“coached and counseled”—for errors and delays, or “breaking trace.” This, he says, was a “dumb rule,” a hangover of legacy thinking inherited from the company’s origins as a ground-only delivery service. “The right thing to do,” Winters says, “is build your route with just your air work, and then look at expensive ground areas that you can do to eliminate the need to go back to that area. It turned a business problem on its head.”
Transport optimization, then, is hard, and understanding how to implement it can be harder still. “One of the hardest things to teach a math analytics group,” Santilli tells me, “is the difference between a feasible solution and an implementable solution. Feasible just means it meets all the math constraints. But implementable is something the human can carry out.”
But optimization has succeeded in coming a very long way. Modeling has become much more sophisticated, a development that Powell outlines in his life’s work, a book called Approximate Dynamic Programming: Solving the Curses of Dimensionality. “You went to the math literature, and it was all toy problems. It was literally about 20 years before I could go to a whiteboard and say, you know what, I can actually write down the problem.” Mapping has improved dramatically. A few decades ago, the mapping service UPS bought literally had people calling businesses to ask them if they actually were where the data UPS had suggested they were. Early GPS maps were also flawed. “When we got some bad results early on,” says Ranga Nuggehalli, UPS’s principal scientist, “we didn’t know whether it was because the algorithm was so bad, or our data was so bad.” It was the latter.
The data acquisition needed for tracking has since been developed. UPS’s “Delivery Information Acquisition Device,” or DIAD, the brown handheld computer upon which you have no doubt signed your name, creates a data architecture that underpins their optimization strategy.
And the end result has been one of slow but steady improvement. Powell and Santilli point to their own success stories. Yellow Freight used to have some 700 “end of lines,” Powell says, which are sorting terminals where cargo is transferred to its end customers. Powell developed a model that delivered a counterintuitive message: Trucks were traveling farther to get to the customer with so many terminals. Today, he says, Yellow Freight has 400 end of lines. “That was the right number,” he says. As for UPS, Santilli notes that a driver in Gettysburg, Pa. is now driving nearly 25 miles less per day, from an original route of more than 150 miles down to 126 miles—with the same number of stops.
We are getting smarter at moving things around. But the less obvious story is that we are getting a grasp on how to model the human element in transportation. Just as we are getting to know algorithms, algorithms are getting to know us.
Tom Vanderbilt writes on design, technology, science, and culture, among other subjects. His most recent book is The New York Times bestseller Traffic: Why We Drive the Way We Do (and What It Says About Us).
Get the Nautilus newsletter
Cutting-edge science, unraveled by the very brightest living thinkers.
