DroneDash: Santa’s Test Flight at UCI

Shortest route

Inspiration

With recent advances in technology and data science, Santa wishes to automate delivering gifts on Christmas so he resorts to using a fleet of drones. With rising fuel prices, he wants to make this process as efficient as possible and reduce the time the drones are in the air.

What it does

Our algorithm solves the Traveling Salesman Problem, a classical optimization problem in computer science, to find the optimal path that visits every location once, starting and ending from UC Irvine.

How we built it

The Melissa’s Datathon dataset provided us with address, city, state, and zip code. From this data, we extracted street names, and used Melissa’s Global Address Web API to extract the latitude and longitude. We primarily used Python and C++ for the algorithm and R for EDA. The final presentation was constructed in Canva.

Challenges we ran into

We initially had some trouble using Melissa’s API to get geocode data. The main challenge we ran into was finding a balance between accuracy and efficiency for our algorithm. We wanted to find the best approximation possible while minimizing computational complexity.

Accomplishments that we're proud of

We were able to significantly reduce the computational cost of finding the shortest route. We creatively utilized our street data to partition the addresses and connected the clusters by their endpoints.

What we learned

We discovered that we trade accuracy, i.e., finding the shortest possible path, for efficient calculation of a path that is “short enough”.

What's next for DroneDash: Santa’s Test Flight at UCI

Our algorithm still has room for improvement in shortening routes, and its effectiveness largely depends on data clustering. For instance, when Santa operates along a single street, the optimized algorithm can simply cover all stops in one continuous pass. However, if the dataset lacks repeating street clusters, we must rely on the general algorithm. Notably, both methods currently fall short of establishing the ideal connections between different clusters—a challenge we plan to tackle in future updates.