Santa Claus Is Coming to Town...

Welcome to the “Illumined Insights” newsletter! Thank you so much for subscribing. This weekly newsletter touches on all things analytics and data science with a focus on areas such as data visualization, AI, and sports analytics.

This week we take a somewhat serious look at Santa Claus and his momentous task to deliver presents to all of the good girls and boys on Christmas.

Stephen Hill, Ph.D.

A 2019 article in the Washington Post (link) estimated that Santa Claus must visit nearly 360 million households during his annual gift-giving adventures around the world on Christmas. The article goes on to estimate that Santa has about 35 hours to complete his deliveries (due to time zones and various sunset/sunrise times around the world). Some “back of the napkin” math yields a necessary speed of 11.2 million miles per hour (18 million kilometers per hour) or just over 1% of the speed of light. Santa would be in quite a hurry to complete his deliveries.

The above calculations don’t even take into consideration the need to develop a route to visit each of the households. This type of routing problem, known as a Traveling Salesman Problem (TSP) has a simple problem statement, but is far from trivial:

The complexity associated with solving a TSP comes from the sheer number of possible routes that can be developed for all but the smallest of problems. How many routes would we need to consider if we were to “brute force" an optimal route to minimize Santa’s travel time by evaluating every possible route and then choosing the shortest one? If we make the assumption that each connection (edge) between destinations is symmetric (i.e., the distance from A to B is the same as from B to A) then we get (396,000,000-1)!/2. Recall that the “!” represents “factorial”. For example, 5! = 5 times 4 times 3 times 2 times 1. For our (396,000,000-1)! value we are dealing with an unimaginably large number. To consider every possible route would take millions of years.

Fortunately, techniques exist that allow us to find the optimal solution without considering every possible route. Unfortunately, these methods can take a long time. Finding an optimal solution for a “large” TSP problem instance can take hours or days or even longer. In short, solving the 360 million household version of the TSP to optimality is beyond our practical reach at this point.

Let’s look at a simplified route for Santa that “just” visits each of the capital cities of the 193 United Nations member states plus Taiwan, Palestine, Kosovo, and Vatican City. This gives us a total of 197 destinations plus the starting point of the North Pole. We’ll assume that Santa is then able to delegate out the present delivery to local elves (or something like that).

We start by finding the latitude and longitude of each of the capital cities . After a bit of digging around online, I came across this site (link) that has a listing of all of the capitals and their coordinates. There are several entities listed that are not part of our list of 197. These were removed. Next, we load the this data into R and use the “distm” function from the “geosphere” package to build a distance matrix. The matrix is calculated with the “haversine formula” that calculates “great-circle” distances between two points given the latitudes and longitudes of the points.

To solve the TSP for these 198 points we use the Concorde solver (link). While the Concorde solver is accessible via the “TSP” R package, it proved a bit difficult to interact with. As a workaround, we write R code to create a “TSPLIB” file that contains the problem characteristics and coordinates of our locations. We can then upload the TSPLIB file to the NEOS server (link). The NEOS server is a free, online repository of over 60 optimization solvers that can be used to solve various optimization problems. Because this problem is not excessively large, we choose to find the exact solution rather than a near-optimal solution.

After a few moments, Concorde, running via the NEOS server produces an optimal solution. The solution is shown in the browser but also emailed.

We then import the optimal tour from the NEOS solution back into R. Now it’s time to plot the optimal tour so that we can get a feel for what Santa’s journey looks like. For our first attempt, let’s just use some basic “ggplot” syntax in R and see what we end up with:

You can get a general feel for the shapes of the continents, but seeing a world map underlying the route would be better. Using ggplot’s “geom_polygon” we can add the world under the route. This is much better, but you’ll notice that there are two routes that appear to cross nearly the entire world. There aren’t actual legs of the route that do this, rather the legs appear like this because they would cross the International Date Line.

To solve this, I chose to migrate to a different package for mapping. The “googleway” package integrates with Google Maps and (helpfully) avoids the International Date Line issue by default. The “googleway” package is described in detail here (link). Note that you’ll need access to the Google Maps API to use this package.

We can zoom in a bit to see Santa’s travels through much of Europe, west Asia, and north Africa.

So, looking at Santa’s optimal route, he begins his journey at the North Pole (of course) before traveling either to Reykjavik, Iceland or Ottawa, Canada. He can traverse the route in either direction because we assume that distances are symmetric. The optimal solution covers 146,179 kilometers (90,831 miles). Traveling at the speed of a typical commercial airliner, Santa could complete this journey in around 160 hours (not counting the time to unload presents at each stop). To complete his journey in 35 hours (the time suggested in the Washington Post article), Santa would need to travel at about 2,595 miles per hour (4176 kilometers per hour) or about 3.4 times the speed of sound. Was that a “ho-ho-ho” I heard trailing that sonic boom on Christmas night???

Illumined Insights Book Recommendations

This week I recommend one of my personal favorite business/analytics books.

Feedback?

Did you enjoy this week’s newsletter? Do you have a topic, tool, or technique that you would like to see featured in a future edition? I’d love to hear from you!

Support the Newsletter?

Support this newsletter with a “coffee” (optional, but appreciated).

Start Your Own Newsletter?

This newsletter is created on and distributed via Beehiiv, the world’s best newsletter platform. Want to start your own newsletter? Click below to get started. Please note that this is an affiliate link. I may receive a small commission if you sign up for Beehiiv via this link.