Introduction

Machinery and equipment are major cost items in farm businesses. Larger machines, new technology, higher prices for parts and new machinery, and higher fuel prices have caused operation costs to rise in recent years. Decisions about technology to be used require accurate estimates of the costs of owning and operating farm machinery (Edwards 2009). In this context, better management of the non-productive operation of machinery (i.e., time used for turning or being serviced) can be essential. The ASABE standard ASAE EP496.3 (2009) lists remarkably low time efficiency rates for several types of machinery and field operations: approximately 80–85 % for tillage operations, 70 % for fertilizer spreaders, 65–70 % for seeding and planting operations, 60–65 % for sprayers, 60–70 % for harvesters (combine, cotton and potato harvesters).

Reduced efficiency is caused by several factors including the turning of the machine near field edges and obstacles as well as loading and offloading of agricultural goods (e.g., seeds, fertilizer, agrochemicals, or harvested crops). The latter are referred to as “servicing” in this paper. The efficiency of field operations is thus influenced by the shape and size of fields (Klemola et al. 2002) and this effect has been studied using indices of field shape complexity (Peltola et al. 2006; Oksanen and Visala 2007). The positioning of storage bins for harvest outputs around the field can have a substantial impact on the efficiency of field operations (Busato et al. 2007). On the other hand, path planning can help to increase the efficiency of agricultural machinery by computing tracks, passes or routes in fields using computer algorithms that optimize any combination of costs, field coverage and time (Palmer et al. 2003; Taïx et al. 2006; Bruin et al. 2009; Bochtis et al. 2010a).

In recent years, developments and improvement of auto-guidance and self-steering systems on machines have led to increased interest in path planning and robotics (Keicher and Seufert 2000; Cariou et al. 2010a). Research in these domains has focused on several problems, either isolated or in combination, such as a decrease in the number of turns by reducing field complexity and splitting the field into simple shaped sub-fields (Jin and Tang 2006; Oksanen and Visala 2007; Hofstee et al. 2009) and finding more suitable turning patterns between adjacent machine tracks (Cariou et al. 2010b; Jin and Tang 2010). Bochtis and Vougioukas (2008) considered mechanical turning limits of machinery in an algorithm that skips tracks in order to simplify turns and to reduce non-productive traveled distance. Depending on the operation, savings of up to 50 % of non-working distance could be achieved. Bochtis and Oksanen (2009) combined the latter method with iterative splitting of the field in different driving directions aiming to reduce the number of turns and to find an optimized sequence of turns between tracks. Dillon et al. (2003) combined coverage and time optimization costs for defining a path that would decrease errors in variable rate fertilization. The large number of possible solutions called for a heuristic optimizer which reduced application errors from 14 to 9 % of the amount of fertilizer required.

It is easy to see that on small fields, turns may involve substantial losses but on larger fields their influence on total efficiency is less important because the percentage of time required for turning is small in relation to the total operation time. In contrast, servicing requirements increase with field size (Witney 1996). Recently, the reduction of in-field travel distance of auxiliary units for both uncontrolled traffic farming (Bochtis et al. 2010b) and controlled traffic farming (Bochtis et al. 2010c) was studied. Oksanen and Visala (2007) considered servicing of machinery in a real-time route optimization problem. Their algorithm considered pre-defined servicing spots with the route of a machine being built during field operation. If a next track would require intermediate servicing (it would lead to an empty sprayer or a full combine somewhere halfway), an alternative route is calculated that includes a visit to a servicing point.

Neglecting servicing in route planning for large fields may force machinery to stop at inappropriate locations or moments which reduce efficiency because available capacity is under-utilized. Therefore, the objective of this work was to contribute to a method that combines choosing the best orientation of parallel tracks with minimization of the time needed for turning between tracks while accounting for time loss due to servicing of the machine. To our knowledge, the integration of methods needed for such optimization has not yet been studied.

Methodology

Overview of the optimization problem

