Behind the Scenes of OptiMap
What really happens when you hit the ‘Calculate fastest roundtrip’-button in OptiMap? The problem we attempt to solve is a classic and is called the ‘Travelling Salesman Problem’ or simply TSP.
Before we dive into this intrigueing question, some definitions are useful. Each location will be referred to as a node, with location number 
denoted 
. There are 
nodes in total. The trip between a pair of nodes is called an edge, and the trip from node 
to 
is denoted 
. The full set of nodes and edges is called a graph and is denoted
.
We note that in the context of driving directions, there is either a way to go from each node to all of the other nodes, or there is no way to reach that node at all. We will assume that there is a way to reach all the nodes, otherwise there would be no solution at all. For ease of notation, we say that the time it takes to traverse an edge is 
.
Another characteristic of the problem we try to solve is that the time associated with an edge is not necessarily equal to the time associated with its reverse edge. This is the result of for instance one-way streets and that it’s easier to turn right than left at an intersection. Thus, our graph is directed.
The first part of solving the problem is defining it. We seek to find an ordering of the nodes, starting and ending at node 1, that visits each location exactly once. This ordering should minimize the total time it takes to traverse.
There are 
possible roundtrips that visits each location exactly once. Evaluating each possible roundtrip, a so-called brute-force approach gets infeasible between 10 to 20 nodes, depending on your patience and hardware. Actually, all known methods of finding the optimal solution use resources exponential in 
.
With 9 or less nodes, it is feasible to write code in JavaScript. So in this case, you get the optimal roundtrip.
If we’re willing to settle for near-optimal solutions, a number of methods are available. These are called heuristic methods. The simplest of these methods is to always travel to the unvisited node that is closest to the one you’re currently at. This method is referred to as ‘Greedy’ in the performance results below.
There are better methods. ‘Ant Colony Optimization’ is one of them. Inspired by the way ants find food in nature, this method uses a swarm of ants, each of which is fairly dumb, to find an intelligent overall solution. Real ants leave pheromone trails when they walk. They can also smell these trails. If an ant finds food close to the ant colony, this trail will be traversed faster than the others and have a stronger smell, because the pheromone dissipates over time.
By letting virtual ants walk randomly around in the graph, we get roundtrips. The ant roundtrips are evaluated by the time they took to complete, with faster roundtrips being assigned a stronger smell. An important question is how the virtual ants choose which nodes to visit next. Probabilities are assigned to each edge going to an unvisited node, depending on its assigned time and how smelly it is:
Here, 
is the smell assigned to edge 
. The ants pick edges according to these probabilites. The constants 
and 
can be used to fine-tune the performance of the ant method.
Another trick which is called k2-opting is used when an ant has completed its roundtrip. We pick two edges of the tour, and see if the edges can be swapped to create a better tour.
The k2-opting procedure is repeated until no two edges can be swapped to create a faster roundtrip. k2-opting is a cheap way of improving many TSP heuristics.
Performance:
| Test Case | Optimal Solution | Greedy | ACO | ACO k2-opt |
| n = 10 | 28 167 | 34 011 | 28 563 | 28 167 |
| n = 11 | 28 294 | 29 758 | 29 542 | 28 294 |
| n = 8 | 25 310 | 26 515 | 25 310 | 25 310 |
| n = 12 | 36 204 | 41 211 | 39 404 | 36 204 |
| n = 12 (Paris) | 11 141 | 12 705 | 12 062 | 11 141 |
| n = 12 (Berlin) | 10 570 | 11 429 | 11 789 | 10 570 |
| n = 12 (N.Y) | 7 608 | 8 714 | 8 361 | 7 608 |
| n = 12 (London) | 4 729 | 4 845 | 5 220 | 4 729 |
The numbers are in seconds. The ACO column is with 30 ants and 30 waves, the k2-opt ACO column is with 10 ants and 10 waves, to make up for the extra computation needed to do the rewiring. The results suggest that the current method should find roundtrips very close to the optimal.
July 19th, 2007 at 23:51
[…] tricks, its also no easy task for a comuter to solve, but with some clever maths (more on the authors blog!), its possible for a computer to have a good stab at it. Anyway try it […]
July 20th, 2007 at 10:41
Excellent! I’ve been trying to develop something like this, but alas, without a degree in Mathematics, I couldn’t. Any chance of you releasing the code
I have a site in development that could take the web by storm if this application was included.
August 7th, 2007 at 12:51
An excellent work. I guess VRP implementation will be your next move? Do you think that this project is appropriate to be a final year project for a non-CS student?
September 17th, 2007 at 01:58
Hi,
My question to you relates to Gmaps API group discussion threads titled “Mapping multiple destinations/drivetimes and finding the best routes”, with the URL:
http://groups.google.com/group/Google-Maps-API/browse_thread/thread/1c06b074b61e8b5/f45141eb5fe579cd?q=%22optimal+route%22&rnum=5&lnk=sbp#f45141eb5fe579c
In particular regarding Mike’s posts saying
“You’re not currently allowed to automate the routing from Google, so you’d have to make those 55 requests manually.”
and in the next post on the same page “The Google route finder only plots routes from X to Y, not X to Y via some intermediate points. All you need to do is to sum the durations of the chosen segments.”
I wish to ask you how then it’s possible to apply Optimap or its enhancements -when this is assumed to be true- with which you can create an optimal loop for up to 9 cities, as you mention. Is there a restriction to develop this on the part of Google?
can, for example, routes from a fixed startpoint to possible connection points be compared and the nearest point with distance infos be displayed, followed by suboptimal, farther points?
if everything with further improvement on your map were ok and feasible (is it?) how far are we from delpoyment of multiple route evaluation for large number of points and routes?
thank you very much for all your information,
best greetings,
berat
September 17th, 2007 at 04:14
Hi Berat,
I read the Google Maps API terms (http://www.google.com/apis/maps/terms.html) fairly well when I signed up, and I read them again today. There does not seem to be anything in there that prohibits my TSP solver.
The 55 requests (actually 110, since the trip from A to B is not always the exact opposite of the trip from B to A) are well within the limit of the 50,000 geocode requests that Google allows daily. This request limit might be a problem if you want to find routings for a large number of points, since you need to know all pairs of distances, i.e for 200 cities, you need to make about 40,000 requests.
Another limitation is that your application has to be publicly available to anyone free of charge. If you intend to use this application for your business, to schedule your deliveries (or whatever), you need to be aware that anyone can use up your daily quota of requests, and then you might not be able to use it for yourself!
The algorithm I use for more than 9 points delivers a solution that is usually very close to optimal. This algorithm can easily handle 200 points, but the request limit will not handle it. This is why I restrict my solver to 20 points.
I do not know how Google’s internal systems work, but I would think that there is little stopping them from making optimal routing for a small number of destinations (say 9) publicly available in the official Google map application.
To answer your last question, the Google daily request limit and the requirement that the application be publicly available without charge, makes multiple route evaluation for large number of points impossible with Google Maps API. Sorry for that.
-Geir
September 24th, 2007 at 10:53
Hi Geir !
in case you are interested in doing custom programming for a austrian company then please get in touch with me so I can provide you with the details.
hubertus hiden org
Many Thanks,
Hubertus
October 31st, 2007 at 12:13
Hi Geir
May I congratulate you on a great app.
I’m in the UK and wondered how I could get your app working with UK postcodes. eg try typing in MK18 1BP or MK18 1BP, UK and it doesn’t work. but these (like all other UK postcodes) work well on google maps normally.
any help or guidance would be much appreciated
thanks
Tim
November 2nd, 2007 at 16:25
Hi,
To answer Tim’s query, this is due to a change in the way Google geocodes UK postcodes which happened last week. Currently it only looks at the first half of the postcode so isn’t very useful. See the thread below for more details:
http://groups.google.com/group/Google-Maps-API/browse_thread/thread/c8808fb120f128e2
I am trying to call Optimap from another webpage using the syntax below but don’t get offered the Calculate Route option:
http://gebweb.net/optimap/index.php?loc0=Fairmeadow,%20Winslow,%20MK18&loc1=Leckhampstead%20Road,%20Akeley,%20Buckingham,%20Buckinghamshire&loc2=St.%20Michaels%20Way,%20Steeple%20Claydon&loc3=Verney%20Farm%20Close,%20East%20Claydon,%20MK18
Can you advise what I am doing wrong ?
Many thanks and great app!
Lucy
November 4th, 2007 at 21:03
The calculate route option should not be displayed, since the route should automatically calculate when called like that.
When I click the link you posted above, I do get the right route calculated right away. Can you post some more info about your browser / java script error messages etc.?
Best regards,
Geir
November 14th, 2007 at 13:11
Hi Geir,
Thanks for the response, apologies for the delay on my side. I am using ie version 7. The javascript error is line 262 char 3 dur…[].0 is null or not an object.
regards
Lucy
November 15th, 2007 at 04:18
Hi again Lucy,
I think I’ve resolved the issue. It would nice if you could try it again and confirm this (be sure to shift-click your browser’s refresh button to make sure it loads the new files).
Geir
November 27th, 2007 at 11:34
Hello,
When I fill in 4 targets 1,2,3,4, you promise to return the optimal result. But the result gives me a trip 1-2-3-4-1, even if 1-3-2-4-1 is shorter and faster (I compared it by putting 1-3-2-1 in this order into your tool).
This means that google calculates the optimal rout for 1-2-3-4-1, but your tool does not calculate changed orders.
Is this a bug?
December 2nd, 2007 at 22:02
Yes, there was a bug that made it not compute anything… Embarassing!
December 4th, 2007 at 13:54
Great work! Just a few days ago I was talking about this with a friend… and as usual, once I started digging for more info, I found your site.
Really cool! Thanks for explaining how you got it working.
December 16th, 2007 at 00:43
Great! Now, for the holidays, I wish the user interface could allow:
start/end: (home address)
places:
best buy
radio shack
sears
target
safeway
Then, dump the instructions into a multiple destination google maps page.
Thanks again!
December 17th, 2007 at 00:41
Holiday shopping routing is certainly a possibility (I’ve used the solver for that purpose myself). I’m probably not going to implement what you’re describing myself, but others are now encouraged to find new uses for the code and implement those themselves. The code is now open source!
December 27th, 2007 at 06:57
A very good tool! Could it be extended to work with different beginning and end locations for a journey? Here are a couple situations where this could be useful.
1. Say I go to the office and pick up destinations I have to visit that day but after my last stop, instead of going back to the office, I go home.
2. Another case is where I initially have the same beginning and end locations for a journey but after making some initial stops, some later stops become canceled. It would be nice if you could then re-compute a new route from my current stop location to the end location that takes into account the changes that result from stop cancellations.
Thanks.
February 4th, 2008 at 21:56
I was looking at your code and was wondering 2 things:
1) How hard would it be to include it on my own page so as not to hammer your API key and servers? (eg what would I need set up)
2) I noticed you had a carpool function (I assume it does an open TSP), how could I go about using that?
By the way, great work on the problem. I wrote one of these in Perl a few years back for a CS class, and the algorithms are quite a challenge.
May 6th, 2008 at 16:58
Hi, I second the previous comment about different starting and ending points. This is a related problem to TSP. A minimum Hamiltonian path allows TSP as a special case. i.e. where the cycle is closed. It would be useful tho have two possible scenarios. a) starting and ending points are pre-selected. b) starting and ending points are let to emerge.
June 5th, 2008 at 13:41
Hi. That’s properly an ace little application you’ve written. Would there be any way of making it so that you had an a->z route, with way points along the way which could be in any order? The idea being for pickups on the way somewhere (gigs in our case), deciding which route is quickest order to pick everyone up in, before going to the gig. That would be really ace.
Cheers for the app- you’re a legend!
m
June 14th, 2008 at 23:19
A few of you have asked about different start and end locations. This functionality is now available if you hit the ‘Calculate Fastest A-Z route’-button. Also, I’ve upped the limit on the number of locations from 20 to 24.
June 25th, 2008 at 21:34
Olá
Quais os arquivos necessários para colocar no meu site.
Não estou conseguindo reproduzir o index.php
Obrigado
Hello
What the files needed to put on my site.
I am not getting the play index.php
Thank you
June 26th, 2008 at 15:43
Olá
Coloquei o directions-export.js , tsp.js, index.php e o import.php no site, o index.php está funcionando ok, mais o import.php não está funcionando.
http://www.zlink.com.br/optimap/index.php?&loc0=-7.1209077392192785,-34.9075984954834&loc1=-7.121418750873643,-34.903221130371094&loc2=-7.128828355854018,-34.93025779724121
Eu pergunto, preciso colocar mais algum arquivo ou alguma outra funcionalidade no meu site para o import.php funcionar correto.
Grato.
June 26th, 2008 at 15:54
Correção:
O index.php e o import.php estão funcionando, mais quando eu disparo o link abaixo, o index.php não mostra os pontos. Eu pergunto, preciso colocar algum outro arquivo no meu site.
http://www.zlink.com.br/optimap/index.php?&loc0=-7.1209077392192785,-34.9075984954834&loc1=-7.121418750873643,-34.903221130371094&loc2=-7.128828355854018,-34.93025779724121
June 30th, 2008 at 19:40
Hi, Geir, congratulations, this tool is excelent! I´m from Brazil and the last time I used the optimap there was an option to copy up to 20 lat, long at once. Now, I couldn´t find it despite the anounce made that is possible to route 24 points. The option is still avaiable?
Thanks a lot. Mariana.
July 2nd, 2008 at 22:22
Oi Mariana
Veja como usar no link abaixo, tem vários exemplos.
http://gebweb.net/blogpost/2007/08/26/optimize-your-trips/
Ricardo
July 16th, 2008 at 03:02
Mariana, the functionality to copy many latitude, longitude coordinates at once is back. Click on the link labeled ‘Bulk Add by Latitude, Longitude’ and then paste your coordinates into the solver. When the results are computed, you have an option to show the raw coordinates of the optimal path right above the driving directions.
July 25th, 2008 at 14:42
Geir,
This is a very impressive application of the TSP. I was wondering if you thought it could be adapted for the Orienteering Problem (OP), aka the Selective TSP, where the salesperson doesn’t have to visit every point, but needs to be back at base in a certain time, having maximised the value of the trip. Each point would have a differing value.
The reason I ask is I’m currently studying if it’s possible to come up with an optimum route for real life orienteering races, where racers have a set time to maximise their score. This would be a fun addition to post-race discussion, where the winners could compare their actual route with the theoretical optimum route, hopefully learning from the process.
I may have a go at tweaking your Javascript, e.g. to use a standard “running pace” for the duration, rather than Google’s GDirection durations. But I was wondering if you had any thought on how easy it would be to adapt OptiMap for the OP.
Thanks,
Ollie
July 28th, 2008 at 04:13
Hi Ollie,
I was an active orienteering runner for 10+ years - that’s why I’m a maps-person
Not that many races actually allow you to pick some points to visits and some not, or even just re-arrange the order of your trip (provided they use e-timing).
My first intuition is that the problem will yield relatively well to Ant-Colony Optimization, even though I haven’t tried it. The harder part is the forest part. Google Maps doesn’t give you directions in forests
It does provide walking directions these days (launched last week: for trips of distance 10 km, there will be a link to show walking directions instead of driving directions). I haven’t checked whether it’s available in the API yet…
Assuming you have boring forests without too many large impassable obstacles (not the kind we have in Norway), you can grab the distance between the points and assume constant speed of the runner. I don’t think this application will be too interesting before we get orienteering-precision maps in Google Maps, though.
July 30th, 2008 at 17:26
Very cool, Geir! A question and two wish-list suggestions:
1) I have noticed that if the user copies in more than the threshhold of 9 locations, so the heuristic algorithm is triggered, different runs of the application will produce different routes. (I understand that any given route is not guaranteed to be optimal, but I don’t understand the random behavior.) Could you explain that for the mathematically challenged?
2) If you were to add generalized functionality for an optional string label, perhaps delimited by parenthesis, to each line of the bulk-load
July 30th, 2008 at 17:32
Apologies. My post got truncated. Here is the rest:
2) If you were to add generalized functionality for an optional string label, perhaps delimited by parenthesis, to each line of the bulk-load coordinates, that would be hugely useful in the result.
3) The ability to print or copy just the map window after panning/zooming would be great. Some routes need multiple graphics of small areas to illustrate them.
August 4th, 2008 at 23:33
I tried to upload a coordinates list, but without success. Probably becaus I run on linux, which does not send a \n between the lines?
August 5th, 2008 at 10:46
Hi,
Does this work for any location, we have similar requirement for a site in India. Can we use this for India?
Thanks
Arun