Coverage Route Optimization for Autonomous Agricultural Vehicles: Mixed-Integer Linear Programming and Hybrid Genetic Algorithm–Dynamic Programming Solutions 

This case study presents the design and implementation of a coverage-routing optimization system for an agricultural vehicle operating in a field with internal obstacles. After the field is decomposed into traversable cells and candidate coverage patterns are generated, the routing problem is formulated as a Generalized Traveling Salesman Problem.

Two solution engines are developed:

• An exact Mixed-Integer Linear Programming model for obtaining optimal solutions and establishing performance benchmarks.

• A scalable hybrid Genetic Algorithm–Dynamic Programming method in which the GA searches over cell sequences and the DP layer determines the optimal coverage option for each proposed sequence.

The case study covers the problem definition, mathematical formulation, algorithm design, implementation structure, and computational evaluation. Numerical experiments compare solution quality, runtime, scalability, and heuristic convergence. The accompanying Python implementation is available through the public project repository.

This work demonstrates how an optimization problem can be translated from geometric and operational requirements into an exact mathematical model and a scalable hybrid solution architecture.

1. Introduction

Complete Coverage Path Planning (CCPP) determines how a vehicle can systematically cover an entire operating region while avoiding obstacles and limiting unnecessary travel, overlap, and maneuvering. In agricultural operations, an effective coverage plan can reduce non-productive travel, fuel and input consumption, machinery wear, and repeated traffic that contributes to soil compaction [4].

Real fields may contain irregular boundaries and internal obstacles such as ponds, trees, rocks, or utility structures. These features interrupt simple back-and-forth coverage and divide the field into multiple traversable regions. The planning problem must therefore coordinate:

• Coverage within each region.

• Transfers between regions.

• Obstacle avoidance.

• Vehicle turning and working-width constraints.

• Selection of a short overall route.

A common modular workflow separates the problem into field decomposition, guidance-track generation, route planning, and final path construction, as presented by Höffmann et al. [1]. More recent benchmarking work similarly organizes agricultural coverage planning into modular stages so that individual algorithms, objectives, and computational results can be evaluated consistently [2].

This case study focuses on the route-optimization stage: jointly selecting how each decomposed cell is covered and determining the order in which the cells are visited.

Figure 1. Coverage-planning workflow for an agricultural field with obstacles: (a) field boundary, obstacles, and headland; (b) decomposition into traversable cells; (c) generation of interior and headland guidance tracks; and (d) optimized closed coverage route with intra-region paths and inter-region transfers. Adapted conceptually from Höffmann et al. [1]; illustration created for this case study.

2. Problem Statement

2.1 Planning objective

Plan a closed complete-coverage route for one agricultural vehicle operating in a polygonal field with internal obstacles.

The field geometry has already been converted into:

• A headland used for turns and transfers.

• A set of obstacle-free interior cells.

• Parallel guidance tracks within each cell.

• Candidate back-and-forth coverage patterns for each cell.

This geometry-preparation stage is treated as an external preprocessing component and is not developed in this case study.

2.2 Inputs

Field geometry

1. • Polygonal outer boundary.

   • Polygonal internal obstacles.

   • Headland and traversable obstacle gaps.

Vehicle and operation parameters

1. • Working direction.

   • Working width.

   • Minimum turning radius.

Preprocessed coverage structure

1. • Set of decomposed cells.

   • Guidance tracks assigned to each cell.

   • Four candidate coverage options for each cell.

   • Entry pose, exit pose, and coverage length of every option.

The four options represent the possible combinations of the outer starting track and initial travel direction. Each option fully covers its corresponding cell and has a defined entry and exit pose.

2.3 Decisions

For every cell:

1.      Select exactly one candidate coverage option.

2.      Determine the position of the cell in the field-level traversal sequence.

For the complete field:

3.      Determine the transfer from the selected exit pose of each cell to the selected entry pose of the next cell.

