Back in the hazy olden days of the pre-2000s, navigating between two locations generally required someone to whip out a paper map and painstakingly figure out the most optimal route between those depending on the chosen methods of transport. For today’s generations no such contrivances are required, with technology having obliterated even the a need to splurge good money on a GPS navigation device and annual map updates.
These days, you get out a computing device, open Google Maps or equivalent, ask it how you should travel somewhere, and most of the time the provided route will be the correct one, including the fine details such as train platform and departure times. Yet how does all of this seemingly magical route planning technology work? It’s often assumed that Dijkstra’s algorithm, or the A* graph traversal algorithm is used, but the reality is that although these pure graph theory algorithms are decidedly influential, they cannot be applied verbatim to the reality of graph traversal between destinations in the physical world.
A Story Of Travelers
The field of graph theory has been around since 1736, when Leonhard Euler published an article on the subject of the Seven Bridges of Königsberg (in Prussia, today’s Kaliningrad in Russia). In this mathematical problem a walk has to be devised through the city in which each of the seven bridges across the city’s Pregel River that connect to the two islands in said river is only crossed once. Euler observed that the only relevant information here are the land masses (the nodes) and the connections between them (the bridges, or edges), which reduces the problem to a simple graph.
On this graph a starting node is selected, with another node as the end node. As each land mass is connected with an odd number of bridges (3 or 5), this means that this problem does not have a solution. The main challenge here lies in devising a mathematically acceptable proof of this impossibility, which is where the foundations for what we today know as graph theory.
From here graph theory got expanded and generalized into relations between objects, finding use in fields from computer science and chemistry to biology and linguistics. Combined with algorithms that can handle such graphs it’s a great way to not only make the basic structure of a network clear, but also to model structures and systems. Naturally, finding a route between nodes remained a crucial part of the field, with a wide range of path finding algorithms developed over the centuries.
Perhaps the most common graph theory problem is that of the Travelling Salesman Problem (TSP), which is somewhat like Euler’s original seven bridge problem, but instead asks for a traveller (a salesman) to be guided between a collection of cities in the most efficient way possible. The trick here is that by blindly trying out each route, the number of possible routes increases rapidly with each added city. By modeling the cities as nodes, an algorithm can then be devised that creates the edges between nodes, taking into account the weight of each node, related to its position on the map.
Although simple route planning is not as daunting as TSP, there are some similarities, in that it involves a weighted, undirected graph, requiring the algorithm to take into account the cost of each edge as well as the total cost, creating a minimum spanning tree. One of the first algorithms for this is Jarník’s algorithm, by Czech mathematician Vojtěch Jarník in 1930. Later this was rediscovered by Robert C. Prim in 1957 and in 1956 by Edsger W. Dijkstra (Dijkstra’s algorithm).
The weight assigned to each node is the Euclidian distance, allowing the algorithm to calculate the distance of any newly discovered node to its current node. In its most simple form as a path finding algorithm, it tries one or more steps in roughly the direction of the destination and selects the shortest branch from these, repeating this procedure until the destination has been reached and something close to the shortest path has been found.
The most well-known improvement to this basic algorithm is probably the A* algorithm (geometric goal directed search), which was developed in 1968 at Stanford Research Institute. Rather than a simple node-to-node algorithm, A* considers the entirety of the nodes, and may skip nearby nodes in order to achieve an overall shorter path between the source and destination. One disadvantage of A* is that it has to keep all nodes in memory, making it much more memory-intensive than alternatives. Despite this, A* has been the usual choice for path finding in the real world.
GPS For Everyone
Before the US enabled higher accuracy with the GPS satellites by turning off Selective Availability (SA), the best precision you could hope for by default was about 50-100 meters. This was clearly not enough to use for live navigation which – along with the high prices for satellite navigation devices during the 1990s – left route planning mostly dependent on paper maps and scribbled-down notes along with the occasional updates from helpful locals. Route planning using automated means was already used at this time, but the biggest use was by route planners at railways, logistics companies and so on.
With highly accurate GPS positioning becoming available in 2000 without the need for SA correction algorithms, and later other global navigation satellite systems (GNSS) becoming available to the public alongside rapidly dropping prices for GNSS-enabled devices, suddenly it became possible to combine digital maps with accurate satellite navigation, far beyond the scope of early satnav devices during the 1990s. This would lead eventually to the rise of smartphones, with their wireless internet connectivity, built-in GNSS support and apps like Google Maps that quite literally put a satnav device into your pocket.
Although it’s useful to get live updates from a remote server on changes along the route, like road work, accidents and obstructions, generally you can use the digital maps offline to plan a route spanning a variety of transport methods and with many options to customize the generated route.
Route Planning Today
The idea of whipping out a portable computing device and asking a piece of route planning software to quickly plan out a route would have seemed futuristic in the 1990s, but these days we barely give doing so a second thought, let alone how it all works. At this point it should be obvious that simply applying a basic graph traversal algorithm like Dijkstra’s would be too simplistic, so what do services like Google Maps and others use?
Although the general response is either “Dijkstra’s algorithm.”, or “A*, of course.”, the truth of the matter is that the former doesn’t play a real role in modern-day route finding and A* has seen itself largely superseded by versions that optimize it even further through e.g. the use of preprocessing. We can consider e.g. the 2009 overview (PDF) provided by Daniel Delling and colleagues titled Engineering Route Planning Algorithms.
One part where the crisp, clean world of nodes and edges runs into some problem is where you have to consider the many details when e.g. plotting a course via a road network. In the real world not every road is the same, after all, and requires heuristics for when to include certain weights and when not. These heuristics include contraction hierarchies (CH) as well as Highway Hierarchies (HH) and many others, which speeds up the search for a route that’s not necessarily the shortest, but also the fastest. By preprocessing the graph, unimportant vertices (intersections) and edges can be skipped, leading to a major speed-up.
Perhaps it should come as no surprise that such route planning algorithms can be conveniently integrated into your own software, using open source projects like OSRM and RoutingKit, which both use map data from OpenStreetMap (OSM). With today’s portable pocket computers and these optimized route planning algorithms and heuristics all it takes is these software components and a good GNSS reception to make your very own satnav.
Where From Here
Although it would seem that we have pretty much cracked the whole route planning problem at this point, the paper by Delling et al. notes a number of challenges that still remain. Most of all, moving beyond static point-to-point routing and taking into account time-dependent factors remains a challenge, as many of the shortcuts and preprocessing that made static routing ‘cheap’ do not work here. Beyond this the characterization of ‘well-behaved’ networks is a consideration. Despite this paper having been written now almost fifteen years ago, it should be clear to anyone who regularly uses route planning software that it is not quite perfect yet.
The integration of more detailed information pertaining to specific travel modes, and preventing awkward situations where for example a truck finds itself wedged into a tunnel or between hedgerows are probably at the forefront of most people’s minds. Now that everyone’s assumption seems to be that they can just whip out their smartphone, plan a route and mindlessly follow the provided instructions, the impact of a heuristic slipping in a few flawed vertices can be rather major.
Although it is liberating to not have to wrangle with a paper map in the car while traveling to one’s vacation destination, the safe assumption is that as amazing as satellite navigation has become, algorithms and data sets aren’t perfect, you should always rely on your common sense and Mk-1 eyeballs first and foremost.
Thumbnail credit: [betaveros] with the fanciest a* illustration we could find on the Internet.
I am in my 30 somethings and cannot imagine my life without G maps. I mean, how to get anywhere unknown without it?
When I was a kid, I just used the stars and my Raleigh Chopper to navigate. I’m 50+ though, you 30+ kids don’t know you were born….
But it’s tricky to use the stars to navigate if your parents expect you home by sundown.
So you’d navigate from one end of a major city to the other, with expressways and raised highways and tunnels, during the day, via the stars?
You 50+ fossils didn’t have to ride your choppers to a real job.
I delivered pizza around the time standalone GPS navigation units were coming out. I remember a coworker had bought one and I couldn’t believe they would sit in their car wasting time typing in the address to a delivery.
It was quicker to look at our big map and figure it out. You’d use a street index to see the grid cell that the street is at on the map then trace the route to the store and remember the turns you had to make. Once you get to the street it’s easy to find the house based on the number.
Cool! I’m sure glad delivering pizzas to a single city is the *only* application for needing directions. Otherwise we actually *would* need GPS.
I think in this case you were just offering a story, so I probably didn’t need to be so sarcastic, but I see a lot of comments on HaD that are essentially saying “This doesn’t suit my personal needs, and is therefore useless!”
You’d sometimes put more priority on using a simpler or more familiar sequence of roads rather than the absolute shortest-time route, I suppose. But paper maps were available with distances for each segment, so even if none of it was familiar it was fine. When you wrote out your route, you could do the arithmetic and watch your odometer to figure out how far along a segment you were, so you’d know if you had missed a turn.
Oh, and you’d also use them when planning out your stops on a long road trip. As long as you stopped for gas/restrooms/snacks before any long gaps between towns and stopped at a rest stop in the afternoon to get a brochure for the motels in whatever town you were going to end up near that night, there was no need for a computer to figure things out.
I think more places used to bother to have a clearly readable street number posted… Once you got close you could easily figure out the numbering method whether it was a straight sequential number, or distance based, odd and even on opposite or the same side of the street, etc. Now it’s GPS or hoping you spot the place, seems like.
The maps would often have small numbers indicating the distance to the next intersecting highway so you mentally take note of your odometer and if the turn was 10 miles you’d start watching at 8 miles or so for confirming signage.
————–
I 3
I______
I
10 I
I 7
________I____________
Kind of like this.
Using maps and roadsigns. You often know where you are, and then find a road going in the direction of the place you want to be. Technically not much different than the labyrinths you can fill out on the back of cornflake boxes.
Most paper maps use different markings depending on what kind of road you were looking at, which lets you estimate how fast you could go. Also to find the wanted address, most map-books (atlas) had registers for each city, where the square in which the address was located were listed.
Lets say you want to go to a small town in Saxony, you know the name, and you know that it roughly is in saxony, you look up the register of the atlas and find the number of the square (and page) on which the map segment containign the location of the town is located. Then you follow the roads in a direction which makes sense back to the area from which you come. IT is handy to note roadnumbers, names and exitnumbers in their order on a piece of paper.
Or have your copilot have the map at hand and follow it himself while you drive.
I am in my late twenties and we used paper maps when i was little. My parents let me check the map regularily while we were on trips. While i also use GPS if it has to go fast, i think i am still capable of navigating by map.
You buy a country wide atlas and keep area specifc maps with you. Or you stop at a gas station & buy a map while asking for directions.
I traveled from the US to Finland via England, France, Germany, Denmark and Sweden having never been to any of those places. I arranged to meet my Finnish friend at a certain place and time in Helsinki about 2 weeks prior. I missed the boat from Stockholm to Helsinki and had to take the boat to Turku instead and still we met at the place and time that was prearranged.
We did this with no maps whatsoever, no cell phones and no GPS. One of my motivations was to get my laundry done but when I got there his washing machine was broken.
I never had a problem getting anywhere before gps. There are lots of other ways to navigate. The inability for people to pay attention due to phones causes a lot of problems on the road. Remembering which directions highways go is easy. memorize major roads on a map in any city you live in is easy. and for finite neighborhood travel, just ask the person you are visiting, not difficult. having a general sense of direction and paying attention to your surroundings goes a long way. can do the same in the woods.
gps on the other hand, often tells me to take the wrong roads, tells me to do a u turn and drive back up the road in the wrong direction. or take routes that are obviously closed due to construction or flooded. So yeah… tech not as good as local knowledge, ever. This is why people still hire guides when visiting new places. Also, gps can lead you to places you’ll get robbed, cuz gps doesn’t have any consideration for human life. gps is nothing more than a fancy paper map that looks at roads for you with zero consideration of what the actual on the ground conditions are.
Once you hit the real world there are a lot of weights you can add. Number of accidents per road. Number of stoplights. Avoid turning left (across oncoming traffic).
As anyone who has had a job delivering or making service calls can tell you, the automatic systems are not the best. Bare minimum I allow it to choose me a route and survey it before I take off as a basic check if it made a logical choice. Just this week I completely avoided a freeway merge and stoplight intersection completely (I was going to a commercial lot, and it had me travel around the block). Not to mention the 20 stoplights I avoided by taking my usual “back route” through a town 20 mins from me, although I was taught this route 30 years ago by my friend’s mother.
Is it a usable tool? Yes. Does it understand what a logical route is? No.
I guess what I am saying is if the apps behaved more like an enhanced paper map that helped /YOU/ make more infirmed and logical choices I would be more impressed.
Although I must say looking at driving patterns I seem to be in a minority.
Things based on openstreetmap might be more able to be adjusted with custom rules and might have more interface details exposed. Even the others at least let you override them with intermediate destinations. On the other hand it’s been pointed out to me that the ones with live traffic data can warn you about things you could only guess at otherwise.
If you choose cycling in Google Maps, it’ll give you various routes based on elevation, so a shorter trip with hills, or longer but flat terrain.
On a side note, I think it was UPS, who invented the “only right turns” routing. Because a left turn might be way more time-consuming than a simple right turn.
(This is, Jenny, different in your country. :)
No, it was definitely Zoolander that invented only turning one way.
Nah, my mum invented it years before, because she didn’t like turning across traffic in her bike.
I think this is one of those parallel discoveries.
Having worked for TomTom, I for a fact know that the routeplanning algorithm is A* with static (heavily preprocessed) map data, with added weights for traffic lights, corners, left turns. But also with static information for every 100m piece of road network about the average speed that is driven there, *for every 15-minute slot of every day of the year*. So it will plan different routes depending on the time of day, based on historic static information.
But that is all just the static information. During route planning, it also takes dynamic information into account. Because again, Tomtom has realtime information on the current average speed driven on any 100-meter section of road in the road network. Plus, it has dynamic information on traffic jams (partly derived from those 100-meter sections, partly received from 3rd party sources) and road works.
While driving, the device will continuously recalculate your route in the background. And if it finds a route that is 2 minutes faster than the current route, it will propose the new route to you. And while driving, the dynamic road information on traffic jams and road works/blocks are updated every minute. It’s called ‘HD traffic’.
Tomtom also has information on the height of overpasses, and if you have entered the height of your vehicle, it will avoid those overpasses automatically (with a margin).
And Tomtom has already had all this since 2011-2012 and has continually improved on it since.
Also, Google cannot do most of those because Tomtom has patented most of it. We’ll have to wait until all the patents run out, and then Google will still have to build the whole infrastructure that Tomtom already has.
So, I don’t really know where that “Where from here” is coming from, but we have already mostly been there since 2011-2012. :) It’s just Google who isn’t there yet.
If you have a transport business, you will find that you will be able to better live up to your promises AND save on your yearly fuel bill at the same time, if you drop your Google maps routeplanner and buy a Tomtom device (or better: download the Android or iOS app and buy the subscription, it’s cheap). This is all fact, not advertisement blurb. I have left Tomtom long ago and have no affiliation with them whatsoever, except being proud of the work that we did at that time.
Having written this, I also acknowledge that ordinary, occasional users, hardly need all that which TomTom offers. They don’t care if they could reach their destination 5 minutes earlier (as example). Also, they don’t drive enough kilometers to really see big savings in their fuel consumption.
It’s mainly professional drivers who will reap the benefits.
Occasional users are not much worse off with Google maps. Google maps gets you to your destination, and if you don’t care how fast and how much it costs, it’s perfect for you. Because it’s free.
But what people don’t realise is that if you regularly make quite some kilometers to destinations where you have never been before, you will save more on time and fuel than what a subscription to Tomtom’s mobile app costs.
Interesting info… but Google and Apple both have routing that takes into account the average speed on the road at the time, and Apple at least constantly looks for faster routes and offers them, and uses current dynamic info like delays due to roadworks and RTAs.
So maybe those patents got licensed? Or what?
Maps for autonomous vehicles will need to be different.
https://www.caranddriver.com/news/a15352149/why-high-definition-maps-are-essential-to-the-next-generation-of-high-tech-cars/
I’m sure Tomtom continued their development efforts after I left the company. ;) Actually I checked it out and they already have ‘Tomtom HD Maps’ now.
But HD maps are mostly only interesting for driverless cars. A normal driver wants to see an abstraction of the road he’s driving on. For one: they can already see a 100% realistic view of the road through their windscreen. ;) All they need to know is: how far is the next corner, and which direction should I take?
+1 Thanks for the inside.
This is some great insider stuff and the best of what HaD comments section has to offer. Thanks!
An example of routing algorithm challenges is where multiple international border crossings are possible. Which one to chose? In the past, using the Lewiston – Niagara Falls – Buffalo border as an example, I’ve found there is a heavy weight to offer the first crossing (shortest path to exit a country), which then becomes the start point for routing in the new country. An experienced driver would take into account wait times, duty free ammenities, toll roads and conditions on the other side of the border, and perhaps even gasoline prices and then choose. For instance, drive past the first crossing (like Lewiston) and drive to the other extreme end, being Fort Erie Peace Bridge. This becomes the longest path to exit, before navigation begins in the next country. In another example, TOLL road cost is ignored, despite what could be heavy cost/distance ratio. For most recreational drivers, saving 5 minutes driving time, would not be worth a $35 toll (HWY 407!) over a toll-free route. But if that savings is 20 minutes or more… different decision.
Great points.
“An example of routing algorithm challenges is where multiple international border crossings are possible. … An experienced driver would take into account wait times, duty free ammenities, toll roads and conditions on the other side of the border, and perhaps even gasoline prices and then choose”
True. But wait times are real-time data that’s no different than wait-times at red lights. You can average that out and use it as a weight in your route planning.
Toll roads, well, you can offer to route with skipping toll roads. With toll roads, people don’t decide on cost. Most often there is still the ‘old’ road, which is about as long, just slower to ride. That means that it would probably cost as much or even less in fuel than taking the toll road (because your car uses more fuel the faster it goes). People mostly choose the toll road only if they want to get at their destination faster, regardless of cost. It’s convenience that they pay for. Professional drivers might take the toll road because the customer pays anyway, and time to delivery is the most important factor.
Gasoline prices are a bit of a hairy thing. Pump station owners don’t like to publish their fuel prices because they make money on people running out of fuel and having no other choice than fueling up at the nearest station they encounter. If they would publish their prices, drivers would plan a route to the nearest cheaper station (often in a town slightly off the highway), and the nearest visible station (which is often on the highway, and costs quite a few more than a station in a village) would miss the opportunity.
Mind you, I’m Dutch. Our road network is much more dense than the normal US road network, and I’m sure there are other differences.
Would be interesting to see what games use today. Games like Command & Conquer used to be state of the art, predating the TomTom. Suspect early navigation developers found some inspiration there.
Another challenging situation is when certain node connections are only available at certain times/days. My example (over which I’ve pulled lots of hair out) is travelling among the Small Isles in western Scotland. The daily ferry takes different routes each day, and it is impossible as far as I can tell, to visit all four islands for
one night each without returning to the mainland for an extra night or two. It’s like the scheduling department tries to make it hard !
I’d consider paying extra for a GPS that doesn’t try to make me turn across traffic in rush hour, especially while towing a heavy or long trailer, or driving a truck.
Plus I’d love to be able to have it find me suburban parking with a certain height clearance.
I’d love to hear more in this series about CH, HH, and optimizations of A*. I’m a huge fan of the Shakey robot which is what A* was invented for, and of STRIPS, which was the original PDDL used for Shakey. An intern of mine has written a recreation of STRIPS which uses A* and some other optimizations to reduce it’s search space, so this is directly applicable.