Traveling Salesmen

With the laptop, the problem of the traveling salesman has found a new dimension. Perhaps it is even time to discuss whether the original criteria of a solution to the traveling salesman problem require reconsideration.

I’m sitting in Terminal 6 at John F. Kennedy Airport in New York, waiting for the flight back to California. For a while now, there is this gentleman looking at me and clearly something is bothering him. When I hear my boarding call and I unplug my laptop from the power outlet, he straightens his back and I sense a definite mood swing. Walking to the gate I turn around to double check that I took all my belongings and I see the man plugging in his laptop and settling in the seat I just occupied. He now overlooks the surrounding area as a king overlooking the area around his castle. Nothing can hurt him anymore.

In my trips to clients across the United States I have learned the locations of power outlets and phone jackets at different airports. Keep your eyes out for flocks of laptops scattered around pillars or phone booths. These are the signs that power or Internet connectivity is not far away.

Since time salesmen have tried to determine how they can plan their visit to the clients of the day. The essence of the traveling salesman problem is basically improving efficiency. In the past travel meant waiting for the transportation vehicle to arrive (horse carriage, train, airplane) or to get at the next stop.

Nowadays we have mobile offices and wireless Internet connectivity. So instead of looking at the pattern of the lights in the ceiling or the color of the carpet in the airline terminals, we can now spend our time preparing for a meeting, work through the list of e-mails that piled up during a meeting, or write columns for a GIS magazine.

There are some limitations to the mobile office though. One of those is battery power. The salesman of today has to bridge the flying time between airports and the time spent at an airport between two connecting flights. This translates into a basic GIS problem: select a route from A to B as a set of flying segments for which the flying time per segment is not more than available battery lifetime and for which the battery can be charged in the time spent between two segments. Account for loss of battery power due to shutdown and startup when the airplane takes of or lands.

Note that shortest distance is no longer one of the traveling salesman’s problems. A longer flight might result in more effective working time and may therefore be considered a more optimal solution.

Extending efficiency to 100% leads to an interesting situation. At one point, the battery cannot be charged enough to last the next flying segment, resulting in making the segments shorter. This however also results in more shutdowns and startups, which has a negative effect on the remaining battery lifespan. Thus segments get shorter and shorter. The traveling salesman gets stuck halfway to his destination… Traveling further is not sensible since it is more efficient to stay at the current location.

A solution to this paradox may come in time as technology progresses. Video conferencing or even virtual reality meetings will become possible in the future, finally solving the traveling salesman for once and for all: the salesman stays at the office! Until then sit back, relax and enjoy the flight.

Appeared in GeoInformatics Magazine (www.geoinformatics.com) in April/May 2003