Multi-vehicle refill scheduling with queueing

Giovanni D'Urso*, Stephen L. Smith, Ramgopal Mettu, Timo Oksanen, Robert Fitch

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

5 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)44-57
Number of pages14
JournalComputers and Electronics in Agriculture
Publication statusPublished - 1 Jan 2018
MoE publication typeA1 Journal article-refereed


  • Agricultural robotics
  • Broadcast spraying
  • Multi-robot scheduling
  • Multi-robot systems
  • Multi-vehicle scheduling
  • Queuing
  • Refill scheduling
  • Slurry application
  • Spot spraying


Dive into the research topics of 'Multi-vehicle refill scheduling with queueing'. Together they form a unique fingerprint.

Cite this