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
September 5th, 2008 at 07:28
Neat Tool, it really works, but I do have a question: Is it possible to upload an itinerary and download the revised itinerary to i.e. a Tomtom, because it is not quite clear what to do with the end-results.
September 6th, 2008 at 17:33
It’s not possible to download directly to Tomtom. I would usually just print the instructions (since I don’t have a GPS). You can try to click the “toggle raw path output” button and copy the latitude, longitude pairs to your GPS unit, but since I don’t own one, I haven’t tried it.
October 1st, 2008 at 16:28
Nice tool to use for geocaching trips. But I noticed it only use routes used by car. In cities I like to use it for the best route on foot.
Is there a way to calculate this?
October 4th, 2008 at 19:39
I’ve just added options for walking directions and avoid highways to OptiMap. The Google Maps API team added walking directions support last week, so this should be one of the first API sites that use them! It’s one of the more requested features for Optimap, so I know there are some happy OptiMappers out there now
I’m certainly one of them, since I don’t have a car and do virtually all my travel on foot / bike. Now when can we get biking directions in the Google Maps API?
October 5th, 2008 at 09:35
Thanks a lot.
It works very well.
October 5th, 2008 at 09:49
I do have a problem getting a route calculated by adding coordiantes in the “Add by bulk …” section.
After entering the programm won’t calculate a route.
I use the following format: N 51° 48.735 E 005° 14.603
October 8th, 2008 at 20:36
I’d like to get a one time solution leaving from Pueblo, Colorado to all the county seats in Colorado. Would it be possible for you to do this and email me the order? Then I can put it in Google maps. (There are 64 counties.)
Thanks
November 6th, 2008 at 00:46
This is a very valuable tool. Thank you!
One curiousity however. When I include 13 points in the URL, your site makes its calculations and provides the routing and trip summary. When I submit the same 13 points (highlight the url and enter), it recalculates and frequently determines a different route and total trip distance. The differences are a little over 1% in the instances I’ve tried and granted thats within my tolerances but shouldn’t your formulas always return the same values given the same inputs?
Regards,
Mike
November 6th, 2008 at 05:58
Hi Mike.
If you enter more than 9 locations, you get a near-optimal solution. This solution is usually “good enough” for practical purposes. Because of the ant colony optimization technique, which uses random numbers, you can get different solutions on the same input.
November 7th, 2008 at 04:14
I am attempting to write a C# program to be able to “scrape” the trip duration and trip length from an optimized route. However, when I execute an HTTPGET request for a url like:
http://gebweb.net/optimap/index.php?loc0=3166%20Diablo%20Avenue%20Hayward%20CA&loc1=3000%20Sand%20Hill%20Rd.%20Menlo%20Park%20CA&loc2=4440%20El%20Camino%20Real%20Los%20Altos%20CA&loc3=321%20East%20Evelyn%20Ave%20Mountain%20View%20CA
the program just gets the main OptiMap page without the script being executed and therefore the program doesn’t have access to the final output.
Can you offrer any suggesions as to whether it is possible to access this information from a non-browser application?
Thanks.
December 19th, 2008 at 14:16
I get a javascript alert(”604″), When adding points in Dubai, UAE. Does this mean that the roads in Dubai are not incorporated in GMaps yet?
Elsewhere, it works fantastic. Awesome.
Thanks,
Michael
February 12th, 2009 at 21:13
Great app.
One thing I noticed. When Calculationg A-Z, the end point listed in the directions is always incorrect.
For example, add the following zips: 95691, 95624, 94550 and Click Fastest A-Z.
The map will display correctly, but the end point in the directions does not match the end point on the map.
Bug?
February 16th, 2009 at 18:07
Hi Chris,
Yes, you found a bug! I’ve fixed it now, but in the past, A-Z directions would always display the address of the second-last added address (or the lat, lng of the last point, if no address was added). Thanks for letting me know!
Geir
March 4th, 2009 at 17:40
Geir,
A feature request if I may: the ability to change and/or delete entered points.
Here in my corner of Pennsylvania (Pittsburgh), there are a number of places that have the same names (for example, there is a Sewickley borough or township in each of at least four of the surrounding counties…), and sometimes it takes a little fiddling with the input to get Google to pick the right one. So, it’d be nice to be able to remove the ones that Google picks wrong & try again.
Thanks!
March 5th, 2009 at 12:32
Hi! I don’t understand well - Why we can’t use ACO for all 24 locations? Does it call GDirections for every intermediate result? And what do you think about branch-and-bound principle for solving TSP?
Best regards!
March 9th, 2009 at 17:46
Hi! Perfect app. …
One thing that I noticed.
When I click on the marker to remove it from the calculated route it gets removed, but when I press the Calculate… button again, I’ll get the same route and all removed markers reappears.
Would be great, if we could update the route with removing markers not only with adding them or starting over.
Best regards!
March 12th, 2009 at 16:34
Hi Geir,
great super application ! This rocks !
Something I’m wondering about :
how hard would it be to add and extra constraint to the optimal route function, to take into account opening hours of locations.
This would be perfect for a holiday trip (musea, etc..).
Greets,
Tom
March 25th, 2009 at 18:35
When I enter a zip or address and click on Add, it does not add the pin to the map. This was working before.
March 26th, 2009 at 03:28
Hi Chris,
I’ve updated the add function to also center the map on the pin again. Please give it a try again and let me know if the problem is still there.
March 29th, 2009 at 21:46
Hi Geir,
thanks a lot for this powerful app!
i was looking for a long time for something similar!
i have to make deliveries by bike, i noticed if not selecting the walking option gives a 604 error with all browsers (ff iron opera ie), when selecting walking many times it gives you directions against traffic, you know when biking across traffic you must go much slower… so could you please fix it?
do you have any plans to up the limit from 24 to 60 or so?
to add any constraints?
thanks a lot
Michael
March 29th, 2009 at 21:57
btw
i tried printing with latest install of ff iron opera and ff was the best one, opera lacked the blue line of route and iron has not got transparency right.
April 2nd, 2009 at 19:13
Geir,
The clickedAddAddress function is now working again. Thanks!
April 16th, 2009 at 16:45
Hi!
Great tool!
What I’m doing wrong - first I tried to paste 134 addresses into the bulk add -> only 7 addresses were added. Then I tried like 15 -> only 3 added.
Help!
Regards, Gerald
April 26th, 2009 at 06:38
Hi.
I would love to see this in a Mathematica notebook.
Please contact me so we can turn this powerful source into a even more powerful application.
April 26th, 2009 at 07:27
Is the 24 locations limit a google limit? or a processing limit?
May 1st, 2009 at 07:24
I don’t see any response to Mike M’s November 7th, 2008 post. We’re trying to do something very similar. Has anyone had any luck writing a C# program (or other server side app) to be able to “scrape” the trip duration and trip length? We’d like to be able to cache distances from various set points so we know the closest spots to include on a map once the selections are made. Has anyone had luck doing server side screen scrapes to get the mileage info? Anyone have samples they’d be willing to share? Thanks if so!
June 29th, 2009 at 15:31
Can you please share the BpTspSolver.js , directions-export.js files too. I would like to go through these two files.
Please help me. Thanking yo in advance
July 20th, 2009 at 18:06
Terrific site! I love using it for routing jobs trying to determine the best path for trips. Keep up the excellent work and attentive support!
July 31st, 2009 at 19:51
Not working for me, gives a 604 error code with the pop-up.
July 31st, 2009 at 20:49
The 604 error is returned by Google Maps if the directions request for one of the points you entered fails. Could be a point is added too far from a road, or an address that isn’t recognized. Not much I can do about that, except maybe spitting out a more readable error message…
August 2nd, 2009 at 16:27
Beautiful Gebweb! I am currently trying to use it in my databases applications. Is there any chance to get just the trip length back? I was trying to find it in the resulting code but did not.
Any help would be great ! Thanks and keep on with this !!!
September 4th, 2009 at 21:10
Why 30 ants in 30 waves? Isn’t that equivilent to sending out 900 ants?
Are you only updating the pheromone after each wave (using the best tour of each wave)?
… just curious.
September 4th, 2009 at 21:16
Also see: http://github.com/philtomson/ACO/tree/pop_based
for a population-based ACO implementation. Pop-based is a bit simpler: we replace the global evaporation phase with a population of tours in a FIFO. As tours enter the FIFO edges are incremented as they leave they’re decremented - so essentially the pheromone on a tour-edge “evaporates” when that tour leaves the fifo. Also try to use integer math as much as possible in the pop-based ACO so that it will be easier to implement in hardware (FPGA), but that should also improve performance on a CPU as well.
September 24th, 2009 at 01:52
I sent the following addresses, which were assigned to one of our Building Inspectors today (we are in Everett, WA USA) to the Optimap site and ended up with directions that included \”kayak across the Pacific Ocean\”, and ending up in China via Hawaii and Japan. Is there something wrong with my formatting? Any suggestions for getting more reasonable results?
http://gebweb.net/optimap/index.php?loc0=3000%20Rockefeller%20Avenue,%2098201&loc1=3612%20183RD%20LN%20SE%2098012&loc2=3612%20183RD%20LN%20SE%2098012&loc3=3717%20224TH%20ST%20SE%2098021&loc4=3721%20224TH%20ST%20SE%2098021&loc5=4207%20143RD%20PL%20SE%2098296&loc6=4207%20143RD%20PL%20SE%2098296&loc7=4201%20143RD%20PL%20SE%2098296&loc8=16419%202ND%20PARK%20SE%2098012&loc9=1324%20159TH%20PL%20SW%2098087&loc10=15930%2014TH%20AVE%20W%2098087&loc11=1301%20158TH%20PL%20SW%2098087&loc12=1303%20158TH%20PL%20SW%2098087&loc13=3620%20224TH%20ST%20SE%2098021&loc14=22307%2037TH%20AVE%20SE%2098021&loc15=22307%2037TH%20AVE%20SE%2098021&loc16=22307%2037TH%20AVE%20SE%2098021&loc17=123%20195TH%20PL%20SW%2098012&loc18=13924%2015TH%20PL%20W%2098037&loc19=18727%203RD%20AVE%20W%2098012
October 8th, 2009 at 00:51
Hi, just wanted to congratulate you on a fine bit of coding. I looked in the source and it’s very impressive, especially considering the tools available for coding JavaScript. Thank you for making this available.
Nathan
October 15th, 2009 at 06:03
Thank you, just used this to map a business trip to visit 11 of our restaurants in the Phoenix, AZ area. You saved me a bunch of time!!!
November 15th, 2009 at 22:31
Gier,
This is so wonderful! I’d love to be able to display a name rather than the lat/long on the output page. So instead of it saying “34.756658,-92.44785″ it could say “Burger King” (or my text of choice). Perhaps it could be added as an input on the query string, like:
http://gebweb.net/optimap/index.php?loc0=34.756658,-92.44785&name0=BurgerKing&loc1=34.754084,-92.420194&name1=McDonalds
This would really make it helpful when directions are printed out.
Jeremy
November 17th, 2009 at 03:43
Hi Jeremy,
This is a useful idea! I’ve implemented this as an optional parameter to the query string, just like you suggested. This should now work:
http://gebweb.net/optimap/index.php?loc0=34.756658,-92.44785&name0=BurgerKing&loc1=34.754084,-92.420194&name1=McDonalds
Geir
November 18th, 2009 at 16:28
That is FANTASTIC, and the addition of the names make the output really helpful.
November 23rd, 2009 at 16:07
Hi!
The “Add list of locations” button does not work in FireFox.
Why?
Gerald
December 18th, 2009 at 08:58
This is a very impressive implementation, thank you.
Is there a way we can pass URL parameters to specify the map size? A bigger map would be more useful. Also, you appear to be using an older version of the google map… would your implementation work with the newest one (with zoom bar, etc.)?
December 18th, 2009 at 09:00
Ah, disregard my second question… I see you are using the map I was referring to. Not sure what I was seeing before!
January 28th, 2010 at 12:15
This is great!! Is it also possible to add the management of several concurrent vehicles? I had seen something similar on http://apps.viamente.com/demo/ but I soon realized it’s a commercial service. Thanks to the open source!
February 19th, 2010 at 19:51
AHHH…i thought this was going to be awesome. i put several locations in and the map works great…..BUT, when i tried to send to TOMTOM there was a problem. the tomtom tech support tried for 40 min to help but with no luck. the route IS going to my tomtom ONE, however, it is either going to an incorrect subdirectory OR is has formatting issues….can you help?
March 18th, 2010 at 18:47
Load of rubbish! this has only worked once for me. I have spent ages putting in addresses and as soon as I click round trip it just says error 602 or 604. I am only putting in 20 addresses each time too
March 20th, 2010 at 02:35
Are you currently selling or licensing the optimap code so it can be hosted on another location?
April 4th, 2010 at 21:42
What is the best way to add addresses? With a comma after each address etc etc?
April 4th, 2010 at 22:03
The best way is to use the “bulk add by address” link, and add one address per line.
Hope this helps!
April 7th, 2010 at 20:53
Hello. Awesome work! I have a problem in scale of points that need to be routed. We have an operation about 5 times a year that requires hitting our full inventory of bus stops (4000+) and even breaking that up into 4 vehicles workload it is a daunting task to make this work effeciently. I am looking for a technical solution to partitioning uot this workload.
We also have an inspection process where the inventory is broken up by service tiers with equal complexity. Do you have any ideas or suggestions on what I could use to address this problem?
April 19th, 2010 at 07:56
How can I use characters like ä when I’m preparing the string used by your script?
Thank you
May 2nd, 2010 at 12:27
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?
May 6th, 2010 at 16:48
Hi! Cool stuff!
I have a question: On your site (http://www.gebweb.net/optimap/) you say that the solver is available under the Common Public licence now (tsp.js) - is that true for the file BpTspSolver.js as well?
Without it, it does not work, right?!
Thanks, Marc
May 7th, 2010 at 18:27
Hi Marc,
I have updated the text to say that the solver code is available under the MIT licence at http://code.google.com/p/google-maps-tsp-solver/ . This includes both tsp.js and BpTspSolver.js. If you make changes to the code, which you believe are useful, please consider updating the code repository
Also, I set up a mailing group if you want to track any changes to the code. You can subscribe here: http://groups.google.com/group/google-maps-tsp-solver
Geir
May 13th, 2010 at 21:01
I read your behind-the-scenes explanation of the Optimap and I must express that you are providing a great tool for small businesses all over. I found out about your tool through a small business owner when he needed my coding expertise and I passed knowledge of this app to my supervisor. I hope this app lands you many more opportunities if it has not already.
June 9th, 2010 at 00:07
Hi, I found this page via a link from wikipedia (TSP-article). Since I did some playing around with the Wolfram Mathematica demonstration notebook files regarding TSP-solving, which illustrate a lot of usefull insights for a first grip on this material quite nice, though somewhat static, I am wondering whether there would be any sane opportunities of solving the TSP of the following way points of a huge travel to asia that I’m planning throughout the next weeks and, if and then in which way one should/could incorporate the factors of visa regulations and “unforeseen incidents” within an attempt to solving it within mathematica - or however. Just let me illustrate this: My plan is to set out from Frankfurt/Germany, where I currently live and travel along an - in the wider sense - by TSP means OPTIMAL route, ideally also making use of the best possible airline and travel fares. I’m planning to do some [legal] volunteer work along and would like to encounter some great couchsurfing.com-related real life experiences
Perhaps providers of emergency roadside repair/roadside assistance services may have some great experience solving those kind of TSPs that I’m likely to run into - judging by general dynamics, visa/time windows, costs and all. Anyone betting on the power of mere intuition on solving this one?: THE ROUTE POINTS are, unless for Frankfurt/Germany as fixed starting point - in NO order at all, which is the route of this search for a route… -> Singapore; Bangkok; Manila; Ho Chi Minh; Angkor Wat; Phnom Penh; Taipeh; Seoul; Brisbane; Sydney; Adelaide; Melbourne Australia; Wellington; Christchurch/New Zealand; Tokyo. I would greately value any hints given to let me get a better idea of how to solve this enormously complex TSP. Thank you very much. Marc