Scalable Algorithms for Discrete Choice Modeling and Assortment Optimization

L'optimisation de l'assortiment vise à identifier un ensemble de produits à offrir aux clients, de manière à maximiser le revenu attendu d'une entreprise. L'un des principaux défis à relever pour résoudre cette tâche provient du fait que les demandes de produits sont interdépendantes, en raison des effets dits de substitution et de halo. Par conséquent un modèle de choix discret doit être appris à partir des données recensées, afin de capturer les comportements d'achat des clients confrontés à des ensembles discrets d'alternatives. Un tel modèle peut ensuite être utilisé comme une sous-routine prédictive pour optimiser les décisions d'assortiment. En pratique, la résolution d'un problème d'optimisation de l'assortiment nécessite donc de trouver le bon compromis entre i) la flexibilité du modèle de choix, qui doit être suffisamment général pour bien représenter le comportement d'achat des clients, et ii) la difficulté de résolution du problème d'optimisation pour trouver l'ensemble de produits qui maximise les revenus. Dans cette thèse, nous traitons à la fois les aspects prédictifs et prescriptifs de ce compromis, en fournissant des procédures d'estimation efficaces pour des modèles de choix discrets généraux et des algorithmes pour identifier des assortiments à revenu élevé. Tout d'abord, nous proposons une procédure efficace pour optimiser les assortiments pour des scénarios dans lesquels chaque produit est associé à un certain coût que l'entreprise doit payer pour offrir ce produit. Nous supposons que les clients choisissent selon un modèle Multinomial Logit. Ce problème est NP-hard. Néanmoins, nos résultats indiquent qu'il est possible d'identifier l'assortiment optimal en une fraction de seconde, en moyenne, même pour des instances avec mille produits. Nous montrons également comment adapter notre approche au cas où les assortiments doivent satisfaire une contrainte sur le nombre maximum de produits disponibles. Deuxièmement, nous proposons un modèle de choix partiellement rangé, qui généralise les modèles de choix entièrement rangé en supposant que les clients forment des préférences strictes uniquement parmi quelques produits pertinents, tout en étant “indifférents” parmi les autres. Ce modèle permet de capturer tout effet de substitution entre les produits. Nous proposons ensuite une procédure d'estimation basée sur la génération de colonnes pour identifier efficacement les comportements des clients en fonction des données historiques de vente. De plus, nous montrons comment optimiser les décisions d'assortiment basées sur un tel modèle. Enfin, nous étendons notre modèle de choix partiellement rangé et notre cadre d'estimation pour capturer les comportements d'achat, tels que les effets de halo, qui ne peuvent être expliqués par aucun des modèles appartenant à la famille de la maximisation de l'utilité aléatoire. Nos résultats sur un ensemble de données de ventes d'épicerie dans le monde réel montrent que la prise en compte de ce type de comportements de choix permet d'augmenter de manière significative la précision prédictive.