The limitations of fastest route navigation

Despite 12 months of Covid restrictions, we can look forward to the return of hustle and bustle in our cities in the near future. I’m sure most people have been in or seen images of London’s black cabs filling the streets and they will return. Whilst taking a traditional black cab in London is usually more expensive than using a service like Uber, black cab drivers argue that it’s better value for money as they can get you to your destination much more quickly.

The reason black cab drivers can do this, they say, is due to the rigorous test they have to pass before they are granted their licence, the world-famous Knowledge.

The Knowledge, which typically takes 3 or 4 years to master, is an in-depth study of London’s streets that has to be committed to memory. A cab driver must be able to take a passenger to their required destination without checking a map, relying on sat nav, or radioing a control room to ask for help. This specialist knowledge, along with a healthy dose of intuition, enables black cab drivers to find the fastest routes and avoid traffic jams, often utilising side streets to save time.

Black Cab

Black cab drivers have a time advantage due to the Knowledge 

More recently, we have adopted satellite navigation technology that can not only measure each possible path in the A to Z but also uses live traffic data to direct drivers to take the quickest route. 

Prior to mass adoption of sat nav, we had a loose equilibrium where the majority of road users, unable to get vital information, would stick to the main roads and those with the Knowledge could make quicker journeys. 

The arrival of car navigation apps created a new dynamic. With information about alternative routes that can reduce journey times, cars other than black cabs can choose to go on the quieter roads. With the Knowledge now available to everyone via technology, we would hope that the overall time spent on roads would decline. However, this isn’t necessarily the case. 

In some situations, we get more traffic as algorithms push too many cars on to certain routes. In others, we don’t use the roads optimally which means time is added to journeys unnecessarily. Importantly, this might explain why black cabs continue to beat Uber cabs on speed tests.

Imperfect information

Navigation apps do not possess perfect information on road use. They may understand some of the current demands on the road such as live positional data or planned routes from those who have entered their destination into the app. They will also have access to historic data around daily peaks and troughs in road usage. 

Navigation apps miss a lot of critical information because humans don’t run to the exact same schedule every day. We may set off 5 minutes earlier or later than usual. We miss going through predicted green lights, or may take a slightly different route, for example, to collect something on our trip. This information is unlikely to be fed into data systems in sufficient time to update routes for all road users in a network. 

As a result, even if we have system-wide traffic reduction, we create an excess supply of cars into certain roads due to traffic variance. Also, note that the excess supply can lead to chaotic conditions as traffic can be non-linear. Just a few too many cars on a single-lane back street can cause severe delays if no suitable passing points exist. 

Modelling to optimise

One of the ways to model traffic across a road network is to look for Nash equilibria, a concept in game theory first proposed by the mathematician John Nash, who was famously portrayed by Russell Crowe in the film A Beautiful Mind. A Nash equilibrium occurs when multiple people agree to a situation that satisfies their needs as they each seek the best outcome for themselves. This could be a happy, or in some cases, an unhappy compromise. 

Most negotiations, including Brexit for example, tend towards a Nash equilibrium, where both sides are relatively happy. However, human behaviour can lead to other issues as indicated by Braess’s Paradox where adding a solution to try and improve a road system can quite quickly become obsolete as the new solution becomes systematically overwhelmed with our own new behaviour. 

A good example of this has been seen recently. Reducing stamp duty on property purchases to help people get a foot on the ladder didn’t actually do much to  help first-time buyers. The purchasing power created by the tax reduction simply lifted house prices resulting in a transfer of wealth from the government (or taxpayers) to existing homeowners. 

Cars and routes – Wardrop, Braess and Nash equilibria

To help illustrate how these models can help solve problems in the real world, imagine we have been asked to find a solution to reduce pollution on the roads between 2 cities. We assume that less time on the road means less pollution and that drivers will attempt to optimise their own time on the road using sat navs. 

Our 2 cities, A and B, are connected via 3 routes:

Route 1 goes from City A to City B via Town C. The journey from A to C takes 7 minutes plus N/2000 where N is the number of cars on that route. If there are 2000 cars on the route, the journey will take 8 minutes. Similarly, Town C to City B takes 5 plus N/2000 minutes. 

Route 2 goes from City A to City B via Town D, which again takes different times depending on the traffic on the road, as shown in the table below. 

Route 3 goes direct from City A to City B via a narrow road that struggles with higher car demand but is quicker when very quiet.

Route Step 1 Step 1 time Step 2 Step 2 time
1 (A to C then B) A to C 7 + N/2000 C to B 5 + N/2000
2 (A to D then B) A to D 5 + N/2000 D to B 6 + N/2000
3 (A to B) A to B 10 + N/1000

Let’s assume that 2000 cars are making the journey at around the same time, and all the cars are using sat nav that can predict how long the journey will take based on other cars and historic and current traffic numbers. 

The sat nav systems are programmed to make each car’s journey as fast as possible (optimised for the individual), so if too many cars are travelling on one particular route then the navigation will recommend another route that will be quicker. 

