Large-Scale Assortment Optimization

Nous présentons dans ce mémoire une solution au problème d'optimisation d'assortiment. Ce problème consiste à choisir, au sein d'un ensemble de produits, le sous-ensemble générant le revenu espéré le plus élevé pour le détaillant. Le fait qu'il existe un nombre exponentiel d'assortiments de produits possibles rend ce problème difficile-et intéressant. En effet, l'énumération explicite des assortiments est impossible en pratique dès que l'on dépasse la vingtaine de produits. Notre but est de fournir un procédé d'aide à la décision pour l'optimisation d'assortiment basé sur les données. Dans cette perspective, la première étape naturelle est de proposer un modèle permettant de rendre compte des comportements des consommateurs. Nous nous intéressons aux modèles de choix basés sur les classements des produits, qui consistent à apprendre une distribution de probabilité sur l'ensemble des classements possibles des produits. En effet, la structure de ces modèles de choix permet une modélisation efficace du problème d'optimisation d'assortiment, dans la forme d'un problème d'optimisation linéaire. Les solveurs classiques permettent de les résoudre pour des instances de taille industrielle. Cependant, le principal inconvénient de ces modèles de choix est leur lenteur d'apprentissage. Ceci est dû au nombre factoriel de classements envisageables. L'apprentissage repose, dans l'état de l'art, sur un modèle de génération de colonnes dont la taille de l'espace des classements rend l'apprentissage du modèle de choix particulièrement long. Pour accélérer l'apprentissage du modèle de choix, nous avons remarqué qu'il était possible, moyennant une adaptation du modèle de choix, de munir l'espace des classements d'une structure forte, permettant de hiérarchiser les classements dans un arbre de décision. Ainsi, nous avons défini un nouveau modèle de choix reposant sur la notion d'indifférence : plutôt que de ne considérer que des séquences classant chacun de produits, nous acceptons aussi les classements partiels de produits. Ceci signifie que nous nous autorisons à considérer des comportements de consommateurs qui, à-partir d'un certain point, sont indifférents entre les produits restants. Cette relaxation de la définition d'une séquence de produits nous permet d'accélérer considérablement la recherche de nouvelles séquences, dans l'algorithme de génération de colonnes, grâce à la structure d'arbre de l'espace. En effet, à chaque itération de la génération de colonnes, nous n'avons qu'à étendre l'arbre de décision d'un niveau supplémentaire. Nous avons appliqué ce nouvel algorithme à des données réelles, fournies par notre partenaire industriel, ainsi qu'à des données artificielles. Dans les deux cas, nous observons des gains de temps de calcul d'au moins un ordre de grandeur. Ainsi, nous devenons capables de résoudre des problèmes jusqu'à un millier de produits, alors que les algorithmes de l'état de l'art étaient limités à quelques dizaines. Ensuite, nous avons étudié une extension possible de ce problème, qui consiste à inclure des nouveaux produits sur-lesquels nous n'avons aucune donnée de transaction, dans l'optimisation d'assortiment. Ces nouveaux produits ne sont connus que par leurs caractéristiques communes avec les anciens produits, ceux sur-lesquels nous avons des données de vente. Nous avons proposé une manière d'introduire ces nouveaux produits dans le modèle de choix évoqué plus haut. Cet algorithme repose sur une mesure de similarité entre les anciens et nouveaux produits et permet de généraliser des comportements de consommateurs connus sur les anciens produits à l'ensemble des anciens et nouveaux produits. Cette extension est particulièrement intéressante pour le problème du choix d'assortiment d'une saison de vente à l'autre, puisqu'il faut prendre des décisions sur les produits de la nouvelle collection à inclure sans avoir encore observé de ventes. Par ailleurs, nous avons montré comment notre nouveau modèle de choix s'adapte au problème d'optimisation d'assortiment présent dans la littérature, ainsi qu'une manière de limiter le surapprentissage. Nous présentons enfin des résultats expérimentaux montrant l'intérêt de l'optimisation d'assortiment. Notre programme d'optimisation, sur des cas réels, propose systématiquement des assortiments plus larges (c'est-à-dire avec plus de produits) que ceux observés dans la réalité. Nous montrons ainsi l'impact d'offrir un large choix au consommateur sur le revenu espéré par le détaillant. Cependant, afin de prendre en compte les contraintes opérationnelles ainsi que la taille limitée des magasins, nous montrons que, même en incluant une contrainte limitant la capacité de l'assortiment à ce qui est observé dans les données, les revenus prédits restent plus élevés d'environ 35% à ce qui est observé dans l'ensemble de contrôle. Ceci montre donc l'impact de l'assortiment sur le choix du consommateur, mais aussi sur le revenu du détaillant. Pour finir, nous proposons une extension de notre travail pour l'élaboration d'un logiciel d'aide à la décision pour l'optimisation d'assortiment. Les dirigeants de boutiques peuvent en effet être réticents à confier l'ensemble de la décision d'optimisation d'assortiment à un logiciel, et préférer garder cette responsabilité. Il peut donc être intéressant de leur proposer un outil suggérant des modifications à la marge d'un assortiment qu'ils proposent eux-mêmes, ainsi que de leur permettre d'évaluer l'impact prédit par notre approche de chaque modification de leur assortiment.