Résumé
Precision agriculture generally requires collecting data through regular sampling or sensor maintenance in the field. Managing technicians who perform these tasks becomes very complex when the number of plots increases.This research was motivated by a real problem of technician scheduling. Fruition Sciences is an information technology company that provides data driven web applications to enable grapegrowers to optimize grape quality and yield. The data come from various sources, including connected sap flow sensors that measure the wine transpiration in order to compute a water deficit index. The company employs several technicians to deploy and maintain such sensors. The technicians also perform regular samplings, routine maintenance and troubleshooting over a typical working day. With the company’s growth over the years, technician scheduling is becoming more and more complex and can benefit from constrained optimization techniques.One of the main challenges of this project was to help the company to clearly identify the optimization problem to solve. Fruition Sciences proposes several kinds of sampling operations that depend on the needs of the enduser. The regularity of a sampling is essential and can have different frequencies (daily, weekly, monthly). One part of the samples must be brought to the laboratory for analyses. Depending on the season, different analyses are performed thanks to different sensors. Technicians have to install and maintain sensors in the vineyards during the period. Because sensors wrap the vine, technicians must regularly inspect sensors to respect the growth of the plant. Also, technicians must prevent and repair faulty sensors and solve troubleshooting. Of course, the planning of technicians must respect the working time constraints like working hours, holidays, weekend, predawn work, etc. Hence, the Technician Scheduling Problem consists in finding a planning of technicians that satisfies all constraints, optimizes the frequency of operations and minimizes the travel time of all technicians.The problem was originally identified as a scheduling problem but during the study it also appeared close to a Vehicle Routing Problem (VRP) (Cortès et al. 2014). First proposed by Dantzig and Ramsey in 1959, the VRP consists in seeking a number of customers with a fleet of vehicles. Several variants of VRP exist, like VRP with time-window, VRP with precedence constraint, or VRP with pickup delivery.We propose a preliminary approach to solve the issue of the scheduling problem. It is based on Constraint Programming (CP), which is a powerful technique to solve combinatorial problems (Rossi et al. 2006). Constraint Programming uses tree search algorithms and branching strategies to decide if a problem has feasible solutions or not.One benefit of constraint programming is its expressiveness that allows a high level of abstraction. In constraint programming, each problem is defined by a set of variables and constraints on these variables. Domains are associated to variables: each value in that domain represents a possible value for the variable. Constraints on two or more variables are stated in a natural way to formulate the given problem and restrict the combinations of values for these variables. A Constraint Optimization Problem (COP) is a problem where one has to find a value for each variable satisfying the set of constraints and to optimize an objective function. A constraint solver can be used to find an optimal solution of the problem. Thanks to the flexibility of CP models, we can consider the addition of extra user-constraints in a simple way.The second main advantage of constraint programming is due to the efficiency of Constraint solvers (Rossi et al. 2006). They are based on the notion of “constraint propagation”. Constraint propagation takes into account the current state of the search tree, that is, variables already instantiated to values, and deletes infeasible values according to the constraints. Constraint propagation can drastically reduce the search effort. For each kind of constraints, specialized and powerful algorithms have been developed to perform propagation efficiently.One of the major issues of the project was to formalize the business rules of the Technician Scheduling Problem. We build a mathematical model of the problem in order to clarify these rules. However, the problem is quite complex and requires validating the rules on real data. Hence, we developed a preliminary COP model using the java library Choco (Prud’homme et al. 2014). The complexity of the problem grows with the number of vineyards, the number of operations and the number of technicians. Our method has been tested on two real instances. A first set of instances located around Paso Robles, California with 15 plots, 4 operations and 2 technicians and a more complex set of instances with almost 200 plots, 5 operations and 4 technicians, in Napa valley, California. Preliminary results shown the technical and economic value of handling such problems with constraint programming. On first instances, optimal solutions are found in seconds. On complex instances, an optimal solution is not found before a cutoff of 5 hours. However, the Solver produces incrementally better-cost solutions, which satisfy all the constraints of the problem.Thanks to our preliminary COP implementation of the problem, Fruition Sciences will be able to clarify and adapt the scheduling rules. This is a necessary step before a relevant and efficient solver could be developed for this problem. A promising perspective would be to use a Large Neighborhood Search approach that gives good results on complex routing problems (Di Gasparo et al. 2016). It combines the efficiency of Local Search with the expressiveness of Constraint Programming.