Mathematics teachers have long enjoyed using Santa Claus and Christmas Eve as an opportunity to talk about the travelling salesman problem (TSP). In this problem, you are given a list of cities and asked to determine the most efficient route that visits every single city exactly once and returns home.
The Christmas version of this problem asks: What is the most efficient route for Santa Claus to take that allows him to start at the North Pole, visit every household in the world that celebrates Christmas exactly once, and return home safely?
Teachers love talking about this problem because it is very hard. The only way to be absolutely certain that you get the correct answer would be to go through every single possible route from city to city, measure the distance of each route, and pick the route that is the shortest.
This approach is simple if you are only visiting a few cities, but the number of possible routes becomes unmanageable very quickly. If you are visiting 10 cities, there are 362,880 possible routes. If you are visiting 20 cities, there are 1.216 million possible routes.
The solution to the TSP for major U.S. cities
David Applegate, Robert Bixby, Vasek Chvatal, and William Cook
The current record, held by the fastest computers, solves the problem for 13,509 locations. Using multiple computers working together, the problem took three months to solve.
In reality, however, Santa’s problem is much more severe than the TSP examples suggest. After all, Santa does not merely visit city centers. According to popular legend, he must potentially visit every residence that celebrates Christmas in the entire world—or, at a minimum, every such residence that contains at least one member who has been sufficiently non-naughty as to deserve a gift.
We will refer to these as “qualifying residences.”
No matter how you slice it, Santa’s traditional single-sleigh approach to Christmas Eve is grotesquely inefficient.
Even the most remote rural areas can contain qualifying residences. During the evening of Dec. 24, there may even be boats in the ocean and planes in the air that could be qualifying residences. Any route used by Mr. Claus must at least have the capacity to be adapted to visit any point on the surface of the Earth during his “tour” on Christmas Eve.
So even with the most efficient route, it will still be a long way to travel in a very short amount of time. The standard physics model of Santa’s behavior, therefore, usually assumes that he travels just under the speed of light.
While this solution does allow him to complete his duties in a reasonable amount of time, it comes with its own perils. For example, accelerating and decelerating at each stop consumes vast amounts of energy, something that Santa must surely be sensitive to in these times of limited fossil fuels.
Then there is the problem of heat caused by the friction of moving through the atmosphere at such high speeds: Santa must undoubtedly be worried that this could contribute to the problem of global warming.
All in all, we have to admit, no matter how you slice it, Santa’s traditional single-sleigh approach to Christmas Eve is grotesquely inefficient. Luckily, there is a better solution: drones.
Distributed delivery
The real problem with Santa’s current approach to present delivery is that he is using a single-threaded, serial solution. By dividing the work of delivery among an arbitrarily large set of drones—a “Yuletide swarm,” if you will—the time required to deliver to every qualifying household in the world, and the speeds required to accomplish this in a single evening, would be greatly reduced.
If time is the most important consideration, then the most efficient way to deliver presents would be to assign a separate individual drone for every qualifying residence—a pitch not that far removed from Amazon’s investments in drone delivery. In this scenario, the amount of time that it would take to deliver every single present in the world would simply be equal to the amount of time that it would take for the longest journey.
There is some debate among holiday season scholars as to whether Santa’s home office is at the geographic North Pole, the magnetic North Pole, or the city of North Pole, Alaska. For convenience, we will assume for our calculations that Santa delivers presents from the geographic North Pole.
The farthest residence from the geographic North Pole is, of course, the geographic South Pole. The Amundsen–Scott South Pole Station is located there, and on Dec. 24, during the warm season, the population there is generally around 200 researchers.
If we assume that at least one of these 200 individuals both celebrates Christmas and meets the minimum required level of non-naughtiness, then Santa would be required to deliver to this location.
The straight-line surface distance from the North Pole to the South Pole is 20,004 kilometres (12,430 miles). With altitude changes during take-off and landing, the actual distance traveled by the drone would be slightly more than that.
Can current drone technology make this trip within the given time frame?
The drones that most people have been talking about in conversations of commercial delivery have been octocopters or quadcopters. These devices are notoriously slow, and can only fly for a limited amount of time. Top speeds are around 80kph, but only for very short periods of time before they have to land and recharge or refuel.
If Santa chose to use a swarm of Predators to delivery Christmas presents, it could travel from the North Pole to the South Pole in approximately four days.
So a Santa Swarm of quadcopters, or anything similar, would be unlikely to ever make a journey from the geographic North Pole to the geographic South Pole.
But who says Santa needs to use the same technology that Amazon says it wants to deliver DVDs with?
Leveling up
The top speed of the modern-day military Predator drone is about 135mph. If Santa chose to use a swarm of Predators to delivery Christmas presents, assuming that there would be no need for the drone to stop to refuel, it could travel from the North Pole to the South Pole in approximately four days.
This is not necessarily a deal-breaker. One of the advantages of using a swarm of drones acting in parallel is that there is no reason that they would all need to wait until Christmas Eve to leave the North Pole. One easy solution would simply be to send out those drones that needed to travel the farthest a few days early.
The Predator drone, however, is not the fastest drone technology available. Boeing transformed one of its signature Lockheed Martin F-16s into a drone and flew it unmanned from Florida to the Gulf of Mexico. F-16s reach a top speed of about 1,500mph (Mach 2).
In theory, if Santa used a swarm of these puppies, with one F-16 drone for each qualifying Christmas-celebrating residence, the entire worldwide delivery could be completed in just over eight hours.
A sensible proposal
Naturally, there are still practical details to be hammered out. For regions that are closer to the North Pole, it may be sensible to use the same F-16 drone for multiple deliveries, rather than investing in a separate drone for every single qualifying residence.
A fleet of some 80 million or so F-16 drones would be expensive after all. (Then again, economics rarely seems to be a factor for Santa Claus. Does he pay for all of the presents himself? Is he reimbursed by the public sector? Does he pay his reindeer, or are they indentured servants? Such mercantile issues are not really addressed in the Santa-related literature.)
Nonetheless, these are minor details compared to the dramatic increase in efficiency that Santa will gain by replacing his light-speed traveling, single-sleigh approach with the much more sensible “Yuletide swarm” of unmanned drones.
And surely the children will support this move, too. After all, reindeer are charming and all, but what child would not prefer the excitement of having an F-16 land on the roof on Christmas Eve?
A version of this story originally appeared on the Kernel on Dec. 17, 2013.
Photo via Dennis Jarvis/Flickr (CC BY 2.0) | Remix by Max Fleishman
