Human Performance in Solving Multi-UAV Over-Constrained Dynamic Vehicle Routing Problems

Abstract

For many logistics applications, such as drone delivery missions, finding an optimized network of routes yields a Vehicle Routing Problem (VRP). Such optimizations are mostly conducted offline prior to actual operations for reasons of computational complexity. In case disturbances arise during operations, for example a sudden loss of a vehicle, the VRP needs to be re-optimized in real-time and this raises concerns regarding obtaining a solution within time. In a previous study, it was demonstrated that humans, when supported through a human-machine interface, can quickly deal with these routing problems through satisficing, providing workable solutions. This paper extends our previous research by exposing human operators to an over-constrained VRP with different mission priorities and vehicle capabilities. Experiment results (n = 16) indicate that the mission type had the largest impact on how participants used the interface and what constraints were relaxed. In particular, during a search-and-rescue context the mission emphasis was put on delivering (medical) payload (close) to as many customers as possible, even if this would involve sacrificing vehicles and relaxing the depot constraint. Ethical aspects of the VRP are taken into account which algorithms do not by themselves, underlining the importance of involving humans in automation. Human operators complement algorithms with their context awareness, yielding more safe, resilient and responsible systems.