In this study, the aim of optimization is to reduce overall non-productive time of a machine in the field. This non-productive time thus constitutes the objective function that is to be minimized. Two losses were considered: maneuvering and servicing. We consider a single field operation and assume that the main part of a field is covered by straight tracks separated by a given width while turning occurs in headlands along the edges. Accordingly, the extreme points of the tracks, which from this point on are referred to as nodes, are placed at some distance from the border of the field, thus allowing space for the machine to turn. Additionally, we assume that a field is geometrically described by a 2D polygon that is defined by vertices (points) given in metric co-ordinates. These vertices define the outer boundary of the polygon and any internal obstacles (forbidden zones) within the field. Finally, the machine is assumed to enter the field at a pre-defined entrance point.

This work draws on earlier work of Bochtis and Vougioukas (2008) who considered two shapes for turning of machines: Ω-turns and U-turns (Fig. 1). The Ω-turn requires more space and time and it is needed when the machine cannot steer directly from one finished track to the next without first moving away from the former so as to allow for the required turning circle. By skipping tracks more room is available so that a faster U-turn can be made.

Fig. 1
figure 1

Turning patterns: Ω-turn between an adjacent track, and U-turn skipping one track (adapted from Bochtis and Vougioukas, 2008)

Full size image

All tracks have to be visited, though; the resulting number of turning combinations to work all the tracks poses a traveling salesmen problem (TSP). These authors considered minimization of non-working distance and they solved the TSP for a given set of tracks heuristically using the Clarke–Wright savings algorithm (Clarke and Wright 1964). In this study, we also adopted the Clarke–Wright savings algorithm because of its conceptual simplicity while still yielding effective solutions (Golden et al. 1980). Today, there are several alternative solutions (e.g., Nagata and Soler 2012; Rego et al. 2011) which could be considered within the framework presented in this paper.

In this paper, optimization concerns the time spent on turns, which are expressed by sequences of segments, each with a length and a specific speed assigned to it. The result of optimization is a complete route over the field. Following this route, the machine depletes its tank capacity (machine storage capacity for inputs like grain or fertilizer) until it reaches a critical point where it cannot finish the next track without a service stop. Depending on the field shape and the orientation of tracks, a machine may not be able to optimally use its tank capacity since the operator may be obliged to have a service stop before the machine’s full capacity has been used. The service stop adds non-productive time to the total time loss. An alternative orientation of the tracks may avoid this problem but, on the other hand, require more costly turns. The overall time-costs of a route are assessed by solving the TSP for a discrete set of tracks covering the field in different directions and choosing the least-cost solution.

Conceptual model and implementation

Figure 2 outlines the sequence of steps of the method. Steps (1) and (2) create a complete route covering the field with straight parallel tracks for a given orientation and connect these tracks by a set of turns that yield the least turning time (Tturning). Step (3) determines the number and the locations of service stops required for the route and the associated servicing time (Tservicing).

Fig. 2
figure 2

Conceptual model of the algorithm

Full size image

Steps 1–3 are repeated by looping over a discrete set of orientation angles. In the examples, 180 angles separated by a step size of 1° were used.

The final route created is for one single machine operation. The algorithm doesn’t handle combinations of operations in one run.

The non-productive time is given by Eq. 1

$$ T_{non\_working} = T_{turning} + T_{servicing} $$
(1)

Equation 1 shows that the time required by the machine for driving between the field entrance/exit point and the first and final nodes of the route is not considered. The optimization problem of choosing an optimal turning sequence along a given set of tracks is a TSP that was solved by a heuristic optimizer, as explained later.

Input data

The geometry of the field and any obstacles within it are assumed to be specified in metric co-ordinates. If provided in lat/long co-ordinates, a transformation to a metric system is first required. Other user-defined inputs are operation width (Width) (m), turning radius (Turning_radius) (m) and capacity (Capacity) (unit) of the machine, as well as the rate at which the tank is filled or emptied (Rate) (unit ha−1), the turning velocity (Vel turning ) (km h−1), the straight non-operational velocity (Vel straight ) (km h−1) and the time needed for servicing (T serv ) (min).

Generation of tracks for a given angle

