Algorithms For Business Resource Optimization

Travelling Salesman Problem. Too complicated?

In the field of mathematical optimization, there is hardly a problem of more fame than the traveling salesperson problem (TSP). Given a number of cities and the distances between them, find a “round-trip” (a tour) that visits every city, returns to the starting point, thereby covering the shortest possible distance. There is a wealth of applications; a historical one is drilling holes on a printed circuit board in a smallest amount of time, but there are many, many more: DNA sequencing, delivering parcels, painting car bodies, storing containers in a harbor, … I would say: whenever you have to find a best ordering or sequence of actions, there is a TSP somewhere around the corner. And that happens a lot in production, logistics, transport and traffic, and elsewhere.

The scientific literature has countless models, solution approaches, and also deep theoretical results and conjectures, you cannot read all this. Try Google Scholar with “traveling sales* problem” (the * because in former times, the person usually was a man) and you get almost a quarter of a million hits! One could explain our entire field only relating to this problem. “Well-studied” is a gross understatement.

About two weeks ago, Randal Olson posted an optimal road trip to visit each U.S. state and D.C., 49 cities in total. Randal implemented his own algorithm, provided beautiful visuals, explained the results, etc., still — without even reading the post to its end at the time — I tweeted

The reason for my spontaneous (you may also call it: arrogant) reaction: This is precisely the setting that started the success of the most powerful technique available today for optimally solving the TSP; presented in this paper from 1954:


Well, 49 cities was large-scale 60 years ago. Bill Cook maintains a web page where you can see optimal tours through more than 85,000 cities! There is even an app for that for your phone. It is so incredibly incredible that this is possible, due a tremendous algorithmic progress (not only improved machines), but this is a different story. In any case, reason enough, for us optimizers, to think about the TSP as being practically solved.

Now, it is an important question:

How on earth can it happen that, what we optimizers think every kid should know, is not even used by every well-educated scientist in a nearby area?

Entering Nathan Brixius with a wonderful metaphor that our optimization tools may be so powerful and general that in situations where this full power is not needed, our tools may be simply overlooked. Read Nathan’s post, it says much more of what goes wrong here. Bottom line is that we are lousy marketers of our profession if we always insist on this generality and power, even when a little less would do. We scare people away with too much technical detail.

Nathan (rightfully, in my opinion) suggests that in order to reach practitioners we sometimes may need to simplify, we may hide scientific rigor in public communication, and may accept that when a practitioner is happy, this may be already optimal — even when it is not in theory.

Once the door is open, you can still provide more tools and a more optimal solution.

Jeez, I bit on my tongue, before I wrote that. Yet, I believe that many of us can agree on what Nathan writes. Operations research and mathematical optimization needs more marketing, more simple examples, more accessible success stories — even though many of us are working on that, it is not enough yet.

No additional post necessary until here.

But now comes what somewhat depresses me. Randal was recently interviewed by NPR News about his work. And you may read the mind of the interviewer, between the lines: Can this scientist really be thinking that this “improbable” tour of 49 U.S. cities will really, ever be traveled by any family?

Can this really be of any practical use?

Yes, Randal may have missed the opportunity to speak further about practical applications of the TSP, but he did provide one accessible example, he did speak in everyday language, he did good marketing for the idea of optimization. And still it seems to be a very fragile construction to convince people about optimization. You have to find exactly the right examples, exactly the right words, exactly the right level of simplification. And all this may vary across the persons you talk to. Is it really so hard to abstract, so hard to at least conceive that this or any other optimization problem may be useful in companies, services, science, everyday life?

Are we too complicated for this world?

0 0 votes
Article Rating
Notify of

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Inline Feedbacks
View all comments
Would love your thoughts, please comment.x