4.      Form one cyclic route covering all cells.

2.4 Path components

The complete route contains two segment types:

• Intra-region paths: productive back-and-forth coverage inside individual cells.

• Inter-region paths: non-productive transfers between cells through the headland and obstacle gaps.

Inter-region connections are generated by an external geometric path-construction procedure. For each ordered pair of cell options, this procedure either returns a feasible transfer path and its length or declares the connection infeasible.

2.5 Optimization goal

Construct a single closed route that:

• Covers every cell exactly once.

• Selects exactly one coverage option for each cell.

• Uses only feasible inter-region connections.

• Minimizes total route cost:

Total Cost = Intra-region Coverage Distance + Inter-region Transfer Distance

Optional maneuvering penalties may be added for tight turns or operationally difficult connections.

2.6 Optimization structure

The problem is represented as a Generalized Traveling Salesman Problem (GTSP):

• Each agricultural cell is one cluster.

• Each cluster contains four nodes representing its coverage options.

• Selecting a node determines the cell’s entry pose, exit pose, and intra-region path.

• A directed edge represents a feasible transfer between two selected options.

• The optimization selects one node from every cluster and connects the selected nodes in a minimum-cost cycle.

This formulation jointly determines the cell sequence and the coverage orientation used within each cell.

3. Mixed-Integer Linear Programming Formulation

The coverage-routing problem is formulated as a mixed-integer linear program based on a generalized traveling salesman problem structure.

3.1 Sets and Indices

3.2 Parameters

3.3 Decision variables

3.4 Objective (minimize total path length)

The cost definition by total traversed distance:

The cost of an edge is defined by the sum of the length of the piecewise linear inter-region path and the length of the intra-region path of the preceding node. This cost function matches the aim of minimizing the overall path length.

3.5 Constraints

3.5.1 Exactly one option per cell (cluster constraint)

for every cell k:

This enforces: Each cell is covered exactly once; and the four nodes corresponding to the same cell are clustered together; we choose one from each cluster.

3.5.2 Degree constraints on selected nodes: Outgoing

For every cell, option (k,o):

This enforces: Each selected node has exactly one outgoing arc; unselected nodes have zero. From (k,o) to (l,p)

3.5.3 Degree constraints on selected nodes: Incoming

For every cell, option (k,o):

This enforces: Each selected node has exactly one incoming arc; unselected nodes have zero. From (l,p) to (k,o)

3.5.1, 3.5.2 and 3.5.3 together: this ensures that the selected nodes form one or more cycles in which exactly one node per cell appears.

3.5.4 Subtour elimination (MTZ group of constraints)

The degree constraints can produce multiple disconnected cycles. The following MTZ constraints eliminate these subtours by assigning each cell a position in the route. One reference cell is fixed at the first position:

MTZ - a) Fix order of reference cell

MTZ - b) bounds on order variables _ Lower Bound (all cells except reference cell)

MTZ - c) bounds on order variables _ Upper Bound

MTZ - d) subtour constraints on arcs (aggregated over options)

3.5.5 Variable domains

4. Scalable Hybrid GA-DP Solution

The MILP formulation provides an exact solution but may become computationally expensive as the number of cells increases. A hybrid solution engine was therefore developed for larger instances.

The method combines:

• A Genetic Algorithm (GA) to search for an effective sequence of cells.

• A Dynamic Programming (DP) evaluator to determine the optimal coverage option for every cell in a proposed sequence.

The hybrid engine uses the same cells, options, feasible transitions, and cost data defined for the MILP model. Only the solution method changes.

4.1 Solution Decomposition

The optimization decisions are separated into two layers.

Outer layer: cell sequencing

Determine a cyclic permutation of the cells (where each cell appears exactly once.):

Inner layer: option selection

For a fixed cell sequence, select one of the four coverage options for every cell:

The option selected for a cell determines:

• Its intra-region coverage path.

• Its entry pose.

