This paper introduces a monitoring problem with limited energy resources and soft constraints on priorities employing a fleet of unmanned aerial vehicles (UAVs). This monitoring problem is a generalization of application cases ranging from surveillance of open-air events to monitoring crime scenes or disaster sites. In order to compute solutions, we propose an insertion heuristic with a negotiation mechanism for energy resources. The solution quality of the heuristic method is compared to cases where an optimal solution is known resulting in an average deviation of approximately 4%. By using this approach, we are able to plan routes for real-world scenarios which are currently unsolvable by general problem solvers in acceptable time. Moreover, the run-time is within seconds for such scenarios. Therefore, the method can be applied to dynamic environments, where re-planning during the mission is required.