With just 2000 cars, no traffic is directed via Route 1 as it takes too long, 25% of the traffic goes via Route 2, and 75% of traffic chooses Route 3. (You can see the maths here).

All cars and routes should end up taking the same time as if Option 2 was slightly longer, some cars will divert to Option 3, making the overall times equal. 

Route Total cars Car journey time
1 (A to C then B) 0 12 minutes
2 (A to D then B) 500 11 minutes 30 seconds
3 (A to B) 1500 11 minutes 30 seconds

As well as looking at the times of individual journeys we also want to know how much time in total was spent on the road. 2000 cars each spending 11 minutes and 30 seconds on the road gives a total road time of 23,000 minutes. This is a Nash equilibrium as each driver follows their own set of rules provided by the sat nav. 

However, this isn’t the optimal solution for our roads. We are actually better off if we don’t optimise each car for the fastest route. Instead, we should aim to aim to minimise the total time all the cars spend on the road.

The answer to that looks like this:

Route Total cars Car journey time
1 (A to C then B) 200 12 minutes 12 seconds
2 (A to D then B) 650 11 minutes 39 seconds
3 (A to B) 1150 11 minutes 9 seconds

We should programme the sat navs to send 200 cars via the slower Route 1 and 650 cars via Route 2. 

We will see a much larger diversion in times, which is somewhat unfair on individual drivers, but we cut the total time on the road to 22,835 minutes. That’s a 0.7% reduction in time, which equates to a 0.7% reduction in pollution. 

If we increase the number of cars to 4000, and the sat navs are set to “fastest time for me” the Nash equilibrium split is different again: 

Route Total cars Car journey time
1 (A to C then B) 333 12 minutes 20 seconds
2 (A to D then B) 1333 12 minutes 20 seconds
3 (A to B) 2334 12 minutes 20 seconds

This time some cars are advised to take Route 1 while a lower proportion is sent via Route 3. This scenario gives a total time for all cars of 49,334 minutes. 

If we now optimise the journeys for the lowest total time on the road the numbers look like this: 

Route Total cars Car journey time
1 (A to C then B) 819 12 minutes 49 seconds
2 (A to D then B) 1362 12 minutes 22 seconds
3 (A to B) 1819 11 minutes 49 seconds

This equates to a total time on the road of 48,834 minutes which is a 1% reduction compared to the “fastest time for me” approach.

John Wardrop, an English mathematician, who developed ideas related to Nash’s model called the system optimal principle the “social equilibrium” and the user optimal principle the “selfish equilibrium”.

From simple to complex

There is, of course, a bigger challenge when running this assessment over entire towns and cities and for any model to work we would require compliance from drivers. 

The examples above give relatively small gains, whereas we would need much bigger gains on our chronically blocked roads to make a difference. To find new optimisations at a system level we would probably need to incentivise or penalise drivers and passengers to achieve this, charging drivers for the price of anarchy. 

The model also explains why there are valid reasons for allowing bus lanes or lanes for cars with multiple passengers; they help reduce the overall number of cars on routes as well as pollution and the time discrimination benefits more people. 

A key requirement for wider improvements would be the implementation of 2-way communications between drivers and traffic control systems. Likewise, when autonomous cars arrive, we will have to force algorithms to follow system-wide rules if we are to optimise the roads – indeed we may need to do so to ensure chaos does not ensue. 

Assuming that we evolve to a pay-as-you-go road model, decisions will need to be made about how we add additional charges to those that benefit from faster routes, or if we run a randomising process for cars. We will also need to take into consideration partial journeys. 

Electric vehicle charging

Another of the areas where our modelling can apply is around Electric Vehicle (EV) charging, which will need some sophisticated planning to manage traffic flow to and from charging points. 

Many electric car owners, looking to self-optimise will seek public EV charging as and when they need it, and once they have a parking spot are unlikely to leave until the car is fully charged. Parking spots will be occupied for different lengths of time depending on the wattage of the charging station and the model of the car plugged into it. 

Electric charging points

How to prevent a chaotic future at EV charging points

If we look to optimise on an individual basis, we will find many drivers pick the fastest charging stations when they don’t need to, which means other drivers who only wanted to charge for short periods are saddled with longer waits. We will quickly trend towards a selfish equilibrium (Wardrop) that is a long way away from any social or system wide optimal solution. 

We also need to consider the walk from the charging destination to where the driver eventually wants to go, be it home, work, or the shops, and factor that into how long they need to charge for. Opportunistic partial charges will be a critical component and dynamic pricing may be needed to reflect an objective to increase driver throughput. 

Like roads, EV charging doesn’t yet have good enough controls to push the system to any sort of suitable Nash equilibrium or system-wide optimisation. You still can’t reliably book EV charging from your phone and most of the apps available are illegal to use whilst driving. 

With the expanding number of EV charging suppliers entering the market, if we don’t start addressing all of these issues now, we face a pretty chaotic future. 

Footnote:

The linear traffic model used does not reflect real-world car behaviour. It was chosen as a simple method to show how increased traffic can increase journey times and lead to different types of system optimisation and equilibria.