Why the shortest route might not always be the quickest, or the most fuel efficient

It might seem strange, but UPS delivery vans don’t always take the shortest route between stops. The company gives each driver a specific route to follow and that includes a policy that drivers should never turn through oncoming traffic (that’s left in countries where they drive on the right and vice versa) unless absolutely necessary. This means that routes are sometimes longer than they have to be. So, why do they do it?

Every day, along with thousands of other companies, UPS solves versions of the vehicle routing problem. In these mathematical problems, you are given a set of points and the distances between them, and you have to find the best route(s) to travel through all of them. Best is usually defined as the route with the shortest overall distance.

Vehicle routing problems are used to organise many things, from coping with more delivery trucks in cities and hailing taxis to catching chickens on a farm. The concept was introduced by George Dantzig in 1959. Over 50 years later, and despite a large body of scientific research, scientists are still looking for new ways to tackle the problem.

UPS have moved away from trying to find the shortest route and now look at other criteria to optimise the journey. One of their methods is to try and avoid turning through oncoming traffic at a junction. Although this might be going in the opposite direction of the final destination, it reduces the chances of an accident and cuts delays caused by waiting for a gap in the traffic, which would also waste fuel.

UPS have designed their vehicle routing software to eliminate as many left-hand turns as possible (in countries with right-hand traffic). Typically, only 10% of the turns are left turns. As a result, the company claims it uses 10m gallons less fuel, emits 20,000 tonnes less carbon dioxide and delivers 350,000 more packages every year. The efficiency of planning routes with its navigation software this way has even helped the firm cut the number of trucks it uses by 1,100, bringing down the company’s total distance travelled by 28.5m miles – despite the longer routes.

It seems incredible that not turning left can lead to such significant savings. The TV series Mythbusters tested this idea and confirmed that, despite many more turns, the policy of only turning right does save fuel. In their one truck experiment they travelled further, but when you scale this up to a global level, UPS really does travel fewer miles in total.

The success of UPS’s policy raises the question, why don’t we all avoid turning left (or right, depending on what country we’re in), as we drive around cities on our daily commutes? If everyone did it, the carbon savings would be huge and there’d probably be far less congestion.

The problem is that not every journey would be made more efficient by following this strategy, and most people are likely only to change their driving style if they personally benefit.

Driver’s dilemma

As with anything related to reducing climate change, if everybody else did it then things would get better and you wouldn’t have to change your lifestyle at all to benefit. But it only needs a few people to not cooperate and the whole system breaks down.

This is a good example of the prisoner’s dilemma, the famous game theory problem. If everybody cooperated then the system as a whole would be much better, but the best thing for an individual when everyone else is cooperating is to be uncooperative and reap the rewards of everybody else’s sacrifices.

So, if you cannot persuade people to always turn right (or left) for the benefit of everyone, it might be down to governments to encourage or even enforce the strategy. For example, we could plan roads that make it more difficult to turn through the traffic. It would take a brave city planner to implement this, but if UPS can save 10m gallons of fuel, how much could a whole city or even a whole country save?