Using the navigation facility on my car (and also on my iPhone), how does the program find the fastest route to get to my destination. I have my own, preferred route, which the nav programs usually use, but sometimes they pick a different route. If I continue using my own route, the program tries to make me turn around to follow its preferred route. As I continue, the estimate time of arrival gets later and later, until suddenly the program gives up and accepts my route and the ETA suddenly drops to a value earlier than all its previous estimates.
What is the algorithm do these programs. I use Wave on my iPhone, which supposedly uses live information from other “wavers” (which should account for traffic delays), but the same phenomenon still occurs.
I have a software development background although I do not know how these algorithms work. I can say that it is computationally intractable to exhaustively consider every possible path. So it must use some kind of heuristics to calculate most likely paths, such as giving priority to major arteries rather than trying to take endless shortcuts through side streets. It probably tries to model how a human would do it looking at a map.
I think you mean Waze. I have used it and I notice that Google Maps, my car GPSs (2 Toyotas and an Infiniti), and my Garmin portable GPS all tend to use more mainstream routes where Waze will often sidetrack you onto these odd shortcuts. I would guess that all these companies guard their routing algorithms quite closely. You will also get widely varying results if there are traffic tie-ups along the preferred route, which all except the built-in car units will handle.
Path-finding is actually a pretty complex subject in Computer Science.
I don’t know what algorithms they actually use these days, but there are quite a few out there. The basic idea is you come up with what is called a weighted graph, where each possible path is given a “weight”. In the case of traffic paths, the weight would likely be the estimated travel time down that particular path segment. By dynamically adjusting the weights, the pathing algorithm can determine the best overall path, even while factoring in estimates of current traffic conditions.
A lot of pathing algorithms are based on Dijkstra’s algorithm:
Since Dijkstra’s original algorithm can be rather computationally expensive, a lot of folks have tweaked it over the years. The A* Algorithm (pronounced A-star) is a good example of this. It uses heuristics to greatly improve the overall performance of the pathing algorithm.
More info:
A - Wikipedia*
A* is used a lot in computer games these days. There is a variant of A* which is called D* that is basically a dynamic version of A*. D* would work well in traffic path calculations, but I have no idea if that is what they are using.
I worked at a couple of companies in the early days of digital mapping, and route-finding was of primary interest. I was not on the programming side (I was in the actual mapping), but I can tell you that the roads themselves are coded in a way that allows the route-finding software to calculate the fastest route.
Essentially, there was a hierarchy geocoded to the roads:
1=freeway (no at-grade intersections),
2=highway/expressway (may have some at-grade intersections),
3=collector road (boulevard or thoroughfare),
4=neighborhood street,
5=dirt road.
As I understood at the time, the route-finding software was programmed to favor the lower-number roads from the above hierarchy, as long as possible. I occasionally got to see these programs at work graphically when they were tested - imagine a web spreading from the start and end points - when one of the tentacles reaches a lower number road it speeds up, until hitting another lower number road, until it hits a freeway. When the two webs finally meet - there is the favored route.
These days with crowd-sourcing like Waze there is a lot more info available, and real time, and I am sure the programming is much more complex, but I bet the roads still have some sort of hierarchy as an aid to route-finding.
I am guessing that modern algorithms take not the type of road into account, but rather the speed limit on that road, since that is what is really of interest if you are optimizing for speed, as suggested by engineer_comp_geek’s explanation. Your list uses road type as a surrogate for speed. Dynamic routers like Waze that take traffic into account would just use the current traffic speed on a road segment rather than the speed limit. I can’t think of any other information that Waze would provide that would be of interest for routing.
Agree. That’s essentially what the 1s, 2s, 3s etc did by assuming a hard-coded range of speed for that road segment. Now using current speed probably provides an easier way to accomplish the same thing.
Yes, Cooking, I do mean Waze. Interestingly, I cannot reach my destination obeying the speed limit. In fact, I usually miss even if I average 10 MPH over the posted speed (other drivers are still passing me, so I guess Waze really does use real traffic speeds). My built-in Nav program has a more conservative time estimate.
My car satnav has three routing options. Fastest, shortest and eco. Fastests uses highways and motorways as much as possible, while shortest takes me down what are often quite unsuitable roads. Eco is some kind of balance between the two.
If I ignore her, she will sometimes keep trying to steer me back onto the original route and sometimes just recalculate very quickly.
We see news reports where truck drivers get stuck on country lanes or trying to make sharp turns in the middle of villages; sometimes to the point of needing a crane to lift them out of trouble. I assume that they set their satnavs at ‘shortest’.
I have a friend who had this strange issue with his nav system: We were at a ski area in Vermont and had to return to our hotel, which was in another valley. I followed the route I had come on, but he used his nav. It told him to take a shortcut, which turned out to be an unplowed dirt road! Fortunately, he turned around before he got stuck, and got to our hotel only an hour after I did!
I don’t see that as an issue with the nav system. The nav system could not know that the road was unplowed.
I am betting that he had it set to “shortest”. “Quickest” would, or should, have sent him on the same road you used.
I recall when Google maps (I think it was) was very new. It defaulted to shortest route or at least that was the default on the computer I looked at. I was traveling between two points on the coast of CT. The suggested route involved getting off and on I-95 to travel short distances on route 1. I think it was 4 times. It was a long time before I consulted that web page again.
Cooking and Bob; I neglected to mention that the road was closed for the season.
With Google’s data, they can do a lot better than mere A*. They can just track “starting at node A120, what are the routings people used to get to node B135”. Then, if you want to go from a particular house at point A, it finds the nearest node with a bunch of stored exits to where you started from. Then look at the different routings people already took and determine which one is quickest.
Validity is determined by statistics. If 200 people in your data in the last month took a particular routing, and only 5 people took a different routing, and you calculate from what you know similar trip times, it makes sense to just use the more common routing.
This is also how autonomous cars are going to do it. Instead of planning every last element of a trip, it can just borrow information from what other autonomous cars experienced for part of the journey, limiting what it has to figure out to the endpoints.
I’m not sure if this is still an issue, but I once was a victim of a poorly implemented “enhancement” in Google maps navigation.
I was using it to get to a friends condo. The condo building’s street address and entrance was on a street that went under a raised interstate. For some reason Google maps insisted that the end point was actually on the interstate at the point closest to the building, not at the street entrance. Obviously I didn’t stop there, so it tried to reroute me back to that point on the interstate after I went past it.
I can only surmise that there was some enhancement that decided that a road at the closest point to the building was a better bet than the official street address. I ran into this feature a couple of other times: a hotel that was supposedly on an interstate off ramp and another business where the end point was a road in an adjacent fenced off subdivision.
This was quite a few years ago. I have to assume that they fixed it, because the whole assumption seems really error prone.
Another question on this topic.
Why is it that my Android device Google maps always changes the perspective of the routes. In other words using Google I want the device to always show the road and direction I am heading true to the orientation of the phone. This way when I am driving and a left or right turn comes up I can see it on the map.
However Google Maps does not do this. As the roads twist and turn the maps twists and turns also. So often my map orientation (if I hold the phone normally) shows me going the opposite direction. Therefore the turns are all messed up in my head. So then I have to use my fingers and re-set the orientation of the map. Very frustrating, and dangerous to do in a moving vehicle.
Is there a setting I am missing ? I have look and looked but do not see.
I am not quite following your description; in particular I do not know what you mean by “true to the orientation of the phone.”
But there are two modes, and when you go to one mode, it will not switch to the other, at least in the several years I have been using Google Maps on an Android phone (I’m on my third or fourth Android phone).
The mode that I see as the default is “north up.” This will show north pointed towards the top of the screen regardless of the orientation of the phone or direction of travel.
There is a little bull’s eye-like symbol on the screen you can press to switch modes to “track up.” This shows the direction of travel towards the top of the screen, and results in the twists and turns you describe. If you start navigating to a destination, the little compass symbol does the same thing; when the N is showing it is “north up,” otherwise “track up.”
I always use “north up” because I like to use it the same way I would use a paper map, and it never spontaneously changes to the other mode.
As has been the case since trucks outgrew cars, truck drivers have to be much more selective about the routes they choose to drive. Most GPS nav solutions, whether app or dedicated hardware, aren’t programmed to consider tunnel/overpass heights, bridge weight limits, vehicle length issues, etc. when computing a nav solution. Often (but not always), younger/newer truck drivers attempt to use a smartphone app to navigate, with the predictable consequences of trying to drive a 13ft tall, 65ft long, 40ton tractor-trailer along a road made for cars, vans, and pickup trucks.
Before the days of smartphones and portable GPS navigators, most truckers spent some quality time every day with their Rand McNally Motor Carrier’s Atlas to figure out their route from Point A to Point B, without stuffing their truck in a tunnel/under an overpass, breaking a bridge, or getting wedged in a turn somewhere. Now, in the US at least, there are a couple GPS navigation options specifically dedicated to truckers, by Garminand Rand McNally.
If you press the circular icon with the red and white compass needle, doesn’t that toggle the map’s orientation between north up, and your heading up?
ETA – This image shows the control I’m trying to describe: google maps icon north up - Google Search