The Traveling Salesman Dilemma

By Paul Whitelam, SVP of Marketing, ClickSoftware

Have you ever heard of the “traveling salesman” problem? It goes like this: If a salesman must visit all 48 capital cities in the continental United States and visit each city only once, what path should he take to yield the shortest overall distance?

Interesting problem isn’t it? It’s simple to state of course, but if you spend a little time with the problem, you’ll quickly see what a brainteaser it is. That’s because there are literally millions of unique travel paths the salesperson can take ... but only one optimal path. Many mathematicians have spent a good part of their careers trying to find the answer. But notice that in the traveling salesman problem, only one factor – distance – must be optimized.

Compare that to field scheduling where you have hundreds of factors – travel distance, travel time, overtime costs, labor costs, employee availability and skills, customer availability and preferences, contractor availability, and others to deal with. So a multidimensional problem such as yours makes the one- dimensional traveling salesman problem look like child’s play. This is why field service organizations need a sophisticated schedule optimization solution because calculating optimal decisions overwhelms the capabilities of traditional workforce management systems.

Let’s walk through a typical schedule optimization problem to highlight the complexity.