# Conception de systèmes de verger-maraîcher à l'aide de la programmation mathématique

Sara Maqrot, Simon de Givry, Marc Tchamitchian, Gauthier Quesnel

► To cite this version:

Sara Maqrot, Simon de Givry, Marc Tchamitchian, Gauthier Quesnel. Conception de systèmes de verger-maraîcher à l'aide de la programmation mathématique. Revue Ouverte d'Intelligence Artificielle, 2021, 2 (1), pp.157-188. 10.5802/roia.13. hal-04918218

HAL Id: hal-04918218

https://hal.science/hal-04918218v1

Submitted on 3 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished 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_1.png" /></figure>
<figure><img src="image_2.png" /></figure>

SARA MAQROT, SIMON DE GIVRY, MARC TCHAMITCHIAN, GAUTHIER QUESNEL
Conception de systèmes de verger-maraîcher à l'aide de la programmation
mathématique

Volume 2, n° 1 (2021), p. 157-188.

<http://roia.centre-mersenne.org/item?id=ROIA_2021__2_1_157_0>

© Association pour la diffusion de la recherche francophone en intelligence artificielle et les auteurs, 2021, certains droits réservés.

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

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_4.png" /></figure>
# Conception de systèmes de verger-maraîcher à l'aide de la programmation mathématique

Sara Maqrot<sup>a</sup>, Simon de Givry<sup>a</sup>, Marc Tchamitchian<sup>b</sup>, Gauthier Quesnel<sup>a</sup>

Résumé. — Dans le cadre du développement durable et des innovations dans les systèmes agroalimentaires, les systèmes mixtes horticoles (vergers et maraîchage) visent à répondre aux enjeux actuels auxquels l'agriculture est confrontée, à savoir une diminution de la pollution des sols, une meilleure gestion des ressources (eau, énergies) et un enrichissement de la biodiversité, tout en continuant d'assurer des fonctions alimentaires. Ils combinent des productions à la fois diversifiées et relativement intensifiées, leur permettant de s'insérer en périphérie urbaine. Ces systèmes agroforestiers reposent sur un ensemble complexe d'interactions modifiant l'utilisation de la lumière, de l'eau et des nutriments. La conception d'un tel système doit donc optimiser l'utilisation de ces ressources en maximisant les interactions positives (facilitations) et en minimisant celles négatives (compétitions). Nous définissons le problème de verger-maraîcher comme un problème d'allocation des arbres et des cultures dans les dimensions spatio-temporelles. Nous proposons deux formulations mathématiques : un modèle quadratique en variables binaires (BQP) et un modèle linéaire en variables mixtes (MILP), obtenant des premiers résultats sur des instances de taille réaliste. Les modèles de l'article sont disponibles ici : https://miat.inrae.fr/degivry/ROIA21.zip.

Mots-clés. — Systèmes d'aide à la décision, agroécologie, problème d'allocation spatio-temporelle de cultures, optimisation combinatoire, programmation mathématique.

## 1. INTRODUCTION

Aujourd'hui, l'agriculture est confrontée à plusieurs problèmes agronomiques, environnementaux et socio-économiques, comme le changement climatique, l'utilisation massive des ressources (eau, énergie) et la nécessité de nourrir une population grandissante. Malheureusement, beaucoup de stratégies visant à améliorer la productivité favorisent l'émergence des problèmes environnementaux comme l'utilisation d'intrants chimiques dans les systèmes de culture intensifs qui contribue au dérèglement

<footnote><sup>a</sup> UR 875 MIAT, Université de Toulouse, INRAE, Castanet-Tolosan, France
*E-mail*: sara.maqrot@onera.fr, simon.de-givry@inrae.fr, gauthier.quesnel@inrae.fr</footnote>

<footnote><sup>b</sup> UR 767 Ecodéveloppement, INRAE, Avignon, France
*E-mail*: marc.tchamitchian@inrae.fr.</footnote>
des écosystèmes. L'agroécologie se présente aujourd'hui comme une voie de transformation possible pour l'agriculture en s'appuyant sur des fonctions écologiques pour remplacer les intrants de synthèse. Dans ce cadre, l'agroforesterie et les systèmes de verger-maraîcher associant arbres fruitiers et cultures maraîchères sur la même parcelle semble une pratique intéressante pour répondre à ces enjeux. En effet, cette association permet de produire d'une manière intensive et écologique avec une meilleure exploitation des ressources naturelles disponibles. De plus, elle offre une biodiversité permettant les régulations naturelles des maladies et des ravageurs.

Le verger-maraîcher était une pratique courante traditionnelle en zone méditerranéenne en Europe jusqu'au milieu du xxᵉ siècle [12, 20, 30]. Elle a été délaissée progressivement en raison de la spécialisation, de l'intensification et de la mécanisation des parcelles agricoles pour répondre à de forts besoins productifs [17]. Aujourd'hui, la rentabilité économique n'est plus le seul critère d'évaluation des systèmes agricoles. Les impacts environnementaux liés à l'utilisation massive d'engrais chimiques et de pesticides de synthèse ont conduit à la recherche de nouvelles voies menant à une agriculture plus durable, tant dans les régions tempérées que tropicales [36]. Dans cette optique, le concept de verger-maraîcher est remis à l'étude pour optimiser les bienfaits des interactions naturelles entre arbres et cultures (voir Figure 1.1).

<figure><img src="image_5.png" /><figcaption>FIGURE 1.1. Apports de l'arbre en milieu agricole. Source : Association Française d'Agroforesterie (http://www.agroforesterie.fr/definition-agroforesterie.php)</figcaption></figure>
Un projet de système innovant de verger-maraîcher débute généralement par une phase de conception préliminaire à son implantation. Cette phase est à la fois complexe et déterminante : complexe car il faut prendre en compte de nombreuses interactions biologiques, pas toujours très connues, mais avec des objectifs et des contraintes économiques ou sociales (charge de travail par exemple), déterminante car certains choix, notamment d'implantation des arbres, verront leurs conséquences se développer tout au long de la durée de vie du système. L'objectif de ce travail est donc de proposer des modèles de conception des systèmes de verger-maraîcher qui tirent bénéfice des associations d'arbres et de cultures maraîchères en optimisant les interactions qui les composent et en tenant compte de leurs évolutions dans l'espace et dans le temps.

Les prochaines sections présentent les concepts généraux nécessaires pour la conception d'un système de verger-maraîcher. Dans un premier temps, nous présentons les propriétés des systèmes agroforestiers, à savoir les interactions aériennes et souter-raines entre arbres et cultures, l'organisation du travail et la rotation des cultures. Dans un second temps, nous discutons les méthodes de recherche opérationnelle utilisées pour la conception des systèmes agricoles. Par la suite, nous formulerons la modélisation mathématique du problème de conception d'un système de verger-maraîcher (Section 2) et présenterons des résultats expérimentaux (Section 3).

## 1.1. INTERACTIONS ÉCOLOGIQUES ENTRE ARBRES ET CULTURES

L'objectif de l'agroforesterie est d'exploiter des processus de facilitation (au sens écologique) entre les deux types de production (arbres et cultures). Cela se réalise par une meilleure utilisation des ressources disponibles (e.g. eau et nutriments). En effet, deux espèces voisines peuvent s'influencer mutuellement soit positivement (facilitation, mutualisme), soit négativement (compétition, inhibition) ou les deux simultanément [10]. Ces interactions écologiques peuvent avoir des impacts majeurs sur le comportement global du système, mais il est souvent difficile de déterminer les influences relatives à chaque interaction [31]. Donc, pour tirer le maximum d'avantages (durabilité écologique) de cette association agroforestière, il est nécessaire d'optimiser ces interactions de manière à ce que les interactions positives l'emportent sur les interactions négatives.

Une interaction écologique fait référence à l'impact majeur d'une espèce sur une autre ou sur le même type d'espèce [5]. En général, il existe trois types d'interactions : neutre (0), positive (+) et négative (-). Si l'interaction est positive, il s'agit d'une complémentarité entre espèces. En revanche, si l'interaction est négative, elle devient compétitive. Ces interactions peuvent évoluer au cours du temps, en passant d'un système complémentaire à un système compétitif ou l'inverse. Généralement, en agroforesterie, les arbres ont une influence majeure sur les cultures. Ils déterminent l'ampleur des interactions grâce à l'évolution continue de leurs systèmes racinaires et à la variation de leur potentiel d'interception du rayonnement solaire. Dans cette optique, les interactions entre arbres et cultures dans un système agroforestier peuvent être classées en deux échelles : les interactions aériennes et les interactions souter-raines (Figure 1.2).
<figure><img src="image_6.png" /><figcaption>FIGURE 1.2. Influences positives et négatives des arbres sur les cultures. Les impacts négatifs sont écrits en italique [34].</figcaption></figure>

## 1.2. INTERACTIONS AÉRIENNES

La présence des arbres dans les systèmes agroforestiers contribue à la modification des conditions microclimatiques. Par exemple, la diminution du rayonnement solaire sous les arbres protège les cultures sciaphiles (qui aiment l'ombre) et aide à réduire le stress thermique [18], en particulier pendant les saisons chaudes. Toutefois, un niveau d'ombre élevé des arbres peut réduire la photosynthèse des cultures associées. Autrement dit, l'ombre modifie la composition et surtout l'intensité du rayonnement photosynthétiquement actif reçu par les cultures et par conséquent modifie la production de biomasse [44]. Ce niveau varie au cours de l'année et de chaque journée. Les jours ensoleillés de l'été présentent une variation journalière marquée de l'interception de la lumière par les arbres. Cette variation est considérablement réduite dans les autres saisons vu que les arbres perdent leurs feuilles [45].

Les arbres servent également de brise-vent, ils permettent de ralentir le mouvement de l'air et de réduire le stress d'évaporation [13]. Cependant, à cause d'une humidité et d'une hygrométrie accrues, ils peuvent favoriser le développement des maladies et des ravageurs (notamment mollusques) [25]. Inversement, ils peuvent abriter une faune (oiseaux, insectes) capable de freiner la propagation de certaines épidémies et l'invasion de parasites [18]. Une synthèse d'un ensemble d'études sur le rôle de la diversité des cultures dans l'amélioration de la biodiversité et la lutte contre les ravageurs révèle la difficulté d'identifier les associations de cultures bénéfiques de celles nuisibles [51].
## 1.3. INTERACTIONS SOUTERRAINES

Dans les systèmes agroforestiers, les arbres jouent un rôle primordial dans la structure du sol. Ils ont globalement des systèmes racinaires profonds qui impactent les conditions subies par les racines des cultures associées, notamment l'exploitation des ressources en eau et en nutriments. Généralement, la compétition pour ces ressources se produit lorsque les systèmes racinaires des espèces associées occupent les mêmes couches du sol [43]. Dans leur revue [33], les auteurs expliquent que malgré la difficulté de déterminer quel genre de compétition souterraine (l'eau ou nutriments) limite la production, la compétition la plus fréquente dans la zone tempérée est celle pour l'eau en saison estivale. Cette compétition prépondérante peut engendrer une concurrence pour les éléments nutritifs.

L'effet positif des arbres dans les interactions souterraines est aussi important. Grâce à leur durée de vie plus longue, les systèmes racinaires des arbres se développent latéralement et verticalement d'une manière hétérogène en cherchant les zones riches en eau et en nutriments [43]. Dans les premières années de leur plantation, les arbres fruitiers ont besoin de plus de nutriments pour s'établir, contrairement aux arbres de bois d'œuvre qui sont plus résilients et qui peuvent décaler leur absorption de nutriments [21]. Il s'agit donc d'une saison où les arbres sont plus en compétition avec les cultures associées ayant les mêmes besoins en ressources.

## 1.4. PRODUCTIVITÉ DES SYSTÈMES AGROFORESTIERS

Les principaux avantages productifs des systèmes agroforestiers sont liés à une meilleure utilisation de l'espace et des ressources naturelles. La productivité d'un tel système dépend du type des arbres et de leurs rythmes de croissances qui sont différents de ceux des cultures. Généralement, l'espace associé aux cultures dans la parcelle est diminué avec la croissance des arbres, ce qui engendre une diminution de leur rendement. Les systèmes agroforestiers sont donc conçus pour optimiser l'utilisation des ressources dans le temps (rythmes de croissance des arbres et cultures) et dans l'espace (e.g. évolution des racines et de l'ombre) en maximisant les interactions positives et en minimisant celles négatives.

