Séminaire Xavier Schepler

Jeudi 22 Novembre 2012 (14h00 (Salle G001))

Xavier Schepler, Laboratoire LITIS, Université du Havre.

Titre : Un algorithme de Branch-and-Price pour le problème de planification durable de rotations culturales.

Résumé : Nous nous intéressons à une application de la Recherche Opérationnelle à l’agriculture: le problème de planification durable des rotations culturales. Ce problème, défini dans la littérature, consiste à couvrir des demandes saisonnières en diverses cultures sur un horizon de temps donné, tout en minimisant l’espace agricole requis.

La rotation culturale est une pratique qui consiste à alterner des périodes de cultures et de jachères et permet de maintenir des rendements satisfaisants avec des engrais naturels en préservant les sols. Dans le problème considéré ici, l’espace agricole est divisé en parcelles de taille identique, et l’objectif revient à minimiser le nombre de parcelles utilisées en associant à chacune d’elles un plan de rotations culturales sur l’horizon fixé. Le problème est noté MSCRP (Minimum Space Crop Rotation Planning). Contrairement au problème tel que traité dans la littérature, nous n’imposons pas de recultiver la parcelle après un certain nombre de périodes de jachère, et les variables de production sont binaires, i.e., à une période donnée, soit la parcelle est complètement cultivée d’une seule et même culture, soit elle est en jachère. Nous démontrons la NP-complétude du problème MSCRP. Nous proposons ensuite une formulation de type Programmation Linéaire en Variables 0-1, plus compacte que les modèles présentés dans la littérature. Une décomposition de type Dantzig-Wolfe est introduite pour résoudre la relaxation linéaire du problème par génération de colonnes, et un algorithme de branch-and-price est présenté. Un schéma de branchement basé sur le théorème de décomposition des flots est introduit. Finalement, nous montrons l’efficacité de la méthode par des résultats numériques sur des instances générées aléatoirement.