Retour aux résultats
Documents de travail (2014), ESSEC Business School

A Branch-and-Price-and-Cut Approach for Sustainable Crop Rotation Planning

ALFANDARI Laurent , PLATEAU A., SCHEPLER X.

Nous étudions un problème de planification de production agricole multi-périodique. Ce problème appartient à la classe des problèmes de planification de rotations culturales, qui ont été particulièrement étudiés dans la littérature ces dernières années. Il consiste à alterner des périodes de cultures et de jachères sur un sous-ensemble de parcelles et sur un horizon de temps donné, de manière à minimiser l'espace agricole requis pour satisfaire les demandes de chaque culture à chaque saison. Nous montrons que ce problème est NP-difficile. Nous proposons une formulation compacte de type Programmation Linéaire en variables 0-1, basée sur des graphes de séquences. Une formulation étendue est ensuite présentée, et un algorithme de Branch-and-Cut-and-Price (BPC) basé sur cette formulation est proposé, avec un sous-problème de pricing polynomial, des règles de branchement ad-hoc et des coupes associées aux contraintes de couverture des demandes. Ceci constitue le premier algorithme de BPC de la littérature pour les problèmes de construction de rotations agricoles. Les expériences numériques sur des instances faisant varier le nombre de cultures, de périodes et de parcelles, montrent l'efficacité de l'approche BPC sur la formulation étendue comparée à la résolution de la formulation compacte, bien que ces deux formulations fournissent la même borne pour la relaxation continue.

ALFANDARI, L., PLATEAU, A. and SCHEPLER, X. (2014). A Branch-and-Price-and-Cut Approach for Sustainable Crop Rotation Planning. ESSEC Business School.

Mots clés : #Agriculture, #Branch, #and, #Price, #and, #Cut, #Génération-de-colonnes, #Planification-de-production, #Recherche-opérationnelle, #Rotations-culturales