Dans cette optique, [18] distingue trois types de stratégies agroforestières : (i) agroforesterie stable avec une densité d'arbres faible (entre 20 et 50 arbres par hectare) où les cultures peuvent coexister en permanence avec les arbres et sur toute la surface, (ii) agroforesterie évolutives avec une plus forte densité (entre 50 et 200 arbres par hectare) où la surface cultivée diminue au cours du temps avec la croissance des arbres, et (iii) agroforesterie éphémère avec une très forte densité (au-delà de 200 arbres par hectare), où les cultures ne sont possibles que pendant les premières années.

Pour garantir une bonne productivité des cultures, il faut bien choisir une des stratégies de densité mentionnées ci-dessus et décider de positionner les arbres d'une manière dispersée ou en alignement. Il faut également choisir de planter les cultures sous les arbres ou de laisser des distances non cultivées autour de leurs troncs. Ces choix se font en fonction de la nature de production (e.g. maraîchage, cultures annuelles, production
de bois, ...), des espèces choisies, de contraintes agro-écologiques (conservation de la biodiversité, protection des animaux, ...) et de la mécanisation adoptée.

## 1.5. ORGANISATION DU TRAVAIL

La charge de travail des arbres fruitiers ne diminue pas au fil du temps à la différence d'une production de bois d'œuvre. Ces arbres devant être en permanence entretenus et les fruits récoltés [34]. Les temps de travaux et leur répartition sur l'année varient d'une espèce fruitière à l'autre, voire des variétés choisies d'une même espèce.

De la même manière, les durées d'interventions des cultures annuelles ou saisonnières sont très variables d'une exploitation et d'une culture à l'autre. Ces durées varient en fonction de l'organisation de la parcelle (regroupement ou dispersion des cultures) et des ressources disponibles (la mécanisation adoptée, la main d'œuvre et le rythme de chacun).

## 1.6. ROTATION DES CULTURES

Après le positionnement des arbres lors de la conception d'un système agroforestier, il convient de gérer la disposition des cultures diversifiées, qui ont des besoins différents en éléments nutritifs. Ainsi, laisser une culture au même endroit plusieurs années peut favoriser les adventices [16], appauvrir le sol et par conséquent affaiblir les rendements. Une solution consiste à pratiquer une succession ou rotation de cultures avec des périodes de jachère, où le sol repose après la production. La rotation de cultures offre plusieurs avantages : maintien de la fertilité du sol, assurer une production de qualité et diminution de l'utilisation des résidus de pesticides, en donnant la priorité à l'utilisation des mécanismes de régulation naturels [7,35]. Dans notre système de verger-maraîcher, les cultures ont des temps de rotation courts de quelques mois donnant la possibilité d'avoir plusieurs cycles sur la même parcelle au cours d'une même année.

## 1.7. ÉTAT DE L'ART DES MÉTHODES DE RECHERCHE OPÉRATIONNELLE POUR LA PLANIFICATION DE CULTURES

La planification de cultures est un exercice crucial pour la conception d'un système agricole rentable. La problématique de savoir quelles cultures planter, en quelle quantité et à quel moment, tout en respectant les propriétés physiques (utilisation de l'eau) et chimiques (utilisation des engrais et pesticides) du sol n'est pas facile. De nombreuses études sur la planification des cultures ont été menées pour aider les agriculteurs dans leurs décisions(1). Nous citons la revue [19] qui fait référence à plus de 120 études sur les modèles de planification et de rotation de cultures. Ces modèles sont basés sur des objectifs différents. Le critère économique est le plus étudié dans la littérature, i.e. la planification des cultures est souvent effectuée de manière à maximiser les rendements de production [23, 28, 32]. De plus, les préoccupations d'aujourd'hui sur la durabilité

<footnote>(1)Nous n'abordons pas dans cet article la problématique du suivi journalier d'un plan de cultures. Voir par exemple le logiciel Qrop https://qrop.frama.io.</footnote>
des systèmes de cultures ont conduit les chercheurs à cibler explicitement des objectifs autres que la rentabilité, des objectifs environnementaux ou écologiques. Par exemple, minimiser l'utilisation des pesticides, réduire l'érosion du sol et améliorer la fertilité physique et biologique du sol [15].

Outre les objectifs qui déterminent la sélection d'un plan de cultures, les modèles diffèrent également par le type de contraintes, qui limitent les décisions relatives aux plans de cultures. Ces contraintes sont souvent liées à la gestion des ressources limitées. Par exemple, la gestion des ressources disponibles en eau d'irrigation avec un objectif de maximiser les revenus [26, 42, 53]. D'autres ressources sont également incorporées dans les modèles de planification de cultures, comme la main d'œuvre et le niveau de mécanisation [15].

Un certain nombre de techniques explorées dans la littérature, pour la planification des cultures, se distinguent selon les objectifs visés et les contraintes considérées. La programmation mathématique est la plus utilisée [24]. En particulier la programmation linéaire (PL) depuis le modèle simplifié de [29], qui vise à maximiser les rendements de production en tenant compte de la disponibilité des ressources en main d'œuvre. Ensuite, des modèles plus réalistes que ce dernier ont été considérés comme une base des systèmes de planification des cultures. Nous citons le modèle « Purdue Top Farmer Cropping Model "B" », destiné à être utilisé directement par les agriculteurs pour la planification de la production des exploitations agricoles [40]. Nous mentionnons également le modèle ROTAT de [15]. Pour les fermes urbaines, nous citons un outil d'aide à la conception de fermes maraîchères diversifiées [8,9]. Toutefois, l'application de la programmation linéaire n'est pas toujours simple, certains problèmes rencontrent des difficultés de formulation mathématique ou d'interprétation des résultats [41]. Pour réduire ces limites, la programmation linéaire a été progressivement étendue à d'autres techniques. Par exemple, plusieurs chercheurs ont suggéré d'intégrer l'incertitude dans leurs modèles. Nous citons [32] qui ont proposé un modèle de programmation linéaire avec des valeurs incertaines (coefficients stochastiques) pour étudier l'influence du climat sur la planification des cultures. Nous mentionnons également [50] qui ont développé un modèle de programmation linéaire pour optimiser l'allocation des cultures, tout en considérant les besoins en eau d'irrigation modélisés comme des variables stochastiques.

Motivés par plusieurs facteurs économiques, environnementaux ou organisationnels, les chercheurs ont développé des modèles d'optimisation multi-critères afin de regrouper divers objectifs lors de la planification des cultures [26, 48, 53]. Cette approche a aussi été utilisée hors du cadre de la programmation linéaire. Par exemple, [49] proposent deux formulations multi-critères (linéaire et non linéaire) du problème de planification des cultures, qu'ils ont résolues par une version améliorée d'un algorithme évolutionnaire. [11] examinent l'efficacité de l'utilisation des métaheuristiques à populations, en utilisant des algorithmes d'intelligence en essaim comparés à un algorithme génétique sur une étude de cas en Afrique du Sud.

Les chercheurs ont suggéré d'autres approches pour résoudre le problème de planification de cultures, formalisé comme un problème de rotation ou de succession de
cultures. Par exemple, [27] utilisent les réseaux de flots pour modéliser les séquences
de cultures non permises comme contraintes dans un modèle standard de programma-
tion linéaire. De même, [14] proposent une modélisation par les réseaux de flots, en
tirant parti de leur structure claire et visuelle, pour utiliser des algorithmes spéciaux
pour la résolution de ces problèmes. Face à ces approches, [22] développent un mo-
dèle de programmation linéaire mixte pour l’allocation de cultures, avec un objectif
de maximiser le profit total, tout en tenant compte de la variabilité des prix et des
rendements. [2] proposent également un modèle de programmation mixte, qui vise à
minimiser la surface nécessaire pour couvrir les besoins des agriculteurs, plutôt que de
maximiser les revenus. L’aspect combinatoire du modèle provient du fait de cultiver
une parcelle ou de la laisser en jachère, alors que les variables réelles concernent les
contraintes sur la demande. Ce problème a été prouvé NP-difficile suite à une réduction
depuis le problème *Set Covering*. Après l’avoir démontré, [3] présentent une amélio-
ration du modèle en proposant une formulation compacte binaire de la programmation
linéaire basée sur les graphes de séquences de cultures, puis une formulation étendue en
utilisant la décomposition de Dantzig-Wolfe. Ils présentent ensuite une résolution par
l’algorithme de *Branch-and-Price-and-Cut* qui a montré son efficacité pour la formu-
lation étendue. [47] proposent la même approche de *Branch-and-Price-and-Cut* pour
résoudre le problème de rotation de cultures maraîchères avec l’objectif de minimiser
la surface totale utilisée. Les résultats obtenus ont montré l’efficacité de la méthode
suite à des expérimentations menées sur des données réelles.

Des méthodes d'intelligence artificielle sont également utilisées dans ce cadre. Nous citons par exemple [1] qui proposent une résolution du problème d'allocation de cultures par satisfaction de contraintes pondérées. Les simulations à base d'agents sont également utilisées. Nous mentionnons [52] qui présente une application d'une architecture multi-agents basée sur un modèle de rationalité d'agent intelligent.

À notre connaissance, aucune des nombreuses études menées sur la planification de cultures n'a examiné l'allocation des cultures annuelles et des cultures pérennes dans une même approche de modélisation. L'originalité de notre étude consiste à la modélisation de la conception d'un système agroforestier urbain (verger-maraîcher), qui associe des arbres fruitiers (cultures pérennes) et des cultures maraîchères (cultures annuelles) sur une même parcelle.

## 2. MATÉRIELS ET MÉTHODES

Comme nous l'avons présenté précédemment, les systèmes agroforestiers reposent
sur un ensemble complexe d'interactions arbres-cultures modifiant l'utilisation de la
lumière, de l'eau et des nutriments. Concevoir un tel système nécessite d'optimiser
l'utilisation de ces ressources, en maximisant les interactions positives (facilitation)
et en minimisant celles négatives (compétition). Dans les sections suivantes, nous
décrivons les choix effectués pour la construction de modèles de conception d'un
système de verger-maraîcher, à savoir, les cultures choisies et leurs caractéristiques, les
interactions aériennes et souterraines considérées, et les règles d'organisation adoptées.
Nous présentons ensuite deux formulations mathématiques du problème, un modèle
quadratique en variables binaires (BQP) et un modèle linéaire en variables mixtes (MILP). Les résultats obtenus seront discutés en Section 3.

## 2.1. MODÉLISATION DU PROBLÈME

Nous définissons le problème de conception d'un système de verger-maraîcher comme un problème d'allocation de cultures. Son objectif est de positionner, sur la même parcelle, des arbres fruitiers et des cultures maraîchères sur un horizon temporel fini. Nous avons représenté la parcelle sous forme d'un carré découpé en $l \times l$ cellules, toutes de même taille (entre $1m^2$ et $4m^2$ chacune). Chaque cellule représente une unité spatiale attribuée à une seule espèce cultivée (un arbre fruitier, une culture maraîchère ou de l'engrais vert), ou au sol nu si l'unité spatiale ne porte aucune espèce cultivée.

