Agriculture fleet vehicle routing: A decentralised and dynamic problem

3.1. Motivation and background

Planning and scheduling of different stages of cultivation for each crop are based on agri-food production goals and agronomic needs. These are typically determined by tables for “technical itineraries”, which describe the entire cycle of crop cultivation processes throughout the year. For example, for the cultivation of maize in Spain, the scheduling of tasks is: deep ploughing in January; stone removal in February and March; harrowing, seeding and fertilisation, fertilising inserting, irrigation system, maintaining herbicide application in April and May; preseeding irrigation, and seeding and soil disinfection in June, etc. [75]. Technical itinerary tables also include scheduling of labourers for each month, required equipment and labour (driver/labourer), yield in hours per hectare of equipment and labour, and raw material (units per hectare).

In this paper, we focus on a scenario where multiple farmers and/or large agriculture conglomerates grow multiple crops with distinct cultivation needs simultaneously while sharing the same agriculture resources (e.g., implements and supply of raw materials such as pesticides, herbicides or chemicals) and a fleet of heterogeneous vehicles (tractors and/or AMRs). Each one of these crops requires tasks that need specific equipment for their implementation, usually a certain type of a tractor and a compatible implement with specific characteristics. For example, for deep ploughing, we need a tractor and a chisel; for stone removing, a tractor and a trailer. Further, some tasks may only be compatible within certain weather conditions while some tasks may be more important than others.

Each task requires a vehicle-implement-raw material combination:

Vehicle (tractor or AMR) parameters include: maintenance and cleaning frequency, operational state, task compatibility and compatibility with implements and related requirements (e.g. power, weight, front power take-off (PTO) used for taking power from a power source, guidance system or not, front loader, specific tires, etc.), driver requirements, fuel autonomy, and type and number of operators needed for operation per each task.

3.2. Description of the AF-VRP

For simplicity and without loss of generality, let us assume that mutually connected farming fields in a region of interest are positioned in the plane E = [ 0 , ℓ ] 2 ⊂ R 2 of side length ℓ > 0 , Fig. 1. We also assume that there is a permanent transport network in the region of interest through which each field can be reached and a temporary transport network in each field composed of narrow and long “aisles” (tractor lines) whose structure and topology is a function of the crop that is grown in the field (Fig. 1). In the latter network, the distance travelled crossing from aisle to another is negligible compared to the distance travelled lengthwise, along an aisle. This setting is similar to conventional multiple parallel aisle warehouse systems.

Formally, we define the problem elements as follows. Figure 2 provides an overview of the sets, indices, parameters and decision variables used.

OPEN IN VIEWER

Fig. 2.

Elements of the formal AF-VRP. In sets, superscripts indicate partitions, and subscripts indices.

We consider a planning time horizon T made of | T | time periods. The transportation network is represented by an undirected weighted graph G = ( N , E ) , where N = { n 1 , n 2 , … , n | N | } is a set of | N | nodes and E = ( e i , e j ) : i ≠ j is a set of edges. Both nodes and edges can be of two kinds: uncapacitated permanent nodes N ρ ⊆ N and uncapacitated permanent edges E ρ ⊆ E and temporary nodes N τ ⊆ N and temporary edges E τ ⊆ E , the latter two both with unitary capacity, where N ρ ∩ N τ = ∅ and N ρ ∪ N τ = N and E ρ ∩ E τ = ∅ and E ρ ∪ E τ = E . The topology of each subgraph representing a field with temporary nodes n ∈ N τ and temporary edges e ∈ E τ (Fig. 1) depends on the cultivated crop and the strength of the ground it represents. To be able to support the weight of a vehicle (an AMR or a tractor) with its respective implement and raw material, the ground should be strong enough. This strength depends on soil humidity, which increases after rain. Thus, cost matrix C = ( c v e t ) (e.g. in terms of travelled time) is defined for each vehicle v ∈ V and each edge e ∈ E at each period t ∈ T . It is a function of (i) the cost of fuel consumption for vehicle v, (ii) the cultivated crop and (iii) weather conditions at edge e at time period t ∈ T .

