How Traveling Salesmen Complicate the Traveling Salesman Problem

traveling_salesmanThe traveling salesman problem is simple in its setup but remarkably complicated to solve. You need to visit a number of cities, say 10, and want to find the shortest route that visits all of them exactly once and brings you back to where you started. From a list of routes it is easy to find the shortest one, but it is incredibly hard to verify that it is the shortest of all possible routes.

Finding a solution gets even more difficult when you go from a (mathematically) feasible solution to one that can be implemented in the real world. That is because you have to incorporate a notoriously unreliable component into your plans: human beings.

[I]n 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….

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….

In other words, the traveling salesman problem grows considerably more complex when you actually have to think about the happiness of the salesman.

That’s from Tom Vanderbilt over at Nautilus, and the whole thing is worth a read. Oh, and there’s also an app for that.