24th March 2015 · By Lee Jacobson

Solving the Traveling Salesman Problem Using Google Maps and Genetic Algorithms

An ideal way to explore the potentials and pitfalls of genetic algorithms is by applying them to real world data. Perhaps one of the easiest ways to do this is by using the Google Maps API to implement a solution to the traveling salesman problem.

If you're unfamiliar with genetic algorithms, or the traveling salesman problem, then you might find the following links useful:
Creating a genetic algorithm for beginners
Applying a genetic algorithm to the traveling salesman problem

Below I've created a very simple route optimizer which uses distance and duration data from the Google Maps API to find the quickest route.

One interesting thing you might observe is how in real life the quickest route is often neither the most direct, or the most obvious route you might think of taking. In the real world there are many restrictions such as road speed and traffic conditions, which are usually equal in importance to the direction when searching for the quickest route. This becomes clear when optimizing the route for driving, to walking or cycling. If you spend a lot of your day behind the wheel, or on foot, you may even be pleasantly surprised to find yourself a quicker daily route. =)

This demo has been built completely in HTML and JavaScript, using just the Google Maps API and the JQuery library. You're welcome to explore the code using the download link at the bottom of the post.

Loading...
Configuration
Travel Mode:
Avoid Highways:
Population Size:
Mutation Rate:
Crossover Rate:
Elitism:
Max Generations:
Debug Info
Destinations Count: 0

Download from GitHub: https://github.com/leejacobson/googlemaps-tsp-ga

Author

Lee JacobsonHello, I'm Lee.
I'm a developer from the UK who loves technology and business. Here you'll find articles and tutorials about things that interest me. If you want to hire me or know more about me head over to my about me page

Social Links

Tags

Comments

blog comments powered by Disqus