Julien Guépet - Modèles mathématiques de gestion de revenu (Yield Management)

De Ensiwiki
Aller à : navigation, rechercher


Modèles mathématiques en gestion de revenu (Yield Management)

Labo G-Scop
Equipe Optimisation des systèmes de production / Optimisation combinatoire
Encadrants Wojciech.Bienia@g-scop.inpg.fr

Etudiant

GUEPET, Julien, MMIS/AAD


Introduction

Mon travail a consisté en l'étude (analyse et compréhension) d'une thèse sur le Yield Management (voir Références). Le but de mon travail était de me familiariser avec les méthodes de Yield Management existantes et d'en développer quelques-unes si possible. Le Yield Management est un ensemble de méthodes ayant pour but de maximiser le chiffre d'affaire généré par la vente d'un produit (d'où le terme de "gestion de revenu"). Les premières méthodes concrètes sont apparues en 1984. Elles ont été développées par la compagnie aérienne américaine DELTA Airlines, afin de lutter contre la dérégulation du transport aérien qui régnait alors. DELTA a ainsi augmenté son chiffre d'affaire annuel de 300 millions de dollars. Les méthodes du Yield Management sont basées sur trois points :

  • La segmentation de la clientèle
  • La surcharge des ventes (overbooking)
  • La variation du prix au cours de la vente (dynamic pricing)

Au cours de mes recherches, je me suis intéressé à la segmentation de la clientèle et au dynamic pricing.

Le Yield Management est né de l'industrie du transport aérien mais il peut être utilisé dans de nombreux domaines, notamment dans l'hôtellerie. Voici le cadre d'application du Yield Management :

  • hétérogénéité des clients
  • variabilité de la demande
  • inflexibilité de la production
  • périssabilité du produit

L'inflexibilité de la production signifie simplement que la production est limité et qu'on ne peut pas l'augmenter (par exemple le nombre de siège dans un avion). La périssabilité du produit signifie qu'à la fin de la vente, il n'est pas possible de réutiliser les produits non vendus (si un avion ne part pas plein, on ne peut pas récupérer les places vides pour le prochain).

Eléments de prérequis

Les prérequis pour mon travail sont assez faibles, toute personne ayant suivi les trois premiers semestres de l'Ensimag peut comprendre mes travaux. Les notions que j'utilise sont :

  • la programmation linéaire
  • la programmation dynamique

Travail réalisé

Segmentation de la clientèle

La segmentation de la clientèle est motivée par le fait suivant : tous les clients ne sont pas prêts à mettre le même prix dans un produit et n'en attendent pas la même qualité. Le principe de la segmentation de la clientèle est donc de couper la clientèle en différentes classes afin de vendre différents produits à différents prix et ainsi profiter de ce que chaque client a à offrir. La question qui se pose alors est comment segmenter. Par exemple pour un avion, cela revient à se demander combien de places doit-on réserver pour la première classe, la classe business, et la classe économique. Mon travail a consisté à implémenter et tester une méthode générale sur un cas particulier, l'exemple traité est le réseau suivant :

Reseau.png

Il y a ici deux vols (de A à C et de C à B) mais trois billets possibles (AC, CB et AB). La question à laquelle nous allons tenter de répondre est combien de places faut-il réserver dans les vols AC et CB pour les vendre en billets AB. Nous pouvons modéliser le problème par le programme linéaire suivant :

Prog lin.png

p_{XY} est le prix du billet de X à Y, c_{XY} est la capacité de l'avion allant du vol de X à Y, d_{XY} est la demande pour les billets de X à Y. On résout ici le problème de façon déterministe alors qu'en fait la demande est aléatoire. L'approximation qui est souvent faite est de modéliser la demande par l'espérance de la variable aléatoire modélisant la modélisant. Cette approximation est bonne en moyenne et assez facile à calculer ou à approcher.

Cette méthode se généralise parfaitement, i.e. on peut résoudre les problèmes de segmentation de la clientèle en résolvant le programme linéaire suivant :

Prog lin2.png

\vec{x} est le vecteur des capacités, \vec{\mu} est le vecteur des espérances de la demande pour chaque type de billet. On définit la matrice A par :

  • a_{ij}=1 si le vol i est utilisé par le produit j
  • a_{ij}=0 sinon

L'expérimentation que j'ai effectuée m'a permis de constater que les avions partent souvent non pleins, alors qu'on a refusé des ventes, les limites données par le programme linéaire ayant été atteintes. Par exemple si les bornes données par le programme linaire sont 180 pour AC, 180 pour CB et 120 pour AB (avec une capacité de 300 dans chaque avion) il peut arriver que le nombre réel de places vendues soit 179 pour AC, 179 pour CB et 120 pour AB et qu'on ait refusé des ventes en AB. J'ai alors mis en place une heuristique qui consiste à remettre en cause les bornes données par le programme linéaire afin de mieux s'adapter aux aléas de la vente. Avant de refuser une vente, on calcule l'espérance de vente dans les autres vols dans le temps restant et on compare avec le nombre de places restantes dans les avions. Si celle-ci est inférieure alors on vend la place (ce qui revient à changer les limites).

