A Java TSP solver which uses Google Maps API

During my studies at the Web Technology Master, I had to do a J2EE web application as exam project. I chose to do an application that manages technical interventions of a company. One exam’s request was to mash up the application contents with contents from the web. So I decided to implement a functionality which tells the technicians what is the shortest route in order to visit every customer with technical problems and to go back to the company’s headquarter.

This was clearly a TSP problem. I solved it using Google Maps API and refactoring Dr.René Grothmann’s Travelling Salesman Applet.

www.nicecode.eu's TSP solver

A screenshot of the example application

Basically, I wrote a class called GTspService from which you can call the method calculateRoute(). This method takes as its only parameter a collection of String that represent the locations to visit (you can use the name of a city or a complete address). The first element of this collection should be the origin of the route. As result, calculateRoute() returns another String collection that represent the order in which you should visit the locations to have the shortest route.

It’s easy as doing:

Collection<String> locations = new ArrayList<String>();
locations.add("L'Aquila");
locations.add("Pescara");
locations.add("Milano");
locations.add("Bologna");
locations.add("Firenze");
locations.add("Napoli");
locations.add("Lecce");
locations.add("Torino");
locations.add("Venezia");
locations.add("Palermo");
TspService tsps = new GTspService();
Collection<String> route = tsps.calculateRoute(locations);
System.out.println(route);

The result:

[L'Aquila, Napoli, Palermo, Lecce, Pescara, Bologna, Venezia, Milano, Torino, Firenze]

GTspService use GoogleMaps API to obtain the locations distance matrix and then gives it to Dr.Grothmann solver, which actually calculates the route.

Since you shouldn’t use Google distance matrix service in applications that don’t show a Google Map, I’ve encapsulated my code in a simple web application that you can find attached to this post (you’ll need a servlet container like Apache Tomcat to make it works). Unfortunately, Google Maps direction service permits you to draw up to 8 locations, not much for a TSP problem. However, my application can still work as a proof-of-concept if you find a service to use instead of Google Maps distance matrix. The actual TSP solver, in fact, works just fine until you give it any distance matrix, its source doesn’t matter. You can find the core code under the directory WEB-INF/lib/tspsolver.jar of the attached .war

Download the code: TSPWeb.war