Routing algorithm selection for field coverage planning based on field shape and fleet size

Hasan Seyyedhasani, Joseph S. Dvorak, Eric Roemmele

Research output: Contribution to journalArticlepeer-review

31 Scopus citations


This project considered the field efficiency of routes created using two routing algorithms, a fast Clarke-Wright heuristic and a slower tabu search meta-heuristic, in 100 different field shapes with 1200 different field work scenarios for each algorithm. Different field work scenarios were generated by varying the number of simultaneously working vehicles (1, 2, 3, and 5) and using three path generation methods. After calculating the routes for all the scenarios using cloud computing and a high-performance compute cluster, the routes were evaluated to determine the field efficiency and field completion time. All tabu search results had field efficiencies above 0.65 and field completion times tightly clustered based on the number of simultaneously working vehicles. Many Clarke-Wright results were clustered with the tabu search results, but others had field efficiencies below 0.37 which indicated that the method failed to produce acceptable results. A logistic regression model was developed to identify the factors that caused unacceptable Clarke-Wright results. This enabled creation of a probability equation for predicting when the fast Clarke-Wright equation would produce acceptable results, and conversely, when it would be necessary to rely on the slower tabu search routing. Field shape complexity as measured by the isoperimetric quotient was the primary indicator that Clarke-Wright could fail to produce an acceptable result. The number of simultaneously operating vehicles was statistically insignificant for one, two or three vehicle fleets, but increasing to five vehicles did adversely affect the ability of the Clarke-Wright algorithm to provide acceptable routes.

Original languageEnglish
Pages (from-to)523-529
Number of pages7
JournalComputers and Electronics in Agriculture
StatePublished - Jan 2019

Bibliographical note

Funding Information:
This research work was supported in part by a grant from the Kentucky Science and Engineering Foundation as per Grant Agreement #KSEF-148-502-16-380 with the Kentucky Science and Technology Corporation. This work was also supported by the USDA National Institute of Food and Agriculture , Hatch Multi State project 1001110.

Publisher Copyright:
© 2018 Elsevier B.V.


  • Agricultural machinery
  • Algorithm comparison
  • Clarke-wright
  • Tabu search
  • Vehicle routing problem

ASJC Scopus subject areas

  • Forestry
  • Agronomy and Crop Science
  • Computer Science Applications
  • Horticulture


Dive into the research topics of 'Routing algorithm selection for field coverage planning based on field shape and fleet size'. Together they form a unique fingerprint.

Cite this