For each temporary edge e ∈ E τ , given is a set of tasks to perform K e , where K e ⊆ K , and K is a set of all tasks to perform in graph G . Each task k ∈ K e is a request for a specific vehicle-implement-raw material (VIR) configuration to walk through temporary edge e ∈ E τ .

For each task k ∈ K e associated with edge e ∈ E τ , we define a cost of the task c k e t and a related required quantity q r t k of raw material r ∈ R , where R is a set of raw materials, in units per edge, depending on time period t ∈ T . We may assume that the cost of respective raw material r for task k ∈ K at edge e ∈ E in time t ∈ T is included in the task’s cost c k e t . For simplicity, we assume that for each time period t ∈ T , this quantity is estimated depending on a weather forecast. Moreover, tasks k ∈ K e for each edge e ∈ E τ may have interdependencies, i.e. a relative order of execution, but they do not have to be necessarily performed in consecutive time periods.

Let V be a set (fleet) of vehicles v ∈ V that are initially positioned in a set of depot nodes N D ⊆ N . For simplicity, and without loss of generality, we assume that agriculture vehicles travel with constant velocity and their itinerary cannot include driving in reverse. Let I be a set of implements i ∈ I to be matched with (installed on) vehicles v ∈ V on a one-to-one basis to perform a task k ∈ K by using raw material r ∈ R . Let ξ v i t be a binary decision variable that is equal to 1 if implement i ∈ I is mounted on vehicle v at time t ∈ T ; and is equal to zero otherwise.

Both implements and the raw materials are initially stored in depot nodes n ∈ N D . For simplicity, in each time period t ∈ T , we assume that one and only one task k ∈ K can be assigned to a VIR configuration.

Each vehicle is characterised by: (i) its capacity L v for carrying raw material (it can carry multiple raw materials as long as their overall quantity does not surpass the vehicle’s capacity L v ); (ii) its implement compatibility ζ v i , where ζ v i = 1 if vehicle v ∈ V is compatible with implement i ∈ I and ζ v i = 0 otherwise (we assume that implements can only be changed at a depot node n ∈ N D ); (iii) its task compatibility γ v b , where γ v b = 1 if vehicle v ∈ V can perform task k ∈ K and γ v b = 0 otherwise; and (vi) its fuel autonomy L v in terms of the number of time periods it can run before it must return to any of the depot nodes n ∈ N D .

The vehicles can move from one node to another if and only if there is an edge e ∈ E connecting the two nodes. Contrary to the classic Vehicle Routing Problem, there is no limit on the number of visits to each task by a VIR combination. When all the assigned tasks have been completed, the vehicle should turn to one of the depot nodes n ∈ N D .

Parameters of each implement i ∈ I include: (i) maintenance and cleaning frequency L i , i.e. maximum number of periods passed in operation between two maintenance activities – the number of time periods it can run before it must return to any of the depot nodes n ∈ N D ; and (ii) task compatibility ϵ i k , where ϵ i k = 1 if implement i ∈ I is compatible with task k ∈ K and ϵ i k = 0 otherwise. To avoid disease transmission, an implement on a VIR configuration should be cleaned when changing from one field to another. This implies visiting a depot node n ∈ N D in a route between two fields.

For each vehicle, a daily task schedule should be given at the beginning of the planning time horizon in terms of a route (path) to follow (edges to visit) and the plan of tasks to do in the field on each of the edges, as well as the remounting of implements, fuel recharging and raw material (re-)loading (visits to depot nodes), when necessary.

