High-performance exact and metaheuristic methods for agricultural path planning

Abstract

Strategic operational planning is essential for making agriculture autonomous, while maintaining sustainability. Optimizing how agricultural machinery maneuvers can help reduce costs and greenhouse gas (GHG) emissions, while increasing productivity. This thesis addresses the Capacitated Path Planning Problem (CPP) in agricultural field operations which is a variant of the Vehicle Routing Problem (VRP) adapted for track-based field logistics with refilling constraints. The aim is to minimize non-working distance, the distance traveled by machinery while not performing productive fieldwork, under capacity and cover age constraints. The problem is first formulated as an Integer Linear Program (ILP) and solved using the Gurobi Optimizer, where sub-tour elimination is efficiently implemented through lazy constraints and callback-based separation routines. Then, a metaheuristic, Simulated Annealing (SA), is developed in C++ to overcome the scalability limitations of exact optimization. This implementation features customized neighbourhood operators and a capacity-aware route-splitting mechanism. Both these methods are tested on real-world benchmark instances. Additionally, a comparative analysis with an Ant Colony Optimization (ACO) implementation demonstrates that the SA achieves near-optimal solutions with significantly reduced runtime compared to the ILP, which produces optimal baselines for small instances. The results highlight a clear trade-off between exactness and computational efficiency and confirm the suitability of metaheuristic approaches for large-scale, refill-aware field routing. This work thus bridges classical routing optimization with precision agriculture by extending CPP to realistic field geometries and providing a scalable framework for autonomous and sustainable agricultural logistics.