An Arable Field for Benchmarking of Metaheuristic Algorithms for Capacitated Coverage Path Planning Problems

TY - JOUR

T1 - An Arable Field for Benchmarking of Metaheuristic Algorithms for Capacitated Coverage Path Planning Problems

AU - Khosravani Moghadam, Erfan

AU - Vahdanjoo, Mahdi

AU - Jensen, Allan Leck

AU - Sharifi, Mohammad

AU - Grøn Sørensen, Claus

PY - 2020

Y1 - 2020

N2 - This study specifies an agricultural field (Latitude = 56 ◦30 00.8” N, Longitude = 9 ◦35 027.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.

AB - This study specifies an agricultural field (Latitude = 56 ◦30 00.8” N, Longitude = 9 ◦35 027.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.

KW - benchmarking; coverage path planning; capacitated field operations; simulated annealing algorithm; ant colony optimization; operation management; precision farming; vehicle routing problem; absolute optimal route

UR - http://www.scopus.com/inward/record.url?scp=85092403839&partnerID=8YFLogxK

U2 - 10.3390/agronomy10101454

DO - 10.3390/agronomy10101454

M3 - Journal article

SN - 2073-4395

VL - 10

SP - 1

EP - 18

JO - Agronomy

JF - Agronomy

IS - 10

M1 - 1454

ER -