Assuming that all the parameters of this problem are deterministic and known a priori and if we do not consider the ownership issues of the fleet and fields to be cultivated in the agriculture fleet vehicle routing, then the off-line and centralised Agriculture Fleet Vehicle Routing Problem (AF-VRP) consists of determining a feasible schedule of the execution of tasks k ∈ K by compatible VIR combinations that minimises the following general cost objective function composed of the costs of the vehicles’ routes and performed tasks: (1) z = min ∑ v ∈ V ∑ e ∈ E ∑ t ∈ T ( c v e t x v e t + ∑ k ∈ K c k e t y v k e t ) , while respecting the tasks’, vehicles’, implements’, and raw materials’ constraints. This can be done for tactical planning a priori, i.e. before the beginning of the first period of the planning time horizon T . In the centralised and off-line version of the AF-VRP problem, the plan of the best VIR combinations for task k ∈ K e is identified at the global level for all edges e ∈ E . The plan includes for each vehicle v ∈ V the route over the transport network edges e ∈ E through each period of a given time horizon t ∈ T and allocation of implement i ∈ I and raw material r ∈ R at time t ∈ T at node n ∈ N D considering the edges’ capacities and respective tasks, and individual task, implement and vehicle constraints.

However, some tasks depend strongly on the weather conditions that may change during the day, e.g. the quantity of irrigation water, pesticides, fungicides and herbicides, which leads us to consider the AF-VRP as a stochastic problem.

The AF-VRP can be viewed as a tactical decision problem which leads to a solution able to face unpredicted contingencies a priori. Similar to other versions of the vehicle routing problem (see, e.g. [62]), there is a dynamic extension of the AF-VRP, which aims at optimal online reconfiguration of the VIR configurations and their online (re-)allocation to a changing set of tasks in real time to face uncertain weather and/or technical events. In case of an unpredicted event (e.g. vehicle breakdown or an unpredicted weather event), a task may be left only partially completed. Thus, we define a non-binary decision variable u v k t e representing a portion of task k ∈ K performed by vehicle v ∈ V at time t ∈ T , where 0 ⩽ u v k t e ⩽ 1 .

Measuring the frequency of changes and the urgency of a task, the framework proposed by [33] classifies the Dynamic VRP problems into weakly, moderately and strongly dynamic problems based on the value of the effective degree of dynamism. However, this measure does not consider the geographical distribution and the travelling times between tasks [62].

The level of urgency of a task depends on the reaction time, i.e. the difference between the disclosure time of a task t k and the end of the corresponding time horizon | T | , which is proportionally related to the quality of solution obtained when introducing the task into vehicles’ routes (see, e.g. [34,62]). The computation time of a proposed solution approach is crucial for real-time effective and efficient agriculture vehicle fleet performance.

3.4. Decentralised AF-VRP

In an intrinsically decentralised context with various individually rational and competitive farmers that use a set of vehicles, implements and raw materials that are owned by one or more individually rational and competitive resource owners, fairness and envy-freeness in the allocation of VIR combinations to tasks have to be considered. Here, we are not only interested in optimising the overall system cost (equation (1)) but we also have to consider the distribution of the costs over both individual farmers and resource owners in the ecosystem. Otherwise, a solution might not be accepted by one or more decision makers. In the latter case, we have to introduce further incentives for these decision makers to behave inline with the wanted system outcome.

Equity. Criteria of equity include fairness and envy-freeness. Envy-freeness is a criterion of fair division. Both vehicle owners and farmers can be modelled as agents. In an envy-free division, every agent feels that its share is at least as good as the share of any other agent, and thus no agent feels envy.

We study the case when the VIR combinations owned by multiple owners are to be allocated to the tasks that are owned by different farmers.

Let us consider the case when farmers are modelled through a set of agents a ∈ A . Note that a task k is a request for a specific VIR configuration to walk through temporary edge e ∈ E τ (owned by some agent a ∈ A ). A VIR configuration may be allocated to every agent a in each time period t ∈ T . Each agent a has a subjective preference relation ⪰ a t over different possible VIR configurations over time based on its individual and private cost dynamics.

Let us assume that the preference of each agent a ∈ A is represented by a cost function z a . Also let X A T be allocation of VIR configurations to agents a ∈ A over time horizon T . An allocation X A T is called envy-free if for all a i , a j ∈ A , z a i ( X a i T ) ⩽ z a i ( X a j T ) . We say that an agent a i envies another agent a j if a i prefers the VIR configurations allocated to a j throughout time horizon T over its own VIR configurations allocated throughout T , i.e. if z a i ( X a i T ) > z a i ( X a j T ) . A division is called envy-free if no agent envies another agent.

