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.

Abstract

This thesis is concerned with assortment optimization. The problem of assortment optimization consists in choosing, among a set of n products available to the retailer, the subset that is most likely to result in the highest revenue. However, the exponential number of possible assortments makes it intractable to evaluate all of them, when twenty or more products are available. In the perspective of data-driven assortment optimization, we propose to learn the transaction data, based on the ranking-based choice models. These models assume that customer préférences can be modelled as ranked sequences of the products. The intrinsic structure of such a choice model allows an efficient formulation of the assortment optimization problem, in form of a mixed-integer optimization problem that can be easily solved by mathematical solvers. Nevertheless, the training of such choice models scales poorly with the number of products. Classical approaches are based on a column generation algorithm to deal with the factorially large number of possible product sequences. In practice, this is intractable even for small numbers of products. We therefore propose a modification of the choice model and of its training. This modification consists in allowing indifference between products after a certain rank: this is justified by the fact that after a certain rank, the ranks are meaningless. With this new formulation, we can structure the factorially large space of sequences in the shape of a tree, which makes it possible to decrease significantly the time required to learn the model. Indeed, at each iteration of the column generation, we only branch the tree to onemore degree. We have applied the new way of training the choice models to real store data provided by our industrial collaborator, and to artificially generated data. In both cases, we noticed that computation times decreased by at least an order of magnitude. We were also able to solve instances up to one thousand products, while previous approaches were limited to several dozens. Besides, we have developed an extension of our algorithm, able to consider adding new products in the optimized assortment. We assume that we have no transaction data on those new products, but only common characteristics (called features) with the old products, for which we have access on transaction data. To deal with those new products, we introduce a measure of similarity among products. Then, we show a way of generalizing the behavior of consumers known among the old products to the set of old and new products. This extension is useful for the problem of season-to-season optimization of assortments, where products of the new season are to be inserted in the assortment without prior information about transactions among them. Additionally, we have found a way of using our choice model in the optimization problem: we show how to limit the error of over-fitting with a boostingmethod. Finally, we show experimental results indicating the interest of assortment optimization. On real instances, our process designs systematically assortments wider than what was noticed in real stores: this shows that, for the given industrial data, it is important to provide the consumer with a broad choice of products to ensure the retailer a higher revenue. Nevertheless, being aware of the operational constraints that retailers face, such as the maximum quantity of products to be displayed at the same time, we have also run our experiments with a capacity constraint in the optimization problem. It consists in limiting the total number of products to be displayed in an assortment to what is observed in real stores. In this case, we still predict a 35% increase in revenues based on our choicemodel. Last but not least, we propose an extension of our work for the design of a decision support tool for retailers. Indeed, we know that some store managers may be reluctant to delegate the whole process of assortment optimization to a fully integrated software. Hence, it may be worthwhile to leave the manager in the position of choosing himself which assortment of products he may like to expose while providing him with some insights on the predicted consequences of certain choices. In particular, what would be the impact on the average revenue per customer of adding this product to the assortment?