Christmas is just around the corner and at Itility we decided to embrace the spirit of this holiday, by giving our November hackathon a holiday twist. Our challenge this time was to act as Santa’s Data-Scientist-Elves (DSEs) and ensure that all of the gifts are delivered in the most efficient way.

What exactly needs to be done?

The challenge was to plan delivery routes of 100.000 gifts of different weights to locations across the globe. To make it more interesting, there are two constraints:

1. Total weight of sleigh constraint (TWOS): Yes, it’s all magic, but even magic has its limit; and so does the sleigh. In our case the sleigh is able to take up to 500kg, excluding Santa.
2. Reindeers Weariness Index (RWI): Even though they possess superpowers, reindeers do get tired. In addition to carrying all the gifts they need to carry Santa (150kg) and the sleigh itself (10kg). Therefore, the teams had to ensure that the number of trips is as low as possible and at the same time the load is as light as possible. To put it in mathematical terms, RWI is calculated as follows:

 
Together with the famous applause meter, the RWI score was later used to determine the winner of the challenge. 

After splitting into 5 teams, DSEs were ready to go. In our hackathon time is at the essence, so shortcuts and simplifications are a much welcomed approach. But as always that brings the question: was it worth it this time?

1. Minimizing covered distance
This solution aimed to simplify the problem by focusing only on minimizing the distance covered by Santa and filling up the sleigh to its maximal capacity. Though it might have seemed like a smart shortcut, it still required significant optimization and modification of the valid route to meet the TWOS requirement. Taken together all the necessary work, the two hours proved to be insufficient to produce a valid solution. Interestingly, not only the time was an issue here. This solution required quite a significant amount of computational power and in the end wasn’t a valid shortcut.

2. Clustering
Another shortcut solution included clustering locations based on their longitude and latitude. Gifts would be then distributed within individual clusters. The main challenge here is balancing the weight of boxes in a given trip. This proved to be a popular solution with three of the teams trying this approach. Interestingly, taking into account only the longitude of the location (since each trip starts and ends at the North pole) resulted in significant reduction of the number of East-West trips, and a lower RWI.

3. Visualizing
Understand your data first. This principle was what drove the success of the winners. They started by plotting the data and analyzing the distribution of the delivery locations. What they noticed is that the locations are quite uniformly distributed across continents, with no locations at sea. Based on this insight, the team decided to isolate locations close to the South Pole as very 'RWI-costly' and keep the number of trips to that area to the minimum. Further they used a longitude clustering limiting East-West type of trips. At the same time, the gifts along individual longitudinal clusters were delivered in a sequence based on their latitude, so nearby present could reach their destination within the same trip. 

Two hours passed quickly and it was time for each team to take the stage and present their solution. Presentations featured many Christmas-themed puns and pictures; all in the spirit of entertaining the audience and winning their approval (as usual measured by applause meter).

While normally this is the end of the hackathons, and we all move back to our regular projects the next day, this challenge proved more special. A few days later we received a new solution from one of the participants, and he has beaten the winners! Now, that’s the competition spirit!

Want to join next time? Sign up for our upcoming hackathon.