Algorithm to use for reaching points from landing pod

Question

I have a quadcopter with some sensors and I want to measure values in set of points on the map (2d problem). Every measurement takes 30 seconds and I assume copter has constant speed of 60km/h. It can fly constantly 20 minutes and then it needs to land to charge for an hour.

I would like to write an algorithm, that automatically computes flight paths and minimizes time to take all the samples.

I can represent the points as a full graph (I assume I am flying so high, that there are no obstacles). Then time to reach the point is cost on the edge, but I have also cost of visiting the vertex and limited "fuel". It is some generalization of TSP or VRP, but I am not sure which one.

There are also problems with gas stations, but they usually find path between two points.

Can you name an algorithm that could solve this or come up with something similar. It is NP hard, but there could be some nice approximate solutions.

Answer 1

The problem isn't easy to solve because there is also the fuel constraints and you need to find groups of pods. You can use a combination of a brute force algorithm and a heuristic. For example a quad tree or a spatial index (hilbert curve) can reduce the dimensions and the search space. It looks similar to the capacitated vehicle routing problem.