Optimize Your Trips
A while ago, I made OptiMap, a Google Maps mashup that will take a number of locations and give you the best way to visit all of them. By best, I mean fastest. Since then, I have been exposed to various ideas on applications for this tool. One is in the real-estate business, where prospective home buyers want to visit a number of houses for sale.
To make things easier for anyone interested in applying this tool, there is now a way for your website to make search requests automatically. This is done by sending a http GET request to http://gebweb.net/optimap/index.php?loc0=start&loc1=dest1&loc2=dest2. Here, start should be replaced by the address or (latitude, longitude) pair where your trip starts and ends, and dest1 and dest2 each should be replaced by either an address or a (latitude, longitude) pair you want to visit.
Up to 20 locations can be specified in the variables loc0, loc1, …, loc19. Remember to http-encode any whitespace etc. in your address strings. This is done automatically if you use the html form element to store your data. Example:
<form NAME="roundtrip" METHOD="get" ACTION="http://gebweb.net/optimap/index.php">
<input NAME="loc0" TYPE="text" />
<input NAME="loc1" TYPE="text" />
<input NAME="loc2" TYPE="text" />
<input NAME="loc3" TYPE="text" />
<input TYPE="submit" VALUE="Submit" />
</form>
In some applications, you will not want the user to be typing in addresses himself, so the html form hidden input element may be more suitable than the text input element. The value of such an element can be set with php when the page is created. It can also be changed with JavaScript, with the following code (assuming the form is called “roundtrip”):
document.roundtrip.elements["loc0"].value = "2 Bloor St West, Canada";
document.roundtrip.elements["loc1"].value = "(37.4419,-122.1419)";
If you have any comments, bugs or feature requests, please leave a comment on this site 
September 21st, 2007 at 15:45
hi, can i contact you via email, i am looking for upto 60 points for an optimised route ?
October 28th, 2007 at 01:02
Great tool. Very cool! Works great when I use it from gebweb.net. I was trying to call it from another web page using your sample code
http://www.greenthmb.com/route.htm
When I input four locations and push submit they are properly displayed on the map but there is no route calculated. What am I doing wrong?
Thanks
Keith
December 9th, 2007 at 14:27
Hi, I really like your page — it’s a great tool. I just have two requests/suggestions:
-Be able to change the default view to a zip code or city
-Some sort of print option so that the map is still displayed. As it is, printing will only print the directions, not the map.
Thanks! Russell
December 14th, 2007 at 21:22
very nice tool, i am only missing the navigation export
December 17th, 2007 at 00:44
There is navigation export to some extent. The page http://www.gebweb.net/optimap/import.php will give you a text field with exported latitude, longitude pairs.
Also, for mobile users, I am pleased to confirm to you that OptiMap works with the iPhone and the iPod Touch.
December 18th, 2007 at 05:18
Once a route is mapped you are forced to click the ‘Start Over’ button. What if I want to add more locations or remove locations to and from my list? I have to start over again. It would be nice to have a ‘Map Route’ button NEXT to the ‘Start Over’ button instead of having the ‘Start Over’ button replace the ‘Map Route’ button.
Also, it would be great if I could arbitrarily decide which node is the starting node
Being able to decide which node is the starting node at any point would be helpful.
Other than that I have only minor suggestions because this is VERY helpful. I actually use it to map deliveries.
Rob
December 31st, 2007 at 09:14
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.
January 2nd, 2008 at 23:22
I case anyone is interested, the non-roundtrip version of the traveling salesman problem, which has different “start” and “end” stops and involves finding the shortest path through a series of stops in between with only one visit per stop is called the “Hamiltoniam Path Problem.”
January 14th, 2008 at 03:14
Russell was asking about printing. I now got it working fairly well. To print, use your browser’s print function (CTRL-P) as you normally would. I recommend using the Opera web browser for optimal results, but Safari works well too. Firefox cannot draw the line that represents the path in the map. As far as I know, no one has gotten that to work for FireFox yet (short of Google, who use a server to generate an image of the map when you click print).
I don’t have Internet Explorer, so please let me know how it works there.
January 15th, 2008 at 06:52
Also added functionality to set default map center and zoom level: Use http GET variables center and zoom, e.g http://gebweb.net/optimap/index.php?center=(60,10)&zoom=5
January 22nd, 2008 at 05:19
Dear Geir,
I am very interested in your optimap technology. Do you provide program consulting services? I am interested in creating a social network using Google Maps and I need help with the development. Please let me know. My email address is (deleted)
Best Regards,
Jeff Torborg
March 10th, 2008 at 17:28
When using the GET request via URL or a form with Safari (v5523.15) it seems to be randomly choosing the start node, and setting loc0 to a random node. Firefox does not seem to have the same problem.
Great tool, thanks.
Max
March 26th, 2008 at 01:25
Fantastic! However, on my map, the purple/blue route line is shifted several inches over. Do you know why? Thanks!
March 28th, 2008 at 17:30
I just have to say, it’s awesome when you come across exactly what you’re looking for and it turns out someone built it just because they’re intelligent and found it interesting. Many thanks for this!
May 25th, 2008 at 17:41
Great tool, is it possible to get it to calculate the shortest rather than the fastest
May 29th, 2008 at 10:26
I try to use your fantastic library on our website and have two little problems.
1. When I add a new location only the shadow of the marker is displayed.
2. Inernet Explorer says “GMap2 is undefined”.
Everything else is working. Thanks a lot, for that great work.
June 1st, 2008 at 22:58
Hello,
I just published a review of your tool on my new blog that focuses on the REO agent community. You can find it here: http://reopro.ning.com/profiles/blog/show?id=2122473%3ABlogPost%3A1538
Of course I have given you credit and back links to both the tool and your parent company.
MY question, which I raise in the blog is saving the image. Is there any way to save the image with the pins. Would it be possible to add the address to the pin?
As an REO AGent, we need to provide reports to the lenders who own the properties and they like to see where the comps are and this would be awesome.
Perhaps you can leave your comments on my blog, this way I know I’ll see it when you answer.
Thanks for a great tool. Let me know if there is anything else I can do to help promote the tool.
John
June 14th, 2008 at 23:01
A few of you have asked for different starting and ending positions. This is now implemented, with the “A-Z” route option.
June 18th, 2008 at 00:19
hello, I was wondering if you were able to get this file directions-export.js and send it to me.
June 18th, 2008 at 16:00
never mind about the file, how does TomTom work, is it free. That’s what you use to get the computed data, it gives the directions? is it free to use TomTom?
July 1st, 2008 at 20:53
It seems that the route always goes in the order I place the points on the map and not the optimal route. Am I doing something wrong?
To test my theory, I clicked on the East coast of the US, then California, then the middle of the US.
Surely the optimal route would go from East Coast, to the middle to California, but your porgram goes East Coast then California then the middle of the US.
Cool interface and idea, let me know if I did something wrong.
August 7th, 2008 at 10:54
Hello Gier,
This is Arun from India. We have a similar requirement to be done for India. Will this work for India also? Please help me out in this.
Regards,
Arun
August 29th, 2008 at 23:04
Great tool. Thank you THANK YOU THANK YOU!
Is there a way to get the optimized route downloaded to a Garmin GPS? Mapquest allows a download to Garmin Communicator, but Google does not.
would love to be able to send a list of addresses to your Tool, have the route optimized then load the right order to see the properties into a garmin gps.
Thanks for a great job!
Steve
September 6th, 2008 at 16:25
There’s currently no way I know of to download the route to a GPS device. You can click the “Toggle raw path output” after you’ve computed a route in Optimap, and enter those lat, lng coordinates on your device. That’s the best I know of right now…
September 22nd, 2008 at 15:29
Hi Geir,
I really love the idea of OptiMap and I would like to implement its possibilities into my Tyre application.
Tyre is a tool for creating and editing itineraries and POI files for use in TomTom devices.
Several people have asked me to provide a new Tyre feature like OptiMap.
Would you please contact me to discuss this issue?
Kind regards,
Jan
September 22nd, 2008 at 22:58
Hi Geir (and others),
We found OptiMap to be a perfect fit for promoting “chaining trips” to save on gas and reduce emissions while running errands in your car. Here’s how we changed the interface for our site:
http://www.smart-trips.org/tripchainer.php
I’m wondering if there is some way we could add “avoid highways” from the Google API to the tsp.js to allow for people making trips by bicycle?
Thanks very much for the excellent web application!
-Brady
October 4th, 2008 at 20:06
I’ve just added options for walking directions and avoid highways to
I’m certainly one of
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
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 13:54
Hi,
I’m trying to use the js api, but the following method fails as described:
Input of the page is generated by a J2EE Servlet:
4029 Debrecen Malomköz utca 4
2314666
October 15th, 2008 at 04:09
Thank you for publishing this wonderful tool. I do have a quick question, maybe I’m missing something so I thought I would ask. My business requires me to decide on jobs all over the state that are completed in one or two days. Before we accept the jobs we map it out to see if it’s too far within our route. So I usually put up to 15-20 addresses, then I look at the map and wonder if the route would be considerably better if I drop one of the locations that doesn’t flow in our route very well. Anyway the tool requires me to re-type all the addresses again without the one I’m trying to drop, and it takes a really long time, especially as I’m playing around with the routes. Is there a way to save the addresses? Or even to just save them for the the current search. Sometimes it will also pull the wrong address (ie I got an address in Ohio) which of course was not in my route for New Hampshire, and I didn’t know it had that error until I had already mapped it out. So is there a way to save addresses or delete ones that are on a list?
Thanks again, either way this is a huge help and I appreciate the use of the program.
Regards,
Mary
October 20th, 2008 at 14:08
Superb tool!
We’d like to use itl to provide a way to visualize and optimize round trips for nurses who visit patient at home. Your tool works perfectly.
We plan to build the URL using visits planned in our system and patient addresses. To provide a very usefull tool, we’d like to personalize the icons on the map by adding the patient name by example. As result icon of the address will be named “1 John” instead of “1″
Do you think it is possible ?
Regards,
Pierre
October 26th, 2008 at 04:40
Mary: I just added functionality that allows you to add a list of addresses in the ‘Bulk add’ text area. I suggest you save your addresses to a text file, one address on each line, and copy-paste it into the ‘Bulk add’ field in OptiMap. You can then experiment with removing each address from the text area.
Pierre: The icons are png graphics files, and are not easily changed. It’s possible to use the standard google text blobs, but they are rather big and clumsy. If you can find some webpage that has Google maps icons that look the way you’d want them to look, you can forward the page to me and I’ll see what I can do.
October 29th, 2008 at 15:24
Hi Gear,
Thank you for your answer. I will try to find some example of icons.
I have now a new problem. When I try to use an http call (By example : http://gebweb.net/optimap/index.php?loc0=av de la gare 10,Sion,Suisse&loc2=rue du scex 32,sion,suisse&loc3=place du midi 28,sion,suisse) I get an error in IE7, locations icons are not present on the map and the trip is not calculated.
IE7 tell me Line: 31, Char: 2, Error: Object expected.
What is wrong in the URL I use?
Many thanks,
Pierre
November 19th, 2008 at 21:02
Veja o link http://code.google.com/apis/maps/documentation/examples/icon-custom.html
Poderia fazer algo assim :
(-3.734378467616159, -38.49334716796875, 1, Dr. Joao)
(-3.736733796713304, -38.49626541137695, 2, Mst. Pedro)
(-3.737697338612461, -38.49336862564087, 3, Dr. Sandro)
(-3.731402179082779, -38.50529909133911, 4, Sr. Aparecida)
November 19th, 2008 at 21:09
Outro exemplo com icone http://econym.org.uk/gmap/geicons.htm
November 22nd, 2008 at 04:03
Please consider writing an App for the Apple iPhone based on your Trip Optimizer, and incorporating the iPhone’s built-in GPS functionality. You could make a lot of money!
December 12th, 2008 at 16:53
Hello Geir,
first I want to tell you, that I’m very impressed of you. It’s not only the “antsColony”-Function that caused a loud, headshaking “wow!”, moreover its your candid interest in some of the really BIG problems, our modern civilisation is facing. It is a pleasure to know that there are people like you out there!
I have been studying spatial science/regional development so I developed a sense for the spatial difficulties declining oil supplies will impose on a ‘petrosociety’. Unfortunately, my professor rejected my 2002 initial proposal for my degree dissertation, wherein I wanted to check the basic assumptions of the various Austrian spatial-development-plans and programs in regard to their consideration of possible future energy shortfall. Instead he gave me some topic, where I’m supposed to praise the opening of a highway (in the south of Vienna, Austria) and the resulting commercial advantages. Since it seems i’m incapable of doing so, I’ve not finished my academic studies yet. And I dont think, that I will do this with this crappy topic. (Thx for your patience with the description of my messy life)
Now there just opened an oportunity to get my academic reputation back. It is about solving a TSP, extended with the “Sequencial Ordering Problem - SOP” and the “Capacitated vehicle routing problem - CVRP”.
Now the actual question:
Would you perhaps help me with certain tips?
Best greetings from Vienna, Austria
Christopher
PS: excuse my lousy english
December 16th, 2008 at 13:56
I have had exactly the same problem as described by the second poster (shown below) when I use http://gebweb.net/optimap/ from IE 7.
When I select a series of locations by left clicking on the map, and click the button to create the route, *sometimes* it works and the route and map are displayed.
However, sometimes it doesn’t and the selected destinations are wiped from the map (as though I had clicked “Start Over Again” button) and no route or journey details are displayed and Optimap appears to have reverted to “start up” mode, awaiting new points to be selected.
However, when I click the map, the marker added has the next number in the original route sequence and does not reset to one - so Optimap is “remembering” the route I entered even though none of the points are now displayed and no route is generated.
I have tried this with IE 6 & 7 and the problem persists regardless of the number of points I enter. I have not tried to generate a route with more than 9 locations.
Can anyone offer suggestions as to why this problem is happening and why it is intermittent and, more importantly, what can I do about it?
This great application is exactly what we have been looking for to solve our problems in speical needs transport but this problem makes it a bit irritatiting to use.
Keith Soldner Says:
October 28th, 2007 at 01:02
When I input four locations and push submit they are properly displayed on the map but there is no route calculated. What am I doing wrong?
Thanks
Keith
January 23rd, 2009 at 23:05
GREAT tool! I LOVE IT. I spent 10 + min searching for something just like it. Hope google adds it or it can add a directions function. THANK YOU
January 23rd, 2009 at 23:06
Cross out that “directions function” - page hadn’t loaded fully. Thanks again
February 18th, 2009 at 02:07
I was wondering if it was possible to export the route as a KML file. I would love to use this for Geocaching trips and one of the ways we can find geocaches on a route is to upload a KML of the route to geocaching.com. This is perfect for finding the optimal route; now I just need it in a KML file. Any suggestions? Thanks.
March 6th, 2009 at 10:21
Hi, sorry my english is not so good. I also use this very nice tool. Now i’m searching for a program/tool to put the roundtrip data (toggle raw path output: 48.462238, 7.942672) to a navigation system like garmin or tomtom. Could someone help me?! Thank You!
March 6th, 2009 at 23:14
I would like to send the route information to my TOM TOM GPS. I understand that Google Maps has a Send to GPS feature but cannot access it for each of my addresses in http://gebweb.net/optimap/.
Any help will be appreciated. Thanks!
March 13th, 2009 at 20:00
Can you explain to me why the number of stops is limited to 24? I have an application that calls for routes of 60 or so stops. How can i optimize this type of route?
March 16th, 2009 at 01:19
Great tool, Are you planning on making another version (perhaps a paid version) that will allow up to 200 stops?
March 19th, 2009 at 03:59
Well done, this is just the type of tool that I had worked on at University but never was really good enough at Javascript to pull it off. I was wondering how difficult would it be to send the directions using var gdir and var addressMarker. In google maps the advanced directions http://code.google.com/apis/maps/documentation/examples/directions-advanced.html are listed numerically and can be clicked in a series that display infowindows with a zoomed version of each location on the route.
Keep up the great work
March 23rd, 2009 at 20:20
Jim, I’m setting up a commercial service for 200+ nodes. Please contact me at info@viamente.com to discuss your application scenario.
Rather than using the smart algorithm developed by Geir, though, we use a proprietary implementation of lin-kernighan which best fits our reference applications and that also includes a variant for pickup&delivery apps.
Geir, thanks again not only for the great code but also for your discussion forum.
March 24th, 2009 at 01:03
For applications where you need more than 24 locations, you are probably much better off with commercial tools such as mentioned above. Google Maps has a limit on the number of directions requests I can send each day. To solve the tsp problem, you need to know the distance between each pair of nodes, so for 200 nodes, you need to query Google’s servers 200*200 = 40000 times. Needless to say, this is not feasible to do for free.
The ant colony heuristic could probably be tuned to solve such big problems, but it needs the input, which is infeasible to get. I am also not sure about the quality of the solutions in this case, since the solutions space is bigger, and the ant colony algorithm would not be able to run as many times.
March 24th, 2009 at 23:56
When enter a zip or address and click on Add, it does not add the pin to the map. This was working before.
May 29th, 2009 at 09:11
i want to add lat & long values and then want u calculate fastest round trip.
Can u help me out how would i do this in tsp solver?
Thanks
Vidhi
June 8th, 2009 at 11:47
Hello Geir,
Thanks for this great tool!
Is it possible to integrate it on my website? i mean completely, no more request to your server?
Thanks.
June 27th, 2009 at 08:22
How about processing for an .kml file. They are just XML and a standard save output for Google Earth. It’s easy to maintain a list of places, pin and unpin them, and save an output file. This would add some pretty killer convenience to the app.
June 29th, 2009 at 14:22
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 11th, 2009 at 15:59
Hi,
great tool.
I have a feature request: I want to specify all options (Walking, Avoid highways, Roundtrip or A-Z Trip) via the API, i.e. by typing into the address line of the web browser.
Greetings, Hans
July 12th, 2009 at 14:46
Hi Hans,
I added the following parameters to the API:
walk - if 0, will use driving directions, if 1, will use walking directions.
avoid - if 0, will include highways, if 1, will avoid highways
mode - if 0, will compute roundtrip, if 1, will compute A-Z trip
E.g http://gebweb.net/optimap/index.php?loc0=start&loc1=dest1&avoid=1&mode=1 will compute the trip without highways in A-Z mode. Hope this helps, and let me know if anything isn’t working.
Geir
July 12th, 2009 at 16:51
Hello Geir,
Great, many thanks!
It would be helpful, if the checkboxes “Walking” and “Avoid highways” are set due to API parameters. Because otherwise it is possible to send e.g. Walking over the API, the correct result is shown in the picture, but the checkbox Walking is unchecked and this is confusing.
Greetings, Hans
July 14th, 2009 at 16:30
Hi Geir,
Great tool !!
Would it be possible to pass a parameter of a vehicles current gps position to be added to the route display?
July 26th, 2009 at 20:55
This tool is fantastic and just what our Sales-Reps need.
I will try to combine this with our CRM system in a way that the sales-reps will select a bunch of customers to visit and will use an export script to translate the selected addresses into a HTML line to call your page.
As we have a huge number of sales reps and we do not want to overflood your webserver, do you think we can implement the coding on our own intranet pages? Can you give me some feedback by eMail if that is possible and how to set this up properly? Especially I would need to know where to get all the files and scripts.
Again, many thanks for that great solution!
Martin Glueckmann
July 29th, 2009 at 15:42
Very nice tool. I would like to suggest a webservice release, where a simple Http GET Request would produce results in XML format only, without maps of any kind. It would be great to integrate to existent applications. You could even charge a bit via Paypal for a certain number of requests to face server proccessing expenses. I would be the first one to use a webservice like that. Regards.
September 13th, 2009 at 15:15
Wonderful tool! Exactly what I need!
Two questions, :
1. When submitting request via GET, I randomly get the error message “Failed to geocode”, when I click “OK” it maps the route with some of the locations but usually missing at least 1. I am submitting all loc(x) values as geocodes.
2. It would be great if for each location one could submit a name(x) that is used to label the geocode/address heading in the step by step directions.
Again, wonderful tool and THANKS SO MUCH!
October 8th, 2009 at 15:02
Very nice tool !
I’m going to use it for a city roud trip competition (rallye) in France using a 3G+ connexion.
Is there a way to get a full screen map without coding a new web page ?
Thanks
October 27th, 2009 at 14:45
Great app! But how do I use it internal on my company? I will just generate a few routes every work day.
November 6th, 2009 at 19:50
I would also like to webservice release, where a simple Http GET Request would produce results in XML format only -as roque
and also a way to split the stops to more then one car.
10X
November 19th, 2009 at 13:37
Hello Geir,
Thank oyu very much for a a great tool
Is it possible to integrate it on my website? i mean completely, no more request to your server?
Thanks.
November 24th, 2009 at 20:18
How do I send a route to my TomTom? The folks at Tom Tom gave me the link here but do not know how! Thanks, Roger
December 9th, 2009 at 20:37
I would also like to split a set of destinations among multiple vehicles. In addition, what about adding a pickup time to each location and routing based on estimated travel times?
December 21st, 2009 at 17:42
Really great job… but how can I do if I don’t care about the Z waypoint ? I need to travel as fast as possible thru all the point starting from the A point….
January 25th, 2010 at 01:24
Geir:
Is it possible to license you code for a user of mine? I would prefer to have it hosted on my server because of the integration requirements. I need to pull points from a database and have your code plan the best round trip route. Thanks, Lee
February 24th, 2010 at 04:31
Hi,
Under your common license, can I slightly re-write this code such that it works on my own server with my own map, instead of calling your GET url and having it return your page?
If so, I would be using my own google maps api KEY, but I know the currently limits on geolocating are like 15,000 a day. How do you get around this limit? Does your site not receive that many addresses a day or do you have a special deal with google? I’m just curious as I will face the same issue myself if I rewrite to work within my site.
Thank you for providing such brilliant code, I look forward to talking with you.
Erik
May 5th, 2010 at 09:21
Hi,
1.) How does one reference you in papers - I don’t see your name or development date for this system?
2.) Prior to your system, what other systems could solve the travelling salesman problem (was it confined to high-end GIS software?)
July 4th, 2010 at 17:22
I can not figure out how to input multiple addresses and get the fast most efficient route. Also at the same time need map and written directions from starting point to the closest to the next closest etc.
July 4th, 2010 at 17:28
Can not figure out how to put in multiple address in radom order and get the most effecient route. Also need at the same time a map and written directions from point A to B to C etc.