Concernant le temps, nous avons considéré un horizon temporel de trois périodes, selon les phases de croissance d'un arbre : période P1 correspond à un très jeune arbre, juste après la plantation, P2 à un jeune arbre qui développe rapidement son système racinaire et sa structure aérienne et P3 à un arbre mature. Chaque période représente un an de rotation (quatre saisons), sauf pour P1 que nous représentons par une seule saison, vu que nous considérons la terre en jachère à cette période. Nous avons ainsi 9 pas de temps et par conséquent 9 grilles de $l \times l$ unités spatiales.

### 2.1.1. Choix et caractéristiques des arbres fruitiers

Pour simplifier le modèle, nous avons choisi un seul type d'arbre fruitier, un pommier, que nous considérons comme un arbre générique dans le modèle.

**ESPACEMENT MINIMAL ENTRE ARBRES.** — Le choix d'espacement entre les arbres au moment de la plantation influe sur leur évolution. De ce fait, il faut définir un espacement permettant aux arbres une croissance sans conflit et une meilleure répartition lumineuse. Cet espacement minimal est plus faible que celui recommandé dans les systèmes de vergers purs, afin d'assurer un bon fonctionnement des cultures maraîchères associées, qui peuvent être impactées positivement ou négativement par la présence des arbres. La figure 2.1 illustre l'espacement minimal considéré dans notre modèle.

<figure><img src="image_7.png" /><figcaption>FIGURE 2.1. Représentation de l'espacement minimal entre arbres. La cellule grise représente un arbre et les cellules croisées représentent les zones interdites à la plantation des autres arbres.</figcaption></figure>
### INTERCEPTION DU RAYONNEMENT SOLAIRE.
— Naturellement, le feuillage des arbres se développe au printemps, se stabilise en été, puis tombe en automne et recommence le printemps suivant. Ainsi, lors des saisons printemps et été, où les arbres ont des feuilles, les cultures plantées à proximité peuvent subir une réduction du rayonnement solaire disponible. Cette zone impactée est généralement liée à la morphologie de l'arbre, à savoir la hauteur, la largeur et la densité foliaire du houppier. Elle est également liée aux différentes saisons de l'année où l'inclinaison des rayons solaires varie.

Pour définir le périmètre d'interception du rayonnement solaire autour de ce fruitier, nous nous sommes basés sur les résultats d'un logiciel de simulation qui prend en considération tous les critères cités ci-dessus comme la saison, la morphologie de l'arbre, et sa densité foliaire. Nous avons traduit ces résultats de simulation pour représenter les niveaux d'interception du rayonnement solaire sous les arbres sur la parcelle carrée de notre modèle de conception et ainsi définir les unités spatiales affectées par la perte de rayonnement solaire (Figure 2.2). Nous faisons l'hypothèse simplificatrice que la perte est la même pour un arbre jeune (P2) ou mature (P3).

<figure><img src="image_8.png" /><figcaption>FIGURE 2.2. Unités spatiales affectées par la perte de rayonnement solaire (cellules croisées) par un arbre (cellule grise), durant les trois périodes P1, P2 et P3.</figcaption></figure>

### SYSTÈMES RACINAIRES DES FRUITIERS.
— Les systèmes racinaires des arbres se différencient des cultures annuelles par leur pérennité. Le développement des racines varie d'une année à l'autre avec une production plus élevée les premières années de l'arbre [4]. Malheureusement, il existe très peu d'informations sur le développement des racines des fruitiers lors des premières années après la plantation. Pour modéliser le système racinaire des arbres fruitiers, nous nous sommes basés sur une simulation 3D d'architecture racinaire d'un pêcher greffé sur un prunier [54]. Le système racinaire des arbres colonise un grand volume du sol. Certaines racines descendent en profondeur, progressivement, d'environ 1m par an. Tandis que d'autres s'étendent latéralement à toutes les profondeurs atteintes avec un maximum de 3m. Cette observation nous a conduit à élaborer le modèle schématisé dans la figure 2.3.

#### 2.1.2. Choix et caractéristiques des cultures maraîchères

Nous avons sélectionné un ensemble de cultures avec des dates et des durées de plantation différentes. Nous avons choisi des cultures de cycle court (une saison), à savoir le melon planté en été et trois variétés de salade, chacune sur une saison
<figure><img src="image_9.png" /><figcaption>FIGURE 2.3. Croissance des racines (cellule croisées) d'un arbre fruitier (cellule grise) en périodes P1, P2 et P3.</figcaption></figure>

(printemps, été et automne). Nous avons également choisi des cultures avec des cycles plus longs qui s'étalent sur deux saisons : tomate et oignon au printemps-été et carotte en été-automne. Finalement, nous avons ajouté deux types d'engrais verts à intercaler avec ces cultures maraîchères pour préserver la qualité du sol.

SENSIBILITÉ DES CULTURES À L'OMBRE. — Pour analyser l'impact de l'ombre des arbres sur les cultures maraîchères, nous nous sommes fondés sur les connaissances expertes d'agronomes. La table 2.1 présente le degré de sensibilité des cultures choisies à l'interception du rayonnement solaire. Cela est représenté par une évaluation qualitative en fonction de la culture et la saison pendant laquelle elle est cultivée. Le symbole (0) indique un effet neutre, (-) un effet négatif et (+) un effet positif. La répétition d'un même symbole (++ ou +++) indique un degré de sensibilité plus fort.

<table><caption>TABLE 2.1. Sensibilité des cultures maraîchères choisies à la perte de rayonnement solaire</caption><thead><tr><td>Cultures</td><td>Printemps</td><td>Été</td></tr></thead><tbody><tr><td>Salade</td><td>0</td><td>+++</td></tr><tr><td>Tomate</td><td>0</td><td>++</td></tr><tr><td>Oignon</td><td>-</td><td>0</td></tr><tr><td>Melon</td><td>-</td><td>-</td></tr><tr><td>Carotte</td><td>-</td><td>0</td></tr></tbody></table>

SYSTÈMES RACINAIRES DES CULTURES MARAÎCHÈRES. — Le développement des systèmes racinaires varie d'une espèce à l'autre du fait de leurs besoins différents en eau et nutriments. La figure 2.4 illustre les systèmes racinaires de certaines espèces choisies [55]. Nous constatons par exemple que l'oignon a des racines peu ramifiées qui se développent dans les couches superficielles autour de la plante (1 pied = 30 cm). De même, le melon a des racines de faible profondeur (2 pieds) mais qui s'étendent bien horizontalement. La salade a des racines latérales bien ramifiées avec une racine pivotante profonde (4 pieds) peu ramifiée. La carotte a des racines qui s'étendent verticalement (5 pieds) avec des branches courtes. Tandis que la tomate a des racines qui remplissent le sol autour de la plante, en s'étendant en profondeur vers de nouveaux territoires. Il est à noter que les données expérimentales sur les systèmes racinaires
sont peu nombreuses et qu'une partie des informations de cet article provient d'experts du domaine.

<figure><img src="image_10.png" /><figcaption>FIGURE 2.4. Illustration de systèmes racinaires d'espèces maraîchères</figcaption></figure>

Pour définir le niveau de compétition pour l'eau entre arbres et cultures, nous avons classé les systèmes racinaires des cultures en fonction de la surface occupée en profondeur. Ce niveau, qui commence à deux pieds du sol, correspond au niveau où les racines des arbres fruitiers commencent à s'étendre en profondeur avec plus de branchement (Figure 2.3). De ce fait, l'ordre de classement est comme suit : (oignon = melon) < salade < carotte < tomate.

Contrairement à cette compétition, associer des arbres et des cultures sur la même parcelle favorise une meilleure utilisation de l'eau grâce aux systèmes racinaires des arbres, qui transfèrent l'eau des couches profondes du sol vers les surfaces superficielles et récupèrent l'excès d'eau qui pourrait nuire aux cultures maraîchères. Dans notre modèle, le surplus d'eau existe à toutes les saisons sauf l'été. À ces saisons, le partage de l'eau se produit automatiquement par la présence d'une culture auprès d'un arbre. Cependant, si la culture est plantée loin d'un arbre, elle pourrait être altérée par un excès d'eau.

**MIXITÉ DES CULTURES MARAÎCHÈRES.** — Une fois que les cultures sont choisies, il faut déterminer en quelles quantités les répartir sur la parcelle, c'est-à-dire définir le nombre de cellules utilisées par culture pour chaque saison de manière à diversifier la production. Pour répondre à cette question, nous avons ajouté des contraintes de mixité des cultures maraîchères, représentées par des intervalles de répartition (exprimés en pourcentage de la surface de la parcelle) : salade 10 %–20 %, tomate 12 %–24 %, oignon 16 %–32 %, melon 12 %–24 %, carotte 16 %–32 % et engrais 15 %–100 %. Les valeurs minimales sont choisies de sorte qu'à chaque saison il y ait une mixité minimale de cultures dans la parcelle, en laissant suffisamment d'unités spatiales pour
positionner des arbres. Les valeurs maximales correspondent au cas où toutes les unités spatiales sont attribuées à des cultures maraîchères sans arbres.

REGROUPEMENT SPATIAL DES CULTURES MARAÎCHÈRES. — Nous avons modélisé cette règle par une pénalisation des cultures dispersées sur la parcelle, évaluées en comparant la culture plantée sur une unité spatiale avec son adjacente horizontale ou verticale (Figure 2.5).

<figure><img src="image_11.png" /><figcaption>FIGURE 2.5. Modélisation de la dispersion horizontale/verticale des cultures maraîchères.</figcaption></figure>

ROTATION DES CULTURES. — Nous avons simplement ajouté des contraintes qui interdisent de planter la même culture au même endroit deux années successives.

## 2.2. MODÈLE QUADRATIQUE EN VARIABLES BINAIRES (BQP)

Pour résoudre le problème de verger-maraîcher, nous avons reformulé le modèle conceptuel, décrit dans la section précédente, en un modèle mathématique. D'abord, nous avons élaboré un modèle basé sur la programmation quadratique en variables binaires sous contraintes linéaires [37, 38], que nous avons ensuite reformulé en un modèle de programmation linéaire mixte [39].

La forme mathématique la plus générale sous contraintes linéaires est la suivante :

$$ \min_{x} \sum_{i=1}^{n} c_i x_i + \sum_{i=1}^{n} \sum_{j \neq i}^{n} q_{ij} x_i x_j \quad (2.1) $$

$$ s.c \quad \sum_{i=1}^{n} a_{ki}x_i \leq b_k \qquad k = 1, \dots, m \quad (2.2) $$

$$ x_i \in \{0, 1\} \qquad i = 1, \dots, n \quad (2.3) $$

où $x$ est un vecteur de variables binaires, $q_{ij} \in Q^{n \times n}$ est une matrice de coefficients réels carrée symétrique ($q_{ij} = q_{ji}$), $b$, $c$ des vecteurs de coefficients réels et $a_{ki} \in A^{m \times n}$ une matrice de coefficients réels.
### 2.2.1. Variables

Pour reformuler le problème de verger-maraîcher sous cette forme quadratique, nous considérons quatre variables binaires :

* $crop_{x,y}^{t,c} = 1$ ssi l'unité spatiale de coordonnées $x$, $y$ a une culture $c$ au temps $t$

* $tree_{x,y} = 1$ ssi l'unité spatiale de coordonnées $x$, $y$ a un arbre

* $shade_{x,y} = 1$ ssi l'unité spatiale de coordonnées $x$, $y$ a l'ombre d'un arbre

* $root_{x,y}^{p} = 1$ ssi l'unité spatiale de coordonnées $x$, $y$ a les racines d'un arbre à la période $p$

### 2.2.2. Paramètres

Soit $L = \{1, \dots, l\}$ l'ensemble des positions horizontales/verticales des unités spatiales d'une parcelle de forme carrée, représentée sous forme d'une grille de taille $l \times l$. La numérotation des positions commence en haut à gauche (i.e. nord ouest) avec les coordonnées ($x = 1, y = 1$). Soit $\zeta$ l'ensemble des cultures, $T$ l'ensemble des pas de temps (chaque pas de temps représente une saison, commençant en automne), et $P$ l'ensemble des périodes de croissances des arbres, avec $T_p$ l'ensemble des pas de temps de chaque période $p \in P$. Dans nos expériences, nous faisons varier la taille de la parcelle $l \times l$ en utilisant un ensemble fixe de $\zeta, T, P$ et $T_p$ :