• Its exit pose.

• The feasible transfer costs to neighboring cells.

The GA handles the large cell-ordering search space, while DP solves the option-selection problem exactly for each cell sequence. This separation follows the structure identified in the original design: cell order is searched globally, while option decisions depend primarily on the preceding and succeeding cells.

Figure 2. Hybrid GA–DP solution workflow. The Genetic Algorithm generates candidate cell permutations, while the Dynamic Programming evaluator selects the optimal coverage option for each cell, checks transition feasibility, and computes the route cost. The resulting fitness value guides selection, crossover, and mutation across generations, producing the best cell sequence and option assignment.

4.2 Chromosome Representation

Each GA chromosome contains only a permutation of cell indices:

Coverage-option indices are not included in the chromosome. For example:

Reason for this representation: Encoding both cell order and coverage options would unnecessarily enlarge the chromosome and the search space. With four options per cell, explicitly encoding the options would introduce up to 4^m additional option combinations.

Instead, the best option assignment is calculated during fitness evaluation. The chromosome therefore remains:

• Compact.

• Permutation-based.

• Compatible with standard routing operators.

• Independent of the MILP solver.

• Focused on the main combinatorial decision: cell order.

4.3 Fitness Evaluation Using Dynamic Programming

For each chromosome, DP determines the minimum route cost over all possible coverage-option combinations.

4.3.1 DP state

4.3.2 Initialization

Because the route is cyclic, the option selected for the first cell must remain consistent when the route is closed.

4.3.3 Forward transition

The current implementation assumes that the required directed transition costs are present in the GTSP cost dictionary. The synthetic experimental instances therefore use complete directed inter-cell transition data. Extending the evaluator to treat missing transitions explicitly as infeasible states with cost +inf is a straightforward future enhancement.

4.3.4 Cycle closure

4.3.5 DP output

For each chromosome, the DP layer returns:

• Total closed-route cost.

• Selected option for every cell.

• Ordered sequence of selected GTSP nodes.

• Feasibility status of the proposed cell sequence.

The returned route cost is used directly as the chromosome fitness.

4.3.6 DP Evaluation Complexity

Step 1 _ Population initialization

Generate an initial population of random cell permutations. Each chromosome contains every cell exactly once. Random initialization preserves population diversity. Geometry-based, centroid-based, sweep-based, or previously available routes could be incorporated as structured seed solutions in future extensions. 

Step 2 _ Fitness evaluation

For every chromosome (Pi) :

1. Run the DP evaluator.

2. Determine the optimal option assignment for that permutation.

3. Calculate the complete cyclic route cost.

4. Store the result as fitness F(Pi).

Lower fitness values represent shorter routes. 

Step 3 _ Parent selection

Use tournament selection:

1. Randomly sample a small group of chromosomes.

2. Select the chromosome with the lowest route cost.

3. Repeat until the mating pool is complete.

Tournament selection provides controlled selection pressure without requiring fitness-value scaling.

Step 4 _ Elitism

Copy the best E chromosomes directly to the next generation.

Elitism prevents the best solution found so far from being lost during crossover or mutation.

Step 5 _ Crossover

Apply Order Crossover to selected parents with probability p(c). Two cut points define a segment inherited directly from each parent, while the remaining positions are filled according to the relative order found in the opposite parent. The operator preserves chromosome length, includes every cell exactly once, and produces valid permutation offspring without requiring repair.

Step 6 _ Mutation

Apply swap mutation with probability p(m). Two chromosome positions are selected randomly and their cells are exchanged. This introduces new cell sequences while preserving permutation feasibility because no cell is added, removed, or duplicated. Insertion, segment reversal, and short-segment shuffle operators could be evaluated in future extensions.

Step 7 _ New-generation evaluation

For every new non-elite chromosome:

1. Run the DP evaluator.

2. Update its optimal option assignment.

3. Calculate its route cost.

4. Replace the previous population with the new population.

