Route Optimization vs Route Sorting

With more and more devices supporting multi destination routing, there has been an increased amount of conversation about taking that feature to the next level– optimizing the order of those destinations to provide the most efficient route. But is your GPS merely sorting the route, or optimizing it? We’ll show you the difference, and how it can shave time off your next sales call.

POI Lists

To start, let’s talk about your GPS’s ‘Find POI‘ feature. When you tell your GPS to bring up a list of nearby POIs and it shows a distance to those POIs, it is showing you a straight line (as the crow flies) distance to that location– not a distance that covers roads. Take the picture to the right for example, those distances (while close) are in a straight line, not the distance it will take to drive there. Until I create a route to those locations, the actual driving distance is unknown.

Imagine two parallel canyons with a road in each, or a river that has roads going up each side but few bridges– you an probably imagine scenarios where the straight line distance might only be a mile, but the roads to get you there would take many many miles to get you there. This doesn’t happen often, but it does illustrate the point that just how close a waypoint is to you doesn’t mean it is the fastest waypoint to get to.

Waypoint Sorting

Some GPS devices have a function they call ‘Optimization’, but what I’ve found is that all it will do is to sort the list from closest to furthest away based on the straight line distance. As illustrated above, this can have some severe limitations– and I certainly wouldn’t call it optimization. I call this “waypoint sorting” since it completely ignores routes.

Route Sorting

Something else I’ve seen GPS devices do is what I call “route sorting”. This is a somewhat more advanced form of waypoint sorting, but it still has limitations. Basically the GPS appears to figure out (based on routes), which waypoint is the closest to your current position, and will put that stop first. Then it figures out which of the remaining waypoints is closest to the first stop, and will go there second. This process is repeated until you finally end up at the point which is furthest away from your starting point. It sounds promising, however you will soon see that this too has some limitations based on how many people want to use the function.

Route Optimization

This is the holy grail for people who drive to a number of stops per day and the order of those stops is not dictated by appointments. Here, the GPS takes a look at each of the waypoints and figures out which order of stops produces the fastest route for the trip. So how is this any better than Route Sorting? Consider this example.

Pop Quiz

Consult the to the right, click on it to enlarge. You are currently at the blue dot near the top of the map. You need to visit points A through I (nine stops) and then return home to the blue dot. All of the streets are two way streets, there are no medians to worry about crossing, and there is nothing else that is designed to be a “trick”. You are on the right side of the road facing South. Which order would you plan to visit each of those locations?

A device that does simple waypoint sorting would probably order them like this:

1. A
2. (turn around) I
3. (cross the street) B
4. E
5. H
6. F
7. (cross the street) G
8. D
9. C

A device that does route sorting would perhaps do something like this:

1. (cross the street) B
2. (turn around) I
3. A
4. (cross the street) C
5. (cross the street D)
6. G
7. (cross the street) F
8. (cross the street) H
9. (cross the street) E

But how would you go? The fastest route is likely one with more right turns than left so you don’t need to cross traffic. It is also likely one where most of the stops are on the right side of the road for the same reason– fewer lanes of traffic to cross. The route should also backtrack (turn around) as little as possible, if at all, to make for a short of route as possible. Therefore the most efficient order (route optimization) to make all of those stops is this:

1. (cross the street) B
2. E
3. H
4. F
5. (cross the street) G
6. D
7. C
8. (cross the street) A
9. I

The route sorting method in this example produces a very inefficient route. You cross the street six times and need to turn around and backtrack some of the route. Strangely enough, the waypoint sorting method actually does a little bit better– you only cross the street twice, but you do need to turn around and backtrack over a segment of the street you have already been across. Finally, the route optimization method naturally performs the best. While you do need to cross the street three times, you really couldn’t do it in any less, and there is no backtracking adding any extra miles to the trip.

Which GPS?

It can get very complicated figuring out which GPS device does which type of sorting/optimization. There are just too many variables such as speed data, turn restrictions, one-ways, etc– this makes it really difficult to reverse engineering what the GPS is doing. With that said, overall we’ve found that the Nuvi 700 series devices perform the best when it comes to route optimization. That doesn’t mean they will never cross the street, nor will it mean they won’t ever backtrack– rather in our testing they generally produce optimized orders that are more logical than other models that claim to offer optimization.

Located in GPS, GPS 101, GPS Maps on Jun 6, 2008