* $\zeta = \{oignon, melon, salade, carotte, tomate, engrais, sol nu\}$

* $T = \{1, \dots, 9\}$

* $P = \{1, 2, 3\}$

* $T_1 = \{1\} \sim \{automne\}, T_2 = \{2, 3, 4, 5\}, T_3 = \{6, 7, 8, 9\} \sim \{hiver, printemps, été, automne\}$.

### 2.2.3. Fonction objectif : optimisation des interactions arbres-cultures

Rappelons que l'objectif de notre problème est de concevoir un système de verger-maraîcher, qui permet d'optimiser les interactions aériennes et souterraines entre arbres et cultures. Basés sur les interactions décrites à la section précédente, nous distinguons trois situations possibles pour chaque unité spatiale :

* $sr$ : où l'ombre et les racines sont présentes,

* $\bar{sr}$ : où les racines sont présentes sans ombre,

* $\bar{sr}$ : où l'ombre et les racines sont absentes.

Chaque situation $\sigma$ est liée à une valeur $v^\sigma$ qui peut être négative ou positive selon le type des interactions (facilitation ou compétition). Cela se traduit par la fonction objectif suivante :

$$ \min \sum_{\substack{p \in P, t \in T_p, \\ c \in \zeta, x, y \in L}} \left[ v^{sr} \times shade_{x,y} \times root_{x,y}^{p} + v^{\bar{sr}} \times (1 - shade_{x,y}) \times root_{x,y}^{p} + v^{\bar{sr}} \times (1 - shade_{x,y}) \times (1 - root_{x,y}^{p}) \right] \times crop_{x,y}^{t,c} \quad (2.4) $$
Notons que, durant les périodes P2 et P3, la présence de l'ombre (Figure 2.2) à une unité spatiale implique la présence des racines (Figure 2.3) :

$$ \text{shade}_{x,y} \Rightarrow \text{roots}_{x,y}^{p} \qquad (2.5) $$

Avec cette implication (équation 2.5) et le fait qu'il n'y a pas d'ombre à la période P1, la fonction objectif 2.4 devient :

$$ \min \sum_{\substack{p \in P, t \in T_p, \\ c \in \zeta, x, y \in L}} [A^{t,c} \times \text{shade}_{x,y} + B^{t,c} \times \text{root}_{x,y}^{p} + C^{t,c}] \times \text{crop}_{x,y}^{t,c} \quad (2.6) $$

Avec :

* $A^{t,c} = v^{sr} - v^{\bar{s}r}$ : valeurs liées au degré de sensibilité des cultures à l'ombre à une saison quelconque ($A^{1,c} = 0$ à l'automne et à l'hiver). Selon la table 2.1, nous affectons un coût de 10 à un effet négatif (-), un coût de 0 à un effet neutre (0) et un coût de -10 à un effet positif (+).

