Multi-vehicle refill scheduling with queueing

We consider the problem of refill scheduling for a team of vehicles or robots that must contend for access to a single physical location for refilling. The objective is to minimise time spent in travelling to/from the refill station, and also time lost to queuing (waiting for access). In this paper, we present principled results for this problem in the context of agricultural operations. We first establish that the problem is NP-hard and prove that the maximum number of vehicles that can usefully work together is bounded. We then focus on the design of practical algorithms and present two solutions. The first is an exact algorithm based on dynamic programming that is suitable for small problem instances. The second is an approximate anytime algorithm based on the branch and bound approach that is suitable for large problem instances with many robots. We present simulated results of our algorithms for three classes of agricultural work that cover a range of operations: spot spraying, broadcast spraying and slurry application. We show that the algorithm is reasonably robust to inaccurate prediction of resource utilisation rate, which is difficult to estimate in cases such as spot application of herbicide for weed control, and validate its performance in simulation using realistic scenarios with up to 30 robots.