# Unmanned Aerial Vehicle Optimal Route Planning for Data Collection of Underground Communicating Sensor Nodes in Agriculture

Christophe Cariou, Laure Moiroux-Arvis, Fatiha Bendali-Mailfert, Yuankang Hu, Jean Mailfert

<figure><img src="image_1.png" /></figure>

## ► To cite this version:

Christophe Cariou, Laure Moiroux-Arvis, Fatiha Bendali-Mailfert, Yuankang Hu, Jean Mailfert. Unmanned Aerial Vehicle Optimal Route Planning for Data Collection of Underground Communicating Sensor Nodes in Agriculture. ACM Journal on Autonomous Transportation Systems, 2025, pp.18. 10.1145/3748732 . hal-05167320

HAL Id: hal-05167320

https://hal.inrae.fr/hal-05167320v1

Submitted on 17 Jul 2025

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Unmanned Aerial Vehicle Optimal Route Planning for Data Collection of Underground Communicating Sensor Nodes in Agriculture

CHRISTOPHE CARIOU, INRAE UR TSCF, Université Clermont Auvergne, Clermont-Ferrand, France

LAURE MOIROUX-ARVIS, INRAE UR TSCF, Université Clermont Auvergne, Clermont-Ferrand, France

FATIHA BENDALI-MAILFERT, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France

YUANKANG HU, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France

JEAN MAILFERT, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France

The massive deployment of soil moisture and temperature sensors inside agricultural plots will become essential in the next years to meet the challenges of the agroecological transition. In such a context, the use of buried communicating sensor nodes is particularly relevant because they are protected underground from human activities, animals and agricultural machinery. Their communication range is however limited to a few meters above the ground, that leads to difficulties in collecting their data remotely. One possible solution is to use one or several UAVs to visit them successively. Nevertheless, this approach requires being able to take into account the presence of obstacles at low flight height in the path planning algorithms, and to solve the Close Enough Traveling Salesman Problem (CE-TSP) in cluttered environments. To meet this need, the objective of this paper is to present the possibility of exploiting real data from an airborne Light Detection and Ranging sensor (LiDAR) to determine the location and height of obstacles in the workspace of the UAV. Based on this data, a cost matrix associated to the trajectories between each node can be calculated, with the possibility for the UAV to fly above the obstacle areas. Next, to optimize the route of the UAV in the CE-TSP framework, this paper presents a simple approach based on a Partheno Genetic Algorithm (PGA) completed with some heuristic rules. Our method is applied in a real use case consisting of 50 sensor nodes distributed in our experimental farm. The results highlight the performances of the method proposed. They demonstrate the capabilities of our method to address the CE-TSP with obstacles, and open the way to future prospects for collecting data of buried sensor nodes using UAVs.

CCS Concepts: • **Theory of computation** → **Approximation algorithms analysis**.

Additional Key Words and Phrases: Unmanned Aerial Vehicle, Underground Communicating Sensors, Combinatorial optimization, Close Enough Traveling Salesman Problem with 3D obstacles, Partheno-Genetic Algorithm, Agriculture

## 1 Introduction

Agriculture will have to face major challenges in the years to come. The food needs of a constantly growing world population require more sustainable agricultural practices to preserve natural resources and the resilience of agricultural systems to climate change must to be improved [11, 14, 20]. To help meet these challenges, monitoring temperature and moisture of the topsoil is becoming essential. The main objectives are to adapt the agricultural practices to the soil conditions, optimize water use in fields and better manage field operations [19, 26]. Collected at a high spatial resolution and at multiple depths, soil moisture and temperature measurements are also needed

Authors' Contact Information: Christophe Cariou, INRAE UR TSCF, Université Clermont Auvergne, Clermont-Ferrand, France; e-mail: christophe.cariou@inrae.fr; Laure Moiroux-Arvis, INRAE UR TSCF, Université Clermont Auvergne, Clermont-Ferrand, France; e-mail: laure.moiroux-arvis@inrae.fr; Fatiha Bendali-Mailfert, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France; e-mail: fatiha.bendali-mailfert@limos.fr; Yuankang Hu, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France; e-mail: Yuankang.HU@doctorant.uca.fr; Jean Mailfert, LIMOS, Université Clermont Auvergne, Clermont-Ferrand, France; e-mail: jean.MAILFERT@uca.fr.

<figure><img src="image_3.png" /></figure>

This work is licensed under a Creative Commons Attribution 4.0 International License.
© 2025 Copyright held by the owner/author(s).
ACM 2833-0528/2025/7-ART
https://doi.org/10.1145/3748732
to feed hydrological models, understand climate variability and early forecast drought and flood conditions [6, 29].

However, the deployment of a high number of sensors inside agricultural plots remains rarely done in practice mainly due to difficulties in remote data collection: the communication networks are in fact not always accessible (e.g. white areas of cell phone networks), and the approaches based on a massive deployment of gateways or on satellite communications can rapidly become cost prohibitive. Moreover, the radio transmitters of the sensor nodes are most often positioned aboveground which constitutes physical obstacles for agricultural machinery present on the plots. The equipments can also be damaged by animals or malicious acts.

To address this issue, we have recently developed an innovative approach enabling to easily measure the moisture and temperature of the topsoil. This approach does not require the installation of costly infrastructures or to subscribe to communication networks: it is based on the development of communicating sensor nodes, totally buried at several tens of centimeters deep, see [4, 30] and Figure 1a. Their communication range can be modeled by a hemisphere-shaped surface as presented in Figure 1b. It is however limited to a few meters above the ground, that leads to difficulties in collecting their data remotely. One solution is to use a Unmanned Aerial Vehicle (UAV) to optimally collect the sensor data by entering successively within their communication range (see Figure 1c). In this way, the energy consumption spent by the nodes to communicate can moreover be significantly reduced. In fact, as the UAV can come close to the sensor nodes, the radio modules of the buried sensor nodes can be configured with a minimum transmit power and a short transmit time. In future work, the sensor nodes could even be woken up from a suited signal sent by the UAV to reduce even further the energy consumption of the nodes, see [3, 27].

<figure><img src="image_4.png" /><figcaption>Fig. 1. (a) Communicating sensor node measuring soil temperature and humidity installed in a pasture, preceding the soil covering, (b) Modeling of the aboveground communication range of the buried sensor node, (c) Objective: optimally plan the route of a rotary wing UAV to visit all the sensor nodes.</figcaption></figure>