Because options are not stored in the chromosome, option selection is recalculated after every crossover or mutation.

Step 8 _ Termination

Continue until the configured maximum number of generations is reached. The best chromosome identified across all generations is then returned. Runtime limits, stagnation-based stopping, and target-cost stopping may be incorporated as future extensions.

4.4.1 Overall GA-DP Complexity

4.5 GA-DP Algorithm Workflow

Input

• Cells K.

• Four coverage options per cell.

• Feasible transition set E.

• Intra-region and inter-region costs.

• GA configuration.

Output

• Best cell sequence.

• Best coverage option for each cell.

• Best complete-route cost.

Procedure

1. Initialize a population of valid cell permutations.

2. Evaluate each permutation using the cyclic DP evaluator.

3. Preserve the best elite chromosomes.

4. Select parents using tournament selection.

5. Generate children using permutation-safe crossover.

6. Apply permutation-safe mutation.

7. Evaluate each new chromosome using DP.

8. Replace the current population.

9. Record the best-so-far route cost.

10. Repeat until the stopping condition is reached.

11. Return the best permutation and its DP-derived option assignment.

4.6 Design Rationale and Computational Advantages

Exact optimization inside each chromosome

For every proposed cell sequence, DP returns the globally optimal option assignment for that sequence.

The GA therefore does not compare chromosomes using arbitrary or locally selected coverage options.

Reduced search space

The GA searches only over m! cell permutations. It does not directly search the combined space: m! * 4^m of cell orders and option assignments.

Clear division of algorithmic roles

• GA: explores the global ordering space.

• DP: exploits the local sequential structure of the option-selection problem.

• Geometric path generator: supplies feasible transfer paths and costs.

• Route decoder: reconstructs the final sequence of intra-region and inter-region paths.

Compatibility with the exact model

The MILP and hybrid engine use the same:

• Cell set.

• Coverage options.

• Feasible edges.

• Intra-region costs.

• Inter-region costs.

• Total-route objective.

This enables direct comparison of:

• Objective values.

• Optimality gaps.

• Runtime.

• Scalability.

• Solution convergence.

Solver independence

The hybrid engine does not require a MIP solver and can be applied when the exact model becomes computationally expensive.

4.7 Role Within the Overall Solution Framework

The two solution engines serve different computational roles:

Exact MILP engine

Used for:

• Small and medium instances.

• Exact optimal solutions.

• Validation of the heuristic.

• Calculation of heuristic optimality gaps.

• Analysis of formulation behavior.

Hybrid GA–DP engine

Used for:

• Larger instances.

• Time-limited planning.

• Rapid generation of high-quality feasible routes.

• Convergence analysis.

• Sensitivity tests with different search configurations.

The MILP acts as the exact benchmark, while the hybrid engine provides the scalable alternative. This creates a consistent basis for the later numerical comparison of solution quality and computational performance.

5. Implementation Architecture 

The implementation follows a modular software architecture that separates problem-instance preparation, mathematical-model construction, solver execution, heuristic optimization, and result reporting. This modular organization is consistent with open-source agricultural coverage-planning frameworks that separate headland, swath, route, and path-planning functions [3]. Both the exact MILP and hybrid GA–DP engines operate on the same GTSP representation, allowing their objective values, selected coverage options, cell sequences, runtimes, and solution outputs to be compared directly.

The architecture is designed to support three primary requirements:

• Consistent input and cost definitions across both solution engines.

• Independent execution of the exact and heuristic approaches.

• Reproducible computational experiments using documented configurations and version-controlled source code.

This section focuses on the software organization and execution structure. The mathematical formulation and internal GA–DP algorithm have already been described in Sections 3 and 4.

5.1 Shared GTSP Data Layer 

The MILP and hybrid GA–DP engines use a common GTSP data structure. The purpose of this shared layer is to ensure that differences between the two approaches arise from the solution method rather than from different problem definitions or cost calculations.

