The Traveling Salesman problem is a popular illustration of the limits of normal computational techniques and equally a popular subject for demonstrations of alternate approaches to solving such challenges.

While the application of evolutionary algorithms to the problem is hardly unique we found it an excellent test-bed to explore alternate approaches. Some worked very well indeed and some hardly at all. This page explains the problem and describes how evolutionary techniques can be applied to produce solutions that approach the optimal.

The traveling salesman problem is a real life business problem. It has direct parallels in factory scheduling, wiring looms, circuit board drilling and of course route planning. Indeed the same problems arise whenever a large number of individual tasks need to be ordered in an optimal manner.

The traveling salesman problem is usually described as planning a route through a number of cities such that each city is only visited once and with the salesman returning to his city of origin. The challenges is to minimise the distance traveled. This seems perfectly straightforward. A glance at the map below would enable anyone to select a good solution from a trip around the five towns and cities shown.

The problem gets more complicated when the number of cities grows and a visual inspection no longer provides an obvious solution. The classic approach would be to measure the distance between each city and to calculate all of the possible routes between them – finally selecting the shortest route.

With five cities the number of possible alternate routes is 5! (five factorial) which is 1 * 2 * 3 * 4 * 5 = 120 different routes. At ten cities the number of alternate routes has grown to 3,628,800 – try it on your calculator. After that the numbers tend to get a bit steep. A 30 city tour would be 2.65 * 10³² different routes and a 50 city tour results in a number around 10⁶⁴. If you don’t think these numbers are big then consider that most cosmologists think that the universe came into being between 12 and 20 billion years ago. That would make the universe perhaps less than 10¹⁶ seconds old. So if we had started our calculations for the 50 city problem at the beginning of the universe, managing perhaps a few million calculations a second with a “super computer” we would still be far from finished.

So, if we can’t calculate the perfect answer how do we solve these sorts of problems? Some approaches have explored the Cartesian space created by the net of nodes to be visited and applied algorithms to calculate near optimal solutions. Real life problems tend to be tackled by applying suitable heuristics to simplify the problem. Usually some “real world” knowledge needs to be applied to the problem in any case. Mountain ranges, rivers, valleys and coastlines influence route plans for instance. Using the apparent distance between locations according to a map of the South Wales valleys would be a severe error as the deep valleys channel vehicles North and South and preclude East West movements. If you were tackling the problem for a specific journey you would probably look for clusters of calls and then try and find an optimal route between the clusters. You probably would not find the perfect solution but you would find an acceptable one. Finding an acceptable solution is the best one can hope for when attempting to solve the traveling salesman problem.

We have applied Monte Carlo techniques to similar real world problems in the past. Our project scheduling software module has on option that allows the user to explore the options for reducing the elapsed time for a project with a minimal impact upon individual tasks. [The story of every project manager’s life.] Given that many tasks may be undertaken in parallel at any given stage of the project this is a complex problem. Near optimal solutions can be obtained in a few seconds by applying a Monte Carlo algorithm.

We decided to try out the related Evolutionary approach to solving this class of problem. We experimented with the equivalent of a 100 city tour (near to 10¹⁵⁸ possible solutions). In this instance we generalised the problem a little by allowing the evolutionary process to select the start and finish points.

Starting with 100 randomly selected points (we did exclude duplicates) plotted on the screen the software then chose 200 random sequences that included every point. Why 200? We decided to keep the best 100 solutions (for the 100 cities but it was an arbitrary choice) and then use them to evolve 100 new possible solutions. The idea being to run through a number of evolutionary generations – selecting the 100 shortest solutions as the parents of 100 new child solutions each generation. So we started with an initial population of 200.

We decided to allow the evolutionary approach to work on the problem completely blind. We excluded possible mutations that included any objective analysis of the data or had any knowledge of Cartesian space. As far as the evolutionary algorithm was concerned it was just working on lists of numbers – with the numbers themselves having no meaning. Our program measured each potential solution and culled the longest with no additional feedback into the evolutionary process.

The screen shot below illustrates the very random track of the best of the first 200 solutions from a typical run.

Insert 

The numbers marked Longest and Mean on the screen shots are pretty meaningless in themselves but their variations gave us some assurance that our population of solutions was retaining a reasonable level of diversity – we did not want to end up in an evolutionary blind alley.

After a few hundred generations the shortest route is now less that half the original best solution.

Insert 

After a lot more generations we see solutions that are approaching the optimal solution evolve. The shortest route is now only 17% of the original best random solution.

The solution shown above can still be improved but you are now in the area of diminishing returns – how long do you want to wait for a solution that is a percent or two better? It all depends upon the cost of course. If you are planning a production run of thousands of items and need an optimal series of component connections then you might make significant savings by running the process longer. If you have a customer waiting on the phone for a cost estimate then you will want to truncate the search more quickly – but confident you have reached a competitive position.

The examples illustrated are fairly typical – once in a while the process threw up a very good solution indeed but we would not want to mislead you into expecting perfection from this technique although we hope we have convinced you it can come up with usable solutions.

If you develop a similar program yourself and watch the progress of the mutations you will probably share our feelings of frustration when you can see an obvious improvement but you have to wait for the process to find it or (as often happens) an alternative just as effective. It was clear after a few runs that a facility that swapped adjacent pairs of points (cities or what have you) in a sequence would quickly shorten certain typical early features of the tracks. We resisted the temptation to add such ideas to the experiment – we wanted to see what the process could do with no clues about the two dimensional track the solutions represented being fed back into the process.

Our test bed allowed us to apply a range of evolutionary and genetic mutations to the population of solutions. We also created an automated routine that ran through a selection of those mutations in a sequence that we could adapt as our knowledge grew. In general, we found that sequences of different, but small, Evolutionary changes applied over a good number of generations most quickly produced solutions that were near optimal. Our experiments indicated that Genetic Algorithms (in general) did not seem well suited to this class of problem although they are promoted by some as being effective. It may be that our population size was too low to make full use of this approach.

It is statistically unlikely that an evolutionary approach would ever throw up the best solution to a problem of this size – in any case you could not check that it was the best solution – but our experiments did produce solutions that were useful and applicable. Our advice to others considering the development of real world applications would be to combine heuristic and evolutionary techniques. It is our experience that such combined approaches produce results that can not be faulted even by experts in the relevant field.

Adit Software Development

Adit Limited can apply optimised heuristic and evolutionary techniques to your business problems. Cost estimating, factory scheduling and route planning share many common features and Adit Limited can deliver software solutions designed to minimise your costs and maximise margins throughout the production process. Contact Adit Limited to discuss your needs today.

[ Home] [About Us] [Systems] [Software Review]