First, space for turning was created as by inward buffering of the outer field boundary and outward buffering of any obstacles inside the field. Field boundaries where turns are needed are identified via intersection with a pattern of tracks (for the orientation angle under consideration) superimposed over the field. The space required for turns near a border was calculated using three variables: the angle between the working direction (Track_angle) (angle in degrees) and the border of the field (Border_angle), Width and Turning radius. The required headland (HL) width was calculated by Eq. 2

$$ HL = \left( {\sin \left( {Track\_angle - Border\_angle} \right) + 1} \right)*Turning\_radius + \frac{Width}{2} $$
(2)

By buffering the edges, a new smaller polygon is obtained which is completely covered by straight parallel tracks with a given orientation Track_angle.

Figure 3 shows an example of the output of the algorithm for this step.

Fig. 3
figure 3

Example of headlands (HL) and tracks created in step 1

Full size image

The final term of Eq. (2) creates the minimum space needed for a machine to avoid border collision while moving at full width (e.g., open spray boom bars or sowing machine). The space is needed for a machine to move near the field border while turning along the tracks is herein designated as Machine maneuvering limit which is a path created from an offset of the field (and/or obstacles) that can be seen in Fig. 4.

Fig. 4
figure 4

U-turn of a machine going from node N1 to node N2

Full size image

Optimized route along tracks

Types of turns and their construction

Two types of turns are considered for connecting the tracks generated by the method described in the previous section: U-turn (see Fig. 4) and Ω-turn (see Fig. 5).

Fig. 5
figure 5

Ω-Turn of a machine going from node N1 to node N2

Full size image
U-turn

The steps for creating a U-turn (see Fig. 4) are as follows:

  1. 1.

    When the machine enters the headland, it continues in the direction of the track until it starts the turn (segment “a”);

  2. 2.

    The machine makes a circular turn around a pivot until it reaches the Machine maneuvering limit (segment “b”);

  3. 3.

    The machine drives along the Machine maneuvering limit (segment “c”);

  4. 4.

    The machine makes a circular turn until it heads in the direction of the target track;

  5. 5.

    The machine drives straight in the direction of the node where the working track starts (segment “e”).

The segments b and d occur at all U turns but the straight segments a, c and e are only needed when or if there is a distance between the extreme nodes of tracks and the turns (a and e) or in the case of skipping adjacent tracks (c).

Ω-Maneuver:

The steps for creating an Ω-turn (see Fig. 5) are as follows:

  1. 1.

    When the machine enters the buffer zone, it continues in the direction of the current track until it starts a turn on the opposite side of the track (segment “a”);

  2. 2.

    The machine turns, following a “lamp bulb” shape until it heads in the direction of the target track (segment “b”);

  3. 3.

    The machine goes straight (if necessary) in the direction of the node where the working track starts;

Step 2 above occurs in all Ω-turns but the straight segment of steps 1 and 3 are only needed if the angle between the track and the border is not perpendicular (meaning that the machine has to move straight until it starts to turn).

In the present implementation, Ω-turns disregard field boundaries, requiring more development.

The cost is calculated from the sum of the time spent in each of these steps by Eq. 3

$$ T_{turn} = \sum\limits_{all\;segments} {\frac{{Dist_{segment} }}{{Vel_{segment} }}} $$
(3)

where T turn is the time spent in one turn [s], Dist segment is the length of one segment [m], and Vel segment is the speed of the machine in the segment (if in turning or straight movement) [m s−1].

Implementation of turns in the algorithm

Figure 6 illustrates the method for implementing U and Ω turns to generate a route between paths that are to be connected.

Fig. 6
figure 6

Steps used for creating U-turns and Ω-turns

Full size image

In Fig. 6, the central turning point (pivot) of a U-turn is located at distance D 2 from the machine maneuvering limit and it is also offset by a distance D 3 perpendicular to the direction of the track. After the pivot has been defined, an arc is built around it in arbitrarily chosen steps of 20° until the machine reaches the Machine maneuvering limit. For the Ω-turn, the pivot is placed in the middle of the tracks at a distance D 4 parallel to them. From this point, an arc is built, again in steps of 20°, except for the steps at each extremity of the arc, which were set at 40° so as to allow the machine to move more smoothly. Note that the choices for 20 and 40° can be adapted to specific needs of machinery.

