Supporting Humans in Solving Multi-UAV Dynamic Vehicle Routing Problems

Real-time optimization of Vehicle Routing Problems (VRP) during mission operations raises concerns regarding obtaining a solution within a reasonable timeframe, especially in domains where operations cannot easily be paused and the number of control parameters is high. Humans, however, are heuristic problem solvers and could potentially complement VRP algorithms in providing quickly a workable and safe solution from which the algorithms can further find the optimum. In this study, a visual interface was developed and evaluated aiming to support humans in manually solving a dynamic VRP in which they needed to solve various simulated payload delivery missions, featuring multiple Unmanned Aerial Vehicles, under failure conditions. Experiment results (n = 16) indicate that the interface enabled the majority of participants to quickly solve the perturbed scenarios, although not always in the most efficient way. Interestingly, participants experienced most difficulty in solving the seemingly easier scenarios, featuring less customers and a relatively low number of vehicles compared to the more complex scenarios.