Solved

# Traveling Salesman Problem - Optimize driving route

Posted on 2008-10-25
1,512 Views
I an using Google mapping to create the driving map and directions of a three to six segment route. I have code attached that shows the path, miles driven and time driven. The real issue is to optimize the route. In the code attached, I have two segments predefined that show the difference.

I need help figuring out the best way to improve the code and optimize the route to the shortest.

The attached txt file needs to be renamed to ans asp file

CompanyTSPtest-asp.txt
TSP-Output.jpg
0
Question by:UHsoccer
• 6
• 3

LVL 18

Expert Comment

I get "directions failed, invalid address" when I run it.  I put my google key in it, and renamed the extension to .ASP

If your question is the one at the bottom of the page, what you would need to do is write a script to post an HTTP request to generate this output, and return it to that script script.  The HTML results are sent back to your script and then you parse that to get the lengths of each leg, then you can put those through whatever algorithm you want to solve the TSP. (I guess that is your question #2)

If your question is how to solve the TSP, there are lots of possible answers to that.  If you have 6 segments, then there are about 720 possible routes (if I'm calculating that correctly), so, a brute force approach is not out of the question.  However, the google maps API can be a little slow sometimes, so, that could be a problem.  (your question #1)

I've used a genetic algorithm to find a "better" route (the only way you can find the "best " route is through brute force, trying all possible combinations which becomes impractical when the number of segments goes beyond 10 or so).  But, that might be overkill for just 4-6 segments.

As for your 3rd question, I believe the google api instruction for adding the +- zoom tool is this one:

0

LVL 18

Expert Comment

I'll have to read through your code in more detail.  It is possible that you can generate all the lengths of the segments within the body of your script (as you are doing to display them) and then you wouldn't have to resort to doing an HTTP post within the script and parsing the results.
0

LVL 18

Expert Comment

I'll attach some code below... this isn't a complete script, but it will show you how you could use a brute force approach to finding the best route.

I'm not much of a javascript expert, so, you may get some syntax errors, but, it should be pretty close.
``````// for saving the best route

var bestDist = 0;

var bestTime = 0;

var bestDistF = 0;

var bestTimeF = 0;

var bestSegment ="";

// for calcing route distance

var stepDist = 0;

var stepTime = 0;

var stepDistF = 0;

var stepTimeF = 0;

var w = 0;

var x = 0;

var y = 0;

var z = 0;

var map = new GMap2(document.getElementById("map"));

for ( w=1; w<=4; w++) {

for ( x=1; x<=4; x++) {

for ( y=1; y<=4; y++) {

for ( z=1; z<=4; z++) {

if ((w != x) && (w != y) && (w != z) && (x != y) && (x != z) && (y != z)) {

var dirn = new GDirections(map);

var segBase = "4424 Patrick Rd, West Bloomfield, MI, 48322";   //  start point and return point

var seg1 = "45001 Ford Rd, Canton, MI, 48187";

var seg2 = "200 Fulton St W, Grand Rapids, MI, 48540";

var seg3 = "3360 Tittabawassee Rd, Saginaw, MI, 48604";

var seg4 = "700 W Norton Ave, Muskegon, MI, 49441";

var segment = segBase + " to: ";

switch (w) {

case 1:

segment += seg1 + " to: ";

break;

case 2:

segment += seg2 + " to: ";

break;

case 3:

segment += seg3 + " to: ";

break;

case 4:

segment += seg4 + " to: ";

break;

default:

//statements;

break;

}

switch (x) {

case 1:

segment += seg1 + " to: ";

break;

case 2:

segment += seg2 + " to: ";

break;

case 3:

segment += seg3 + " to: ";

break;

case 4:

segment += seg4 + " to: ";

break;

default:

//statements;

break;

}

switch (y) {

case 1:

segment += seg1 + " to: ";

break;

case 2:

segment += seg2 + " to: ";

break;

case 3:

segment += seg3 + " to: ";

break;

case 4:

segment += seg4 + " to: ";

break;

default:

//statements;

break;

}

switch (z) {

case 1:

segment += seg1 + " to: ";

break;

case 2:

segment += seg2 + " to: ";

break;

case 3:

segment += seg3 + " to: ";

break;

case 4:

segment += seg4 + " to: ";

break;

default:

//statements;

break;

}

segment += segBase;

stepDist = 0;

stepTime = 0;

stepDistF = 0;

stepTimeF = 0;

// === read through the GRoutes and GSteps ===

for (var i=0; i<dirn.getNumRoutes(); i++) {

var route = dirn.getRoute(i);

var geocode = route.getStartGeocode();

var point = route.getStep(0).getLatLng();

stepDist = stepDist + route.getDistance().meters / 1609;

stepTime = stepTime + route.getDuration().seconds / 3600 ;

stepDistF = stepDist.toFixed(0);

stepTimeF = stepTime.toFixed(1);

}

// compare whichever field you want to give you the best route,

if ((bestDist == 0) || (stepDist < bestDist)) {

bestDist = stepDist;

bestTime = stepTime;

bestDistF = stepDistF;

bestTimeF = stepTimeF;

bestSegment = segment;

}

} // end if

}  // end for z

}  // end for y

}  // end for x

}  // end for w

// now, do whatever you want with the bestSegment
``````
0

Author Comment

Thanks,

Added your code where I expected it to ne needed. Basically the "segment" that I need, would be the final bestSegment from your code.
It runs a while, gives a warning that it might take sometime and then finally stops, but I cannot tell WHICH segment it ended up with

Is there actually a way to display the value of bestSegment AS it is changed going through the four loops?

Current code is attached. I simplified the addresses to simply the City, State and ZIP

By the way, what timezone are you in? I am EST (Eastern USA)

CompanyTSPv2asp.txt
0

LVL 18

Expert Comment

Well, I would assume that after running that bit of script that I gave you, which it appears you have inserted at just the right spot, then you would fall through into your old code and change this line (or lines)

//dirn.load("from: West Bloomfield, MI to: Novi, MI to: Troy, MI", {getSteps:true});

So that you reference the bestSegment from the code above:

Then, that would go ahead and print out the actual map with direction and such.  You should probably comment out these two lines which show up after my code, because I had to declare the same variables above, so, the variables should still be available to you.

var map = new GMap2(document.getElementById("map"));
var dirn = new GDirections(map);

As far as printing it out, as you're going, not sure of javascripts syntax... maybe the alert statement, like you have in there?

I tried your example again, but again get the error when it tries to create a new GDirections.  I get that error, "Directions Failed: INvalid Address"

The only other thing I was a bit worried about, was that you had coded a handler which would basically fire once the GDirections object  dirn.Load() statement finished executing.  We've got that same Load statement executing up in the Loop, so, if that is something that takes a lot of time to load, then you might be having a problem with that Load statement inside of the loop.

I'm in the EST as well.
0

Author Comment

Made the recommended changes. Puzzled by error 601, I added the segment that it uses to the alert statement and it appears fine. When I click OK, it continues processing. In the end (after a significant amount of time) it display the map only (no driving directions) and highlights a route which is not optimum.
Tried to use "alert" to display the segment being used.

My concern at this point is that the amount of processing might get out of hand when I try to process all my data.....
CompanyTSPv2-asp.txt
0

LVL 18

Expert Comment

I'm guessing that the 601 error is making it exit out of the loop, so, the bestSegment is only the bestSegment up until that point.  It would really be nice if you could get it to print the segments and the distances inside of the loop, because then you would know how many segments had made it through up until the point of the error.

The algorithm that builds the possible routes is going to execute them in this order... keep in mind the start and ending points would be on either end of these segments.

Seg: 1 to: 2 to: 3 to: 4
Seg: 1 to: 2 to: 4 to: 3
Seg: 1 to: 3 to: 2 to: 4
Seg: 1 to: 3 to: 4 to: 2
Seg: 1 to: 4 to: 2 to: 3
Seg: 1 to: 4 to: 3 to: 2
Seg: 2 to: 1 to: 3 to: 4
Seg: 2 to: 1 to: 4 to: 3
Seg: 2 to: 3 to: 1 to: 4
Seg: 2 to: 3 to: 4 to: 1
Seg: 2 to: 4 to: 1 to: 3
Seg: 2 to: 4 to: 3 to: 1
Seg: 3 to: 1 to: 2 to: 4
Seg: 3 to: 1 to: 4 to: 2
Seg: 3 to: 2 to: 1 to: 4
Seg: 3 to: 2 to: 4 to: 1
Seg: 3 to: 4 to: 1 to: 2
Seg: 3 to: 4 to: 2 to: 1
Seg: 4 to: 1 to: 2 to: 3
Seg: 4 to: 1 to: 3 to: 2
Seg: 4 to: 2 to: 1 to: 3
Seg: 4 to: 2 to: 3 to: 1
Seg: 4 to: 3 to: 1 to: 2
Seg: 4 to: 3 to: 2 to: 1

Now, as far as it getting out of hand when trying to process all of your data, that's a real possibility with this problem.  You have two issues with scaling.  First, the number of possible routes increases exponentially as you increase the number of segments.  I've found that the brute force way starts to bog down with 10-12 cities.  At that point, you need to switch to another "search" algorithm.  Many other algorithms have been used to solve the TSP problem, including the Genetic Algorithm that I've used.

These search algorithms sort of take potshots at finding a good root, then use some methods to try and optimize those results a bit, and then give you a better route, but, none of them can guarantee that you've got the best route (unless you do the brute force).  The search algorithms will go through many less evaluations of the length of the route than the brute force one will, that is why they are used, they are faster.

The second scaling/performance issue you have is how much processing power it takes to evaluate the distance and time of a single route.  I think you are calling some google API's for that, and google is very slow.  What you might consider doing is if google can give you back the lat/lons of each city on the route (and if that is faster than it calculating the time and distance), then, it is fairly easy to calculate the distance between two lat/lons "as the crow flies".  So, you could do that calculation in your program, which would be faster than having google figure out the distance based on the driving directions.

The only problem with this is that your "best" route would be calced based on the "as the crow flies" distance, and the actual driving distance and time might not be the most optimal (though, it would probably be one of the top two or three).
0

Author Comment

Thanks for your comments, I actually have all the lat/lon values for the locations that I am working with. I also have the math for the "as the crow flies" distance.
Maybe I will use that to get a reasonable estimate of the shortest, then submit that to Google for actual driving distance and time.
However,  Once I added an Alert in the loop I saw that the times and distances do not get calculated.
which could give rise to the 601 error. It actually calculated rather quickly ...

The other thing I noticed is that since the logic does not bypass pass "duplicate" paths (backwards) as 1234 and 4321, It eliminate 50% of the work.
The next step I will try tonight, is to store the "reverse" path  in an array and once it gets to that simply bypass it.

CompanyTSPv2-asp.txt
0

LVL 18

Accepted Solution

mdougan earned 500 total points
Yes, I saw the reverse paths, but couldn't think of a way to easily eliminate them.  However, I wasn't sure that it is valid to eliminate them, since I didn't know if google would choose the same exact routes for each direction.

In your original code, you execute the Load function call on that GDirections object, but then you immediately set a "callback" event handler.  This event handler is supposed to fire once the Load finishes.  I think you have to find a way to do the same thing inside of this loop.  Maybe the event handler simply sets some global flag to true and you have to loop just after the load statement until that variable is true, then proceed with the distances etc.  If you don't do this, then I'm guessing that Load hasn't had time to get the distance and time stuff.  If google's other APIs are any indication, I bet that will slow your process down a bit.
0