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

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.