However, the operating time of the UAV is limited by the capacity of its rechargeable battery. The length of the flight path has therefore to be optimized, all the more if a large number of nodes has to be visited.

Our approach naturally uses the Close Enough Traveling Salesman Problem (CE-TSP) framework: along a shortest path, the UAV has just to enter inside the hemispheres to collect the data without the need to go through the centers. The CE-TSP was largely studied in the literature. However, most of the proposed approaches are purely theoretical without considering real use cases. They are also essentially two-dimensional and free-obstacle.

In comparison with these works, the paper first presents a relevant way of modeling the workspace of the UAV. Many obstacles as tall vegetation, trees or buildings are taken into account. Then, a simple and efficient Evolutionary Algorithm is described to solve the CE-TSP in this cluttered environment. The UAV can fly efficiently
at different heights: low for collecting data from sensor nodes, high for avoiding obstacles. The main contributions of this paper are therefore:

* To present a way of exploiting real data from an airborne Light Detection and Ranging sensor (LiDAR) to accurately determine the location and height of obstacles in the workspace of the UAV,

* To outline a simple and efficient Partheno Genetic Algorithm (PGA) for UAV path planning in the context of CE-TSP with obstacles (CE-TSP-O),

* To give results on an experimental farm.

This paper is organized as follows. Section 2 presents a brief literature survey on the CE-TSP. Section 3 first introduces the real use case we worked on. Then, the exploitation of real data from an airborne Light Detection and Ranging sensor (LiDAR) is presented to determine the location and height of obstacles in the workspace of the UAV. Section 4 details our trajectory planning algorithm based on several steps: after some pre-processing operations to build the obstacle map for the UAV, a strategy to bypass the obstacles is proposed. The cost matrix between the nodes is deduced and a Partheno Genetic Algorithm (PGA) completed with some heuristic rules is developed for solving the CE-TSP. Section 5 gives several results enabling to highlight the performances of the method proposed. Finally, Section 6 contains the conclusion and future research.

## 2 Literature survey

The Traveling Salesman Problem (TSP) is a classical problem in combinatorial optimization which has been widely studied in the literature [38]. The goal is to determine the most cost-effective tour for visiting a given set of locations. A generalization of this problem is the TSP with neighbours (TSPN) where the neighbourhoods are represented by regions rather than by points, see [1]. The TSPN adds thus the possibility to collect the data just by entering the regions. The shape of these regions built around the targets can be more or less complex, see [9], [16], [41]. The Close Enough Salesman Traveling Problem (CE-TSP) is a special case of the TSPN where the neighbourhoods are represented by disks.

The CE-TSP has been particularly studied since 2006 for data collection vehicles. In [18], a vehicle has to collect customer's data from electricity and water meters using Radio Frequency Identification (RFID). The authors modeled the communication ranges of the meters by disks of same radius. The aim was to find the shortest path between them. [10] studied several metaheuristic algorithms for obtaining a tour of good quality. The proposed strategy was to build some super nodes using convex hull and clustering techniques before solving the TSP. Combinations of Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) are found in [39]. Exact methods such as Branch-and-Bound algorithms are applied in [7].

The concept of Steiner Zones (SZ) has been introduced in [28] to reduce the complexity of large-size problems. In fact, multiple targets can often be covered simultaneously by positioning the vehicle at the intersection areas between several disks. A set of new target points can therefore be first defined inside these intersection areas. A TSP is then solved with the consideration of these new points. Finally, the obtained trajectory is slightly modified to improve the solution by successively moving the target points following a TPP (Touring a Sequence of Polygons) algorithm.

Another approach consists in discretizing all the disks with a limited number of hitting points before applying a TSP solver [5]. A first discretization scheme consists of placing the points only on the perimeter of the disk. A second one also constructs new points inside the disks. This approach enables to highly reduce the calculation costs while obtaining a relatively good solution.

Some dynamic variants of CE-TSP have also been studied: the CE-TSP with Time Window (CE-TSP-TW) adds for example some temporal constraints on the availability of the targets [33]. The cost matrix between the targets can also be time-dependent [23]. Several objective functions are also sometimes considered: [15] combines for example travel costs and profits. [24] maximises the transmission rate of sensor nodes while minimizing the total
energy consumption of both sensor nodes and the UAV. In a different way, [36] proposes to visit only a subset of sensors and to use machine learning techniques to infer the data of unvisited sensors.

However, the consideration of barriers has been more recently addressed in the context of TSP, TSPN and CE-TSP. The main application is delivery in urban areas which faces a number of obstacles. In [37], a tour between points in the plane has to take into account obstacles represented by line segments randomly generated. [31] proposed an exact method to solve the Hampered Traveling Salesman problem with Neighbourhoods (H-TSPN). The objective is to find the shortest path in the plane that joins several points without crossing any polygonal barriers. [8] deals with H-TSPN from a geometrical point of view and the construction of a safe perimeter to bypass obstacles. [21] proposed an extension of the sequence-based Branch-and-Bound method to address the CE-TSP with polygonal obstacles. [17] studied both a Genetic Algorithm for solving the TSP and a projective algorithm for finding the shortest path around inflated obstacles. [25] developed a machine learning-assisted approach for an Unmanned Surface Vehicle (USV) for visiting multiple water monitoring stations. The difficulty is that the dimensions of obstacles vary with the tides. [13] proposed a metaheuristic method called GLNS-CETSP to find the shortest collision-free path on a map with numerous obstacles. It combines a solver for finding the shortest path between two target disks and an algorithm which constructs the trajectory iteratively.

In view of this literature survey, a first gap concerns the exploitation of real data to determine the real location, shape and height of obstacles. The way used to model obstacles is however essential as this will affect directly the path planning algorithm. A model close to the real world is therefore necessary with the presence of buildings but also tall vegetation. A second point is to consider that the UAV can change its altitude level during the flight: this degree of freedom is rarely exploited in the literature, although that impacts the strategies and the path planning algorithm. As we will see hereafter, our paper addresses these two gaps. A simple and effective Partheno Genetic Algorithm combined with heuristics rules is also described for solving the CE-TSP. The proposed method is applied on a real use case.

## 3 Use case and obstacle modeling

Our objective is to develop a UAV path planning algorithm to collect the data of a high number of sensors distributed in a real environment. To that end, we have considered a real use case within our experimental farm, see Figure 2a. Numerous obstacles (e.g. tall vegetation, trees, buildings) are present in this environment for a UAV flying at low height. To take into account this real environment, we considered the data delivered by a High Definition airborne Light Detection and Ranging sensor (HD LiDAR) of the French National Geographic Institute (IGN).