Since the VIR configurations are indivisible, an envy-free allocation may not exist. Deciding whether an envy-free and complete allocation exists is NP complete. Deciding whether an envy-free and Pareto efficient allocation exists is above NP [15]. Thus, we have to resort to approximate heuristic approaches to solve this difficult problem.

Fairness in the AF-VRP in this context depends also on the choice to maximise egalitarian social welfare (i.e. minimise the worst off cost, min max a ∈ A z a ), to maximise the utilitarian social welfare (i.e. minimise the overall cost, min ∑ a ∈ A z a ) or to minimise the elitist social welfare (i.e. the best off cost, min min a ∈ A z a ) in the decentralised AF-VRP.

Unfortunately, by optimising the system based on the worst-off performance, we deteriorate the system efficiency and thus, the utilitarian welfare. From the overall system efficiency point of view, we can use utilitarian social welfare which sums up the agents’ individual utilities in a given allocation and thus gives us a measure of the overall and average benefit for the system. However, optimising the utilitarian social welfare is not acceptable in the systems whose success is based on self-concerned individually rational agents’ acceptance (see, e.g. [11]). This is because in utilitarian systems, the optimum is paid by (usually a few) worst off agents. The latter, however, might not comply with paying the price of the system optimality (see, e.g. [36]). Nash Welfare optimisation maximises the product of the agents’ utilities and results in both egalitarian and utilitarian welfare maximization (see, e.g. [43]). When applying Nash Welfare optimisation, we obtain ( min ∏ a ∈ A z a ). The resulting objective function is non-linear and we can linearise it by introducing a log operator similar to [43].

5.1. Multi-index assignment problem

The methods for dynamic AMR fleet task assignment and dynamic (re-)routing are relevant in various scenarios, such as, e.g. emergency services (e.g. [5,39,40,69]), taxi, hot meal home delivery and vehicle sharing. After a meticulous analysis of the available solutions, we have identified that the combination of these methods can provide a true differential value in the agriculture vehicle fleets.

The problem of allocation of the vehicles to implements and indivisible tasks may be modelled as a multi-index assignment problem [61] that we re-run in each time period when the constituents of the problem change. Each constituent part of this allocation is characterised by a set of attributes describing its availability and compatibility with the rest of the constituents that influence the cost or profit resulting from such a multi-index allocation. Assume there are n vehicle agents, m tasks and k implements. Here, the emphasis is on one-to-one assignment among the elements in each set. Furthermore, each vehicle agent has a valuation function that maps each implement-task combination to some non-negative value particular to that vehicle agent. These valuations are additive, which means that an agent’s value for a set of task-implement combinations is simply the sum of the values of each combination of this set. Our goal is to compute a one-to-one allocation, i.e. a partitioning of | K | tasks, | I | implements and V vehicle agents, of minimum overall cost. The mathematical formulation of such a problem leads to axial k-index assignment problems [63] and in the case of three indices (vehicles, implements and tasks), to the axial 3-index Assignment Problem (axial 3AP), which is an NP-hard binary programming problem for which the only scalable and efficient solution approach is based on (meta-)heuristics (e.g. [77]). Moreover, no polynomial-time algorithm can achieve a constant performance ratio for this problem unless P = NP [13]. Crama and Spieksma designed approximation algorithms that yield a feasible solution whose value is not worse than 3/2 of the optimal value when the overall assignment cost is a decomposable sum of the costs of all three set pairs [13].

