Category Archives: VRP

Why UPS drivers don’t turn left and you probably shouldn’t either

Graham Kendall, University of Nottingham

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.

Vehicle routing problems involve finding the best route between points.
Wikipedia Commons

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?

Graham Kendall, Professor of Computer Science and Provost/CEO/PVC, University of Nottingham

This article was originally published on The Conversation. Read the original article.

Help solve Santa’s logistics troubles with a little maths

Hzc4c9fp 1387556093
It’s a long way for one man and his reindeer to travel.

Graham Kendall, University of Nottingham

In just one night, Santa has to visit millions of homes to deliver presents. If he could travel at the speed of light, the task would be simple. The Conversation

However, Einstein’s formula, E=MC², tells us that anything with mass cannot travel faster than the speed of light. And as we all know, Santa has mass. That’s before you even count all the presents that have to be transported along with his sleigh. Then add Rudolph and co and what you get is a lot of flying mass that makes Santa’s chances of travelling faster than light pretty slim.

Luckily, there are other options available to Santa to help increase his chances of delivering all the presents on time. And they relate to what is known in maths as The Travelling Salesman Problem.

Even Einstein couldn’t solve Santa’s woes.

In this problem, a salesman has to plan a route through a number of cities. He has to start and end at the same city and visit every other city in between just once, while minimising the distance he travels. If we replace the salesman with Santa and the cities with chimneys, then Santa’s problem is a variant of the Travelling Salesman Problem.

Unfortunately, this isn’t much consolation to Santa. The Travelling Salesman Problem is known to be NP-Complete. This means that there is no known efficient algorithm that always returns the optimal solution in a reasonable time.

In fact, most mathematicians and computer scientists believe that no such algorithm exists, although this is yet to be proved. Anyone who can prove that it does exist (or indeed that it doesn’t) stands to win $1 million for solving one of the Millennium Problems and proving whether P=NP (or not).

Back to Santa. What can he do to plan his route? Although we do not know of an algorithm that is guaranteed to tell Santa the best route to take, there are algorithms that attempt to do this in reasonable time.

It’s not even simple when he gets to his destination.

The Route Santa application, from Napier University, is one. The app shows an example of an algorithm solving the Travelling Santa Problem. Those hoping to receive gifts on the 25 December can contribute to the efficient running of Santa’s rounds by uploading their address into an interactive map. The Route Santa software will then add that address to its list and work out the best route for Rudolph. The more hopeful recipients that sign up, the more efficient Santa’s journey will be.

One type of the algorithm used for these type of problems are known as genetic algorithms because they are based on natural phenomena such as evolution, inheritance and selection.

Santa’s problem is your problem too

We tend to take it for granted that Santa will make his millions of deliveries on time every year but the Travelling Salesman Problem affects our daily lives, particularly now that so much of what we buy, from our food to our clothes and technology is delivered to our doors. If we can work out the best route for Santa, we can also contribute to thinking about how to make other delivery services more efficient for the other 11 months of the year.

Graham Kendall, Professor of Operations Research and Vice-Provost, University of Nottingham

This article was originally published on The Conversation. Read the original article.

The Conversation