Cette heuristique ne change pas fondamentalement les résultats, mais elle permet de créer une méthode s'adaptant au cours de la vente, optimisant ainsi le remplissage de l'avion. Le pourcentage d'augmentation du chiffre d'affaire par rapport à la méthode sans remettre en cause les bornes est assez faible, mais reporté sur le chiffre d'affaire annuel de grandes compagnies, cela représente une somme non négligeable.

Dynamic Pricing

Le dynamic pricing est motivé par les constatations suivantes :

  • plus un client a besoin d'un produit, plus il est prêt à le payer cher.
  • plus un client achète une place tôt, plus il a de chance de l'annuler avant le jour du départ.

Il parait donc interéssant de faire varier le prix au cours de la vente afin de vendre tous les produits tout en maximisant le prix de vente. Afin d'illustrer ce principe, on peut observer les courbes suivantes :

Dyn.png

La figure de gauche représente la demande en fonction du prix (ce n'est qu'un exemple). Choisir un prix revient à fixer la demande, le chiffre d'affaire réalisé est alors égal à l'aire sous le rectangle (en bleu sur la figure du milieu). L'idée du Dynamic pricing est d'utiliser plusieurs prix au cours de la vente afin de réaliser plusieurs rectangles, i.e. réaliser un meilleur chiffre d'affaire.

La question qui se pose alors est de choisir le prix afin d'optimiser le chiffre d'affaire. Je me suis intéressé au cas où on ne considère qu'un seul produit. Mon travail m'a amené à modéliser le problème de Dynamic pricing de la façon suivante :

  • On discrétise la dimension du temps (t=1..T)
  • On considère un nombre fini de prix possibles (on appellera \Omega_p l'ensemble des prix)
  • On suppose que la demande ne dépend que du temps et du prix (d(t,p))

L'avantage de telles hypothèses est qu'on peut utiliser l'historique des ventes (i.e. les ventes antérieures et similaires) pour prédire la demande à l'aide de méthodes statistiques. On peut alors formuler notre problème comme le problème d'optimisation suivant :

Opti.png

où p est le vecteur des prix que nous cherchons à déterminer, C est la capacité à ne pas dépasser (exemple : le nombre de places dans un avion), et d la demande. On peut résoudre ce problème par programmation dynamique avec l'équation de Bellman suivante :

Prog dyn.png

La résolution de ce programme dynamique est en O(TNd) où N est le cardinal de \Omega_p et d la demande moyenne, ce qui est donc efficace. Remarquons que si on utilise un marquage pour se rappeler des choix qui sont faits, cette méthode nous donne non seulement le prix pour toutes dates t mais aussi le nombre de places qu'il faut vendre à ce prix. Mais là encore cette méthode ne s'adapte pas à la variation de la demande. Pour palier à ceci, il suffit de refaire le calcul après chaque période de vente t en enlevant les places déjà vendues. Cela permet au modèle de réagir aux aléas de la demande à chaque période. Le coût d'une telle méthode est alors en O(T^2Nd), cependant chaque calcul étant effectué à la fin d'une période de vente, cette augmentation n'est pas gênante (coût amorti en O(TNd)).

Conclusion

Toutes les méthodes énoncées dans cette page ont été implémentées et testées. Les conclusions de ces tests sont que ces méthodes sont efficaces du point de vue du temps de calcul, et offre de bons résultats du point de vue du chiffre d'affaire (voir le rapport pour plus de précisions sur l'implémentation et les tests). Cependant je n'ai pas eu le temps d'étudier le couplage des deux principes (segmentation et dynamic pricing). Je propose une généralisation du programme dynamique de dynamic pricing afin de faire ce couplage (voir transparent de présentation oral 23/26, lien en bas de page), mais elle est de coût exponentiel en le nombre de classes de clientèle considérées (O(TN^nd) où n est le nombre de classes). J'aurais aimé étudié une heuristique qui consiste à segmenter la clientèle dans un premier temps et faire le dynamic pricing sur chaque classe ensuite. Ceci permet de revenir à des temps de calcul raisonnables, mais l'optimalité du résultat n'est plus garantie. J'aurais particulièrement voulu étudier l'écart à la solution optimale.

Références

  • Pricing and Revenue Management, thèse de Roy KEACH, Instut de Mathématiques de l'Ecole Polytechnique Fédérale de Lausanne

Documents additionnels