Reynen et al. [67] present alternate integer programming formulations for the multi-dimensional assignment problem with decomposable costs with an increased number of variables and present solution methods based on Lagrangian Relaxation and massively parallel algorithms. Aiex et al. [1] designed a greedy randomised adaptive search procedure with path relinking (GRASP) for solving axial 3APs. GRASP is a multistart metaheuristic for combinatorial optimisation consisting of a construction procedure based on a greedy randomised algorithm and a local search. A parallel version appeared in [52]. Their computational experiments showed very good results compared with previously proposed heuristics. Huang and Lim [28] proposed a hybrid genetic algorithm for this problem and reported on extensive computational experiments. Li et al. [36] propose a novel convex dual approach to the three-dimensional assignment problem. It is shown that Li et al.’s dual approach is equivalent to the Lagrangian relaxation method in terms of the best value attainable by the two approaches. However, the pure dual representation is not only more elegant, but also makes the theoretical analysis of the algorithm more tractable. An asymptotically optimal approximation algorithm for axial k-index assignment problems was given by Kravtsov [31]. Frieze et al. [21] study random multi-dimensional assignment problems where the costs decompose into the sum of independent random variables. They minimise the total cost and show that with high probability a simple greedy algorithm is a ( 3 + O ( 1 ) ) -approximation. An adaptive algorithm that extends the basic greedy-type algorithmic schemes using transition to a probabilistic setup based on variables randomisation for solving the axial 3-Index AP was also proposed [49]. Here, the minimisation of an objective function is replaced by the minimisation of its expectation.

5.2. Assignment problem

The multi-index assignment problem is a higher dimensional version of the standard linear (two-dimensional) assignment problem, i.e. a weighted bipartite matching problem in which the objective is to minimise total cost of assigning n resources to n tasks. The latter is an important subproblem of many NP-hard optimisation problems, e.g. Traveling Salesperson Problem for which both sequential (Hungarian algorithm, the shortest path algorithms and auction algorithms) and parallel implementations of these algorithms are known.

In the case where sets of fixed (one-to-one) vehicle-to-implement combinations are static and given in advance, each such combination can be considered as an agent. Then, the multi-index assignment problem is simplified to the assignment problem focusing on the one agent-one task allocation at the time (e.g. [6,40]).

The dynamic task assignment problem is equivalent to the assignment problem for which several centralised approaches exist, e.g. [53]. One of the best known is the Hungarian method [32]. In [22], Lujak et al. propose a distributed version of the Hungarian Method for multi-robot task allocation where mobile robot agents are required to store all the information locally and there is no available shared memory.

One of the tools for mechanism design of agent systems are auctions, e.g. [3,41,68]. The implementation usually requires solving a combinatorial non-linear optimisation problem, which is in general NP-hard and intractable for complex networks. However, with certain relaxations, the latter can be modelled as a convex optimisation problem [3,56]. Computational optimisation auctions are methods that are similar to the Gauss-Seidel and Jacobii methods, e.g. [3]. This approach is well suited for massive parallelisation of local decision-making based on the information interchanged among multiple processors. It is modular, based on regular interactions, incremental, analysable, and permits incentive engineering. In [41,44], Lujak et al. proposed a modified version of Bertsekas’ auction algorithm for the case of incomplete information exchange and explored the deterioration of the solution quality according to the size of the communication network and proposed strategies to overcome this problem. Responding to the task assignment in the case of the medical emergency assistance of urgent out-of-hospital patients by ambulances, Lujak et al. proposed a distributed algorithm for the simultaneous assignment of ambulances [5,39] and ambulances and hospitals to multiple simultaneous patients in [40], where the authors also proposed an ambulance vehicle Voronoi-based relocation approach. Moreover, in [43], Lujak et al. proposed the route assignment approach that considers fair and envy-free routes and improves the overall efficiency in respect to the user optimum. Here, fair routes are related to the overall route cost that should be as balanced as possible between the vehicles, while envy-freeness is related to individual route costs that should not vary between each other more than some predefined factor.

Through a dynamic vehicle reassignment, we can significantly increase the overall performance of the fleet and lower farming costs. Furthermore, by dynamic routing, the fleet can divide the tasks to perform and each fleet vehicle can then respond in real time to any changes in terrain characteristics by rerouting and while doing so, maintain the region of interest well covered, so as to reach tasks quickly and efficiently. A distributed multi-agent computation model for route guidance under congestion in vehicle traffic considering envy-freeness and fairness was proposed by Lujak et al. in [42,43]. It was shown by simulation experiments that by proposing routes that are envy-free and fair, the user equilibrium traffic assignment solution can be improved towards the system optimum.

