Journal
AGRONOMY-BASEL
Volume 10, Issue 10, Pages -Publisher
MDPI
DOI: 10.3390/agronomy10101454
Keywords
benchmarking; coverage path planning; capacitated field operations; simulated annealing algorithm; ant colony optimization; operation management; precision farming; vehicle routing problem; absolute optimal route
Categories
Funding
- Aarhus University, Denmark
Ask authors/readers for more resources
This study specifies an agricultural field (Latitude = 56 degrees 30 ' 0.8 '' N, Longitude = 9 degrees 35 ' 27.88 '' E) and provides the absolute optimal route for covering that field. The calculated absolute optimal solution for this field can be used as the basis for benchmarking of metaheuristic algorithms used for finding the most efficient route in the field. The problem of finding the most efficient route that covers a field can be formulated as a Traveling Salesman Problem (TSP), which is an NP-hard problem. This means that the optimal solution is infeasible to calculate, except for very small fields. Therefore, a range of metaheuristic methods has been developed that provide a near-optimal solution to a TSP in a reasonable time. The main challenge with metaheuristic methods is that the quality of the solutions can normally not be compared to the absolute optimal solution since this ground truth value is unknown. Even though the selected benchmarking field requires only eight tracks, the solution space consists of more than 1.3 billion solutions. In this study, the absolute optimal solution for the capacitated coverage path planning problem was determined by calculating the non-working distance of the entire solution space and determining the solution with the shortest non-working distance. This was done for four scenarios consisting of low/high bin capacity and short/long distance between field and storage depot. For each scenario, the absolute optimal solution and its associated cost value (minimum non-working distance) were compared to the solutions of two metaheuristic algorithms; Simulated Annealing Algorithm (SAA) and Ant Colony Optimization (ACO). The benchmarking showed that neither algorithm could find the optimal solution for all scenarios, but they found near-optimal solutions, with only up to 6 pct increasing non-working distance. SAA performed better than ACO, concerning quality, stability, and execution time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available