Exact and Heuristic Methods for Capacitated Path Planning for Agricultural Field Operations

Abstract

This paper addresses the Capacitated Coverage Path Planning Problem (CPP) arising in agricultural field operations. It aims to determine an efficient sequence of field tracks to be serviced by an agricultural machine subject to limited onboard capacity and refilling constraints, while minimizing non-working distance. The non-working distance is the length traveled by the machinery not performing productive fieldwork. Optimizing how agricultural machinery maneuvers can help reduce operational costs and greenhouse gas (GHG) emissions, while increasing productivity. The problem is formulated as a variant of the constrained Vehicle Routing Problem (VRP), which is NP-hard. A novel exact Integer Linear Programming (ILP) formulation is proposed. We employ a commercial optimizer, Gurobi, to obtain optimal reference solutions for smaller instances. To overcome scalability limitations, a metaheuristic based on "simulated annealing (SA) methodology" is proposed. Our algorithm incorporates customized neighborhood search operators and a capacity-aware route-splitting mechanism to explicitly handle refilling operations. Computational experiments are conducted on real-world field instances. The proposed metaheuristic is evaluated against the exact formulation. The results indicate that SA consistently produces near-optimal solutions with substantially reduced computation times.