Right now the entire world is working its way through one of the most difficult logistical problems it has ever faced. The Pfizer Covid-19 vaccine, which has some very stringent storage requirements, has to be distributed as quickly as possible, well everywhere on the planet! It’s not an easy problem to solve, trying to find the most efficient way of getting the vaccine to literally every human being, and remember the longer it takes to get the vaccine to everyone the more people will die!
Obviously shipping directly from the factory to each individual would not be the optimal solution, even if the vaccine didn’t have to be stored at a temperature of -70ºC. So instead you designate a number of depots, hospitals in the case of a vaccine, that receive shipments from the factory and then the depots distribute the vaccine to individuals.
In that case how many depots? Where should they be? What about a multi-layered approach where the factory ships to major depots that ship to smaller, more local depots in turn who then distribute the vaccine to individuals? So, how many layers? It’s a lot of questions to answer, and remember, people are getting sick every minute!
Real life situations like the Covid vaccine are members of a class of mathematical problems known as the ‘Traveling Salesman Problem’ or TSP. In its most simple description a salesman is required to visit N number of cities and wants to calculate the shortest possible route connecting them all. Remember the longer the journey the more time it takes and time is money after all. TSP is considered to be one of the classic problems in mathematical optimization.
For two cities the solution is pretty obvious. Travel to one city, then straight to the other and then back home, which city you visit first doesn’t matter since going along exactly the same path in the reverse order still leads to the same total distance. As you add cities however the problem quickly becomes much more complicated. Consider three cities, which we shall name 1, 2, and 3. There are in fact six separate combinations that get you to all three cities as shown in Table 1.
However once again following the same path in exactly the opposite direction leads to the same total distance traveled so there are really only three solutions, see Table 2. Each of these distinct solutions now has to be evaluated to determine which is the shortest.
Adding one more city to bring the number to four increases the number of different combinations to 24, see Table 3. And even after we after we reduce the number by half to account for symmetry that still leaves us with 12 distinct paths to be evaluated for total distance, see Table 4.
So if our traveling salesman wants to visit two cities there is only one path for him to follow, for three cities there are three distinct routes, for four cities 12. As more cities are added the numbers just explode, five cities yields 60 routes and before long you’ve reached the point where even a supercomputer will have to take a good bit of time to find the optimal, shortest path. In fact the TSP is so simple yet so enormous a problem that it is often used to evaluate the performance of new computer and software designs and methodologies.
Now in real life it usually isn’t necessary to find the absolutely best route. Think about it, if there are 50 million possible solutions then there are probably at least a thousand that are within 0.1% of the optimal. If one of that thousand can be found quickly it may make more sense to get started with a good solution rather than wait for a supercomputer to find the perfect one.
That’s why mathematicians at Hokkaido University in Japan have developed an analog computer that quickly finds a good solution to the TSP by mimicking the feeding behavior of, Slime Mold! You see slime molds are large, single celled organisms that are capable of deforming their bodies in a manner similar to an amoeba. In their search for food a slime mold will send out a number of tendrils is several directions. Those tendrils can sense the chemical traces of nutrients so tendrils that sense food nearby get bigger and longer and form sub tendrils while those that don’t sense food shrink.
In this way a slime mold will very quickly find any available food and shape its body to take advantage of any resource. Inspired by the slime mold’s search methodology Professor Seiya Kasai and his student Ph.D. candidate Kenta Saito designed an analog circuit where resistance values are used to represent distances. A breadboard circuit for a four city problem was built that quickly found a solution that, if not the best, was significantly better than the average solution.
The circuit is so designed that additional cities can be easily added and the amount of time required to find a good solution only increases linearly with the number of cities added. In other words while it would take a digital computer five times longer to calculate the best five city solution than the best four city solution, it only takes the analog circuit 25% longer to find a good five city solution.
In the real world a good solution now is often better than the best solution later, remember time is money and in many cases lives. Slime molds took millions of years to evolve a practical way to solve the traveling salesman problem, now we can profit from their instinctive knowledge. Another example of science learning by studying nature.