The traveling salesman problem is one of the more famous challenges in mathematics. This is the problem of finding the shortest route for visiting a number of cities once and then returning to the place of origin.

Of course, it’s straightforward to find routes that visit each city in this way.  The big challenge is in finding the shortest.

There’s one fail-safe way of doing this–by sheer brute force.  That means measuring the length of every tour and working out which is shortest. The problem is that this task becomes increasingly lengthy as the number of cities increases. Indeed, for  large numbers of cities, it is computationally unfeasible. 

It’s easy to imagine that there might be some kind of clever mathematical shortcut that solves this problem. Not so. In fact, mathematicians tend to agree that a general shortcut will never be found (this is the so-called P=NP debate).

Instead, they have to rely on optimisation processes that search for short solutions but are unable to prove that these are indeed the shortest ones. 

So the challenge for all practical purposes is to find algorithms that produce good results and that are computationally efficient. 

Today, Jeff Jones and Andrew Adamatzky at the University of the West of England in the UK reveal an unusual approach. These guys say a reasonable solution can be found by representing the cities as a series of dots in a virtual petri dish, submerging the dots in a blob of virtual goo and then shrinking the blob.

In simplified terms, the blob clings to the dots as it shrinks, linking them with a minimal surface, rather like a soap bubble surface. “As the blob shrinks it morphologically adapts to the configuration of the cities,” they say.

When all the dots sit on the surface of the blob,  the resulting surface is a solution to the traveling saleseman problem that is generally pretty good. 

The magic ingredient in all this is the special goo. It consists of many particles that each move according to a set of simple rules, like autonomous agents. These sit in a sea of “chemoattractant”, a virtual scent that the particles are attracted to.  At each stage in the calculation, each particle senses the chemoattractant around it and then moves towards the region of highest concentration. As it moves, it leaves behind its own trace of the chemoattractant for other particles to follow.

The result is a kind of intelligent blob that shows emergent behaviour, such as the ability to minimise its surface area.

Jones and Adamatzky have put this intelligent goo through its paces by setting it lose on traveling salesman problems consisting of 20 cities randomly distributed in a virtual petri dish.  They’ve placed videos of the shrinking process here.

The results are good but not perfect. The created 20 different scenarios of 20 cities and ran the blob 6 times on each. They then compared the blob’s shortest route with the actual shortest path found by brute force. Jones and Adamatzky say that if this shortest route is of length 1, the intelligent blob found tours with a mean best tour length of 1.04, mean average tour length of 1.07 and mean worst tour length of 1.09.

That’s not bad. But the real advantage is in the simplicity of the approach which is essentially emergent and involves no special optimisation processes. It also produces a map of the route at the end (although some human interpretation is required to  make sense of it).

There are disadvantages, of course. There are some configurations of cities that the blob cannot cope with. These occur when the shortest route forms a kind of strait between two cities rather than a connection, like the Strait of Gibraltar between the Atlantic Ocean and the Mediterranean Sea. Instead, the blob tends to connect them.

Nevertheless, this is an interesting form of unconventional computing that produces a fascinating alternative to conventional traveling salesman algorithms. It bears the closest resemblance to “rubber band” approaches which surround the cities with a rubber band and then progressively attempt to stretch the band to connect cities within. The big difference is that the material properties of the blob are emergent rather than pre-programmed.

Jones and Adamatzky say the next step would be to create a physical model of this system in which a real blob does the work, perhaps using viscoelastic, free energy minimisation. Designing such a material might be tricky, however. 

Another approach, which might have broader application, would be to distill the properties of this unconventional computation into a classical algorithm.

Best of all is the prospect of logistics managers planning delivery routes by dipping road network models into vats of intelligent goo.  So we’ll  wait with anticipation for this new science of traveling salesman alchemy.

Ref: arxiv.org/abs/1303.4969: Computation of the Traveling Salesman Problem by a Shrinking Blob