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.
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
Manuel
Nov 19, 2012 @ 22:47:24
Hello, I’m working on a university project which involves calculating drive distances.
I tried to review your tspsolver.jar without success, could you specify which SDK did you used to create it?
Thanks!
Manuel.
Matteo Catena
Nov 20, 2012 @ 16:57:10
Dear Manuel,
tspsolver.jar has been created using jre 1.6. (Please note: you can “unjar” it, there is the source code in it.)
TSPWeb has been created using java 7.
What is the error that you’re receiving?
Hi Matteo Catena
Oct 07, 2014 @ 15:25:33
Now we are talking..Finally I see a SOLUTION for the so much discussed PROBLEM, the TSP.Though a bit dis-heart-ned, coz I can’t download or execute the code you have shared.
Hey bro, please help me with it. I am a 2nd year graduation student, I need your code as a start point. I have an idea for a project that I can base on your work.
TSPWeb.war available above for download: what is .war extension. I made it .rar and extracted. But the trick failed. The decompression software reported an error.
Please help me in setting this up on my machine. Plz…
Time is running bro, need to submit my project in 2 weeks. We Indians have always be the 11th hour rushers. But if I am able to set up your code, it will be a ride ahead…
Hope to hear back from you…
Regards
Parth K.
Matteo Catena
Oct 07, 2014 @ 16:27:46
.war is Web ARchive. You can deploy the archive in a Tomcat server to run it. Alternatively, You can easily uncompress it in Linux. Under Windows, you may need third party software. 7zip seems to do the job (http://superuser.com/questions/133295/how-to-open-a-ear-war-file-in-windows-7), but I haven’t tried. Once you’ve decompressed it, you’ll find a .jar containing the specific TSP code. Good luck with your project!
Matteo
Hi Matteo Catena
Oct 07, 2014 @ 17:40:42
loads of thanks brother.
hope you are around if I get stuck somewhere…
thanks to my savior
you made my day!
have a plate of butter chicken and a can of beer…
bill is on me!
Cheers!
Luca R
Feb 06, 2015 @ 19:25:40
Quote from your google dev link:
“The Distance Matrix API has the following limits in place:
Users of the free API:
100 elements per query.
100 elements per 10 seconds.
2 500 elements per 24 hour period.”
Perhaps something was changed since 2012, when you wrote this article! Does your program accept multiple addresses up to 100 now?
I’ll try your code asap!
Ciao e grazie!
Matteo Catena
Feb 07, 2015 @ 11:03:21
Ciao Luca,
the node limit was not on the distance matrix but on the graphical map.
The underlying tsp solver should work ok with hundreds of points. But I have no idea if the map will draw those and the resulting path.
Let me know!!
Luca R
Feb 12, 2015 @ 19:55:37
Ciao Matteo.
Now I see what’s the problem. Could you upgrade your code to print only the ordered list of waypoints, if they’re more than 8?
I’ve got no success trying to modify your source code: unfortunately I’m not able to work on java servlet yet now.
Luca
Matteo Catena
Feb 22, 2015 @ 21:49:47
Ciao Luca,
sorry for this late answer.
You don’t need to work with servlets to do what you need. Inside the downloadable archive there is a .jar containing the TSP solver and its code. You can modify that. Good luck!