Implementing Traveling Salesman Problem on Google Earth

Just had fun for my project in data Structure and Algorithm class, building Traveling Salesman Problem on a real data about crime records happened in Pittsburgh, USA in 1990. The data consists the location of the crime happened.

The task is building a minimum TSP path and a optimum path using brute force, then implement it into Google Earth by making a KML file.

Here is the data CrimeLatLonXY1990

I tried to run the code for data record 12 to 18.
Beware, since in this task I am comparing Minimum TSP Path (Blue Line) to Optimum Brute Force path (Red Line), the brute force would be running in N! times to compute the minimum path.

So if I choose record 12 to 18, there will be 7 records: 12,13,14,15,16,17,18.

Brute force will test the path for all of the possibilities, which means in this case, there will be 7! possibilities.
I tried to run it for 10 nodes, and it goes crazily slow.  So don’t try it for more than 9 nodes.

source:  GitHub

part 3

Final result on Google Earth.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

by Bliss Drive Review