A problem instance contains the following primary elements:

• A set of agricultural cells.

• A set of candidate coverage options associated with each cell.

• A node for every cell-option combination.

• A directed set of feasible transitions between options belonging to different cells.

• An intra-region coverage cost for every option.

• An inter-region transfer cost for every feasible directed transition.

• A combined edge cost used by both optimization engines.

Each GTSP node is represented by a pair (k,o), where k identifies the agricultural cell and o identifies one of its candidate coverage options. Selecting a node therefore specifies not only that the cell is visited, but also the entry pose, exit pose, travel direction, and intra-region path used to cover that cell.

The shared instance layer provides four important guarantees:

1. Both engines evaluate the same cells and coverage alternatives.

2. Both engines use the same feasible-transition set.

3. Both engines calculate route cost using the same objective definition.

4. A route returned by either engine can be decoded into the same sequence of selected GTSP nodes and corresponding coverage and transfer segments.

This common data layer is the central interface between geometric preprocessing and optimization. The geometric component generates cells, coverage options, poses, and feasible transfer paths, while the optimization components receive the resulting discrete nodes, arcs, and costs. Consequently, the MILP and GA–DP implementations remain independent of the specific geometric path-generation procedure used upstream.

5.2 Software Components 

Table 1 summarizes the main implementation files and their responsibilities.

The component structure separates reusable optimization logic from executable scripts. The core MILP expressions are isolated from solver-specific launchers, while the hybrid engine is separated from its experiment configuration and reporting script. This organization reduces duplication and allows individual components to be modified or extended without restructuring the complete application.

5.3 Execution Flow and Outputs 

The implementation supports two parallel solution flows coordinated through an optional repository-level execution pipeline. The pipeline generates one shared GTSP instance and passes it unchanged to the MILP engine, the hybrid GA-DP engine, or both. This ensures that comparative runs use identical cells, coverage options, feasible transitions, and cost data.

Exact MILP flow

1. A fixed or randomly generated GTSP instance is loaded.

2. The shared cells, options, feasible arcs, and cost dictionaries are passed to the Pyomo model.

3. The objective and constraint groups are constructed through the corresponding catalog modules.

4. The selected solver interface executes the model.

5. The active decision variables are decoded into the selected GTSP nodes and cyclic route.

6. The objective value, route sequence, selected options, solver status, and runtime are reported.

The solver-specific scripts provide convenient entry points for CBC, GLPK, and HiGHS without changing the underlying optimization model.

Hybrid GA–DP flow

1. The same GTSP instance is loaded.

2. GA configuration parameters are supplied to the hybrid engine.

3. The initial population of cell permutations is generated.

4. Each permutation is evaluated by the cyclic DP procedure.

5. Selection, crossover, mutation, and elitism produce successive populations.

6. The best cell sequence and its DP-derived option assignment are retained.

7. The final route cost, selected nodes, runtime, and convergence history are reported.

Coordinated pipeline flow

1. Define the problem size, instance seed, selected method, MILP solver, and GA configuration.

2. Generate one shared GTSP instance.

3. Execute the selected optimization engine or both engines sequentially.

4. Collect standardized summaries containing objective value, runtime, termination status, configuration, and output-file references.

5. Append one result row per method to a common experiment-results CSV file.

Because the pipeline supplies the same generated instance to both engines and records their outputs using a common schema, objective values, runtimes, termination conditions, and algorithm configurations can be compared directly without an additional cost-reconciliation step. 

The implementation may produce the following outputs:

• Selected cell traversal sequence.

• Selected coverage option for each cell.

• Ordered sequence of GTSP nodes.

• Complete cyclic route cost.

• Solver or heuristic runtime.

• MILP termination and solver status.

• GA best-so-far cost history. 

• Generation-level execution logs.

• Heuristic convergence plots.

• Data required for subsequent route visualization and comparative experiments.