<figure><img src="image_5.png" /><figcaption>Fig. 2. (a) Real use case: experimental farm INRAE, Google Earth © Digital Globe, 46°20'22.35"N, 3°25'44.28"E, (b) Digital Surface Model (DSM) of this area created with QGIS from HD airborne LiDAR data of the French National Geographic Institute (IGN) (https://geoservices.ign.fr/lidarhd). This area of 400 hectares represents 100 millions of 3D points (25 points per square meter).</figcaption></figure>
An airborne LiDAR provides in fact a cloud of georeferenced points (latitude, longitude, altitude) corresponding to the uppermost points of the vegetation, the buildings and the ground. By using a High Definition LiDAR, very detailed information can be obtained, leading to a large amount of data in return (e.g. with 25 points per square metre, an area of 400 hectares represents 100 millions of 3D points). These data can be used to quantify and predict crop biomass for the development of agricultural decision support systems [32]. Here, we use them to create the Digital Surface Model (DSM), see Figure 2b. From this DSM, it is possible to determine the relative height of vegetation and buildings above the surrounding ground surface. Actually, by using the geographic information system software QGIS, the Digital Elevation Model (DEM) is first created from the points classified as belonging to the ground in the DSM, see Figure 3a. By subtracting the DSM from the DEM, the normalized Digital Surface Model (nDSM) is then obtained, see Figure 3b (this area is a grid 1400 m×1500 m representing 2.1 millions of 3D points). This nDSM can then be loaded in a numeric computing platform (Matlab), see Figure 4. A use case is next defined with 50 buried sensor nodes deployed inside this area. The positions and communication ranges of the nodes are shown in Figure 4 and given in Appendix A.

<figure><img src="image_6.png" /><figcaption>Fig. 3. (a) Digital Elevation Model (DEM), (b) Normalized Digital Surface Model (nDSM).</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 4. Use case (Matlab): the black areas are obstacles for the UAV, the red hemispheres represent the positions and communication range of 50 buried communicating sensor nodes.</figcaption></figure>

From this 3D environment, the objective is now to determine the shortest path for the UAV to collect the data of all the communicating sensor nodes. We can notice that, as the drone will move at a constant speed, the trajectory length calculated with the Euclidean distance will be directly proportional with the flight time of the UAV. In this case, the Euclidean distance is thus a relevant variable to minimize. It is used to compute the distance between each pair of points (target points or additional waypoints which will be created to bypass the obstacles). Obviously, other metrics (e.g. Manhattan distance) could be considered. An important constraint to be considered is also that the UAV has to come close to each sensor node (at a height $h_{uav}$ which will be defined in the following) to collect the data adequately: this necessitates to solve the CE-TSP with obstacles (CE-TSP-O).

To easily determine the presence of obstacles between two nodes for the UAV flying at low heights, we first propose to project the 3D points of the nDSM into a 2D black and white image (1400×1500 pixels) where the
white pixels will correspond to the ground and the black pixels to the obstacles, see Figure 5a. The consideration of a 2D image will enable to easily add a safety distance in the horizontal plane for the drone by means of mathematical morphology tools (dilation). The obstacles are thus considered slightly larger than they really are in the path planning algorithm. That is called "inflated obstacles" or "obstacles with safe perimeters" in the literature (however, the distances are always calculated in the 3D space). A dilation with a square structuring element 3×3 is therefore applied to fill small holes in obstacle areas and slightly increase their size, see Figure 5b.

In this dilated image, see Figure 5c, if the pixels are all white between two nodes, that means the space is free for the UAV. On the contrary, if at least one pixel is detected black between two nodes, that means there is at least one obstacle. In this case, the positions and heights of the obstacles between the nodes are retrieved in the 3D space. This data will be used to calculate a bypass distance when flying over the obstacle area.

<figure><img src="image_8.png" /><figcaption>Fig. 5. (a) 2D white and black image representing the obstacle map for the UAV, (b) Dilation of the image to inflate the obstacles for safety purpose, (c) Top image : if the pixels are all white between two nodes, the space is free for the UAV. Bottom image: if at least one black pixel is detected, at least one obstacle is present.</figcaption></figure>

# 4 Method developed to address the CE-TSP with 3D obstacles (CE-TSP-O)

Figure 6 presents the successive steps of our trajectory planning method. First, the airborne LiDAR data are used to create the nDSM. This model is then used to create 3D and 2D obstacle maps. Next, a strategy is defined to bypass the obstacles by flying above them. From this strategy and the coordinates of the sensor nodes, the cost matrix is calculated for all the pairs of nodes. Finally, a Partheno-Genetic Algorithm (PGA) completed with heuristic rules enables to propose a tour for the CE-TSP-O that determines the 3D trajectory of the UAV.

## 4.1 Avoidance strategy and cost matrix

The presence or absence of obstacles between two nodes, as well as their positions and heights, are determined by the 3D and 2D obstacle maps. The cost matrix $D = (d_{ij})$ of the UAV trajectory can then be calculated before investigating a solution for the CE-TSP. Each component of this matrix represents the Euclidean flight distance
<figure><img src="image_9.png" /><figcaption>Fig. 6. Block diagram of the proposed method for addressing the CE-TSP with obstacles (CE-TSP-O).</figcaption></figure>

between a pair of nodes (e.g. matrix 50×50 in case of 50 nodes). A strategy to bypass an obstacle between two sensors must therefore be previously defined.

Let us consider n sensor nodes: $S = \{s_1, \dots, s_n\}$. The data transmitted by a node $s_i$ of Cartesian coordinates ($s_{ix}$, $s_{iy}$, $s_{iz}$) can be collected by the UAV if the UAV enters inside the communication range $C_i$ linked to the node $s_i$. To simplify, this area $C_i$ is assumed to have a shape of a hemisphere of radius $r_i$ as depicted on Figure 1b. Moreover, we assume that the UAV has to fly at a height $h_{uav}$ to collect the data, see the notations in Figure 7.

<figure><img src="image_10.png" /><figcaption>Fig. 7. Strategy adopted in the presence of one or more obstacles.</figcaption></figure>

The height of an obstacle $k$ is noted $h_{obs}^k$. Let us denote by $K(i, j)$ the set of indices of the obstacles between the sensors $i$ and $j$. We have $K(i, j) = \{k_1, k_2, \dots, k_l\}$ where $k_1$ (resp. $k_l$) is the nearest (resp. farthest) obstacle from sensor $i$ to sensor $j$. Two distinct cases are considered:

