Category Archives: Vehicle Routing Problem

A day in the life of a smart-city commuter – and why it’s not so far from reality

Marcin Budka, Bournemouth University

The alarm on your smart phone went off 10 minutes earlier than usual this morning. Parts of the city are closed off in preparation for a popular end of summer event, so congestion is expected to be worse than usual. You’ll need to catch an earlier bus to make it to work on time.

The alarm time is tailored to your morning routine, which is monitored every day by your smart watch. It takes into account the weather forecast (rain expected at 7am), the day of the week (it’s Monday, and traffic is always worse on a Monday), as well as the fact that you went to bed late last night (this morning, you’re likely to be slower than usual). The phone buzzes again – it’s time to leave, if you want to catch that bus.

While walking to the bus stop, your phone suggests a small detour – for some reason, the town square you usually stroll through is very crowded this morning. You pass your favourite coffee shop on your way, and although they have a 20% discount this morning, your phone doesn’t alert you – after all, you’re in a hurry.

After your morning walk, you feel fresh and energised. You check in at the Wi-Fi and Bluetooth-enabled bus stop, which updates the driver of the next bus. He now knows that there are 12 passengers waiting to be picked up, which means he should increase his speed slightly if possible, to give everyone time to board. The bus company is also notified, and are already deploying an extra bus to cope with the high demand along your route. While you wait, you notice a parent with two young children, entertaining themselves with the touch-screen information system installed at the bus stop.

Bus stops of the future.
from www.shutterstock.com

Once the bus arrives, boarding goes smoothly: almost all passengers were using tickets stored on their smart phones, so there was only one time-consuming cash payment. On the bus, you take out a tablet from your bag to catch up on some news and emails using the free on-board Wi-Fi service. You suddenly realise that you forgot to charge your phone, so you connect it to the USB charging point next to the seat. Although the traffic is really slow, you manage to get through most of your work emails, so the time on the bus is by no means wasted.

The moment the bus drops you off in front of your office, your boss informs you of an unplanned visit to a site, so you make a booking with a car-sharing scheme, such as Co-wheels. You secure a car for the journey, with a folding bike in the boot.

Your destination is in the middle of town, so when you arrive on the outskirts you park the shared car in a nearby parking bay (which is actually a member’s unused driveway) and take the bike for the rest of the journey to save time and avoid traffic. Your travel app gives you instructions via your Bluetooth headphones – it suggests how to adjust your speed on the bike, according to your fitness level. Because of your asthma, the app suggests a route that avoids a particularly polluted area.

Sick ride.
Mr.tinDC/Flickr, CC BY-NC-ND

After your meeting, you opt to get a cab back to the office, so that you can answer some emails on the way. With a tap on your smartphone, you order the cab, and in the two minutes it takes to arrive you fold up your bike so that you can return it to the boot of another shared vehicle near your office. You’re in a hurry, so no green reward points for walking today, I’m afraid – but at least you made it to the meeting on time, saving kilograms of CO2 on the way.

Get real

It may sound like fiction, but truth be told, most of the data required to make this day happen are already being collected in one form or another. Your smart phone is able to track your location, speed and even the type of activity that you’re performing at any given time – whether you’re driving, walking or riding a bike.

Meanwhile, fitness trackers and smart watches can monitor your heart rate and physical activity. Your search history and behaviour on social media sites can reveal your interests, tastes and even intentions: for instance, the data created when you look at holiday offers online not only hints at where you want to go, but also when and how much you’re willing to pay for it.

Personal devices aside, the rise of the Internet of Things with distributed networks of all sorts of sensors, which can measure anything from air pollution to traffic intensity, is yet another source of data. Not to mention the constant feed of information available on social media about any topic you care to mention.

The ConversationWith so much data available, it seems as though the picture of our environment is almost complete. But all of these datasets sit in separate systems that don’t interact, managed by different entities which don’t necessarily fancy sharing. So although the technology is already there, our data remains siloed with different organisations, and institutional obstacles stand in the way of attaining this level of service. Whether or not that’s a bad thing, is up to you to decide.

Marcin Budka, Principal Academic in Data Science, Bournemouth University

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

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