Sunday, May 3, 2015

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.