Tue August 6, 2013

The Water Delivery Man Problem

Optimal route for the 33-city traveling salesman problem in the 1962 Car 54 contest. Proctor & Gamble sponsored a $10,000 grand prize for the winning entry. Mathematicians Robert Karg and Gerald Thompson tied for first place.
Credit Bill Cook / In Pursuit of the Traveling Salesman

There is a problem that has vexed mathematicians for the greater part of the past century. Currently, there is no solution, and nobody knows for certain whether or not one exists. But cracking the code would be a huge breakthrough both in theoretical mathematics and practical everyday applications. Ellis Robinson brings the story, starting with a description of the problem from physicist Eddie Farhi.

“You’re a salesman. And you have to visit 500 cities. And you know the distances between all those cities. Now your task is to visit each city once, but you have to take the shortest route. How am I going to do that—how am I going to find the shortest route? Just list every possible route, and pick the shortest. Well, you pick the first city.. there are 500 choices. Then, I pick the next city, there are 499 choices. Then I pick the next city, there are 498 choices. So the number of choices is 500 times 499 times 498 times 497, and so on. That number is so huge, that if you had every computer in the world, operating since the beginning of time, they would not be able to go through 500 factorial routes. It’s way too big.”

Paul Jones owns and operates Dreamtime Water, a familiar service in the back alleys of Aspen.

“How many points do you deliver to?”


“How many do you break down per day?”

“There’s eight days, so about a hundred.” “So each day you’re doing a hundred city traveling salesman problem?”


He’s been delivering drinking water in the Roaring Fork Valley since 1997. I wanted to find a real-life traveling salesman to ask, ‘how do you optimize your delivery route each day?’

“You know there’s 20 miles between each Aspen, Basalt, Carbondale, and Glenwood. It makes sense to focus, and do all your deliveries in one of those towns in one day.”

Jones has never used a computer program to optimize his route.

“I would love to know what a computer would think my most elegant solution would be. I’ve had the same solution pretty much since the beginning.”

That isn’t to say Paul’s job is simple or straightforward. He’s calculating distances in his head as he juggles other factors; like where to park his delivery truck.  Adding in variables like parking makes the traveling salesman problem much harder to solve.

“It may be that when I’m delivering in front of the courthouse, it’s really better to do that first thing in the morning when there aren’t many police cars around. Unless you program the computer to take things like that into account, that could really screw things up (laughter).”

Fortunately, there is hope for both mathematicians and water delivery drivers seeking an answer to the seemingly unsolvable traveling salesman problem. Again, Physicist Eddie Farhi

“Maybe with a quantum computer there is a new avenue.”

Quantum computers are in their infancy, but may represent a new paradigm for computing. Traditional computers rely on binary digits, or bits, to represent data, which can be either a zero or a one. But a quantum bit, or “qubit,” can be a one, a zero, or some mixture of one AND zero. This property allows the qubit to carry richer information than the traditional bit.

Farhi hopes that quantum computers could solve the traveling salesman problem without calculating the distance of every possible combination of cities, or places that need water.
“If you didn’t have to exhaustively search, but be confident that you had found the global optimum... That would be a huge progress..”

Solving the problem wouldn’t just be a notch in the belts for mathematicians. The applications would extend to the fields of planning, logistics, even DNA sequencing.

Until then though, no computer can easily find the most efficient route for Jones. And so he keeps relying on his mind, finding tricks like always putting the glass bottles on the driver’s side of his truck.

“It saves time! If nothing else, it’s a more elegant solution to the traveling salesman problem... or the water delivery problem! We’re gonna rename it.”