• Structured experiment records stored in a common CSV file, including instance identifiers, algorithm settings, objective values, runtimes, solution status, optimality gap where applicable, and links to generated logs and convergence plots.

Generated outputs are stored separately from the source code and are excluded from version control where appropriate. This keeps the repository focused on the reproducible implementation rather than on transient execution artifacts.

5.4 Software Design Principles 

The implementation is organized around the following design principles.

Shared data model.
Both optimization engines consume the same cells, coverage options, feasible transitions, and cost definitions. This prevents data-preparation differences from affecting the comparison between methods.

Separation of responsibilities.
Instance generation, model definition, solver execution, heuristic search, and reporting are maintained as distinct software responsibilities. Each component has a limited and identifiable purpose.

Modular solver interfaces.
The MILP formulation is not tied to one solver-specific script. CBC, GLPK, and HiGHS can be selected without rewriting the mathematical model.

Heuristic solver independence.
The hybrid GA–DP engine does not require a MILP solver. It operates directly on the GTSP data and can therefore remain available when an exact solver is unavailable or unsuitable for a larger instance.

Direct method comparability.
Both engines return equivalent solution concepts: a cyclic cell sequence, one selected option per cell, and a total route cost. This supports direct calculation of objective differences, runtime differences, and heuristic optimality gaps.

The orchestration pipeline strengthens this comparability by generating the instance once, passing the same in-memory data object to both engines, and recording both results under a standardized output schema. 

Reproducibility.
The implementation uses documented dependencies, explicit solver and algorithm parameters, deterministic toy data, configurable instance and GA random seeds, and structured CSV result storage. These features allow individual runs and complete comparative experiments to be repeated under the same conditions. 

Extensibility.
The optimization layer is separated from geometric preprocessing. A future field-decomposition or transfer-path-generation component can replace the synthetic data generators provided that it returns the expected GTSP data structure.

5.5 Repository and Reproducibility 

The implementation is maintained in the following public repository:

GitHub repository:
https://github.com/asefi-h/gtsp-route-coverage-optimization

The repository contains the complete Python implementation of both solution approaches, the dependency specification, execution instructions, and project documentation.

Reproducibility is supported through:

• A requirements.txt file containing the required Python packages and versions.

• Fixed seeds for deterministic or repeatable synthetic experiments.

• A deterministic toy instance for solution validation.

• Separate entry-point scripts for the MILP and hybrid GA–DP engines, together with a high-level pipeline for coordinated comparative execution.

• Standardized CSV output that preserves the instance seed, method, solver or GA configuration, objective value, runtime, termination status, and associated output-file paths for every run. 

• Documented solver requirements and execution commands.

• Version-controlled source code and commit history.

• A GitHub Actions continuous-integration workflow.

• An automatically updated CI status badge in the repository README.

The CI workflow runs after each push to the main branch and for pull requests targeting that branch. It checks out the repository on a temporary Ubuntu environment, configures Python 3.12, installs the dependencies declared in requirements.txt, and compiles the Python source files. A successful workflow confirms that the repository can be prepared in a clean environment and that the committed source files pass the automated compilation check.

Before the formal experiments, the coordinated pipeline was validated on a small shared instance. The MILP and hybrid GA-DP engines returned the same objective value and the same cyclic route up to rotation, confirming consistent data transfer, objective evaluation, and structured result collection across the two workflows.

The CI process is intentionally lightweight. It validates environment setup and source-code integrity but does not replace the computational experiments presented later in this case study. Numerical validation, solution-quality comparison, and scalability testing are addressed separately in Section 6.

6. Computational Experiments and Results

This section evaluates the exact MILP and hybrid GA–DP approaches in terms of solution quality, runtime, scalability, and convergence across increasing problem sizes.

6.1 Experimental Setup 