* $B^{t,c} = v^{\bar{s}r} - v^{\bar{\bar{s}}r}$ : valeurs liées aux interactions générées par les systèmes racinaires des arbres fruitiers et des cultures maraîchères (compétition ou partage pour l'eau). Basés sur la figure 2.4, nous avons déjà défini le niveau de compétition pour l'eau en classant les cultures maraîchères dans un ordre croissant selon leurs systèmes racinaires : (oignon = melon) < salade < carotte < tomate. Ainsi, basés sur ce classement, nous attribuons respectivement (en été) les coûts suivants : 0, 10, 20 et 30. Ensuite, nous donnons un coût négatif pour les cultures permettant de partager les ressources en eau avec des arbres en toutes saisons sauf en été (Table 2.2) : -10 pour les cultures maraîchères et -20 pour l'engrais vert.

* $C^{t,c} = v^{\bar{s}\bar{F}}$ : valeurs liées à l'absence de l'ombre et des racines des arbres. Nous évaluons cette situation par un coût de 10 quand le partage n'est pas en place (valeurs opposées de la colonne partage, Table 2.2). Plus un coût dû à l'absence de l'ombre en été : 20 pour la salade et 10 pour la tomate.

<table><caption>TABLE 2.2. Valeurs liées aux interactions souterraines (compétition et partage pour l'eau).</caption><thead><tr><th></th><th>Compétition</th><th>Partage</th></tr></thead><tbody><tr><td>Salade printemps</td><td>0</td><td>-10</td></tr><tr><td>Salade été</td><td>10</td><td>0</td></tr><tr><td>Salade automne</td><td>0</td><td>-10</td></tr><tr><td>Tomate</td><td>30</td><td>-10</td></tr><tr><td>Melon</td><td>0</td><td>0</td></tr><tr><td>Carotte</td><td>20</td><td>-10</td></tr><tr><td>Oignon</td><td>0</td><td>-10</td></tr><tr><td>Engrais</td><td>0</td><td>-20</td></tr><tr><td>Sol nu</td><td>0</td><td>10</td></tr></tbody></table>
La table 2.3 résume les valeurs $A^{t,c}$, $B^{t,c}$ et $C^{t,c}$ associées à chaque culture maraîchère dans une saison quelconque. Ces coûts sont déterminants pour la quantité à planter et le placement des cultures sur les unités spatiales. Pour réduire le nombre des unités spatiales affectées au sol nu $c_0$, nous ajoutons respectivement aux coefficients associés $(A^{t,c_0}, B^{t,c_0}$ et $C^{t,c_0}$) des valeurs égales à $\max_{t,c \neq c_0}(A^{t,c}) + 10$, $\max_{t,c \neq c_0}(B^{t,c}) + 10$ et $\max_{t,c \neq c_0}(C^{t,c}) + 10$ respectivement.

<table><caption>TABLE 2.3. Coefficients de la fonction objectif (2.6), représentés par des couleurs selon les espèces et les durées de plantation. Les coefficients $A^{t,c}$ en hiver ($t \in \{2, 6\}$) et en automne ($t \in \{1, 5, 9\}$) sont en gris pour indiquer l'absence de l'ombre à ces deux saisons.</caption><thead><tr><th rowspan="2"></th><th colspan="3">Hiver</th><th colspan="3">Printemps</th><th colspan="3">Été</th><th colspan="3">Automne</th></tr><tr><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th><th>A</th><th>B</th><th>C</th></tr></thead><tbody><tr><td>Salade printemps</td><td></td><td></td><td></td><td>0</td><td>-10</td><td>10</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>Salade été</td><td></td><td></td><td></td><td></td><td></td><td></td><td>-30</td><td>-10</td><td>20</td><td></td><td></td><td></td></tr><tr><td>Salade automne</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>-10</td><td>10</td><td></td></tr><tr><td>Tomate</td><td></td><td></td><td></td><td>0</td><td>-10</td><td>10</td><td>-20</td><td>30</td><td>10</td><td></td><td></td><td></td></tr><tr><td>Melon</td><td></td><td></td><td></td><td></td><td></td><td></td><td>10</td><td>0</td><td>0</td><td></td><td></td><td></td></tr><tr><td>Carotte</td><td></td><td></td><td></td><td></td><td></td><td></td><td>0</td><td>20</td><td>0</td><td></td><td>-10</td><td>10</td></tr><tr><td>Oignon</td><td></td><td></td><td></td><td></td><td>10</td><td>-10</td><td>10</td><td>0</td><td>0</td><td></td><td></td><td></td></tr><tr><td>Engrais vert 1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td>-10</td><td>10</td><td></td></tr><tr><td>Engrais vert 2</td><td></td><td>-10</td><td>10</td><td></td><td></td><td></td><td></td><td></td><td></td><td>-10</td><td>10</td><td></td></tr><tr><td>Sol nu</td><td>40</td><td>30</td><td></td><td>20</td><td>40</td><td>30</td><td>20</td><td>40</td><td>30</td><td>40</td><td>30</td><td></td></tr></tbody></table>

### 2.2.4. Fonction objectif : optimisation de la dispersion des cultures

En plus de l'objectif principal qui consiste à optimiser les interactions arbres-cultures, nous modélisons le regroupement spatial des cultures maraîchères comme un objectif secondaire de notre problème. Selon la figure 2.5, le terme (2.7) traduit la pénalisation de la dispersion spatiale des cultures, évaluée en comparant (deux à deux) les cultures présentes dans les unités spatiales adjacentes horizontales et verticales. Nous accordons à chaque dispersion un coefficient de pénalisation, $C_{disp} > 0$. Pour avoir la dispersion comme critère secondaire par rapport aux interactions, nous mettons $C_{disp} = \frac{1}{2 \times l^2 + 1}$, avec $l$ la dimension de la grille, pour que dans le pire cas la somme des dispersions soit inférieure à 1, en supposant que la valeur absolue des coefficients des interactions $(A^{t,c}, B^{t,c}$ et $C^{t,c})$ soient des valeurs entières, nettement supérieures à 1.
Nous ajoutons ce terme quadratique à la fonction objectif 2.6.

$$
C_{disp} \times \left[ \sum_{\substack{t \in T, c \in \zeta, \\ x,y \in L^2, x<l}} ((1 - \text{crop}_{x,y}^{t,c}) \times \text{crop}_{x+1,y}^{t,c} + (1 - \text{crop}_{x+1,y}^{t,c}) \times \text{crop}_{x,y}^{t,c}) \right. \\
\left. + \sum_{\substack{t \in T, c \in \zeta, \\ x,y \in L^2, y<l}} ((1 - \text{crop}_{x,y}^{t,c}) \times \text{crop}_{x,y+1}^{t,c} + (1 - \text{crop}_{x,y+1}^{t,c}) \times \text{crop}_{x,y}^{t,c}) \right] \quad (2.7)
$$

2.2.5. Contraintes

Afin de compléter le modèle mathématique, nous avons défini les contraintes li-
néaires suivantes :

(1) Une culture ou un arbre sur chaque unité spatiale

$$
\text{tree}_{x,y} + \sum_{c \in C} \text{crop}_{x,y}^{t,c} = 1 \quad (\forall t \in T, \forall x, y \in L^2) \quad (2.8)
$$

(2) Espacement minimal entre arbres (Figure 2.1)

$$
\text{tree}_{x,y} + \text{tree}_{x+1,y} \le 1 \quad (\forall x, y \in L^2, x < l) \tag{2.9}
$$

$$
\text{tree}_{x,y} + \text{tree}_{x,y+1} \le 1 \quad (\forall x, y \in L^2, y < l) \quad (2.10)
$$

(3) Aucun arbre sur les bordures Est et Ouest de la parcelle

$$
\mathrm{tree}_{x,l} = 0 \quad (\forall x \in L) \tag{2.11}
$$

$$
\text{tree}_{1,y} = 0 \quad (\forall y \in L) \tag{2.12}
$$

(4) Définition de l'ombre au Nord, Est et Ouest d'un arbre (Figure 2.2)

$$
-6 \times \text{shade}_{x,y} + \sum_{\substack{i \in \{\max(1-x,-1), \dots, \min(l-x,1)\} \\ j \in \{0, \dots, \min(l-y,1)\}}} \text{tree}_{x+i, y+j} \le 0 \quad (\forall x, y \in L^2) \quad (2.13)
$$

$$
\text{shade}_{x,y} - \sum_{\substack{i \in \{\max(1-x,-1), \dots, \min(l-x,1)\} \\ j \in \{0, \dots, \min(l-y,1)\}}} \text{tree}_{x+i, y+j} \le 0 \quad (\forall x, y \in L^2) \quad (2.14)
$$

(5) Évolution des racines d'un arbre (Figure 2.3)

$$
\mathrm{root}_{x,y}^{1} - \mathrm{tree}_{x,y} = 0 \quad (\forall x, y \in L^2) \tag{2.15}
$$

$$
-9 \times \text{root}_{x,y}^{p} + \sum_{i \in I, j \in J} \text{root}_{x+i, y+j}^{p-1} \le 0 \quad (\forall x, y \in L^2, \forall p \in \{2, 3\}) \quad (2.16)
$$

$$
\text{root}_{x,y}^{p} - \sum_{i \in I, j \in J} \text{root}_{x+i, y+j}^{p-1} \le 0 \quad (\forall x, y \in L^2, \forall p \in \{2, 3\}) \quad (2.17)
$$

où $I = \{\max(1-x, -1), \dots, \min(l-x, 1)\}$ et $J = \{\max(1-y, -1), \dots, \min(l-y, 1)\}$.
(6) Contrainte de rupture de symétrie verticale des solutions

$$ \sum_{x \in \{1, \dots, \lfloor l/2 \rfloor\}, y \in L} \mathrm{tree}_{x,y} - \sum_{x \in \{(l-\lfloor l/2 \rfloor+1), \dots, l\}, y \in L} \mathrm{tree}_{x,y} \le 0 \quad (2.18) $$

(7) Quantités minimales et maximales des cultures

$$ \minBalance(t, c) \le \sum_{x,y} \mathrm{crop}_{x,y}^{t,c} \le \maxBalance(t, c) \quad (\forall t \in T, \forall c \in \zeta) \quad (2.19) $$

(8) Rotation de cultures

$$ \begin{gathered} \mathrm{crop}_{x,y}^{t_2,c} + \mathrm{crop}_{x,y}^{t_3,c} \le 1 \quad \forall t_2 \in T^2, \forall t_3 \in T^3, \\ \forall c \in \{\mathrm{oignon}, \mathrm{tomate}, \mathrm{carotte}, \mathrm{melon}\} \end{gathered} \quad (2.20) $$

(9) Cultures sur deux saisons consécutives

$$ \mathrm{crop}_{x,y}^{t,c} - \mathrm{crop}_{x,y}^{t+1,c} = 0 \quad (\forall p \in P, t=f_c(p), \forall x,y \in L^2, \forall c \in \{\mathrm{oignon, tomate, carotte, engrais}\}) \quad (2.21) $$

Pour cette dernière contrainte (2.21), $f_c(p)$ représente le pas de temps $t$ qui correspond à une culture $c$ plantée à la saison $t \in T_p$ de la période $p$ et qui dure deux saisons. Pour illustrer, l'engrais vert est planté en automne, i.e. $f_{\text{engrais}}(1) = 1$, l'oignon et la tomate sont plantés au printemps, i.e. $f_{\text{oignon \lor tomate}}(2) = 3$, et la carotte est plantée en été, i.e. $f_{\text{carotte}}(3) = 8$. La contrainte (2.18) supprime les solutions obtenues par symétrie verticale (du fait des motifs symétriques d'ombre et de croissance des racines), permettant d'accélérer la résolution du problème.

## 2.3. MODÈLE LINÉAIRE EN VARIABLES MIXTES (MILP)

Pour reformuler le problème de conception de verger-maraîcher sous forme d'un programme linéaire mixte (MILP), nous avons simplifié (relaxé) le modèle précédent, en supprimant les contraintes sur la rotation de cultures (2.20) et l'objectif secondaire sur leur regroupement spatial (2.7). Ces deux éléments seront traités de manière heuristique une fois le modèle résolu (Section 2.3.2). Ces simplifications vont nous permettre de réduire drastiquement le nombre de variables du problème et d'avoir une fonction objectif linéaire.

### 2.3.1. Reformulation du problème

Nous séparons le problème principal en deux sous-problèmes : (i) le positionnement des arbres et (ii) l'optimisation des interactions arbres-cultures au fil du temps. Cette séparation permet de profiter d'une décomposition de Benders [6,46]. Celle-ci consiste à séparer les variables en deux ensembles (deux niveaux de décision) : les variables appartenant au problème maître et les variables appartenant au sous-problème primal. Généralement, le problème maître est plus facile à résoudre que le problème d'origine car il s'agit d'une relaxation i.e. il considère les variables du sous-problème comme des valeurs constantes fournies par la résolution du sous-problème dual. En d'autres termes, le sous-problème dual alimente le problème maître restreint par des contraintes
(ou coupes) qui renforcent le problème maître jusqu'à obtenir un problème équivalent au problème d'origine.

Le premier problème (i) correspond au problème maître restreint (PMR) dans l'approche de Benders et le second problème (ii) correspond au sous-problème (SP). Le problème maître garde les variables binaires $tree_{x,y}$, $shade_{x,y}$ et $root_{x,y}^p$, et les contraintes associées (2.9)–(2.18). Les contraintes restantes (2.19)–(2.21) appartiennent au sous-problème.

Le problème maître communique avec le sous-problème en introduisant de nouvelles variables entières qui correspondent au nombre d'arbres, c.-à-d.,

$$trees = \sum_{x,y \in L^2} tree_{x,y},$$

au nombre d'unités spatiales à l'ombre,

$$shades = \sum_{x,y \in L^2} shade_{x,y} - trees,$$

et au nombre d'unités spatiales de présence de racines à chaque période $p$,

$$roots_p = \sum_{x,y \in L^2} root_{x,y}^p - trees$$

Concernant les variables du sous-problème, au lieu d'avoir des variables binaires $crop_{x,y}^{t,c}$ qui définissent exactement l'emplacement $x$, $y$ de toute culture $c$ à toute saison $t$, nous les remplaçons par des quantités de production suivant le type de situation dans laquelle se trouvent les unités spatiales associées. Nous distinguons trois configurations possibles : unités spatiales ayant ombre et racines ($sr$), unités spatiales avec seulement des racines ($\bar{sr}$), et unités spatiales sans ombre ni racines ($\bar{\bar{sr}}$). Les variables continues correspondantes sont respectivement : $q_{crop_{sr}^{t,c}}$, $q_{crop_{sr}^{t,c}}$, et $q_{crop_{sr}^{t,c}}$. Elles représentent des partitions de l'ensemble des unités spatiales de la parcelle (sauf celles attribuées aux arbres), leur somme est égale à $q_{crop_{sr}^{t,c}}$ (2.23)-(2.24). Nous ajoutons les contraintes (2.25)-(2.26) pour assurer une allocation faisable sur des unités spatiales ayant ombre ou racines sans présence d'arbre. Avec cette reformulation, le SP a maintenant une fonction objectif linéaire :

$$\min \sum_{t \in T, c \in \zeta} (A^{t,c} + B^{t,c}) q_{crop_{sr}^{t,c}} + B^{t,c} q_{crop_{sr}^{t,c}} + C^{t,c} q_{crop_{sr}^{t,c}} \quad (2.22)$$
Sous contraintes,

$$q_{\text{crop\textsubscript{sr}}^{t,c}} + q_{\text{crop\textsubscript{sr}}^{t,c}} + q_{\text{crop\textsubscript{sr}}^{t,c}} - q_{\text{crop\textsubscript{sr}}^{t,c}} = 0 \quad (\forall t \in T, \forall c \in \zeta) \quad (2.23)$$

$$\sum_{c \in \zeta} q_{\text{crop}^{t,c}} - l^2 + \text{trees} = 0 \quad (\forall t \in T) \quad (2.24)$$

$$\sum_{c \in \zeta} q_{\text{crop}^{t,c}} - \text{shades} = 0 \quad (\forall t \in T \setminus \{1\}) \quad (2.25)$$

$$\sum_{c \in \zeta} (q_{\text{crop}^{t,c}} + q_{\text{crop}^{t,c}}) - \text{roots}_p = 0 \quad (\forall p \in P, \forall t \in T_p) \quad (2.26)$$

$$\min\text{Balance}(t, c) \le q_{\text{crop}^{t,c}} \le \max\text{Balance}(t, c) \quad (\forall t \in T, \forall c \in \zeta) \quad (2.27)$$

$$q_{\text{crop}^{t,c}} - q_{\text{crop}^{t+1,c}} = 0 \quad (\forall p \in P, t = f_c(p), \forall c \in \{\text{oignon, tomate, carotte, engrais}\}) \quad (2.28)$$

$$q_{\text{crop\textsubscript{sr}}^{t,c}} - q_{\text{crop\textsubscript{sr}}^{t+1,c}} = 0 \quad (\forall p \in P \setminus \{1\}, t = f_c(p), \forall c \in \{\text{oignon, tomate, carotte, engrais}\}) \quad (2.29)$$

$$q_{\text{crop}^{t,c}_{\text{sr}}} - q_{\text{crop}^{t+1,c}_{\text{sr}}} = 0 \quad (\forall p \in P \setminus \{1\}, t = f_c(p), \forall c \in \{\text{oignon, tomate, carotte}\}) \quad (2.30)$$

$$q_{\text{crop}^{t, \text{engrais}}_{\text{sr}}} - q_{\text{crop}^{t+1, \text{engrais}}_{\text{sr}}} \le 0 \quad (\forall p \in P, t = f_{\text{engrais}}(p)) \quad (2.31)$$

Notons que les unités spatiales de présence d'ombre ou de racines ne changent pas à l'intérieur d'une même période. En conséquence, les cultures plantées sur deux saisons consécutives de la même période doivent garder les mêmes quantités de production (le même nombre d'unités spatiales à l'ombre et aux racines) (2.29)-(2.30). En revanche, des cultures sur deux saisons, comme l'engrais, qui chevauchent deux périodes peuvent être affectées à plus d'unités spatiales de racines à la seconde période qu'à la première (2.31).

La variable $q_{\text{crop\textsubscript{sr}}^{t,c}}$ apparaît uniquement dans la contrainte (2.23) en tant que variable d'écart. Nous pouvons la supprimer en remplaçant (2.23) par la contrainte suivante :

$$q_{\text{crop}^{t,c}_{\text{sr}}} + q_{\text{crop}^{t,c}_{\text{sr}}} - q_{\text{crop}^{t,c}} \le 0 \quad (\forall t \in T, \forall c \in \zeta)$$

En conclusion, l'objectif du sous-problème est de définir les quantités de production dans le temps sans spécifier l'emplacement des cultures sur la parcelle. Ce qui rend la fonction objectif (initialement quadratique) linéaire. Il est facile de vérifier que l'équation (2.22) est équivalente à l'équation (2.6).

Pour assurer la faisabilité du sous-problème, le positionnement des arbres (dans le problème maître) doit se faire de manière à laisser suffisamment d'unités spatiales pour l'allocation des cultures (dans le sous-problème) permettant de satisfaire les demandes de production. Nous ajoutons donc, au problème maître les contraintes redondantes
suivantes :

$$ \text{trees} \le l^2 - \sum_{c \in \zeta} \minBalance^{t,c} \quad (\forall t \in T) \quad (2.32) $$

$$ \text{trees} \ge l^2 - \sum_{c \in \zeta} \maxBalance^{t,c} \quad (\forall t \in T) \quad (2.33) $$

Pour finir, nous combinons le modèle PMR et le modèle SP pour former notre modèle linéaire à variables mixtes (MILP). Nous utilisons pour le résoudre l'approche de décomposition de Benders implémentée dans CPLEX. Celle-ci sépare automatiquement les variables discrètes d'un problème MILP mises dans le problème maître et les variables continues dans le sous-problème.

### 2.3.2. Construction d'un plan d'allocation complet pour l'approche MILP

Par rapport au modèle quadratique qui permet de définir les positions exactes des arbres tree<sub>x,y</sub> et des cultures crop<sub>x,y</sub><sup>t,c</sup>, le modèle MILP permet de positionner uniquement les arbres. Il permet également de définir les quantités des cultures selon les configurations possibles des unités spatiales ($q_{crop_{sr}^{t,c}}$, $q_{crop_{sr}^{t,c}}$, $q_{crop_{s\bar{f}}^{t,c}}$<sup>(2)</sup>).

Pour construire un plan d'allocation complet (voir Algorithme 1), nous pouvons attribuer aléatoirement, à une culture c, $q_{crop_{sr}^{t,c}}$ (respectivement $q_{crop_{sr}^{t,c}}$, $q_{crop_{s\bar{f}}^{t,c}}$) unités spatiales parmi celles libres ayant ombre et racines (resp. racines seulement, ni ombre ni racines) à chaque pas de temps t. En revanche, attribuer une culture c qui dure deux saisons successives n'est pas si simple, car elle doit être attribuée à la même unité spatiale x, y au temps t et t + 1, i.e. $crop_{x,y}^{t,c} = crop_{x,y}^{t+1,c}$.

Concernant l'engrais vert qui chevauche deux saisons t et t + 1 sur deux périodes différentes, nous utilisons une procédure d'affectation spécifique. Dans le cas où nous avons $q_{crop_{sr}^{t,engrais}} < q_{crop_{sr}^{t+1,engrais}}$, nous devons alors trouver $q_{crop_{sr}^{t+1,engrais}} - q_{crop_{sr}^{t,engrais}}$ unités spatiales sans racines au temps t et avec racines au temps t + 1 lors de l'allocation de $q_{crop_{s\bar{f}}^{t,engrais}}$. Cela a pour objectif de conserver une quantité totale constante de l'engrais, qui sera affectée aux mêmes unités spatiales au temps t et t + 1. Les unités spatiales restantes $q_{crop_{s\bar{f}}^{t,engrais}} - (q_{crop_{sr}^{t+1,engrais}} - q_{crop_{sr}^{t,engrais}})$ sont choisies arbitrairement parmi les unités spatiales sans racines.

Pour satisfaire ces contraintes d'engrais entre deux périodes (2.31) et les contraintes de cultures maraîchères sur deux saisons à la même période (2.28)-(2.30), nous construisons un plan d'allocation avec un ordre de pas de temps décroissant, commençant en automne de la période P3 (voir Figure 2.6 et Algorithme 1, ligne 22). Concernant les dimensions spatiales, nous commençons l'attribution par le côté en haut à gauche puis nous cherchons les unités spatiales les plus proches (distance minimum par rapport à l'axe des y puis à l'axe des x). Ce qui permet de réduire la dispersion

<footnote><sup>(2)</sup>Notons que $q_{crop_{s\bar{f}}^{t,c}} = q_{crop^{t,c}} - q_{crop_{sr}^{t,c}} - q_{crop_{sr}^{t,c}}$ (Eq. 2.23).</footnote>
<table><caption>**Algorithme 1 :** Construction d'un plan d'allocation complet des cultures</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>Entrées :</td><td><i>tree</i><sub>x,y</sub>, <i>shade</i><sub>x,y</sub>, <i>root</i><sup><i>p</i></sup><sub>x,y</sub>, <i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub>, <i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub>, <i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub></td></tr><tr><td>Output :</td><td><i>crop</i><sup><i>t,c</i></sup><sub>x,y</sub></td></tr></tbody></table><p><b>1 Procedure Allouer</b>(<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>type</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>type</i>, <i>p'</i>, <i>type'</i>)</p><p><b>2</b> si (<i>t</i> &lt; max(<i>T</i>) &amp; twoseason(<i>c</i>) &amp; <i>f</i><sub>c</sub>(<i>p</i>) = <i>t</i>) alors retourner ;</p><p><b>4</b> pour <i>y</i> &lt; 1 à <i>l</i> faire</p><p><b>6</b> pour <i>x</i> &lt; 1 à <i>l</i> faire</p><p><b>7</b> si (<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>type</i></sub></sub> = 0) alors retourner ;</p><p><b>8</b> si (<i>tree</i><sup><i>t</i></sup><sub>x,y</sub> &amp; Type(<i>p</i>, <i>x</i>, <i>y</i>) = <i>type</i> &amp; Type(<i>p'</i>, <i>x</i>, <i>y</i>) = <i>type'</i>) alors</p><p><b>9</b> <i>tree</i><sup><i>t</i></sup><sub>x,y</sub> &lt; false ;</p><p><b>10</b> <i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>type</i></sub></sub> &lt; <i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>type</i></sub></sub> - 1 ;</p><p><b>11</b> <i>crop</i><sup><i>t,c</i></sup><sub>x,y</sub> &lt; 1, ∀<i>c'</i> ∈ ζ \ {<i>c</i>}, <i>crop</i><sup><i>t,c'</i></sup><sub>x,y</sub> &lt; 0 ;</p><p><b>12</b> si (twoseason(<i>c</i>) &amp; <i>f</i><sub>c</sub>(<i>p</i>) &lt; <i>t</i>) alors</p><p><b>13</b> <i>tree</i><sup><i>t-1</i></sup><sub>x,y</sub> &lt; false ;</p><p><b>14</b> <i>crop</i><sup><i>t-1,c</i></sup><sub>x,y</sub> &lt; 1, ∀<i>c'</i> ∈ ζ \ {<i>c</i>}, <i>crop</i><sup><i>t-1,c'</i></sup><sub>x,y</sub> &lt; 0 ;</p><p><b>15</b> fin</p><p><b>16</b> fin</p><p><b>17</b> fin</p><p><b>18</b> fin</p><p><b>19</b> Tableau booléen <i>tree</i><sup><i>t</i></sup><sub>x,y</sub> pour identifier les unités spatiales disponibles pour les cultures;</p><p><b>20</b> ∀<i>x</i>, <i>y</i> ∈ L<sup>2</sup>, <i>t</i> ∈ T, si (<i>tree</i><sub>x,y</sub> = 1) alors <i>tree</i><sup><i>t</i></sup><sub>x,y</sub> &lt; false sinon <i>tree</i><sup><i>t</i></sup><sub>x,y</sub> &lt; true;</p><p><b>22</b> pour <i>t</i> &lt; max(<i>T</i>) à 2 faire</p><p><b>23</b> Ordre inverse des cultures entre les périodes P2 et P3;</p><p><b>25</b> si (<i>t</i> ≥ min(<i>T</i><sub>3</sub>)) alors ζ &lt; ζ3; <i>p</i> &lt; 3 sinon ζ &lt; ζ2; <i>p</i> &lt; 2;</p><p><b>26</b> pour chaque (<i>c</i> ∈ ζ) faire</p><p><b>27</b> Allouer(<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>sr</i>, <i>p</i>, <i>sr</i>);</p><p><b>29</b> si (<i>c</i> = engrais &amp; <i>t</i> &lt; max(<i>T</i>)) alors</p><p><b>30</b> Allouer(<i>q</i><sub><i>crop</i><sup><i>t-1,c</i></sup><sub><i>sr</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>sr</i>, <i>p</i> - 1, <i>sr</i>);</p><p><b>31</b> Allouer(<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub> - <i>q</i><sub><i>crop</i><sup><i>t-1,c</i></sup><sub><i>sr</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>sr</i>, <i>p</i> - 1, <i>sr</i>);</p><p><b>32</b> sinon</p><p><b>33</b> Allouer(<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>sr</i>, <i>p</i>, <i>sr</i>);</p><p><b>34</b> fin</p><p><b>35</b> Allouer(<i>q</i><sub><i>crop</i><sup><i>t,c</i></sup><sub><i>sr</i></sub></sub>, <i>t</i>, <i>c</i>, <i>p</i>, <i>sr</i>, <i>p</i>, <i>sr</i>);</p><p><b>36</b> fin</p><p><b>37</b> fin</p></td></tr></tbody></table>
horizontale des cultures. De plus, nous attribuons les cultures selon un ordre inverse entre les périodes P2 et P3 afin de favoriser la rotation des cultures (Figure 2.6 et Algorithme 1 ligne 25).

En utilisant ce schéma de construction plutôt qu'une recherche de positions pour chacune des cultures par exemple, nous simplifions la complexité temporelle de l'algorithme. Celle-ci est en $O(xyT\zeta)$. Le temps d'exécution pour les plus grandes instances (quelques secondes) reste insignifiant en comparaison du temps de résolution du problème MILP.

<figure><img src="image_12.png" /><figcaption>FIGURE 2.6. Règles de construction d'un plan d'allocation complet. Ordre inverse des pas de temps à partir de la saison automne de la période P3 pour satisfaire les contraintes d'égalité / d'inégalité des cultures qui durent deux saisons. Ordre inverse des cultures entre les périodes P2 et P3 pour favoriser la rotation des cultures.</figcaption></figure>

### 3. RÉSULTATS ET DISCUSSIONS

Dans cette section, nous présentons les résultats et leur analyse. Les expérimentations numériques ont été réalisées avec deux logiciels d'optimisation commerciaux, CPLEX (méthode exacte de type Branch-and-Bound) et LOCALSOLVER (recherche locale de type recuit simulé). Le paramétrage utilisé est celui par défaut.

#### 3.1. CHOIX DES INSTANCES ET RÉSULTATS COMPARATIFS

Pour évaluer l'impact des interactions aériennes et souterraines, nous avons considéré trois scénarios :

* *Above* qui donne une grande importance aux interactions aériennes, à savoir le positionnement des cultures à l'ombre ou au soleil. Dans ce scénario, nous multiplions les coûts associés aux interactions aériennes (valeurs A, Table 2.3) par 10.

* *Below* qui accorde une importance significative aux interactions souterraines, notamment la compétition ou le partage des ressources en eau. Dans ce scénario, nous multiplions les coûts associés aux interactions souterraines (valeurs B, Table 2.3) par 10.
* *Equilibrate* est un intermédiaire entre les deux scénarios *Above* et *Below*, il correspond à un compromis entre les différentes interactions sans en privilégier aucun type (valeurs conservées telles quelles, Table 2.3).

Afin de mieux appréhender les limites des logiciels d'optimisation, pour chacun des scénarios, nous avons conçu trois modèles avec une complexité croissante en terme de contraintes et de relation entre les variables. Le modèle *Basic* où nous optimisons l'objectif principal (2.6) sur les interactions sans les contraintes (2.20) sur la rotation des cultures ni le critère sur la dispersion (2.7). Le modèle *Rotate* qui est équivalent au modèle *Basic* avec les contraintes sur la rotation des cultures, et le modèle *Dispersion* équivalent au modèle BQP complet. Nous avons présenté les résultats de ces modèles dans [38], obtenus avec le solveur CPLEX v12.6.32. Le calcul a été effectué en utilisant 32 cœurs d'un processeur AMD Opteron 6176 à 2,3 GHz, avec 378 Go de RAM. Malgré le nombre important de processeurs, la résolution reste lente pour des petites tailles de grille. La table 3.1 présente le temps réel mis par CPLEX pour trouver les optima des différents modèles pour une grille de taille 10 × 10.

<table><caption>TABLE 3.1. Temps mis par CPLEX v12.6.32 utilisant 32 cœurs pour résoudre les modèles BQP relaxés de taille 10 × 10 (†: gap restant d'optimalité d'environ 3 %).</caption><thead><tr><th colspan="3">Equilibrate</th><th colspan="3">Above</th><th colspan="3">Below</th></tr><tr><th>Basic</th><th>Rotation</th><th>Dispersion</th><th>Basic</th><th>Rotation</th><th>Dispersion</th><th>Basic</th><th>Rotation</th><th>Dispersion</th></tr></thead><tbody><tr><td>31h57</td><td>71h40</td><td>†238h55</td><td>00h10</td><td>00h23</td><td>46h03</td><td>00h32</td><td>04h32</td><td>71h40</td></tr></tbody></table>

D'après la table 3.1, la résolution du scénario *Equilibrate* est beaucoup plus lente que celle des scénarios *Above* et *Below*, vu que le premier doit équilibrer l'optimisation des interactions aériennes et souterraines, contrairement aux deux derniers qui donnent de l'importance à un seul type d'interaction. Concernant les modèles, nous observons une différence significative entre le modèle *Dispersion* et les modèles *Basic* et *Rotate*. Par conséquent, dans le suite de ce travail, nous avons décidé de ne garder que le modèle BQP *Basic* et de comparer son temps de résolution par rapport à celui du modèle MILP en faisant varier la taille de la grille de 4 × 4 à 20 × 20 (Figure 3.1). Notons que ces deux modèles expriment le même problème (mêmes optima).

Les expérimentations présentées dans la figure 3.1 ont été faites avec CPLEX v12.7 qui utilise la décomposition de Benders automatique pour le modèle MILP et les options par défaut pour le modèle BQP excepté une sauvegarde de l'arbre de recherche sur disque et l'utilisation de 4 cœurs d'un processeur Intel Xeon CPU E5-2680 à 2,5 GHz, avec 256 Go de RAM. Nous remarquons que l'approche MILP est bien plus rapide que l'approche BQP de plusieurs ordres de magnitude sur tous les scénarios.

De la même manière, les résultats obtenus sur l'instance *Equilibrate* pour une taille réaliste de 50×50 pour une résolution limitée à 3 600 secondes en utilisant seulement 10 cœurs ont montré que le modèle MILP fournit le meilleur résultat (valeur de l'objectif égal à 112 490). LOCALSOLVER v7.0 appliqué sur le modèle quadratique BQP *Basic*
<figure><img src="image_13.png" /><figcaption>FIGURE 3.1. Temps mis par CPLEX v12.7 utilisant 4 cœurs pour résoudre les trois scénarios avec les modèles BQP *Basic* et MILP.</figcaption></figure>

trouve une solution (118 850) meilleure que celle trouvée par CPLEX pour le modèle BQP *Basic* (349 050) et proche de celle du modèle MILP.

Ces résultats nous montrent que le modèle MILP est bien plus facile à résoudre que le modèle BQP et permet de trouver en temps limité des solutions de meilleure qualité qu'une recherche locale pour une taille de problème réaliste. Rappelons que le modèle MILP permet de définir l'emplacement des arbres dans la parcelle et la quantité des cultures à planter dans les zones de présence ou d'absence de l'ombre et des racines des arbres, sans préciser l'emplacement de plantation des cultures maraîchères comme dans le modèle BQP. Cela explique la différence significative en nombre de variables et de contraintes entre MILP et BQP, qui joue un rôle important lors de la résolution. Par exemple, le modèle MILP sur l'instance de taille 50 × 50 contient 12 500 variables binaires, 276 variables réelles et 22 826 contraintes alors que le modèle BQP pour la même instance nécessite 582 147 variables binaires et 244 396 contraintes.

## 3.2. DISCUSSION ET VISUALISATION DES SOLUTIONS

Pour la résolution du problème de conception de verger-maraîcher, nous avons décidé de ne garder que le modèle BQP *Basic* et le modèle MILP c'est-à-dire sans optimiser la dispersion et sans considérer les contraintes sur la rotation des cultures. Nous avons choisi des modèles avec des tailles de parcelles (10 × 10), (15 × 15), (20 × 20), (30 × 30) et (50 × 50) dans les scénarios *Equilibrate*, *Above* et *Below*.

Pour chaque scénario testé, nous analysons les solutions obtenues en termes du nombre d'arbres, de la mixité des cultures maraîchères, et de leur positionnement par rapport aux zones d'interaction délimitées autour des arbres. Pour cette analyse, nous considérons les solutions optimales trouvées pour une parcelle de taille 10 × 10. Il
s'agit des solutions obtenues par CPLEX avec le modèle BQP. La figure 3.2 représente, pour chaque scénario, la position des arbres et la répartition des cultures aux périodes P2 et P3. Pour la période P1, nous considérons que les arbres n'ont pas d'influence hors de leurs propres unités spatiales.

En regardant la figure 3.2, nous remarquons que les trois représentations respectent les contraintes modélisées, comme l'espace minimal entre les arbres (selon Figure 2.1) et les dates et durées de plantation des cultures maraîchères. La grande différence entre les trois scénarios consiste dans le nombre et la position des arbres (18 arbres pour Above, 21 pour Below et 24 pour Equilibrate). Dans le scénario Above, les interactions liées à l'ombre sont plus coûteuses que les autres. Pour avoir moins d'unités spatiales à l'ombre, la solution retenue comporte moins d'arbres. Cela permet de réduire le coût lié aux interactions aériennes de valeurs négatives (valeurs A, Table 2.3). Nous remarquons la présence de quatre arbres espacés. Cela a pour objectif d'assurer un nombre suffisant d'unités spatiales à l'ombre pour les cultures qui en bénéficient comme la salade. De manière similaire, dans le scénario Below, les interactions liées à la présence de racines sont les plus coûteuses. Les arbres sont donc regroupés pour avoir moins d'unités spatiales liées aux interactions souterraines de coût négatif. Par exemple, les cultures qui sont en compétition pour l'eau avec les racines des arbres sont attribuées avec des quantités minimales. Par exemple, 12 unités pour la tomate (contre 24 dans le scénario Above). Concernant le scénario Equilibrate qui correspond à un compromis entre les interactions aériennes et souterraines, la topologie des unités spatiales est équilibrée entre à l'ombre, au soleil avec ou sans racines. Il s'agit d'un intermédiaire entre les solutions des deux autres scénarios, des arbres tassés regroupés et d'autres espacés.

Cependant, si ces solutions respectent bien les contraintes agronomiques posées, elles se caractérisent par une division de l'espace entre une zone de mixité arbres-cultures (ce qui était recherché) au Nord et une zone de cultures pures au Sud, où sont placées les cultures qui ne bénéficient pas des interactions. Au regard de nos objectifs initiaux, ces solutions ne sont donc pas réellement satisfaisantes, et sont d'ailleurs contredites par la pratique, les agriculteurs gérant des vergers-maraîchers n'hésitant pas à placer ces cultures au sein des zones arborées.

La figure 3.3 représente la meilleure solution trouvée avec le modèle MILP pour une taille de 50×50. La solution comprend 800 arbres qui représentent 32 % de la parcelle, le reste étant attribué aux cultures maraîchères. Bien que le modèle MILP ne permette pas de définir le positionnement exact des cultures, en appliquant l'Algorithme 1, nous avons obtenu une représentation qui tente de regrouper les cultures par espèce et d'appliquer la rotation de cultures pour préserver les propriétés du sol, i.e. ne pas planter la même culture au même endroit pendant deux périodes successives. On constate que contrairement aux solutions précédentes, la zone arborée s'étend sur la quasi-totalité de la parcelle, répondant ainsi à nos objectifs initiaux. L'assolement sur deux ans, les cultures placées en zone arborée et l'extension de cette zone sont ici plus proches des pratiques réelles.
### Scénario Above 10 × 10

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

### Scénario Below 10 × 10

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

### Scénario Equilibrate 10 × 10

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

FIGURE 3.2. Représentations d'une parcelle de taille 10 × 10 (solutions optimales du modèle BQP *Basic*) aux périodes P2 et P3 pour les trois scénarios *Above*, *Below* et *Equilibrate*.
<figure><img src="image_17.png" /><figcaption>Scénario *Equilibrate* 50 × 50 (meilleure solution trouvée : 84 960)</figcaption></figure>

FIGURE 3.3. Représentation de la meilleure solution trouvée (modèle MILP et Algorithme 1) par CPLEX v12.8 avec 30 cœurs durant 3600 secondes pour la conception d'une parcelle de verger-maraîcher de taille 50 × 50 aux périodes P2 et P3 dans le scénario *Equilibrate*.

## 4. CONCLUSION

Contrairement aux approches existantes sur l'allocation de cultures annuelles dans les systèmes agroforestiers, nous avons proposé différents modèles de conception d'un système de verger-maraîcher, associant des cultures saisonnières et des cultures pérennes. Nous avons explicitement décrit les modèles conceptuels et mathématiques, en détaillant l'optimisation des effets positifs et négatifs des interactions potentielles générées par la combinaison des arbres et des cultures.

Malgré la taille importante (nombre de variables et de contraintes) du problème de conception de verger-maraîcher notamment pour des parcelles de taille réaliste (50 × 50), nous avons obtenu des solutions approchées d'assez bonne qualité en temps raisonnable. Les meilleurs résultats ont été obtenus par CPLEX avec la méthode de décomposition de Benders appliquée sur le modèle linéaire mixte, dépassant une méthode de recherche locale. L'exploitation des symétries au niveau du problème maître (i.e. conduisant aux mêmes nombres d'arbres et d'unités spatiales à l'ombre et en racines) est une possible piste d'amélioration pour la résolution du modèle MILP.

Il serait intéressant de développer et tester d'autres approches de recherche locale permettant d'offrir des solutions de bonne qualité en temps relativement court de
manière à pouvoir interagir avec l'utilisateur dans ses choix de modélisation et enrichir
le modèle avec un plus grand choix de légumes et d'arbres fruitiers. Par ailleurs
l'utilisation de méta-heuristiques travaillant sur une population de solutions permettrait
d'étudier la diversité des solutions optimales ou proches de l'optimum.

BIBLIOGRAPHIE

[1] M. AKPLOGAN, S. DE GIVRY, J.-P. METIVIER, G. QUESNEL, A. JOANNON & F. GARCIA, « Solving the crop allocation problem using hard and soft constraints », *RAIRO-Operations Research* **47** (2013), n° 2, p. 151-172.

[2] L. ALFANDARI, J.-L. LEMALADE, A. NAGIH & G. PLATEAU, « A MIP flow model for crop-rotation planning in a context of forest sustainable development », *Annals of operations research* **190** (2011), n° 1, p. 149-164.

[3] L. ALFANDARI, A. PLATEAU & X. SCHEPLER, « A branch-and-price-and-cut approach for sustainable crop rotation planning », *European Journal of Operational Research* **241** (2015), n° 3, p. 872-879.

[4] D. ATKINSON, « The growth, activity and distribution of the fruit tree root system », *Plant and Soil* **71** (1983) (en), p. 23-35.

[5] D. R. BATISH, R. K. KOHLI, S. JOSE & H. P. SINGH, *Ecological Basis of Agroforestry*, CRC press/taylor&francis éd., CRC Press, 11 2007 (english).

[6] J. F. BENDERS, « Partitioning procedures for solving mixed-variables programming problems », *Nume-rische mathematik* **4** (1962), n° 1, p. 238-252.

[7] E. F. BOLLER, C. MALAVOLTA, E. JORG & I. O. FOR BIOLOGICAL CONTROL OF NOXIOUS ANIMALS AND PLANTS (éd.s.), *Guidelines for integrated production of arable crops in Europe, Wadenswil, Switzerland, 12-13 April 1997 : IOBC Technical guideline III*, 1st ed éd., IOBC / wprs bulletin = Bulletin OILB / srop, n° v. 20,5, International Organization for Biological and Integrated Control of Noxious Animals and Plants, West Palaearctic Region Section, Avignon, France, 1997 (en), OCLC : ocm45523124.

[8] N. BRULARD, « Outils d'aide à la conception de systèmes de production maraîchers urbains optimisés pour la vente en circuits courts et de proximité », Theses, Communauté Université Grenoble Alpes, I 2018.

[9] N. BRULARD, V.-D. CUNG & N. CATUSSE, « Conception de systèmes de production agricoles urbains optimisés pour la vente en circuits courts et de proximité », in *ROADEF 2015, 16ème congrès de la Société Française de Recherche Opérationnelle et d'Aide à la Décision*, 2015.

[10] J. F. BRUNO, J. J. STACHOWICZ & M. D. BERTNESS, « Inclusion of facilitation into ecological theory », *TRENDS in Ecology and Evolution* **18** (2003), p. 15-29.

[11] S. CHETTY & A. O. ADEWUMI, « Comparison Study of Swarm Intelligence Techniques for the Annual Crop Planning Problem », *IEEE Transactions on Evolutionary Computation* **18** (2014), n° 2, p. 258-268.

[12] C. COULON, F. AND DUPAZ, F. LIAGRE & P. POINTEREKAU, « Étude des pratiques agroforestières associant des arbres fruitiers de haute tige à des cultures ou des pâtures », Rapport de fin de contrat rédigé à la demande du ministère de l'aménagement et du teritoire et de l'environnement, Ministère de l'Aménagement et du Territoire et de l'Environnement, 2000.

[13] J. E. DAVIS & J. M. NORMAN, « Effects of Shelter on Plant Water Use », *Agriculture, Ecosystems and Environment* **393** (1988), p. 393-402.

[14] N. K. DETLEFSEN & A. L. JENSEN, « Modelling optimal crop sequences using network flows », *Agricultural Systems* **94** (2007), n° 2, p. 566-572.

[15] S. DOGLIOTTI, M. K. VAN ITTERSUM & W. A. H. ROSSING, « A method for exploring sustainable development options at farm scale : a case study for vegetable farms in South Uruguay », *Agricultural Systems* **86** (2005), n° 1, p. 29-51.

[16] C. DOUCET, S. E. WEAVER, A. S. HAMILL & J. ZHANG, « Separating the effects of crop rotation from weed management on weed density and diversity », *Weed science* **47** (1999), p. 729-735.
[17] C. DUPRAZ & F. LIAGRE, *L'agroforesterie : une voie de diversification écologique de l'agriculture européenne?*, Cahier d'étude DEMETER - Économie et Stratégies agricoles, 2006.

[18] C. DUPRAZ & F. LIAGRE, *Agroforesterie : Des arbres et des cultures*, Editions France Agricole, 2ème éd., 2011 (français).

[19] J. DURY, N. SCHALLER, F. GARCIA, A. REYNAUD & B. J. E., « Models to support cropping plan and crop rotation decisions. A review », *Agron. Sustain. Dev* **32** (2012), n° (2) (english), p. 567-580.

[20] M. P. EICHHORN, P. PARIS, F. HERZOG, D. INCOLL, F. LIAGRE, K. MANTZANAS, M. MAYUS, G. MORENO, V. P. PAPANASTASIS, D. J. PILBEAM, A. PISANELLI & C. DUPRAZ, « Silvoarable Systems in Europe - Past, Present and Future Prospects », *Agroforestry Systems* **67** (2006), p. 29-50.

[21] M. P. EICHHORN, P. PARIS, F. HERZOG, L. D. INCOLL, F. LIAGRE, K. MANTZANAS, M. MAYUS, G. MORENO, V. P. PAPANASTASIS, D. J. PILBEAM, A. PISANELLI & C. DUPRAZ, « Silvoarable Systems in Europe - Past, Present and Future Prospects », *Agroforestry Systems* **67** (2006), n° 1 (en), p. 29-50.

[22] C. FILIPPI, R. MANSINI & E. STEVANATO, « Mixed integer linear programming models for optimal crop selection », *Computers & Operations Research* **81** (2017), p. 26-39.

[23] A. GALÁN-MARTÍN, C. POZO, G. GUILLÉN-GOSÁLBEZ, A. ANTÓN VALLEJO & L. JIMÉNEZ ESTELLER, « Multi-stage linear programming model for optimizing cropping plan decisions under the new Common Agricultural Policy », *Land Use Policy* **48** (2015), p. 515-524.

[24] J. J. GLEN, « Mathematical models in farm planning : a survey », *Operations Research* **35** (1987), n° 5, p. 641-666.

[25] J. GRIFFITHS, D. S. PHILLIPS, S. G. COMPTON, C. WRIGHT & L. D. INCOLL, « Responses of slug numbers and slug damage to crops in a silvoarable agroforestry landscape », *Journal of applied ecology* **35** (1998), p. 252-260.

[26] A. P. GUPTA, R. HARBOE & M. T. TABUCANON, « Fuzzy multiple-criteria decision making for crop area planning in Narmada river basin », *Agricultural Systems* **63** (2000), n° 1, p. 1-18.

[27] W. K. HANEVELD & A. W. STEGEMAN, « Crop succession requirements in agricultural production planning », *European Journal of Operational Research* **166** (2005), n° 2, p. 406-429.

[28] E. O. HEADY, « The Economics of Rotations with Farm and Production Policy Applications », *Journal of Farm Economics* **30** (1948), n° 4, p. 645-664.

[29] ———, « Simplified Presentation and Logical Aspects of Linear Programming Technique », *Journal of Farm Economics* **36** (1954), n° 5, p. 1035-1048.

[30] F. HERZOG, « Streuobst : a traditional agroforestry system as a model for agroforestry development in temperate Europe », *Agroforestry Systems* **42** (1998), p. 61-80.

[31] A. F. HUNTER & L. W. AARSSEN, « Plants Helping Plants. », *BioScience JSTOR* **38** (1988), p. 34-40.

[32] T. ITOH, H. ISHI & T. NANSEKI, « A model of crop planning under uncertainty in agricultural management », *International Journal of Production Economics* **81-82** (2003), p. 555-558.

[33] S. JOSE, A. R. GILLESPIE & S. G. PALLARDY, « Interspecific interactions in temperate agroforestry », in *New Vistas in Agroforestry*, Springer, 2004, p. 237-255.

[34] A. KAESER, F. SEREKE, D. DUX, F. HERZOG & A. R. T. RECKENHOLZ-TÄNIKON, « Agroforesterie moderne en Suisse », Tech. report, Station de recherche Agroscope Reckenholz-TÄnikon, 2010.

[35] B. LETEINTURIER, J. L. HERMAN, F. D. LONGUEVILLE, L. QUINTIN & R. OGER, « Adaptation of a crop sequence indicator based on a land parcel management system », *Agriculture, Ecosystems & Environment* **112** (2006), n° 4, p. 324-334.

[36] E. MALÉZIEUX, « Designing cropping systems from nature », *Agron. Sustain. Dev* **32** (2012), p. 15-29.

[37] S. MAQROT, S. DE GIVRY, G. QUESNEL & M. TCHAMITCHIAN, « Designing mixed fruit-vegetable cropping systems by integer quadratic programming », in *Acta Horticulturae*, International Society for Horticultural Science (ISHS), Leuven, Belgium, 11 2017, p. 265-274.

[38] S. MAQROT, S. DE GIVRY, G. QUESNEL & M. TCHAMITCHIAN, « Designing mixed fruit-vegetable cropping systems by integer quadratic programming », in *8th International Congress on Environmental Modelling and Software (iEMSS)* (toulouse, France), vol. 2, 7 2016, p. 8 p.

[39] S. MAQROT, S. DE GIVRY, G. QUESNEL & M. TCHAMITCHIAN, « A Mixed Integer Programming Reformulation of the Mixed Fruit-Vegetable Crop Allocation Problem », in *Advances in Artificial Intelligence* :
*From Theory to Practice*, Lecture Notes in Computer Science, Springer, Cham, 6 2017, p. 237-250 (en).

[40] B. A. McCARL, W. V. CANDLER, D. H. DOSTER & P. R. ROBBINS, « Experiences with farmer oriented linear programming for crop planning », *Canadian Journal of Agricultural Economics/Revue canadienne d'agroéconomie* **25** (1977), n° 1, p. 17-30.

[41] A. NEVO, R. OAD & T. H. PODMORE, « An integrated expert system for optimal crop planning », *Agricultural Systems* **45** (1994), n° 1, p. 73-92.

[42] G. NIU, Y. P. LI, G. H. HUANG, J. LIU & Y. R. FAN, « Crop planning and water resource allocation for sustainable development of an irrigation region in China under multiple uncertainties », *Agricultural Water Management* **166** (2016), p. 53-69.

[43] M. VAN NOORDWIJK, G. LAWSON, K. HAIRIAH & J. WILSO, *Root distribution of trees and crops : competition and/or complementarity*, tree-crop interactions : agroforestry in a changing climate. cabi, wallingford, uk éd., CAB International, 1996, 221-257 pages.

[44] C. K. ONG, J. E. CORLETT, R. P. SINGH & C. R. BLACK, « Above and below ground interactions in agroforestry systems », *Agroforestry Systems* **45** (1991), p. 45-57.

[45] J. W. PALMER, « Diurnal Light Interception and a Computer Model of Light Interception by Hedgerow Apple Orchards », *Journal of Applied Ecology* **14** (1997), p. 601-614.

[46] R. RAHMANIANI, T. G. CRAINIC, M. GENDREAU & W. REI, « The Benders Decomposition Algorithm : A Literature Review », *European Journal of Operational Research* (2016), p. 801-817.

[47] L. M. R. SANTOS, P. MUNARI, A. M. COSTA & R. H. S. SANTOS, « A branch-price-and-cut method for the vegetable crop rotation scheduling problem with minimal plot sizes », *European Journal of Operational Research* **245** (2015), p. 581-590.

[48] R. A. SARKER & M. A. QUADDUS, « Modelling a nationwide crop planning problem using a multiple criteria decision making tool », *Computers & Industrial Engineering* **42** (2002), n° 2, p. 541-553.

[49] R. SARKER & T. RAY, « An improved evolutionary algorithm for solving multi-objective crop planning models », *Computers and Electronics in Agriculture* **68** (2009), n° 2, p. 191-199.

[50] L. N. SETHI, S. N. PANDA & M. K. NAYAK, « Optimal crop planning and water resources allocation in a coastal groundwater basin, Orissa, India », *Agricultural Water Management* **83** (2006), n° 3, p. 209-220.

[51] S. SIMON, J. BOUVIER, J. DEBRAS & B. SAUPHANOR, « Biodiversity and pest management in orchard systems. A review », *Agronomy for Sustainable Development* **30** (2010), p. 139-152.

[52] P. TAILLANDIER, O. THEROND & B. GAUDOU, « A new BDI agent architecture based on the belief theory. Application to the modelling of cropping plan decision-making », in *International environmental modelling and software society (iEMSs)*, 2012.

[53] G. TSAKIRIS & M. SPILIOTIS, « Cropping pattern planning under water supply from multiple sources », *Irrigation and Drainage Systems* **20** (2006), n° 1 (en), p. 57-68.

[54] G. VERCAMBRE, L. PAGÈS, C. DOUSSAN & R. HABIB, « Architectural analysis and synthesis of the plum tree root system in an orchard using a quantitative modelling approach », *Plant and Soil* **251** (2003), n° 1, p. 1-11.

[55] J. E. WEAVER & W. E. BRUNER, *Root Development Of Vegetable Crops Ist Edn.*, Mcgraw-Hill Book Co.; London, 1927.

**ABSTRACT.** — Mixed fruit-vegetable cropping systems are a promising way of ensuring environmentally sustainable agricultural production systems in response to the challenge of being able to fulfill local market requirements. They combine productions and make a better use of biodiversity. These agroforestry systems are based on a complex set of interactions modifying the utilization of light, water and nutrients. Thus, designing such systems requires to optimize the use of these resources : by maximizing positive interactions (facilitations) and minimizing negative ones (competitions). To reach these objectives, the system's design has to include the spatial and temporal dimensions, taking into account the evolution of above- and belowground interactions over a time horizon.
For that, we define the mixed fruit-vegetable cropping allocation problem using a discrete representation of the land and the interactions between vegetable crops and fruit trees. We propose two formulations of the problem, using Binary Quadratic Programming (BQP) and Mixed Integer Linear Programming (MILP), obtaining first results on realistic problem sizes. Models are available at https://miat.inrae.fr/degivry/ROIA21.zip.

KEYWORDS. — Agroecology, spatial and temporal crop allocation problem, discrete optimization, mathematical programming.

Manuscrit reçu le 30 mars 2021, révisé le 15 juillet 2021, accepté le 1er septembre 2021.