A year ago, I wrote code to generate an optimized route between a set of locations. The algorithm was based on the third of four obvious algorithms that solve the traveling salesman problem. The traveling salesman problem is the problem of getting the shortest route between a set of many locations. There is the brute force algorithm which generates every possible route and measures all of them to get the best – this is a terrible algorithm since anything more than a few locations causes the algorithm to be very slow. The second algorithm picks a starting locations and finds the closest location to use as the next point on the route – it’s faster but it can generate terrible routes in some cases. The fourth algorithm is far too complicated for me to understand so I didn’t even try to implement it. I settled on an algorithm that finds the distances from every location to every other location, sorts these by distance, then picks the next usable shortest distance from the list and sets that segment as part of the final route. This algorithm that I implemented is interesting because there is actually a little bit of work needed to determine which of the next segments is usable – if a location already has two connections to other locations then no segment going to or from it is usable. There is also an issue where a route cannot be made into a loop unless it includes every location – a viable route doesn’t have multiple separate loops!
But this is a digression. What I really wanted to mention was the fact that my code to do the route generation is using the straight line distance between the locations using some simple math to take into account the curvature of the Earth. What it really needs is the driving distance between all locations. This is where the newly discovered Google Distance Matrix API comes in; I just found the Google API that lets me send in a list of origins and destinations and get back the driving distances between them. Google charges $0.005 per individual result making a four-location test cost $0.8 total. I hope that they at least don’t actually compute the duplicates if the matrix has the same locations for origins and destinations even if they do charge for them; In my code, I don’t include or even calculate the straight-line distances between two locations more than once.
Here’s a sample request using some “random” data:
https://maps.googleapis.com/maps/api/distancematrix/json?destinations=39.259007870879195,%20-119.92568988355471|41.43206,-81.38992|New%20York%20City%2C%20NY&origins=39.259007870879195,%20-119.92568988355471|41.43206,-81.38992|Washington%2C%20DC&units=imperial&key=[YOUR KEY HERE]
And here is the result:
{
"destination_addresses" : [
"Churchill County, NV, USA",
"45 Bell St, Chagrin Falls, OH 44022, USA",
"New York, NY, USA"
],
"origin_addresses" : [
"1368 Zurich Ln, Incline Village, NV 89451, USA",
"45 Bell St, Chagrin Falls, OH 44022, USA",
"Washington, DC, USA"
],
"rows" : [
{
"elements" : [
{
"distance" : {
"text" : "140 mi",
"value" : 225770
},
"duration" : {
"text" : "2 hours 33 mins",
"value" : 9168
},
"status" : "OK"
},
{
"distance" : {
"text" : "2,338 mi",
"value" : 3763264
},
"duration" : {
"text" : "1 day 12 hours",
"value" : 128103
},
"status" : "OK"
},
{
"distance" : {
"text" : "2,769 mi",
"value" : 4455852
},
"duration" : {
"text" : "1 day 18 hours",
"value" : 151825
},
"status" : "OK"
}
]
},
{
"elements" : [
{
"distance" : {
"text" : "2,257 mi",
"value" : 3632501
},
"duration" : {
"text" : "1 day 10 hours",
"value" : 122213
},
"status" : "OK"
},
{
"distance" : {
"text" : "1 ft",
"value" : 0
},
"duration" : {
"text" : "1 min",
"value" : 0
},
"status" : "OK"
},
{
"distance" : {
"text" : "439 mi",
"value" : 706594
},
"duration" : {
"text" : "7 hours 3 mins",
"value" : 25391
},
"status" : "OK"
}
]
},
{
"elements" : [
{
"distance" : {
"text" : "2,545 mi",
"value" : 4096089
},
"duration" : {
"text" : "1 day 15 hours",
"value" : 138780
},
"status" : "OK"
},
{
"distance" : {
"text" : "355 mi",
"value" : 570999
},
"duration" : {
"text" : "5 hours 47 mins",
"value" : 20801
},
"status" : "OK"
},
{
"distance" : {
"text" : "225 mi",
"value" : 361950
},
"duration" : {
"text" : "3 hours 53 mins",
"value" : 13964
},
"status" : "OK"
}
]
}
],
"status" : "OK"
}
I have yet to implement this new feature in my route generation code because this is a work project and the boss has not decided we need this. I’m sort of hoping that we do end up using this in the future just because I want to see it working and not just written about.