The exact MILP and hybrid GA–DP methods were evaluated on synthetic GTSP instances containing 5, 10, 20, 30, 40, 50, 60, 70, and 80 agricultural cells. Each cell contained four candidate coverage options. For every problem size, the instance was generated using random seed 1234, ensuring that the experiment was reproducible and that both methods received exactly the same cells, options, feasible transitions, and route costs.

The MILP models were solved using CBC. A maximum solver time of 300 seconds and a relative MIP-gap tolerance of 0.0001, corresponding to 0.01%, were applied to every instance. The hybrid method used GA seed 1 and three problem-size-dependent configurations:

The experiments were executed on a 64-bit Windows computer with an AMD Ryzen AI 9 HX 370 processor and 32 GB of installed RAM. Reported runtimes represent solver-level wall time. The GPU was not used by either solution method.

6.2 Results and Discussion 

Table 3 compares the objective values and runtimes returned by CBC and the hybrid GA–DP method. A lower objective value represents a shorter complete coverage route.

CBC proved optimality only for the five-cell instance. For every instance containing 10 or more cells, CBC reached the configured 300-second solver limit before satisfying the 0.01% MIP-gap tolerance. The remaining CBC gaps ranged from approximately 10.53% to 38.72%, indicating that the solver had not established tight optimality bounds within the allotted time.

Figure 3. Runtime scalability of CBC MILP and hybrid GA–DP across increasing problem sizes. The logarithmic time scale shows that CBC reached the 300-second limit for all instances with 10 or more cells, while GA–DP remained substantially faster across the tested range.

For the five-cell instance, GA–DP reproduced the exact MILP objective, providing a direct validation of the heuristic and its DP option-selection layer. From 10 cells onward, GA–DP returned an objective value below the incumbent solution found by CBC at the time limit. The improvement over the CBC incumbent ranged from 0.19% to 21.29%. These differences should not be interpreted as improvements over the unknown exact optimum; rather, they show that the heuristic found stronger feasible solutions than the time-limited MILP run.

As shown in Figure 3, the runtime difference became substantial from 10 cells onward. GA–DP solved the 10- and 20-cell cases in approximately one to two seconds, while CBC used the complete five-minute allowance. For the 30- to 50-cell cases, GA–DP required approximately 10–23 seconds. Even at 80 cells, it completed in about 87 seconds, remaining below one-third of the CBC time limit.

The convergence history for the representative 40-cell instance illustrates the search behavior of the hybrid method. The objective decreased rapidly during the initial generations and then improved progressively through smaller refinements. The best value continued to decline late in the run, indicating that the combination of elitism, mutation, and DP-based evaluation continued to identify improved cell sequences rather than terminating after the initial rapid convergence.

Figure 4. Hybrid GA–DP convergence for the 40-cell instance using a population of 80 and 200 generations. The best-so-far objective decreases sharply during the early generations and subsequently converges through smaller incremental improvements.

Overall, the experiments show a clear division between the two methods. The MILP remains valuable for obtaining certified optimal solutions on small instances and for validating the heuristic. Under the fixed 300-second limit, however, its ability to prove solution quality deteriorated quickly as the number of cells increased. The hybrid GA–DP method provided feasible routes consistently, scaled to all tested sizes, and produced lower-cost feasible solutions than the CBC incumbent for every time-limited instance. To illustrate how the optimized solution is interpreted at the route level, Figure 5 shows a sample coverage route with the selected traversal order and movement components.

Figure 5. Sample optimized coverage route. Cell labels indicate the traversal sequence. Red lines show intra-region coverage paths, blue lines show inter-region transfers, and orange lines indicate headland travel.

7. Concluding Remarks

This case study developed a complete optimization framework for route coverage planning in agricultural fields represented as a Generalized Traveling Salesman Problem. The formulation jointly determines the traversal sequence of decomposed field cells and the coverage option selected within each cell, while accounting for productive intra-cell travel and non-productive transfers between cells. By expressing the planning problem through a shared set of GTSP nodes, feasible directed transitions, and route costs, the same problem instances can be solved and evaluated consistently by both exact and heuristic methods.