Figure 6 also illustrates that Eq. 3 constitutes the sum of D 1 , D 2 , and D 3 .

Obtaining an optimized sequence of turning between tracks

Figure 7 explains by an example how the algorithm retrieves an optimized sequence of tracks which are connected by turns.

Fig. 7
figure 7

Example of the heuristic optimization applied to obtain a route, visiting each track only once

Full size image

As in the example of Fig. 7a, when two nodes are located at a smaller distance than twice the Turning radius, a Ω-turn between them is constructed (for example between nodes 1a and 2a). Otherwise a U-turn is used (for example between nodes 1a and 3a); only one type of turn is possible between two specific nodes. For each node, a complete set of turning distances to all other nodes is retrieved. These distances are divided by the corresponding velocity to obtain the time required for turning between the nodes (Eq. 3). The time is saved in an array list TN (“turning between nodes”). Figure 7a displays an example of distances obtained between the nodes.

The problem is thus to find an optimal sequence of tracks, visiting each track just once, such that the total non-operational time is minimized. As indicated above, this poses a TSP. To solve this problem, the heuristic Clarke–Wright savings algorithm (Clarke and Wright 1964) was used. The algorithm retrieves savings calculated by the difference (in time) of two paths (illustrated in Fig. 7b), which is also stored in the array list TN.

Afterwards, the TN list is sorted from the highest to the lowest savings value, and while building the route from the ordered list every track that has been visited is marked not to be visited again. The resulting sequence of the given example can be seen in Fig. 7c, where the arrows and the numbers give the direction and sequence for the route. The sum of all the turns retrieves the total turning time (Tturning) as is shown in Eq. 4

$$ T_{turning} = TN[T_{turn\;1a \to 4a} ] + TN[T_{turn\;4b \to 2b} ] + TN[T_{turn\;2a \to 5a} ] + TN[T_{turn\;5b \to 3b} ] $$
(4)

In case of an obstacle within the field, a Machine maneuvering limit is created around it and additional turns are to be made to circumvent it. Note that nodes are allowed to link only to other nodes near the same feature; a node near the field boundary cannot have a turn-link to a node near an obstacle.

Servicing

When a machine follows a route, it is consuming its tank capacity at a given rate; each track covers an area and the corresponding amount of product is subtracted from the capacity of the machine. In this work, before the next track is entered, a calculation is done to check if the remaining capacity is sufficient for completing the next track. If this track demands more tank capacity than available, the algorithm skips the suggested turn and looks for a shorter track that may allow the use of the remaining tank capacity, thus overruling the choice of the savings algorithm for turning. If the quantity required to work any closer tracks is more than the remaining capacity then servicing is required and the machine must stop, thus increasing the number of service stops (N serv ) by one.

Servicing time is then given by:

$$ T_{Servicing} = N_{Serv} *T_{Serv} $$
(5)

where T serv is the user-given time for one service. T serv is included in the total non-productive time (Eq. 1) which is the quantity to be minimized.

Example applications and discussion

The algorithm was used to create routes on irregularly shaped fields and for field operations with and without servicing stops in the example applications given below.

Disking without servicing

Figure 8 shows a field with an area of 1.87 ha near Wageningen, The Netherlands. A disking operation was considered with Width = 3 m, Turning_radius = 4 m, a Vel straight speed of 8 km h−1 and a turning Vel turn of 3 km h−1. A total of 180 different angles (see Fig. 10 for examples) were considered. Figure 9 shows examples of different routes created for the different directions of work tried. The two orientations are not the best working directions, but just show how for each orientation considered an optimal route was computed. Figure 10 shows the optimized route.

Fig. 8
figure 8

Field-plot located near the city of Wageningen, the Netherlands (Source Google™ Earth, extracted in April 2010, ©Google Inc.)

Full size image
Fig. 9
figure 9

Alternative routes for two angles and the corresponding non-productive time

Full size image
Fig. 10
figure 10

Optimized route found for the disking operation

Full size image

The optimized orientation was the same as the one currently exercised in the field (Fig. 8); a less obvious result was the sequence of tracks suggested to be followed for maneuvering. When compared to conventional turning between adjacent tracks, a 50 % reduction in the maneuvering time was obtained.

