This year, Sinterklaas wants to take a smarter approach. That is why, in the series Sinteresting, he visits researchers at the University of Twente. For his route-planning dilemma, he turns to Clara Stegehuis, Associate Professor in Applied Mathematics.
A familiar mathematical problem
When Sinterklaas explains how he travelled through the country last year, Clara immediately shakes her head. "Sinterklaas, alphabetical order may feel organised, but it is nowhere near efficient. You keep travelling back and forth when that really isn’t necessary."
She explains that his challenge looks a lot like the travelling salesman problem, often abbreviated as TSP. This well-known mathematical problem asks a seemingly simple question: what is the shortest route that visits a series of cities without skipping any?
"Imagine you want to visit twenty cities," Clara begins. "Because you always depart from the same place – the steamboat – the starting point is fixed. For the remaining nineteen cities, you could, in theory, calculate every possible order: nineteen times eighteen times seventeen… all the way down to one. That is what we call nineteen factorial. And that number is enormous. To be precise: 121,645,100,408,832,000 — more than 120 quadrillion possible routes."
Why smarter calculations are needed
Fortunately, Clara explains, we do not have to calculate all those possibilities. There is a much smarter method called Branch and Bound. It works a bit like looking ahead. You estimate how short a route can possibly become. If you already know that a route will be longer than another one you have found earlier, you can discard that option immediately and continue with a route that still has a chance of being the shortest.
Clara sketches the situation with a few quick lines on paper. "In mathematics, we call this a decision tree," she says. "Every time you choose the next city to visit, a new branch appears. But instead of working out every branch completely, we first calculate a lower bound. If that bound is already worse than a route we found earlier, we cut that branch off. There is no need to explore it further."
To make it concrete, Clara gives an example. "Suppose you start from the steamboat and need to visit three cities: Enschede, Amsterdam and Maastricht. That gives you three possible starting branches. If we follow the branch to Enschede first, two possibilities remain. For each branch we can calculate a minimum possible distance. If that minimum is already too long, we stop right away."
Sinterklaas looks relieved. "So Rekenpiet doesn’t have to calculate everything after all?" "Exactly," Clara replies. "We only explore the routes that still have a chance of being the best."
Delivering presents much faster
With this smarter calculation method, Sinterklaas can significantly shorten his route.
And if he sends a few Pieten into the surrounding villages from each major city, he no longer needs to visit every place himself. "If you approach it like this," Clara continues, "you should have no trouble finishing on time this year."
Technology closer than you might think
Clara’s explanation shows how applied mathematics can help make smarter choices in complex situations. That applies to logistics, but just as easily to a story about presents and Pieten. Mathematical theory becomes far more interesting once you see how practical it can be – useful for Sinterklaas, but also for delivery services facing the same December rush every year.
Watch the video to see how Clara and Sinterklaas work together to ensure every present arrives on time.
