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.
|Number of pages||7|
|Journal||Computers and Electronics in Agriculture|
|State||Published - Jan 2019|
Bibliographical noteFunding 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.
© 2018 Elsevier B.V.
- Agricultural machinery
- Algorithm comparison
- Tabu search
- Vehicle routing problem
ASJC Scopus subject areas
- Agronomy and Crop Science
- Computer Science Applications