The elves approached the problem in several different ways, ranging from complex to naively simple. This is because some participants spent a few hours working on an optimal solution, while other participants didn’t have as much time to contribute or focused their time on making a festive map. Several entries employed Mixed Integer-Linear Programming using the CBC solver. Of course, the problem is too large to solve as an optimization problem directly while considering all possible routes.
One method was to optimize subsets of the cities, and then visually decide where to link one subset to the next. Another method was to solve the optimization while relaxing the “no sub-tours” constraint, and then progressively add constraints until all sub-tours are eliminated (similar to this post).
Another method employed the mlrose python package and genetic algorithms as the solver. Here’s the best route discovered by the elves, which used the CBC solver and progressively added constraints to eliminate sub-tours.
Some elves tried to implement solutions from scratch. One such elf surveyed greedy routes: Start with a random city, send Santa to the next-closest city not already visited, and continue until all cities are visited. Try that with each candidate city as a starting point, and then use the best solution. While this resulted in a slightly longer trip overall, it ran in a fraction of the time that it takes to execute the optimizers.
Some elves took an even more naïve approach, and we thank them for establishing a baseline of sorts. If Santa were to average the latitude and longitude of each city, and then rank the cities by that average, he would have to travel over 3 times as far as the best solution. Here’s the rather comical path that he would take:
There were even some elves that decided to add additional factors to make the problem more interesting.
What if Santa has to slow down to take sharp angles?
What if he has to consider population density?
What if he can only deliver when its dark outside at the specific location?
This is the beauty of a Datathon: if there is something that seems interesting to a participant, this is the time to pursue it, learn about it, and share it with peers. (In real-world problems, great value often comes from brainstorming beyond the presented constraints, but the team has to be careful to budget time appropriately.)