Case studies optimizing maneuvering and servicing time

Harvesting

The algorithm was also applied on three field operations that require servicing. The servicing was assumed to be performed at any margin of the field. A harvesting operation was assumed on an 84.5 ha field (see Fig. 11). The properties of the machine used were: Width = 9 m, Turning_radius = 8 m, Vel straight  = 10 km h−1, Vel Turn  = 2 km h−1, Capacity = 7 000 kg, and Tserv = 5 min Yield = 3 000 kg ha−1.

Fig. 11
figure 11

Arable field located in the province of Mato Grosso do Sul, Brazil. (Source Google™ Earth, extracted in April 2010, ©Google Inc.)

Full size image

The optimal route found for this operation is shown in Fig. 12.

Fig. 12
figure 12

Optimized route found for a harvesting operation without auxiliary machinery

Full size image

Surprisingly, Fig. 13 shows an optimal orientation of 8° (not parallel to any of the field boundaries), 55.47 min of turning time and 185 min time needed for servicing, which totals 240.47 min of non-productive time.

Fig. 13
figure 13

Non-working time spent in the harvest operation for different angles (90° is the exact north)

Full size image

Harvesting this field required at least 36 servicing stops (see Fig. 12) which is not uncommon for harvest operations on large fields because of the high rate at which the tank is filled. During harvest operations such servicing is usually performed by auxiliary machinery (on-field servicing) that offloads the machine only when its tank is completely full.

If the capacity of the machine was fully used for the whole harvest (which could be achieved with the additional auxiliary machinery), a total of 33 stops would be required The algorithm found a route that leads the machine to three more stops for servicing without on-field operations but that may be preferable to avoid soil compaction from the auxiliary machinery and/or the cost of auxiliary machinery.

Figure 13 shows that the orientation having the least maneuvering requirements (18°) did not produce the minimum total non-working time. Quite to the contrary, choosing the least maneuvering time would lead to one of the highest servicing times.

Manure injection

A manure distribution operation was assumed on a 4.98 ha field (Fig. 14). The properties of the machine used were: Width = 4 m, Turning_radius = 5 m, Vel straight  = 8 km h−1, Vel turn  = 3 km h−1, a Capacity = 10 000 l, and a T Serv  = 15 min, Rate = 4 000 l ha−1. All around the fields, a headland with a fixed width of 5 m was planned.

Fig. 14
figure 14

Arable field located in the province of Limburg, the Netherlands. (Source Google™ Earth, extracted in April 2010, ©Google Inc.)

Full size image

The route shown in Fig. 15 shows the single solution where the manure injection required five servicing operations; all other solutions required the machine to reload six times or more. Even so, servicing accounted for 68.3 % of the total non-working time in the optimized route.

Fig. 15
figure 15

Optimized route found for manure distribution on a 4.98 ha field

Full size image

It can be observed that the algorithm tried to avoid time-consuming Ω-turns (Figs. 10, 12, and 15). However, depending on the angle of the machine heading towards the border of the field and the distance of remaining nodes, Ω-turns may be required.

Comparison of two sprayers

A spraying operation was simulated in a 397 ha field (Fig. 16). In this case study, two sprayers, a self-propelled sprayer (Spr1) and a tractor-pulled sprayer (Spr2), each with different machine properties were compared to study the effect of their properties on the optimized route.

Fig. 16
figure 16

Arable field located in the province of Cherkassy, Ukraine. (Source Google™ Earth, extracted in April 2010, ©Google Inc.)

Full size image

The properties of Spr1 are: Width = 27 m, Capacity = 2 m3 (effective capacity), Turning_radius of 5 m, Vel straight  = 12 km h−1, Vel turn  = 7 km h−1, and T Serv  = 10 min.

The properties of Spr2 are: Width = 40 m, Capacity = 5 m3 (effective capacity), Turning_radius of 6 m, Vel straight  = 10 km h−1, Vel turn  = 6 km h−1, and T Serv  = 15 min. For both sprayers, the Rate was 120 dm3 ha−1.

Spr1 can be operated at higher speed than Spr2, but owing to their difference in width, they have identical productivity when expressed in area per hour.

