Using Genetic Algorithms to solve the Traveling Salesman Problem on Bing Maps

A couple of years ago I was really into Genetic Algorithms and Ant Colony Systems, mostly focusing on solving known NP-Complex problems such as the TRP (Traveling Salesman Problem) and the VRP (Vehicle Routing Problem).

As I have a couple of interesting use-cases that could benefit from these types of algorithms what better way to refresh my knowledge than making a simple mapping experiment solving the TRP problem?

Here's a short summary of these concepts:

• TRP - Optimization problem that tries to find the shortest route that passes on all supplied points

• Genetic Algorithm
• There's a population were each element represents a solution to the problem
• The algorithm progresses through various iterations, called generations
• On each generation the various elements of the population mate and create new elements
• The fittest elements survive and the weakest die

It obviously has much more going on than that, including stuff like roulette selection, mutation, elitism, etc.

I'll create a map where the user can input waypoints and the algorithm will find the shortest path.

1. Creating the problem space

I'll simply add a map on which the user can click to add new points. Clicking on an existing point removes it.

Now, drawing a path for the points. This polyline will represent the route to be optimized.

I've actually changed the default pushpin to have one with a centered anchor point

Now I just need the algorithm :)

2. Creating the optimization algorithm

Regarding genetic algorithms, and although conceptually they might look sophisticated and complex, in reality they're incredibly simple. Actually, most of the algorithms based on real-life models (like ant-colonies, genetic, simulated annealing) are very easy to grasp and implement.

Regardless, various JS libraries already exist and instead of reinventing the wheel I've chosen one called "genetic-js". I've never used it before but it does look really cool: clean API, good documentation and a nice set of features.

I'll need to implement:

• a seed function:

Used to generate the various individuals of the population. In this particular case each element will include all the waypoints on a random order.

• a fitness function:

Measures the fitness of an individual. Will represent the total distance of a route, hence the smaller the better. The distance will be, for now, linear, not taking into consideration the driving route. I'm using Vincenty's formulae for the distance calculation.

• a crossover function:

This function represents how two children are generated after two individuals have mated. I'm just going to make a dumb crossover function that just picks a random segment from a parent and mixes it with the other parent. As a side-note this is typically where the algorithm is optimized by using smarter mating strategies instead of just relying on chance. These are called "greedy" implementations vs "pure" ones.

• a mutation function:

There's a small probability of an individual simply mutating. This function represents how that will happen. I'm going to do a basic mutation function that just swaps random points of the route. Similarly to the crossover function, the mutation function also benefits a lot from greedy approaches. Anyway, not really the scope of this post to create an optimized algorithm so the random version will do.

Also, some additional parameters should be set, mostly around probabilities, selection logic for mating, etc.

To trigger the process I've added a simple button and a couple of labels to update the progress.

Now, testing the sucker:

Initial setup with 20 points

During the Execution

Final Route found

The current algorithm typically takes a lot of iterations (generations) to reach good solutions. There are very detailed studies on proper crossover and mutation functions to achieve good TSP results. Eventually I might update this sample to improve the algorithm, but for now you can test this live as-is at: http://psousa.net/demos/bingmaps/trp/