In agricultural capacitated field operations, i.e. operations where material is transported into the field (e.g. seeding, spraying and fertilizing) or out of the field (harvest), a number of routes are needed for a primary unit to cover the entire field due to its capacity constraint. Hence, the operation of a primary unit must be carefully planned to improve the field operation efficiency. In this paper, an approach for the generation of optimal optimized route to be followed by primary units aimed at reducing the travelled nonworking distance is presented. The presented approach consists of two stages. The first stage is about the field geometrical representation where the field is split into parts; the headland area in which the machines can make turns, and field body that is the main cropping area. In geometrical sense, both of them are expressed as a geometrical map using geometrical primitives, such as point, line segment, and polygon. The field body is covered by a set of parallel straight field-work tracks that has two intersections with the field boundary. The second stage is to find the optimal route which is formulated as a capacitated vehicle routing problem (CVRP). It was solved by implementing the ant colony algorithm combined with the Clarke-Wright savings algorithm. A case study is presented based on two fields; the results show that, by using the optimum routing generated, the non-working distance can be reduced in the range of 47.02% - 49.76 %compared with the conventional work pattern.
Agricultural capacitated operations are field operations that either bring material into the field, such as spraying, planting, and fertilizing, or remove material from the field, such as harvesting. Normally, the machines used for capacitated operations do not have storage capacity for all the material to be brought in to or out from the field, thus the operations involve multiple, co-operating machines. According to the terminology proposed by Bochtis and Sørensen (2009; 2010) , cooperative field operations are executed by one or more primary units (PUs) executing the main task and one or more units (SUs) servicing the PUs. Due to the capacity constrain, the PU usually requires several routes, i.e. detours from the field body in order to refill or empty the tank, to fully cover the whole field. Each route consists of three parts, refilling, resuming, and applying in the case of material input operations and emptying, resuming and applying in the case of material output operations. Hence, the operation of a primary unit must be carefully planned to improve the field operation efficiency.
A large amount of papers have been reported for the planning of PUs. These
works mainly has focused on two reseedgeh aspects: field geometrical representation
and planning within the geometrical representation. The field geometrical
representation involves the generation of two types of geometrical entities: field
tracks and headland passes using the geometrical primitives (e.g. points, lines, etc.).
A number of methods to deal with this problem has been introduced and developed
recently
The vehicle routing problem (VRP) is a well-known combinatorial problem, which has been widely used in the industrial sector. Recently, the VRP has been implemented for the planning of infield operations. Bochtis (2008) showed the potential of using VRP for single or multiple machinery systems. Alia et al. (2009) proposed a combination of VRP and minimum cost network flow problem aiming to find the optimal routes for harvesters.
In this paper, a method was developed for capacitated machines, which consists of two stages; the first stage is about the field geometrical representation where the field is split into parts, the headland area in which the machines can make turns, and field body that is the main cropping area. The second stage is to find the optimal route which is formulated as capacitated vehicle routing problem (CVRP). It was solved by implementing the ant colony algorithm combined with the Clarke-Wright savings algorithm. 2
2.1
Assumption • • • •
Only fields without obstacles are considered, and the field is assumed two-dimensional (flat)
2.2
Overview
The presented approach is divided into two stages. The first stage regards geometrical field representation, where a field represented by geometrical primitives: such as points, lines and polygons that can be used for operational planning and the specific of the method of generation of geometrical field representation is described in section 1.3. In the second stage, the route planning is formulated as vehicle routing problem (VRP) with the goal to minimize the travelled distance. The details of VRP formulation is shown in section 1.4. A diagram description of the proposed approach is given in the Fig.1.
The input consists of the set of the coordinates of the field boundary, the operating width of the implement w , the number of headland passes n and the driving directionθ . In the following, this method is introduced in detail. Headland generation
The field headland area is created by offsetting the boundary inwardly a certain width that equals to the multiplication of the operating width, w times the number of headland passes n . The distance from the field boundaries to the first headland pass is half of the operating width, w / 2 while the distance between subsequent passes of headland equals to the operating width w . An inner boundary is created at distance w / 2 from the last headland pass. Fig.2.a shows the headland generation with 2 headland passes.
A set of straight tracks parallel to the driving direction θ covering the field body is generated. Each individual track is represented by two end points that are located on the inner field boundary. The distance between subsequent tracks is equal to the operating width w . Let T = {1,2,3...n'} be the ordered set of the tracks. An illustrative example of the generated tracks is shown in Fig. 2.b.
a b Fig.2. Field geometrical representation: (a) headland generation; (b) track generation. 2.4
Second stage: Vehicle routing problem Casting agricultural field operation into vehicle routing problem
As mentioned before, the field route planning can be casted as a vehicle routing problem (VRP) which is a well-known combinatorial optimization problem. The VRP consists of determining a set of routes with minimum distance for vehicles starting and ending at a single depot and satisfying the demand of the customers with the constraints that each customer is served exactly once, and the total demands of the customers in each route do not exceed the capacity of the vehicle. Mathematically, it can be formulated as a weighted graph G = (V , E) , where V = {0,1,2,..., n} is the set of nodes and
E is the set of edges in the graph. The depot is denoted as vertex 0; the remaining node set V \ {0} is denoted as the customers. For each edge (i, j) ∈ E, i ≠ j , a non-negative cost d ij is assigned, representing the transit cost. Each customer i ∈V , i = 1,2,..., n is associated with a non-negative q demand i . A fleet of identical vehicles is available at the depot, each with capacity Q . Let F = { f1, f 2 ,...} be the fleet of vehicles. The objective of the VRP is to find a set of minimum cost routes to serve all the customers satisfying following constraints: (i) each customer is visited exactly once by exactly one vehicle, (ii) all routes start and end at the depot, (iii) for each vehicle route, the total demand does not exceed the vehicle capacity Q .
In the geometrical field representation, each track is represented by two ending points. The nodes of the VRP correspond to these ends of tracks. The demand of a node is set as half of corresponding total demand of a track. For material input operation as well as the material output operation, the demand of a node represents the quantity of material that need to be distributed or picked up from the field area.
Edge cost assignment
There are three types of edges between each pair of the nodes, namely: edges connecting RU and track ends, edges connecting pairs of nodes that represent two ends of two respective tracks, called headland turnings. And the edge cost for connecting both ends at same track
For the first type of edge, the edge cost is the travelled distance between track ends and depot along the headland path. In the case where two nodes represent the two ends of one track, the connection between these two nodes has to be enforced. In other words, once a vehicle selects one end as the track entry, the vehicle has to finish the operation on the current track, namely exits at the opposite end of the current track before moving to another track. Therefore, for these nodes, the edge cost is set as zero. While the edge cost of the third type is determined by the distance corresponding the headland turning travelled by the vehicle from the exit point of current track to the entry point of the next selected track. To meet practices, when the tractor drives from one track to another it drives along one of the headlands paths, which headland path can be specified in the algorithm. From each end of a track it is usually possible to turn either left or right to exit the track, then along the headland pass to enter the next track. The distance for travelling from one track to another is calculated as the turn distance to exit the track plus the distance along the headland plus the turn to enter the next track. Fig. 3 shows the edge connection.
The VRP belongs to the class of NP-hard problems, as the size of the problem increases, it turns out be harder and harder to obtain an exact solution in a reasonable time. Recently, the focus of research towards this problem was on using metaheuristics, such as Tabu research, Genetic research, and ant colony system.
In this paper, we focus on ant colony algorithm (ACO) to solve the VRP, which is a mathematical model of ants behavior in finding the shortest route between colonies and food. The principle is based on that every ant deposits the pheromone on the passed path. However, the pheromone starts to evaporate over time, thus reducing its attractive strength. A short route is passed frequently by ants, and thus the pheromone density on shorter paths is higher than longer ones’, consequently, the shortest route has the highest pheromone density (Dorigo, 1996).
. It mainly consists of three steps in each iteration: • • •
Construction of vehicle routes by ants based on the pheromone information; Application of local research to improve the routes;
Pheromone information update.
Construction of vehicle routes
The way of ant constructing the vehicle routes is as follows: firstly, all the artificial ants are placed at the depot, then successively choose the customer to visit, until all the customers have been visited, whenever the selection of the next customer violates the rule that total demand of current visited customer exceed the vehicle capacity, then a new route will be started from the depot again. At each construction step, an ant k at current node i to choose the next city j from a feasible set of customers according to Eq.1: pij = [τ ij ]α [η ij ]β [µ ij ]
γ λ∈Ω ∑[τ iλ ]α [η iλ ]β [µ iλ ] γ , if j ∈ Ω
, τ íj Where Ω = { j ∈V \ visited nodes} , denotes the pheromone concentration on the edge (i, j) , which is used to describe how good was the selection of customer j in previous iterations ,η íj representing how promising is the selection of customer j from current customer i , and µ ij is the savings of combining two customers i and customer j on one route against visiting them on separate routes.
Specifically, for calculation the savings for each pair of nodes, the following rule is used.
a b
After the ants have constructed their respective routes, each ant’s routes are improved by a local search. In this paper, the 2-opt heuristic was used. The 2-opt algorithm iteratively modifies the current generated route by removing two edges then two new edges used to reconnect the route until no further improvements are possible. Details of the 2-opt can be found in CROES (1958). Pheromone update
After the solution construction by all the ants, the pheromone trails are updated according to solutions found by the ants. Here the rank based scheme proposed in Bullnheimer et al. (1998) is used, in which only the best ranked ants (also called elitist ants) are used to update the pheromone trails where the rank is according to the solution quality. The pheromone updated is done as follows:
σ −1 τ ´new = ρτ old + ∑ Δτ iaj +σ Δτ i*j , ij ij
Where ρ is the trail persistence ( 0 < ρ < 1), thus the trail evaporation is given by1 − ρ . There are two types of pheromone trails that are deposited. First, the best solution found is updated as if σ ants had visited it. The quantity of pheromone
* * deposited by the elitists is Δτ i*j = 1/ L , where L the objective value of the best solution found so far is. Second, the only the σ − 1 best ants are allowed to deposit pheromone on the edge they has traversed, the quantity of pheromone deposited by k theses ants depends on their rank k and the solution quality L . For instance, the kth best ant deposits Δτ ikj = (σ − k ) / Lk . However, edges that do not belong to those solutions evaporate their pheromone at the rate (1 − ρ ) . 3
The case study was based on two fields (referred as to field A, B in Fig.5) located in research Centre Foulum. Denmark. The field A has an area of 3.3 ha, while field B has an area of 4.1 ha. The operations involved are slurry applications which consist of an application unit (AU) with tank size of 30 m3 and a stationary refilling unit (RU) with tank size of 45 m3. The application rate for the distribution of Nitrogen is 0.0043 m3/m2, the operating width of the AU is 9 m and the turning radius is 6 m. For both fields, the number of the headland passes is set to be 2. In order to investigate the benefits of the optimized route by the model, the conventional strategy as described by Dionysis (2009) is used. For finding the shortest connection distance of blocks, parameters of the ACO algorithm were set as： ρ = 0.5 ,α = 1, β = 5 and σ = 6 , and the number of iteration was 300. The number of the ants used was equals to the number of the nodes (track endings).
The optimized route generated by the developed method for field A is RU-> 27-> 28-> 24-> 23-> 19-> 20-> 16-> 15-> RU-> 11-> 12-> 8-> 7-> 3-> 4-> 2-> 1-> 5-> 6> 10-> 9-> 13-> 14-> 18-> 17-> RU->21-> 22-> 26-> 25-> 29 ->30. The total nonworking distance (including the turning, transport distance) is 662.4 m, while when using the conventional coverage strategy, the total non-working distance is 1250.4 m. 30 28 26 24 22 20 18 16 14 12 10 8 6 4 2 29 27 25 23 21 19 17 15 13 11 9 7 5 3 1
RU
The optimized route generated by the developed method for field A is RU-> 1 -> 2 -> 6 -> 5-> 9-> 10 -> 14-> 13-> RU-> 17-> 18-> 22-> 21-> 25-> 26-> 24-> 23 -> 19-> 20-> 16 -> 15 -> RU-> 11->12-> 8 ->7-> 3->4. The total nonworking distance (including the turning, transport distance) is 500.43 m, while when using the conventional coverage strategy, the total non-working distance is 996 m. 26 24 22 20 18 16 14 12 10 8 6 4 2 25 23 21 19 17 15 13 11 9 7 5 3 1
RU
In capacitated operation, a number of routes are required for a primary unit to cover a normal size field. In this paper, an approach for the generation of optimal route for primary units aimed at reducing the non-working distance travelled is presented. The proposed approach consists of two stages, the first stage is field geometrical representation, and the second stage is to find the optimal route which is formulated as capacitated vehicle routing problem (VRP). The VRP problem is solved by ant colony algorithm.
To demonstrate the developed method, two fields were used for case study. The results show that the developed method can provide optimized solution in terms of non-working distance, subsequently non-productive time. The reduced non-working distance can reach 47.02%, 49.76 % in field A, field B, respectively.