The traveling salesman problem (TSP) is an example of a combinatorial optimization problem. Suppose there are 20 cities. The goal of TSP is to find the path that visits each city once, and has the shortest distance.
Combinatorial optimization problems are typically very difficult. A powerful technique for solving many kinds of combinatorial optimization problems is the simulated bee colony meta-heuristic.
As part of my exploration of the R language, I thought I’d take a look at solving the TSP using R. I created a dummy problem where there are 20 cities with distances set up so that the distance between cities (n and n+1) is 1.0, and the distance between cities n+1 and n is 1.5. Therefore, the optimal path is (1, 2, . ., 20) with total distance of 19.0 units.
With 20 cities, there are 20! = 2,432,902,008,176,640,000 different paths (assuming each path is distinct) to explore so a try-all approach won’t work.
Bee colony optimization loosely simulates the foraging behavior of bees. There are hundreds of possible concrete implementations of a bee colony algorithm. I set up just the most rudimentary version that leaves out many important ideas, but even so, I was able to solve TSP.
I learned a lot about R syntax and quirks while exploring this little problem.