* If no obstacle is detected between two nodes $s_i$ and $s_j$, the coefficient $d_{ij}$ is the Euclidean distance calculated according to (1).

* If one or several obstacles are detected between these nodes, the strategy adopted is that the UAV climbs from its current height $h_{uav}$ to the maximal height of the obstacles $h_{max}$ plus a security value $h_s$, see (2) and Figure 7. $d_1$ is the distance between the node $s_i$ and the first obstacle. $l_{obs}$ corresponds to the length of the obstacle area. $d_2$ is the distance between the last obstacle and the node $s_j$. With these notations, the coefficient $d_{ij}$ is calculated according to (3).

$$d_{ij} = \sqrt{(s_{ix} - s_{jx})^2 + (s_{iy} - s_{jy})^2 + (s_{iz} - s_{jz})^2} \quad (1)$$

$$h_{max} = \max_{k \in K(i,j)} (h_{obs}^k) + h_s \quad (2)$$
$$d_{ij} = \sqrt{(h_{max} - h_{uav})^2 + d_1^2 + l_{obs} + \sqrt{(h_{max} - h_{uav})^2 + d_2^2}} \quad (3)$$

The cost matrix D can then be built from (1), (2) and (3), see the illustration in Figure 8.

<figure><img src="image_11.png" /><figcaption>Fig. 8. Calculation of distances between all node pairs.</figcaption></figure>

Obviously, this approach could be easily extended to other dimensions, e.g. the horizontal plane to avoid obstacles from the sides. This would be particularly relevant for tall and narrow obstacles. A future work should develop a more complete solution which would deal with the real 3D shapes of obstacles.

## 4.2 Partheno-genetic algorithm and heuristic rules

Looking for an exact solution for the matrix D can be costly in time and resources. We propose a metaheuristic algorithm providing a near-optimal solution to the CE-TSP. The main advantage of such metaheuristic algorithms is to rapidly obtain a satisfactory solution, even when vast solution spaces are considered. The most known metaheuristic algorithms are the Genetic Algorithms (GA), the Simulted Annealing (SA), the Particle Swarm Optimization (PSO), the Ant Colony Optimization (ACO) and the Tabu Search algorithms, see [35].

In this work, we decided to develop a Partheno-Genetic Algorithm (PGA) for its simplicity of implementation and the possibility to easily experiment different mutation operators. This algorithm generates a tour based on the cost matrix D. Heuristic rules are next applied to slightly modify the obtained trajectory to take into account the communication ranges of the sensor nodes.

### 4.2.1 Partheno-Genetic Algorithm.
The genetic algorithms are evolutionary algorithms based on the evolution of a population by applying different random mutations and crossover operations over time. A Partheno-Genetic Algorithm (PGA) is a variation of the Standard Genetic Algorithms (SGA) which does not consider crossover operations between individuals. Our algorithm is depicted in Figure 9a and [2]: the algorithm starts from the creation of an initial population composed of N individuals (N is multiple of 5). Each individual has a chromosome whose sequence is randomly generated and represents a possible tour for the UAV. The population is next divided in groups of 5 individuals: in each group, the individual whose sequence has the minimal Euclidean distance is kept and called the survivor. The four other individuals of the group are removed and replaced by copies of the survivor with four possible mutations: on a random interval, the sequence of the numbers is either reversed, swapped, right-shifted or left-shifted, see Figure 9b. Finally, all the individuals are randomly remixed to form a new population. This process is repeated until a predetermined number of iterations is reached or the Euclidean distance d of the best route is no more changing during several successive iterations.
<figure><img src="image_12.png" /><figcaption>Fig. 9. (a) Principle of the Partheno-Genetic Algorithm (PGA), (b) Mutation operations on a random interval of a survivor.</figcaption></figure>

4.2.2 Heuristics rules. Next, to take the convex areas of the nodes into account (the trajectory of the UAV can pass within the hemispheres without the need to pass through the center), we consider a set of heuristic rules to reduce the tour length of the solution obtained with the TSP, see Figure 10.

<figure><img src="image_13.png" /><figcaption>Fig. 10. Heuristic rules for route reduction with three sensor nodes: (a) Nodes aligned $\Rightarrow$ tour unchanged, (b) $s_j \to \hat{s}_j$, (c) $s_j \to \hat{s}_j$, (d) $s_j \to \hat{s}_j$, (e) Presence of an obstacle on the route $\Rightarrow$ tour unchanged or obstacle bypass.</figcaption></figure>
In fact, at a constant flying height of the UAV (e.g. $h_{uav}=5$ m), the intersection of the XY-plan with a hemisphere is a disk whose radius represents the communication range of the sensor node on a plan (e.g. with a hemisphere of radius $r_i=10$ m, an UAV flying at $h_{uav}=5$ m leads to disks of radius $\sqrt{r_i^2 - h_{uav}^2}=8.66$ m). Instead of passing through the center of the targets, a shortest route can be built in some cases. For this purpose, let's consider three successive sensor nodes in the sequence determined from the TSP ($s_i \to s_j \to s_k$), see Figure 10. Five cases occur.

* Figure 10a: if the nodes are aligned (i.e. $det(s_i\vec{s}_j, s_j\vec{s}_k) = 0$), $s_j$ remains unchanged.

* Figure 10b: if the height $h$ of the triangle $[s_i s_j s_k]$ from the vertex $s_j$ is lower than the radius $r_j$ of the circle $C_j$, $s_j$ is replaced by $\hat{s}_j$.

* Figure 10c: if $h = r_j$, this is a particular case: $s_j$ is replaced by $\hat{s}_j$ which belongs also to $C_j$.

* Figure 10d: if $h > r_j$, the bisecting lines of the triangle $[s_i s_j s_k]$ are considered: $s_j$ is replaced by $\hat{s}_j$ which is the intersection point of $C_j$ and the bisecting line from the vertex $s_j$.

* Figure 10e: if the created trajectory ($s_i \to \hat{s}_j \to s_k$) goes through an obstacle, two options are possible. The first one is to keep the old trajectory ($s_i \to s_j \to s_k$), the second one is to bypass the obstacle.

These heuristic rules can be applied on groups of three successive circles of the route calculated by the PGA: they are repeated until the obtained trajectory no longer changes.

# 5 Results

The complete algorithm was implemented on an Intel(R) Core(TM) i7-12700H computer running at 2.30 GHz and equipped with 32 GB of RAM. It was programmed in Matlab 2024b with several functions (data loading, cost matrix calculation, PGA, heuristics for CE-TSP, calculation of the distance of the final trajectory). Each function was carefully verified by unit tests (UT).

## 5.1 Comparison with other works

Before applying our complete method to the real use case, the results of our Partheno-Genetic Algorithm (PGA) were first compared to the results obtained with other heuristic algorithms on different benchmarks. The first test was carried out on the benchmark « eil51 » of TSPLIB composed of 51 disks, see Figure 11a. A distance of 319.803 m was obtained with the PGA. The length of the best trajectory founded by [40], using an algorithm based on probabilistic modelling, was identical (319 m long). This first comparison therefore highlights the relevance of our algorithm. Next, we considered a real-world scenario « car_30.cetsp »: this one is composed of 75 target disks for a car door welding robot, see Figure 11b. In this scenario, several disks overlap each other. A distance of 5253.22 m was obtained with the PGA. This result is slightly shorter than the two determinist methods implemented by [22] (respectively 5272.49 m and 5436.60 m), but slightly longer than the memetic algorithm (5204.78 m). Another test was carried out on the benchmark « kroD100 » of TSPLIB composed of 100 disks, see Figure 11c. We chose the benchmark with a low overlap ratio (0.02), i.e. each node's radius is 0.7798 m. Despite its simplicity and many overlaps, the PGA provides a competitive solution (164.79 m) in comparison with the heuristic methods proposed by [28], [34] and [12] (length of respectively 162.76, 163.74 and 163.66 m). Table 1 summarizes these results. The PGA could be improved by carefully considering the possibility of multiple overlaps between the disks. However, since the sensor nodes are supposed to be far enough apart so as not to overlap, the PGA is efficient enough for our application.

## 5.2 Use case with $h_s=5$ m

The complete method was next experimented on the real environment depicted in Figure 2a. 50 buried sensor nodes whose communication range is equal to $r = 10m$ were considered, see Appendix A. The height of the UAV is set to $h_{uav} = 5$ m to adequately collect the data. The initial population of the genetic algorithm is composed of
<figure><img src="image_14.png" /><figcaption>Fig. 11. Comparison with other works: (a) Result of the PGA on the benchmark « eil51 » (TSPLIB) composed of 51 disks, (b) Result of the PGA on the real-world scenario « car_30.cetsp » composed of 75 disks, (c) Result of the PGA on the benchmark « kroD100 » (TSPLIB) composed of 100 disks.</figcaption></figure>

N = 1000 individuals. In a first experiment, we set the height of security for the UAV at $h_s=5$ m. Figures 12a, 12b and 12c show respectively the sky view of the trajectory obtained, the display of the trajectory in 3D and the height of the waypoints for the UAV. The total length of the generated trajectory is 5385 m. This result is obtained after a calculation time of 7.7 s (5.45 s to load the point cloud relating to the nDSM and 2.25 s for calculations of the PGA). We observe that the hitting points are selected in the manner to reduce the trajectory length. We can also see in Figure 12b that additional waypoints are incorporated into the tour of the UAV to bypass the vertical obstacle areas. The trajectory is finally programmed in the mission planner of our experimental UAV, see Figures 13a and 13b.

## 5.3 High $h_s$ for the PGA to avoid obstacle areas

In this second experiment, we set $h_s = 100$ m in the calculation of the cost matrix, in order to force the PGA to find a solution avoiding as much as possible the obstacle areas. The results are given in Figures 14a, 14b and 14c.
<table><caption>Table 1. Comparative results.</caption><thead><tr><th colspan="2">benchmark: eil51 (TSPLIB)</th></tr><tr><th>PGA</th><th>TSPN [41]</th></tr></thead><tbody><tr><td>319</td><td>319</td></tr></tbody></table><table><thead><tr><th colspan="4">benchmark: car_30.cetsp</th></tr><tr><th>PGA</th><th>2-phase-TSP [22]</th><th>2-phase-GTSP [22]</th><th>MA-CETSP [22]</th></tr></thead><tbody><tr><td>5253.22</td><td>5272.49</td><td>5436.60</td><td>5204.78</td></tr></tbody></table><table><thead><tr><th colspan="4">benchmark: kroD100 (TSPLIB)</th></tr><tr><th>PGA</th><th>SZ2 [28]</th><th>GLNS [34]</th><th>GSOA [12]</th></tr></thead><tbody><tr><td>164.79</td><td>162.76</td><td>163.74</td><td>163.66</td></tr></tbody></table>

<figure><img src="image_15.png" /><figcaption>Fig. 12. (a) Sky view of the generated trajectory for the UAV, (b) Display of the trajectory in 3D: when an obstacle is detected between two nodes, two additional way-points are incorporated in the trajectory enabling to fly over the obstacle areas, (c) Height of the waypoints for the UAV: the trajectory includes nine obstacles. The maximum value is 21.26 m.</figcaption></figure>

We observe in Figure 12b that the new trajectory passes through very few obstacles (4 instead of 9). As a result, this trajectory is 5869 m long, that means an increase of about 9%. This result highlights that a compromise needs to be found between a safe trajectory with a minimum of obstacle to bypass, and the shortest trajectory involving more obstacles, i.e. more risks of collision.

## 6 Conclusion and discussions

The aim of this work is to develop a simple and relevant approach to collect the data from a large number of buried communicating sensor nodes distributed in the environment by means of a UAV flying at various heights. Our approach takes into account the presence of obstacles in the path planning algorithm that solves the CE-TSP. We first present the possibility of exploiting real data from an airborne Light Detection and Ranging sensor (LiDAR). It accurately determines the location and height of obstacles over which the UAV may fly. The obstacle map for the UAV is deduced from the construction of the normalized Digital Surface Model (nDSM) which is processed to build a 2D white and black image locating the obstacles. Next, the trajectory cost matrix *D* between
<figure><img src="image_16.png" /><figcaption>Fig. 13. (a) Trajectory programming in the Mission Planner interface, (b) Our experimental UAV to perform the data collection task.</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>Fig. 14. (a) Sky view of the generated trajectory for the UAV, (b) Display of the trajectory in 3D, (c) Height of the waypoints.</figcaption></figure>

all the pairs of nodes is calculated. A Partheno Genetic Algorithm (PGA) completed with some heuristic rules finally builds a good quality tour. The proposed method is applied to a real use case with 50 sensor nodes.

