Do your bit for science (by putting your house on Santa's list)

Algorithms can solve Christmas delivery headache

Date posted

13 December 2016

12:44

COMPUTING experts are joining forces with Santa Claus to ensure nobody misses out on a present at Christmas.
  

Edinburgh Napier software engineers are helping Saint Nick plot the shortest possible sleigh route as he embarks on his annual mammoth Christmas Eve present delivery run.

And families are being asked to register their address to help reinforce the illustration of how software algorithms can solve complex problems – while at the same time ensuring they are not left empty-handed on Christmas Day.

www.routesanta.org was developed by Dr Neil Urquhart, a lecturer in the university’s School of Computing, as a fun festive way of showcasing optimisation techniques. The more people who add their own house to Santa’s list on the webpage demo map, the more effective the demonstration of how the software adjusts the route to incorporate new delivery points.

Neil said: “If Santa has to make five deliveries there are 60 possible routes he can take, but if he has to make 10 deliveries then there are 1.8 million possible routes. As the number of deliveries rises, it soon becomes impossible to check all of the options, even using modern computing power. 

“So how do we find a route for Santa? The secret lies in the fact that we don’t need to find the best route; a short route will do, so we don’t need to check out every possible route.”

www.routesanta.org uses a technique known as an Evolutionary Algorithm, which starts out with a set of random routes and makes small changes.

The better changes - those that make the route shorter - are retained, and over time the length of the routes improves. Evolutionary Algorithm has been used by researchers at Edinburgh Napier and all over the world to solve problems as diverse as designing software, creating university timetables and scheduling waste collection.

Neil said: “Managing delivery logistics effectively and efficiently is a challenge faced by companies and manufacturers of all sizes on a daily basis. The goal is to distribute to as many customers as possible, using the most cost effective and environmentally sustainable route within the desired delivery schedules.”

While adding your home to www.routesanta.org will help to demonstrate the effectiveness of the technology in planning an efficient route, Neil stressed that Santa would have the last word on whether householders had behaved well enough to justify delivery of a present.

To find out more about the technology behind the demo, email him on n.urquhart@napier.ac.uk 


School of Computing

The School of Computing will equip you for the future in a fast-changing and fascinating sector. From networking to cybercrime, sound design to web development, we offer innovative, accredited courses taught by industry experts in labs that feature cutting-edge kit.