Because of the large width of the sprayers, almost no skipping of tracks occurred; most of the turns were between adjacent nodes.

Depending on the orientation, Spr1 needed between 23 and 30 servicing stops; the optimized route of Fig. 17a has 23 stops. Spr2 needed either 9 or 10 servicing stops. In the latter case, the optimum orientation of tracks was not exactly parallel to the longest edge of the field because otherwise one more stop would be required which would increase the total non-working time.

Fig. 17
figure 17

Optimized routes found for the case study for two sprayers, a Spr1 and b Spr2

Full size image

Servicing accounted for 87.6 and 82 % of the total non-working time for Spr1 and Spr2, respectively.

Figure 18 shows the non-working time spent for both sprayers for different orientations of the tracks. The minimum non-working times for Spr1 and Spr2 were 262.57 and 164.54 min, respectively.

Fig. 18
figure 18

Non-working time found for each sprayer for different angles tried (90° is the exact north)

Full size image

In Fig. 18, the large capacity of Spr2 led to a significant increase in the efficiency of the machine and to render it more suitable for this field. The non-working times amounted to 84.15 min for Spr1 and 47.37 min for Spr2. For Spr1, working parallel to the longest field border would require 64.51 additional minutes of servicing when compared to the optimized route. The difference in time between Spr1 and Spr2 in their optimized routes is 98 min.

The comparison shows that the approach can be used for selecting suitable machinery for operations given field geometry and economic factors such as fixed and variable costs.

Figures 13 and 18 give the reduction in non-working time for the directions of work tried. Choice of orientation for establishment of crops are not always related to operational issues (like sowing in direction north–south to improve solar interception by the crop) and the impact of such a decision can be determined from these figures. Also comparing the graphs between different operations in one field allows the choice of an optimized route to be followed in row-crops (crops where the machine must follow the rows since planting such as potatoes or corn).

Conclusion

A method was presented for route planning to design a complete geometrical route that minimizes the time spent on two non-working procedures: turning and servicing. The algorithm was illustrated using six case studies on fields having different geometry and considering different operations. Alternatively other optimization criteria (such as energy consumption) could have been considered.

The algorithm is capable of creating routes in fields of different shapes and sizes, also taking into consideration the presence of obstacles in the field. The simplifying assumptions of the demonstrated applications included:

  1. 1.

    A predetermined starting point for field operations has to be selected;

  2. 2.

    Field operations are performed in straight parallel tracks;

  3. 3.

    The examples considered a single field operation.

The algorithm creates unique maneuvers, allowing these to consider the relation between the direction of work and the border of the field. This improvement allowed development of routes in fields with more irregularities or with working directions that are not perpendicular to the border, which was a limitation in previous works.

In these case studies, the direction of work that retrieves lowest turning time is not the same that retrieves the lowest servicing time. Ignoring one of the issues in determining a path/route may lead to excessive turns or servicing stops.

The algorithm was capable of optimizing a route over fields with widely different geometries and for different operations. One example application also demonstrated that the method can be used for selecting machinery based on their properties and the geometry of fields.

The algorithm has several limitations: it only considers a single working direction, it assumes straight parallel tracks (no curved paths), trafficability of the soil is not taken into account and so far only two types of turns were implemented. Additionally, methods chosen for servicing are not yet in full accordance with reality. Servicing locations are usually not available around the whole field, thus requiring an adaptation of the driving direction to reach the servicing spots. In general, the machine has to move from a node to a near servicing spot which requires additional time that was not considered in this paper. Large fields can also have roads inside that can be crossed as if they are part of the field. These roads should be inserted and interpreted by the algorithm to achieve this purpose. A more developed work considering the movements of a machine outside the field would increase the impact of servicing.

Nevertheless, the algorithm already provides an idea of the impact of servicing time in relation to the maneuvering time, suggesting that the first should indeed be taken into consideration. Some examples showed that optimized routes to use the capacity of the machine more efficiently do not always have the suggested route for maneuver savings. This is also true for operations in small fields like in the in-soil manure injection case study where the servicing had higher impact on the definition of the optimal route.