Traveling Salesman with Perl, R and Google Maps

tl;dr: ggplot-nyc & googlemap-nycTSP-Map (the Dancer app)

One day I decided to glue-together a couple cool Perl modules and the visualization capabilities of R to generate a map of locations and the computed path of a traveling salesman (TSP) – who in this case is a restaurant critic.

The prerequisite is to have MongoDB installed and loaded with the freely available restaurant test data at

With that data loaded, the first thing is that the program loads essential perl pragmas and CPAN modules:

Next, handy variables are declared and initialized.  This includes getting the MongoDB database configuration with YAML and using it to instantiate a new mongo client object:

Here is creds.yaml by the way:

With those set, a database query can be made to select the restaurants to inspect:

The next set of steps is the traveling-salesman logic.  The selected restaurant address coordinates are added, the TSP algorithm is solved and the resulting polygon centroid (“center of gravity”) of the points is found:

Now the coordinates are mapped with R, to a PNG file, with the excellent ggmap package:

Next, some R variables are declared (i.e. latitude/longitude vectors and the data.frame to plot):

Now, the map is generated based on the polygon centroid computed earlier:

Finally, the R graphics device is closed and the perl-R session is stopped:

Here is the output of the program for Manhattan grade-A restaurants with a rating of 70 or higher:

And here is the map that is produced:

(I can’t seem to figure out how to make the map larger, yet. And adding get_googlemap(…, size = c(x,y)) is not the answer. Grrrr)






UPDATE: I have found a much better way to render a map!  (Updated code here.)

This code throws out R in favor of the perl module HTML::GoogleMaps::V3.  Instead of generating a small PNG, the new code makes an HTML file with a handy Google Map.

Ok.  After the code above, up to the TSP algorithm solving, we find the path centroid as before:

Next comes the beginning of the updated logic:

Then we add markers to this map, for each optimal coordinate in order.  Also the path is added to the map:

Finally we print-out the resulting HTML to save to a file:

This is run as:

Here is a screenshot of the resulting map:








Note: Although not reflected here, the updated code includes output of the optimal path, directions to each waypoint, and the driving directions for the whole route!  Here is a screenshot of the route driving directions map: