Entrepôts autonomes à l'ère du e-commerce : apprentissage automatique pour la prise de décision en temps réel

La récente et rapide croissance du commerce et ligne a fondamentalement changé le secteur de la vente au détail et, plus généralement, la façon dont les individus consomment. Cette industrie fait face à une grande compétitivité avec une grande volatilité de sa clientèle. En cherchant constamment à réduire ses délais de livraison tout en minimisant les coûts, les chaînes logistiques font face à un défi de taille pour satisfaire une demande grandissante et s'adapter à des tendances qui évoluent constamment. Cette thèse considère un nouveau type d'entrepôt de stockage automatique, appelé centre de distribution robotisé, qui est particulièrement bien adapté aux spécificités du commerce en ligne. Dans un centre de distribution robotisé, une flotte de robots récupère et entrepose des étagères remplies d'articles dans l'espace de stockage. Ces étagères sont apportées à des stations de cueillette où des opérateurs humains sélectionnent les articles pour satisfaire les commandes. En pratique, un robot réalise une succession continue de cycles de commandes doubles. Ces cycles correspondent à une première tâche de stockage, suivi immédiatement d'une tâche de récupération, puis d'une durée d'attente à une station. Ce processus engendre une multitude de problèmes de décision tels que l'allocation d'emplacements de stockage, l'ordonnancement des commandes, l'affectation d'une station de cueillette et autres. De plus, la promesse d'une livraison toujours plus rapide force les vendeurs à considérer une nouvelle commande dès que celle-ci est placée. Pour cette raison, ainsi que la nature dynamique du système d'entreposage, la prise de décision doit être réalisée en temps réel dans un environnement incertain. Cette thèse s'organise autour de trois articles publiés ou soumis dans des journaux scientifiques. Compte tenu du manque habituel de formalisation des problèmes de décision en temps réel, le premier article propose un modèle de programme dynamique stochastique qui modélise les décisions opérationnelles dans un centre de distribution robotisé. L'objectif de ce modèle est de formaliser les opportunités d'optimisation dans ce système afin de permettre aux chercheurs de développer de nouvelles approches dans un environnement bien défini. Reproduit par un simulateur à événements discrets, ce modèle est illustré par une étude de simulation qui vise à comparer les règles de décision standards d'allocation d'emplacements de stockage : un stockage aléatoire, sélection de l'emplacement disponible le plus proche, un stockage par classes et la politique gloutonne de temps d'accès et de transition le plus court. Le second article présente une méthode d'apprentissage d'une politique de stockage par zones. Un élément essentiel des centres de distribution robotisés est leur grande modularité de stockage. Lorsqu'un robot replace une étagère, il peut sélectionner n'importe quel emplacement disponible. Étant donné le nombre important de robots opérant simultanément, cela crée de nombreuses opportunités. Cette modularité permet d'adapter la configuration de l'entrepôt à de nouvelles tendances de la demande et de créer des cycles les plus efficaces possibles. Cet article utilise une méthode d'apprentissage par renforcement qui vise à minimiser le temps de déplacement des robots. Les décisions sont prises dans un processus de décision markovien partiellement observable où l'état du système est représenté par de l'information sur la configuration actuelle de l'espace de stockage, la prochaine commande à traiter et des statistiques sur les distributions d'arrivée des commandes. Basé sur cette représentation, un agent de Deep Q-learning est utilisé pour apprendre à quelle zone de l'entrepôt chaque étagère devrait être dynamiquement affectée. De plus, une stratégie d'exploration de trajectoires est proposée afin de tirer profit des informations sur les commandes déjà révélées à un instant donné. Avec une étude de simulation, la méthode proposée, incluant l'exploration de trajectoires, génère des résultats qui améliorent de 7.6% la meilleure règle standard de décision en termes de temps de déplacement. Le troisième article propose une autre approche d'apprentissage pour sélectionner dynamiquement les emplacements de stockage exacts (au lieu de zones) en utilisant des méthodes de recherche d'arbres. Une recherche arborescente Monte-Carlo est employée hors ligne pour accumuler de l'expérience de haute qualité. Cette recherche d'arbre étant particulièrement coûteuse en temps de calcul, elle ne peut être déployée en temps réel. Cependant, un réseau de neurones peut être utilisé pour apprendre de cette expérience avec une certaine représentation d'état du système (les emplacements libres et les étagères requises sont représentées par leurs coordonnées). Ce réseau est ensuite employé comme prédicteur d'actions dans plusieurs nouvelles politiques de stockage, soit tel quel, soit dans des stratégies d'exploration de trajectoires ou de recherches d'arbres supervisées. Le niveau de performance obtenu est constamment supérieur aux règles de décision de la littérature et dépend du temps de calcul alloué à la prise de décision. Par exemple, la meilleure politique de recherche d'arbre supervisée améliore la meilleure règle de décision de 13.7%.

Abstract

The growth of e-commerce has changed the way people consume and the business-to-consumer retail market segment. The goal of increasing delivery speed while remaining cost-effective poses significant new challenges for supply chains as they race to satisfy the growing and fast-changing demand. This thesis considers a recent automated warehouse called Robotic Mobile Fulfillment System (RMFS), particularly well-suited for e-commerce operations. In an RMFS, a fleet of small robots retrieves and stores shelves of items in the storage area. These robots bring the shelves to picking stations, where a human operator picks the required items to fulfil orders. The life of a robot is a succession of dual command cycles where a storage task is immediately followed by a retrieval task to finally wait in line at a picking station. Such cycles involve numerous decisions, from storage allocation to order sequencing, picking station assignments, and others. Also, online retailers promise speedy deliveries, which requires that new orders be included in the set of requests to fulfil as soon as they are known. For this reason, and because of the very dynamic nature of the robots' cycles, decision-making needs to be done in real-time, in an uncertain environment. This thesis is articulated around three articles, published, or submitted to scientific journals. First, and because such a real-time problem often lacks a formal description, we propose a mathematical framework that models decision-making in an RMFS as a stochastic dynamic program. This model's objective is to formalize optimization opportunities to allow researchers to develop more advanced methods in a well-defined environment. Embedded in a discrete event simulator, this model is illustrated by simulations to compare against standard storage decision rules, including a random storage policy, a closest open location policy, a class-based storage policy, and the shortest leg (greedy) policy. In a second phase, we present a method that learns a zone-based storage policy. A distinguishing feature of an RMFS is its great storage modularity. Indeed, when a robot returns a shelf to the storage area, it can select any available location. Because of the large number of simultaneously operating robots, there are plenty of available options. This flexibility allows the warehouse's layout to adapt to new demand patterns and create efficient cycles. We propose to tackle this storage allocation sub-problem by using Deep Reinforcement Learning to minimize the robots' average travel time. The decision-making process is first formulated as a Partially Observable Markov Decision Process where information about the current layout of the warehouse, the next order in line, and the demand distribution is available. Based on this state representation and a discrete event simulator, a Deep Q-learning agent is used to learn to which zone a shelf should be dynamically assigned. Additionally, we propose a rollout strategy to enhance our method by leveraging more information about already revealed orders at a given time step. Using simulations to compare our method to the best standard decision rule (shortest leg) showed average performance gains of 7.6% in travel time. Finally, and motivated by the good results of the rollout strategy, a different learning approach is proposed to dynamically select exact storage locations (instead of zones) using tree search methods. This approach first consists of running offline an efficient yet computation costly Monte Carlo Tree Search method to generate a high-quality experience. This experience is later learned by a neural network with a proper coordinates-based features representation. The obtained neural network is used as an action predictor in several new storage policies, either as it is or in rollout and supervised tree search methods. The supervised tree search method explores the tree's nodes most likely to be visited by the policy network. The obtained performance levels depend on the computation time available at a decision step and are highly competitive compared to real-time decision rules from the literature. For instance, the best-supervised tree search instance improves by 13.7% the shortest leg policy.