Drone Route Optimizer

The final view of the drone routes (the multicolored lines). The green dot is the Depot, and the blue polygon is the region of flight.

Inspiration

Initially being drawn to NextEra Energy because of their commitment to clean energy and our familiarity with their values and mission, we wanted to do a project under their specific track. After reading more about the challenge and having the opportunity to flex our skills with designing efficient algorithms and visualizing skills, we committed to work on a project for the NextEra Energy: Drone Optimization Challenge. Since half of our team members had machine learning and algorithm experience, this track proved to be a challenging but interesting project!

What it does

With the provided data from the track, our project uses an optimized Vehicle Route Planning algorithm and visualization tools to allow users to interact and examine the optimal path of the NextEra Drones on a map.

How we built it

On the backend, we used NumPy and Shapely per the challenge specification to load in the provided datasets. We used SciPy to implement the Floyd-Warshall algorithm and re-create the provided predecessor dataset. We used the Google OR library to design our Vehicle Route Planning algorithm to find a heuristic pathing between the drones and specified photo locations where the drones will take pictures of utility poles. On the frontend we used Streamlit to show the results of the algorithm in a web-view, and Foilum to showcase the routes of the drones on a map.

Challenges we ran into

Since this challenge required significant knowledge about data structures and understanding operational research (OR), we had to spend a lot of our time familiarizing ourselves with popular optimization methods and algorithms for the Traveling Salesman problem. Making an algorithm that didn't have a long runtime also proved to be a challenge, and we feel that our project could explore different types of algorithms that would make the project even more optimized. Our biggest challenge however was the inability of the algorithm to be contained with the provided polygon. The distance matrix given did not have enough information to constrain drone routes to the extremely narrow provided routes, and so there are routes with straight lines through regions outside the polygon. If given more time to work on this challenge, we would use a different coordinate system able to adjust routes to avoid the polygon.

Accomplishments that we're proud of

For two of our team members, this was their first hackathon and it was amazing for them to commit to our project. We're also proud of the fact that our team members learned a significant amount of knowledge, from optimization, visuals, or how these concepts are applied to the real world.

What we learned

We learned more about the mathematical foundations of optimization, such as finding the relationship between the nodes and edges, which helped us make our algorithms. We learned about Streamlit and the power it has to create a frontend from a basic Python project, as well as the Google OR library for an efficient implementation of Vehicle Route Planning algorithm.

What's next for Drone Route Optimizer

Find a more efficient algorithm to reduce runtime and increase accuracy, as well as further polishing our visualizations and front-end of showing off our results.