How does your navigation system find the fastest route in a road network, if it does not know where traffic jams occur and how long they last?
It is an early summer morning and you and your family are looking forward to spending a few weeks near a beautiful lake in Italy. The sun has just risen when you load the last suitcase in the trunk of your car and take place behind the wheel, ready to drive to the airport for your early flight to Milan. It is important to get to the airport on time, as the summer season results in long waiting lines at airport security. That’s why you already asked your navigation system the travel time of the shortest route from your house to the airport the night before and chose your departure time accordingly.
When you start the car, you notice that your family has already fallen asleep. The only sounds come from the car engine and the navigation system, that has just turned on.
You suddenly get alarmed, as your navigation system shows the same route it did last night, but with a longer travel time! How is that possible, if the route has not changed… Can you trust the way your navigation system computes travel times? Does it take possible delays into account? And if so, how is it able to predict the delay you will experience on your route?
The first navigation systems
Millions of people make routing decisions every day, trying to find the shortest route between, for example, their home and work. If you would know that you could simply drive the maximum speed on each road, you could compute the travel time of all possible routes and pick the fastest. The first navigation systems did a similar thing: compute the fastest route under the assumption that you will always drive at maximum speed.
However, there are routes from your home to the airport in which you have to travel through Spain or Norway, and you can imagine that these would never qualify as the shortest route. The first navigation systems, therefore, used a smart procedure, called Dijkstra’s algorithm, in which only routes that are relatively close to both your house and the airport are taken into account.
The problem with this procedure, however, is that you will not always be able to drive the maximum speed on every road, due to events such as traffic accidents and heavy rainfall. In the search for the optimal route, it is important to take the effect of these events into account, as you do not want to end up in a long traffic jam, resulting in you and your family missing your flight…
Delays that show a pattern
Your navigation system is clearly not just following Dijkstra’s procedure, since you know it would then always show the same travel time for the same route. That means that it takes some extra information into account, which it uses to better predict your travel time. You still don’t know what this information is, but you decide to trust the system and drive the route it advises, hoping you will get to the airport on time.
At the first intersection on the route, you are unfortunate and have to wait for a red light. When you look around, you notice that it is busy at this intersection. Your watch shows that it is around the time you would normally travel to work, which is often around the time the rush hour starts as well. On workdays, you try to travel around this time, as you know from experience that your delay will be much less severe than it would be when travelling in the middle of the rush hour. Then you suddenly realise that the upcoming rush hour may be the cause of the longer travel time prediction, because if you can already predict that the delay will be more severe later this morning, your navigation system should be able to do this as well!
Rush hour satisfies a regular pattern, and your navigation system is therefore indeed able to adequately predict the delay you will suffer from it. The Dutch road network contains loop detectors that count how many cars pass that point per minute and track their average speed. By studying data collected from these detectors you can observe the speed pattern during rush hour on a certain road. Data of the past years may reveal that during rush hour, the driven speed on a certain road in the city first decreases gradually, then stays constant for a while, and ultimately increases back to the maximum speed, the pattern shown in the figure below.
Your navigation system now uses these speed patterns to make a better travel time prediction. These speeds are dependent on the time of day, making the travel time prediction dependent on your time of departure. Last night, when asking your navigation system the travel time of the shortest route, you did not realize this yet. Therefore, you did not specify your time of departure, with as result a different travel time prediction as compared to this morning.
Delays that show no pattern
Satisfied that you know why your navigation system showed a longer travel time this morning compared to last night, you continue driving on the route. Snoring sounds confirm that your family is still asleep and, if the travel time turns out as predicted, you will still make it to the airport in time.
You are, however, not fully at ease, as there might still be unexpected traffic jams on the route, and you are not sure if your navigation system takes these into account as well…
Predicting the occurrence and consequences of unpredictable events is a difficult task for your navigation system. Recent developments in navigation systems and their connection to the internet, allow for communication between road managers and your navigation system. This way, if an incident occurs – if, say, a truck driver falls asleep and causes an accident – your navigation system will be informed.
Unfortunately, most navigation systems do not yet know how to use this information to predict the consequences to your travel time. Some navigation systems will just advise you to change your route, and circumvent the incident altogether. This is not always the best option, as it may just be a broken-down vehicle stranded on the emergency lane having no effect on your travel time. So how can future navigation systems use the incident information to find an optimal route?
Studying incidents that happened on a road in the past can help predict the travel time you are facing when there is currently an incident. One way to do this is by using probabilities. Your navigation system could collect all the durations of past incidents and compute the probability of a certain duration. With this information, your navigation system can e.g. compute the probability that the incident is already cleared when you arrive at the incident location. This is of course extremely helpful in predicting the consequences of an incident to your travel time.
But, as it turns out, the use of probabilities also leads to some difficulties, one of which directly involves your own choices: the amount of risk you are willing to take!
To understand how the amount of risk you are willing to take determines your optimal route, let’s return to the car. You are still driving to the airport and still intend on catching that flight. Imagine that you have to choose between route A and route B, of which route A is longer in distance and therefore generally takes longer to traverse. Your navigation system has been notified that there is an incident at the end of route B, and, with the data it has stored from past incidents, computes that the probability that this incident is cleared when you arrive there is high. The expected travel time on route B is therefore still lower than the expected travel time on route A. There is, however, a small probability that the incident is not cleared when you arrive, in which case you will not make it to the airport in time. Because you do not want to take that risk, you prefer route A, for which the probability of on-time arrival is higher. Thus, your navigation system will need to know how much risk you are willing to take, to determine what your optimal route is.
Unfortunately, the navigation system in your car does not have this functionality yet, but new advances in both mathematics and traffic monitoring will lead to better routing advice in future navigation systems, that can take your wishes into account! Currently, you can already use the detection of incidents by road managers and their communication to your navigation system to circumvent incidents and reduce the risk of ending up in a long traffic jam. So, on your way to the airport, you keep paying attention to the navigation system, as to not miss any valuable information on the road conditions. Luckily, there are no incidents on your route and you arrive at the airport on time. Italy, here you come!
What if I tell you that long queues in airports are also caused by the impatient passengers that arrive too far in advance at the airport? Today, we will analyze how the organization of the security check queue affects the waiting time of passengers.
You have a job interview in 20 minutes and you are in a hurry to arrive at your application in time. To make matters even more stressful, there are many routes to your destination, but you have no idea which one to select. Luckily, you have access to a navigation system that can help you in your route selection process.
Recently there has been a breakthrough in the field of algorithms for geometric network problems, concerning the complexity of the Euclidean Travelling Salesman Problem.
It is safe to say that traveling impacts the peak performance of teams and athletes in general - studies have been done across all kinds of sports that confirm this intuitive idea. Thus, to avoid unfair- and unhappiness, an organizer should aim to minimize the effect of travel time disparities.