From the results, incorporating the real workspace of the UAV to accurately and optimally plan its trajectory is clearly important. The limits are however to have up-to-date data. A way to attenuate errors due to changes in the environment is to use the flight of the UAV to collect information about the presence, shape and position of obstacles. In this way, obstacle maps could be updated regularly.

# 7 Perspectives

The future work of this study concerns several directions:

* The first one consists of defining better strategies to bypass the obstacles. In fact, in case of punctual and high obstacle (e.g. an isolated tree), it could be more efficient to bypass the obstacle on the sides.

* If the battery percentage of the drone drops below 20% during its mission, a security system triggers a Return to Launch (RTL) procedure, that means the drone stops its mission and automatically returns to its
take-off point. In future work, we intend to take into account the percentage of remaining battery in our path planning algorithm to adapt the trajectory in real-time.

* Another major improvement is to deal with several areas in the communication range of a buried communicating sensor node to represent the quality of communication, see Figure 15: if the UAV passes through the center area, the data collection will be assured. If the UAV passes only within the middle area, the communications will be satisfactory. Finally, if the UAV passes in the larger area, the communications will be uncertain. These new considerations will require to combine two antagonistic objectives, namely the search of the shortest trajectory and the quality of communications.

<figure><img src="image_18.png" /><figcaption>Fig. 15. Future work: several areas will be considered in the communication range of each buried communicating sensor node, corresponding to the quality of communication with the UAV.</figcaption></figure>

* We focus on optimal trajectory planning in terms of total traveled distance with the presence of obstacles. However, it could be interesting, as proposed in [25], to add other objectives, as minimizing the energy consumption of the sensor nodes or maximizing the transmission rate. To that end, accurate models of the nodes and the UAV have to be carefully established, completed with real measurements (e.g. wind strength, flight dynamics, weight and consumption of on-board equipment).

* Finally, real-world applications of data collection use one or several UAVs. That requires to have an efficient monitoring system. At the time being, on our ground control system, we have only the visual feedback of the flight trajectory of the UAV with its main parameters (e.g. location, speed, height). A more complete monitoring system should be developed for managing complex data collection tasks.

We can also notice that the European regulations restrict the maximal distance between the ground control system to the UAV: this distance must not exceed 1 km (scenario STS-02). This value is much lower than the communication capacity of our drone (20 km), that can already cover a medium-sized farm.

Our work is thus relevant to contribute to the development of UAVs to collect data from buried communicating sensor nodes in the agricultural sector. Our work is obviously not restrictive and other sectors of activity could benefit of these new perspectives, as the environmental monitoring and civil security.

## Acknowledgments

This work was supported by the International Research Center "Innovation Transportation and Production Systems" of the I-SITE CAP 20-25. The authors also acknowledge the ANR (French National Research Agency) for the financial support of the OCOD project n°ANR-24-CE25-7644.

## References

[1] E.M. Arkin and R. Hassin. 1994. Approximation algorithms for the geometric covering salesman problem. *Discrete Applied Mathematics*, 55(3):197-218 (1994). doi:10.1016/0166-218X(94)90008-6

[2] C. Cariou, L. Moiroux-Arvis, F. Bendali, and J. Mailfert. 2024. Optimal route planning of an Unmanned Aerial Vehicle for data collection of agricultural sensors. *IEEE Int. Conference on Computer Communications (INFOCOM) - Workshop on Networked Robotics and Communication Systems (NetRobiCS)*, Vancouver, BC, Canada, 1-6 (2024). doi:10.1109/INFOCOMWKSHPS61880.2024.10620865
[3] C. Cariou, L. Moiroux-Arvis, F. Pinet, and J.P. Chanet. 2022. Data collection from buried sensor nodes by means of an unmanned aerial vehicle. *Sensors*, 22(15), 5926 (2022). doi:10.3390/s22155926

[4] C. Cariou, L. Moiroux-Arvis, F. Pinet, and J.P. Chanet. 2023. Internet of Underground Things in Agriculture 4.0: Challenges, Applications and Perspectives. *Sensors*, 23, 4058 (2023). doi:10.3390/s23084058

[5] F. Carrabs, C. Cerrone, R. Cerulli, and M. Gaudioso. 2007. A novel discretization scheme for the Close Enough Traveling Salesman Problem. *Computers and Operations Research*, 78:163-171, (2007), 163-171. doi:10.1016/j.cor.2016.09.003

[6] M. Cosh, T.G. Caldwell, and C.B. Baker. 2021. Developing a strategy for the national coordinated soil moisture monitoring network. *Vadose Zone Journal*, 20(4):e20139 (2021). doi:10.1002/vzj2.20139

[7] W.P. Coutinho, R.Q.D. Nascimento, A.A. Pessoa, and A. Subramanian. 2016. A branch-and-bound algorithm for the Close-Enough Traveling Salesman Problem. *INFORMS Journal on Computing*, 28(4):752-765 (2016). doi:10.1287/ijoc.2016.0711

[8] D. Debnath, A.F. Hawary, M.I. Ramdan, F.V. Alvarez, and F. Gonzalez. 2023. QuickNav: An Effective Collision Avoidance and Path-Planning Algorithm for UAS. *Drones*, 7(678) (2023). doi:10.3390/drones7110678

[9] J. Deckerova, P. Vana, and J. Faigl. 2024. Combinatorial lower bounds for the Generalized Traveling Salesman Problem with neighborhoods. *Expert systems with applications*, 258 (2024). doi:10.1016/j.eswa.2024.125185

[10] J. Dong, N. Yang, and M. Chen. 2007. Heuristic approaches for a TSP variant: The automatic meter reading shortest tour problem. *Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies* Springer, Boston, MA., (2007). doi:10.1007/978-0-387-48793-9_10

[11] EC. 2023. EU Agricultural Outlook for markets, 2023-2035. *European Commission, DG Agriculture and Rural Development, Brussels*, (2023). doi:10.2762/722428

[12] J. Faigl. 2018. GSOA: Growing Self-Organizing Array - Unsupervised learning for the Close-Enough Traveling Salesman Problem and other routing problems. *Neurocomputing*, 312:120-134 (2018). doi:10.1016/j.neucom.2018.05.079

[13] L. Fanta. 2021. The Close Enough Travelling Salesman Problem in polygonal domain. *Master thesis, Prague University*, (2021). https://dspace.cvut.cz/bitstream/handle/10467/96747/F3-DP-2021-Fanta-Lukas-Fanta_Lukas_The_Close_Enough%20-Travelling%20_Salesman_Problem_in_polygonal_domain.pdf

