Monthly Archives: December 2016

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

Why is the Christmas TV schedule still so eagerly anticipated in the Netflix era?

Joanne Knowles, Liverpool John Moores University

We might think that in an age of on-demand, instantly available viewing, TV scheduling doesn’t matter anymore. But the announcement of the Christmas television schedule still excites viewer anticipation and much media comment. Christmas viewing, it seems, is something the viewing public are invested in, and which evokes feelings of nostalgia and affection.

For broadcasters, too, it’s a chance to demonstrate their values and show how well they represent the public they serve. The well-publicised Christmas Day “ratings battle” has for years been seen as a snapshot of which broadcaster currently prevails in the public’s affections. Is it the BBC, surviving still as Britain’s major public service broadcaster, or ITV – once regarded as the populist rival who gave the people what they really wanted? In either case, issues of scheduling and new viewing habits can have an effect on ratings.

TV networks which have tried experimenting by putting aside the conventions of scheduling haven’t fared well. When Fox decided in 2004 to test out the assumption that the summer is only fit for repeats and low-quality shows by commissioning five new shows for the season, they found their audience share dropped 18% in the Nielsen ratings from the previous summer’s performance. It’s been noted too that summer reruns can also do better than the original screenings of the same material. This reinforces the notion that broadcasters’ top-quality material is best saved for the traditionally more autumn and winter seasons when there is greater demand because people tend to stay at home more.

Doctor Who – a Christmas Day stalwart.

As I’ve found in my research, broadcasters tend to stick to tried and tested assumptions about seasonal scheduling, even in recent years. They save their “best” shows for autumn and winter, consigning less privileged series to the graveyard of the summer slot. And while it is seen as prestigious to be included in the Christmas schedule, ITV was seen as having buried one of its postponed dramas, Mister Eleven, by consigning it to the two Friday evenings before Christmas in 2009 when many people were expected to be on seasonal nights out and at work parties.

The BBC shores up its status as a national institution by providing us with the familiar territory of the Queen’s speech – and returns to former glories by reviving Top of the Pops as a one-off yearly event. While Christmas special episodes of well-loved shows have been long established, a more recent development is the revival of series that have ended their regular run of production to be produced and broadcast solely as Christmas specials. Fondly-regarded series like Only Fools and Horses and The Royle Family have continued to make strictly seasonal appearances in this way. Sherlock’s first series was screened in the summer, but since has found a distinctive position as a Christmas and New Year television event.

This year’s Christmas Day highlights will include the programme now regarded as a contemporary national treasure, The Great British Bake Off, for a final time before the show makes its highly publicised and controversial move to Channel 4, as well as established BBC1 hits such as Call The Midwife. Both these shows can be seen as capturing nostalgia for a historical sense of Britishness which allows the BBC to restate its claim as the nation’s broadcaster.

But the BBC is also careful to attend to audience preferences as well as to the critical reception of its Christmas offerings. The success of the sitcom Mrs Brown’s Boys (which was universally panned by critics but which had many loyal fans) shows this: it was the best-selling box set of 2013, showing its ability to attract consumers who expected to view it repeatedly and at the time of their choice as well as when transmitted. Mrs Brown’s Boys has been particularly successful as a Christmas viewing event – it was the most-watched programme on Christmas Day in both 2013 and 2014.

Mrs Brown’s Boys: back for Christmas in 2016.
BBC/BBC Studios/Alan Peebles

Last year’s ratings winner was ITV’s Downton Abbey, profiting from the relatively new practice of including “timeshifted” viewers who watched the programme up to one week after its Christmas Day transmission.

Some shows benefit more than others from this. Doctor Who, which has itself become a modern staple of Christmas viewing after its revival in 2005, gained just under 2m viewers in 2015 when timeshifting was taken into account, whereas Downton Abbey garnered 4m more viewers. It could be said that this actually marks a kind of victory for Doctor Who as a programme that viewers prefer to sit down and watch in real time on Christmas Day, rather than recording it for later.

But when even the refined in-laws of the BBC’s The Royle Family, in their 2008 Christmas special, confess as they sit down to dinner to have “Sky Plussed the Queen”, we can probably expect that even the apparently hallowed Christmas viewing schedule will become less significant in the future.

Joanne Knowles, Senior Lecturer in Media, Culture, Communication, Liverpool John Moores University

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