The unhappy traveling salesman problem
Solving the traveling salesman problem is difficult enough without having to consider the happiness of the salesman. But Tom Vanderbilt reports that’s essentially what UPS, FedEx, and the like have had to do.
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.”
Stay Connected