[14] FAO. 2022. The Future of Food and Agriculture, Drivers and Triggers for Transformation. *Food and Agriculture Organization of the United Nations: Rome, Italy*, 3 (2022). doi:10.4060/cc0959en

[15] D. Feuillet, P. Dejax, and M. Gendreau. 2005. Traveling Salesman Problems with Profits. *Transportation Science*, 39(2):188-205 (2005). doi:10.1287/trsc.1030.0079

[16] I. Gentilini, F. Margot, and K. Shimada. 2012. The Travelling Salesman Problem with neighbourhoods: MINLP solution. *Optimization Methods and Software*, 28(2):364-378 (2012). doi:10.1080/10556788.2011.648932

[17] M. Greiff and A. Robertsson. 2017. Optimisation-based motion planning with obstacles and priorities. *IFAC*, 11670-11676 (2017). doi:10.1016/j.ifacol.2017.08.1677

[18] D. Gulczynski, J. Heath, and C. Price. 2006. Close Enough Traveling Salesman Problem: A discussion of several heuristics. *Perspectives in Operations Research*, 36:271-28 (2006), 3. doi:10.1007/978-0-387-39934-8_16

[19] S. Gurung, S. Thakur, B. Smithers, and M. Acevedo. 2020. Wireless soil moisture sensor networks for agriculture. *Waste-management Education Research (WERC), Las Cruces, NM, USA*, (2020). doi:10.1109/WERC49736.2020.9146500

[20] C. Kremen. 2020. Ecological intensification and diversification approaches to maintain biodiversity, ecosystem services and food production in a changing world. *Emerging Topics in Life Sciences*, 4(2):229-240 (2020). doi:10.1042/ETLS20190205

[21] K. Kucerova. 2023. Lower Bound Estimates for Path Planning in Environment with Obstacles. *Master's thesis, Faculty of Electrical Engineering, CTU Prague* (2023). https://dspace.cvut.cz/bitstream/handle/10467/109412/F3-DP-2023-Kucerova-Kristyna-main.pdf

[22] Z. Lei and J.K. Hao. 2024. An effective memetic algorithm for the Close Enough Traveling Salesman Problem. *Applied Soft Computing*, 153(3):111266 (2024). doi:10.1016/j.asoc.2024.111266

[23] C. Li, M. Yang, and L. Kang. 2006. A new approach to solving dynamic Traveling Salesman Problems. *In: Wang, TD., et al. Simulated Evolution and Learning. SEAL 2006. Lecture Notes in Computer Science, vol 4247. Springer, Berlin, Heidelberg*, 4247:236-243 (2006). doi:10.1007/11903697_31

[24] L. Liu, A. Wang, G. Sun, J. Li, H. Pan, and T. Q. S. Quek. 2025. Multi-objective optimization for data collection in UAV-assisted agricultural IoT. *IEEE Transactions on Vehicular Technology*, 74(4):6488-6503 (2025). doi:10.1109/TVT.2024.3514664

[25] Y. Liu and R. Bucknall. 2018. Efficient multi-task allocation and path planning for unmanned surface vehicle in support of ocean operations. *Neurocomputing*, 275:1550-1566 (2018). doi:10.1016/j.neucom.2017.09.088

[26] J. Lloret, S. Sendra, L. Garcia, and J.M. Jimenez. 2021. A wireless sensor network deployment for soil moisture monitoring in precision agriculture. *Sensors*, 7243 (2021). doi:10.3390/s21217243

[27] M. Magno and Jelicic V. 2016. Design, implementation, and performance evaluation of a flexible low-latency nanowatt wake-up radio receiver. *IEEE Transactions on Industrial Informatics*, 12(2):633-644 (2016). doi:10.1109/TII.2016.2524982

[28] W. Mennell, B. Golden, and E. Wasil. 2011. A steiner-zone heuristic for solving the Close-Enough Traveling Salesman Problem. *12th INFORMS Computing Society Conference, Homeland Defense, Monterey, CA, USA*, 13 (2011). doi:10.1287/ics.2011.0004
[29] L. Mimeau, Tramblay Y., and L. Brocca. 2021. Modeling the response of soil moisture to climate variability in the Mediterranean region. *Hydrology and Earth System Sciences*, 25:653-669 (2021). doi:10.5194/hess-25-653-2021

[30] L. Moiroux-Arvis, C. Cariou, and J.P. Chanet. 2022. Evaluation of LoRa technology in 433-MHz and 868-MHz for underground to aboveground data transmission. *Computers and Electronics in Agriculture* 194, 106770 (2022). doi:10.1016/j.compag.2022.106770

[31] J. Puerto and C. Valverde. 2024. The Hampered Travelling Salesman problem with Neighbourhoods. *Computers and Industrial Engineering* 188, 109889 (2024). doi:10.1016/j.cie.2024.109889

[32] A. K. Sangaiah, J. Anandakrishnan, V. Meenakshisundaram, M. A. A. Rahman, P. Arumugam, and M. Das. 2025. Edge-IoT-UAV adaptation toward precision agriculture using 3D-LiDAR point clouds. *IEEE Internet of Things Magazine* 8(1):19-25, 109889 (2025). doi:10.1109/IOTM.001.2400027

[33] S. Semami, H. Toulni, and A. Elbyed. 2019. The Close Enough Traveling Salesman Problem with time window. *Int. Journal of Circuits, Systems and Signal Processing*, 13 (2019), 579–584. https://www.naun.org/main/NAUN/circuitssystemssignal/2019/b582005-akw.pdf

[34] S. L. Smith and F. Imeson. 2017. GLNS: An effective large neighborhood search heuristic for the generalized traveling salesman problem. *Computers and Operations Research*, 87:1-19 (2017). doi:10.1016/j.cor.2017.05.010

[35] E-G. Talbi. 2009. Metaheuristics: from design to implementation. *Wiley Encyclopedia of Operations Research and Management Science*, (2009). https://zeus.inf.ucv.cl/~bcrawford/DiplomadoIA_2021/Cap1_Metaheuristics_Talbi.pdf

[36] X. Tao, E. Damron, and S. Silvestri. 2024. High-precision crop monitoring through UAV-aided sensor data collection. *ICC 2024 - IEEE International Conference on Communications, Denver, CO, USA*, 3506-3511 (2024). doi:10.1109/ICC51166.2024.10622745

