Traveling Salesman with Perl, R and Google Maps

tl;dr: ggplot-nyc && googlemap-nyc && TSP-Map (the Dancer2 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 https://docs.mongodb.org/getting-started/shell/import-data/.

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:

Comments

*