In case of finding an optimised solution in real-time, automation may not be a helpful tool to be able to select preferable decisions and implement actions due to the complexity involved. More notably, in the case of an over-constrained dynamic vehicle routing problem as there is no solution which can satisfy all the constraints in real-time with a limited number of vehicles. This also resembles a real-life situation. However, as humans are good at problem-solving, there is a proposal to introduce a human to improve the performance by presenting an interface. Thus, the automation will be used to acquire and analyse the necessary information and display it in the interface, the human can then use this information to decide a preferable action and then implement it during mission operation. An interface design from previous research, with additional features, was used for a payload delivery mission to control Unmanned Aerial Vehicles. The human performance and the interface effectiveness is evaluated in an over-constrained dynamic vehicle routing problem for different mission objectives. Results show that the interface supported the humans, and additionally, the participants came up with a solution to satisfy the individual goal for a particular mission objective by relaxing specific constraints. It could be established that humans can come up with a solution for the over-constrained problem in a limited time required, thus it is an acceptable alternative which can be used to be able to come up with solutions. Having a human-in-the-loop is beneficial in case of a vehicle routing problem.