Drone Paths

This was a really interesting project I did for my Graph Theory class at UCLA. The context for the problem is the following:

A company plans to use drones to drop sensors to the locations your scheme designated on the map, and wants your help on planning the routes of the drones. You are asked to work out two scenarios:

Scenario 1:

The company will use a large drone that can carry all the sensors; however, this drone consumes fuel fast, and thus it is important to minimize the total travel distance of the drone. The drone will start from a drone station at the center of the map (where the receiver/sink will be), and needs to return to the same point. Moreover, because it is a large drone, as it flies above a square x, it can simultaneously drop sensors not only on the square x but also on all neighboring squares inside a 5 ˆ 5 square with center x.

Scenario 2:

The company will use multiple drones, that are smaller and need to obey the following restrictions:

• Each drone can carry up to 300 sensors at a time.

• Drones depart again from the central node (sink) and can fly to any location on the map even across blocked areas, however, due to fuel constraints, each of these drones can travel a distance of at most 1100 units (counting the return distance) and then it needs to return to the central node to refuel.

• The company has only M drones that can be used for deployment.

The following is my report and a link to the Python notebook I made that solves these 2 scenarios.

Code
Report