[37] J. VanDrunen, K. Nam, M. Beers, and Z. Pizlo. 2023. Traveling Salesperson Problem with Simple Obstacles: The Role of Multidimensional Scaling and the Role of Clustering. *Computational Brain and Behavior*, 6 (2023). doi:10.1007/s42113-022-00155-0

[38] Y. Xu and C. Che. 2019. A brief review of the intelligent algorithm for Traveling Salesman Problem in UAV route planning. *9th International Conference on Electronics Information and Emergency Communication (ICEIEC), Beijing, China*, 1-7 (2019). doi:10.1109/ICEIEC.2019.8784651

[39] Z. Yang, M.Q. Xiao, Y.W. Ge, D.L. Feng, L. Zhang, H.F. Song, and X.L. Tang. 2018. A double-loop hybrid algorithm for the traveling salesman problem with arbitrary neighbourhoods. *European Journal of Operational Research*, 265(1):65-80 (2018). doi:10.1016/j.ejor.2017.07.024

[40] B. Yuan, M. Orlowska, and S. Sadiq. 2007. On the optimal robot routing problem in wireless sensor networks. *IEEE Transactions on Knowledge and data engineering*, 19(9):1252-1261 (2007). doi:10.1109/TKDE.2007.1062

[41] B. Yuan and T. Zhang. 2017. Towards Solving TSPN with arbitrary neighborhoods: A hybrid solution. In: *Wagner, M.*, Li, X., Hendtlass, T. (eds) *Artificial Life and Computational Intelligence. ACALCI 2017. Lecture Notes in Computer Science*, vol 10142. Springer, Cham., (2017). doi:10.1007/978-3-319-51691-2_18

A Appendix: Coordinates of the sensor nodes

Received 29 November 2024; revised 3 June 2025; accepted 11 July 2025
<table><caption>Table 2. Coordinates in Lambert-93 conformal conic projection and ranges of the sensor nodes.</caption><thead><tr><th>Number</th><th>Longitude (m)</th><th>Latitude(m)</th><th>Range (m)</th><th>Number</th><th>Longitude (m)</th><th>Latitude(m)</th><th>Range (m)</th></tr></thead><tbody><tr><td>1</td><td>733191.57</td><td>6582924.53</td><td>10</td><td>26</td><td>733201.33</td><td>6582631.74</td><td>10</td></tr><tr><td>2</td><td>733238.19</td><td>6582896.36</td><td>10</td><td>27</td><td>732900.11</td><td>6582566.13</td><td>10</td></tr><tr><td>3</td><td>733096.36</td><td>6582671.14</td><td>10</td><td>28</td><td>732915.72</td><td>6582467.15</td><td>10</td></tr><tr><td>4</td><td>733284.59</td><td>6582877.51</td><td>10</td><td>29</td><td>733007.74</td><td>6582546.94</td><td>10</td></tr><tr><td>5</td><td>733225.62</td><td>6582817.11</td><td>10</td><td>30</td><td>733113.43</td><td>6582571.95</td><td>10</td></tr><tr><td>6</td><td>733214.37</td><td>6582722.98</td><td>10</td><td>31</td><td>733054.91</td><td>6582456.58</td><td>10</td></tr><tr><td>7</td><td>733153.29</td><td>6582655.23</td><td>10</td><td>32</td><td>732963.23</td><td>6582357.58</td><td>10</td></tr><tr><td>8</td><td>733339.23</td><td>6582826.73</td><td>10</td><td>33</td><td>732933.98</td><td>6582220.15</td><td>10</td></tr><tr><td>9</td><td>733339.05</td><td>6582777.75</td><td>10</td><td>34</td><td>733041.17</td><td>6582354.56</td><td>10</td></tr><tr><td>10</td><td>733488.97</td><td>6582745.04</td><td>10</td><td>35</td><td>733019.24</td><td>6582199.62</td><td>10</td></tr><tr><td>11</td><td>733437.99</td><td>6582713.66</td><td>10</td><td>36</td><td>732945.11</td><td>6582125.48</td><td>10</td></tr><tr><td>12</td><td>733271.83</td><td>6582650.66</td><td>10</td><td>37</td><td>732994.43</td><td>6582122.42</td><td>10</td></tr><tr><td>13</td><td>733359.79</td><td>6582669.36</td><td>10</td><td>38</td><td>732747.36</td><td>6582267.45</td><td>10</td></tr><tr><td>14</td><td>733410.45</td><td>6582560.91</td><td>10</td><td>39</td><td>732816.86</td><td>6582316.91</td><td>10</td></tr><tr><td>15</td><td>733337.00</td><td>6582520.87</td><td>10</td><td>40</td><td>732891.33</td><td>6582368.40</td><td>10</td></tr><tr><td>16</td><td>733199.44</td><td>6582569.97</td><td>10</td><td>41</td><td>732855.87</td><td>6582242.05</td><td>10</td></tr><tr><td>17</td><td>733149.83</td><td>6582400.01</td><td>10</td><td>42</td><td>732705.09</td><td>6581632.66</td><td>10</td></tr><tr><td>18</td><td>733239.10</td><td>6582489.23</td><td>10</td><td>43</td><td>732786.77</td><td>6581678.19</td><td>10</td></tr><tr><td>19</td><td>733264.82</td><td>6582400.64</td><td>10</td><td>44</td><td>732887.65</td><td>6582681.44</td><td>10</td></tr><tr><td>20</td><td>733158.66</td><td>6582317.44</td><td>10</td><td>45</td><td>733411.60</td><td>6582464.75</td><td>10</td></tr><tr><td>21</td><td>733148.42</td><td>6582236.76</td><td>10</td><td>46</td><td>733347.44</td><td>6582243.62</td><td>10</td></tr><tr><td>22</td><td>733136.09</td><td>6582154.62</td><td>10</td><td>47</td><td>733480.74</td><td>6582047.45</td><td>10</td></tr><tr><td>23</td><td>733246.36</td><td>6582315.03</td><td>10</td><td>48</td><td>733494.85</td><td>6581916.26</td><td>10</td></tr><tr><td>24</td><td>733274.86</td><td>6582237.45</td><td>10</td><td>49</td><td>733333.27</td><td>6581994.01</td><td>10</td></tr><tr><td>25</td><td>733240.24</td><td>6582141.86</td><td>10</td><td>50</td><td>733214.47</td><td>6581930.50</td><td>10</td></tr></tbody></table>