The exact MILP formulation provides a rigorous benchmark and remains valuable for validating model behavior, certifying optimality on smaller instances, and measuring heuristic solution quality. The computational results also demonstrate the combinatorial growth of the problem. With four coverage options per cell, increasing the number of cells expands both the sequencing space and the number of possible option assignments. Under the configured 300-second limit, CBC proved optimality for the five-cell instance but reached the time limit for every larger case. This illustrates why exact formulations alone may become impractical when route-coverage planning must be performed at larger operational scales.

The hybrid GA–DP method was designed specifically to exploit the structure of this combinatorial problem. The Genetic Algorithm provides the exploratory component by searching broadly across alternative cell sequences through selection, crossover, and mutation. The Dynamic Programming evaluator provides the exploitative component by determining the globally optimal coverage-option assignment for every proposed sequence. This explore–exploit division reduces the GA search space from the combined space of cell permutations and option assignments to the cell-ordering space alone, while preserving exact option selection within each fitness evaluation.

The experiments show that this design scales substantially better than the time-limited MILP approach. The hybrid method produced feasible solutions for all tested instances up to 80 cells and remained well below the MILP time limit. For the five-cell validation case, it reproduced the exact MILP objective. For all larger instances, it produced lower-cost feasible routes than the incumbent returned by CBC within the available time. These results do not establish optimality for the larger cases, but they demonstrate the practical value of combining global metaheuristic exploration with exact dynamic-programming evaluation.

The modular implementation also contributes to scalability and reproducibility. A shared data layer ensures that both engines use identical instances and cost definitions, while the high-level execution pipeline supports controlled experiments, explicit random seeds, standardized parameter settings, and structured CSV result storage. This architecture separates geometric preprocessing, optimization logic, solver execution, and reporting, making the framework suitable for extension beyond the synthetic instances used in this study.

Several improvements could strengthen the approach further. GA parameters could be tuned systematically or adapted dynamically as the search progresses. Geometry-based seed solutions, local-search improvement, and parallel chromosome evaluation could accelerate convergence and improve solution quality. The framework could also be tested with a variable number of coverage options per cell rather than the fixed four-option structure, sparser transition networks, multiple random instances per problem size, and real field geometries generated from agricultural maps and vehicle constraints. These extensions would provide a broader assessment of robustness and move the framework closer to operational deployment.

Overall, the case study demonstrates how a large-scale route-coverage problem can be translated into a precise combinatorial optimization model and then addressed through complementary exact and scalable solution methods. The MILP establishes mathematical rigor and benchmarking capability, while the hybrid GA–DP architecture provides the computational flexibility needed for larger planning instances.

8. References

[1] Höffmann, M., Patel, S., and Büskens, C. “Optimal Coverage Path Planning for Agricultural Vehicles with Curvature Constraints.” Agriculture, 13(11), 2112, 2023. https://doi.org/10.3390/agriculture13112112

[2] Mier, G., Casado Faulí, A. M., Valente, J., and de Bruin, S. “Fields2Benchmark: An Open-Source Benchmark for Coverage Path Planning Methods in Agriculture.” Smart Agricultural Technology, 12, 101156, 2025. https://doi.org/10.1016/j.atech.2025.101156

[3] Mier, G., Valente, J., and de Bruin, S. “Fields2Cover: An Open-Source Coverage Path Planning Library for Unmanned Agricultural Vehicles.” IEEE Robotics and Automation Letters, 8(4), 2166–2172, 2023. https://doi.org/10.1109/LRA.2023.3248439

[4] Höffmann, M., Patel, S., and Büskens, C. “Optimal Guidance Track Generation for Precision Agriculture: A Review of Coverage Path Planning Techniques.” Journal of Field Robotics, 41(3), 823–844, 2024. https://doi.org/10.1002/rob.22286