5.3. Vehicle routing problem

At the tactical level, the problem of routing a fleet of vehicles combined with implements through the execution of farming tasks in the fields may be modelled as a vehicle routing problem (VRP). VRPs are a class of combinatorial optimisation problems that consist of determining sequences of tasks for a fleet of vehicles with limited resources while minimising an objective function that is typically the total completion time or the total cost. VRPs are defined on graphs, and the tasks to be performed are associated with nodes or with arcs. When the tasks, e.g. deliveries, are associated with nodes, the corresponding problems are called node routing problems whereas when the tasks are associated with arcs, these are named arc routing problems.

The basic arc routing problem related to the AF-VRP is the Capacitated Arc Routing Problem (CARP). The CARP aims to determine a minimum cost set of routes that serve a subset of edges with positive demand under capacity constraints. For this problem introduced by Golden and Wong [24], many exact and heuristic algorithms have been proposed and are described in the book of Laporte and Corberan [12] and in the recent annotated bibliography by Mourão and Pinto [51]. The CARP is a simplified version of the AF-VRP where the edges to be traversed correspond to the aisles of the fields and the demand to the quantities of raw materials to be used. However, the AF-VRP includes several additional features that make it challenging to obtain good solutions for instances of the size encountered in practice.

When addressing an arc routing problem, it is essential to consider whether its transformation into a node routing problem presents a particular advantage or not. On the one hand, in arc routing problems, demand is associated with edges, and the graph is frequently sparse, which could represent an advantage that can be exploited in the design of solution algorithms. Lechford and Oukil [35] described an approach where they exploit the sparsity in the identification of promising routes. On the other hand, an arc routing problem can be transformed to a node routing problem (see, e.g. Pearn et al. [58] or Longo et al. [37]) for which many efficient algorithms have been proposed (e.g. [50,54,72,80,81]).

When there is only one vehicle, node routing problems reduce to variants of the classical Traveling Salesperson Problem (TSP). Among them, some are relevant since they include some key features of the AF-VRP. In this paper, we focus on narrow and long aisle farming fields, in which the distance travelled across from aisle to another is negligible compared to the distance travelled along the length of the aisle. This setting is similar to conventional multiple parallel-aisle warehouse systems. The Steiner TSP (STSP) is an extension of the TSP that is suitable for these instances. Given a list of locations, some of which are required, and the distances between them, the goal is to find the shortest possible walk that visits each required location and then returns to the origin. As we are looking for a walk, vertices can be visited more than once, and edges may be traversed more than once. Exact approaches to this problem only exist for warehouses that have at most three cross aisles. For other layout types, various heuristic approaches exist, e.g. [78].

The TSP considers minimising the overall travel time of a salesperson but if we concentrate on minimising the waiting times of the tasks, then we speak about the Travelling Repairman Problem [18]. Luo et al. [47] extend the multiple Travelling Repairman Problem (m-TRP) by considering a limitation on the total distance that a vehicle can travel. The resulting problem is called the Multiple Travelling Repairmen Problem with Distance constraints (MTRPD). The authors design a tailored branch-and-price-and-cut algorithm for this problem proposing a bounded bi-directional label-setting algorithm for the pricing subproblem. The m-TRP has characteristics in common with the problem we have to solve for the management of an agricultural fleet.

Another node routing problem related to the AF-VRP is the Field Service Routing Problem (FSRP). Given a limited number of technicians, the FSRP consists of determining a set of optimal technician routes to serve customer requests, while ensuring that each technician has the required skills for his/her tasks. There is an analogy between the technicians and the vehicles, implements and raw materials we present here. The most relevant variant was introduced by Kovacs et al. [30] where teams of technicians have to be built for some time period to complete most of the tasks. Several other extensions have been considered, including stochastic travel and service time and priorities between the tasks (see, e.g. [7]).