Modèles et méthodes pour l'optimisation du processus de préparation de commandes dans les entrepôts de type e-commerce

RÉSUMÉ: Dans les dernières décennies, les activités liées au e-commerce ont connu un développement considérable à travers le monde, donnant lieu à un environnement extrêmement compétitif. Pour s’approprier des parts de marché, les entreprises proposent des services de plus en plus innovants comme la livraison rapide. La mise en place de ce type de services passe par une bonne gestion de la chaine logistique, et notamment la politique de stockage et de préparation des commandes à l’intérieur des entrepôts. Ces politiques doivent s’adapter à un nouveau pattern de demande caractérisé par un grand nombre de commandes à préparer quotidiennement, chacune composée de peu d’items. De plus, les offres de livraison rapide font que chaque commande arrive avec une date limite de préparation qu’il est impératif de respecter. Certains entrepôts d’e-commerce implémentent des systèmes automatisés dans lesquels la préparation des commandes est principalement prise en charge par des robots. Cependant, ces systèmes engendrent des coûts opératoires extrêmement élevés, souvent difficiles à assumer pour des entreprises de petite et moyenne tailles. La majorité des entrepôts suivent encore des systèmes classiques dans lesquels des préparateurs de commandes démarrent d’un dépôt central, se déplacent à pied dans les allées de l’entrepôt pour récupérer les différents items des commandes et les ramènent à l’unité d’assemblage. Afin de s’adapter au pattern de demande associée au e-commerce, ces entrepôts implémentent de nouvelles techniques de stockage et de préparation des commandes à l’échelle tactique et opérationnelle. L’objectif de cette thèse est de proposer des modèles et des méthodes pour optimiser la préparation des commandes dans les entrepôts implémentant ces techniques et d’étudier leur impact. Dans la première partie de cette thèse, nous étudions l’impact d’une pratique émergente dans les entrepôts d’e-commerce, à savoir la possibilité de prendre en charge une commande par plusieurs préparateurs (la collecte des items d’une commande est répartie sur plusieurs personnes). Nous considérons un ensemble de demandes avec des dates limites de préparation et un ensemble de préparateurs munis de chariots à capacité limitée. L’objectif du premier problème étudié est de planifier les tournées de chaque préparateur afin de collecter tous les items des commandes à temps et de minimiser la durée totale de collecte. La résolution de ce problème nécessite de déterminer le regroupement en lots des items, l’affectation des lots aux préparateurs et l’itinéraire de collecte des items de chaque lot. Pour résoudre le problème, nous proposons une heuristique basée sur le principe “route-first schedule-second”. Dans la phase de routage, l’heuristique répartit les items de toutes les commandes en grands lots et construit les tournées associées à chaque lot en utilisant une adaptation de la procédure de Split. Dans la phase d’ordonnancement, les tournées construites sont affectées aux préparateurs (et séquencées) à l’aide de la programmation par contraintes. À travers une comparaison utilisant un benchmark d’instances publiques, de notre méthode avec une méthode de la littérature qui résout la version du problème où l’ensemble des items d’une même commande doit être collecté par un même préparateur, nous démontrons qu’une réduction de la durée totale de collecte de 30 % en moyenne peut être réalisée en autorisant la collecte d’items d’une commande par plusieurs préparateurs. Dans la deuxième partie de la thèse, nous étudions l’adaptation du problème de routage d’un préparateur (c.-à-d. définir la séquence de visite des différents emplacements de stockage lors d’une tournée afin de minimiser la distance parcourue) dans un nouveau type d’entrepôt, dit à étagères mixtes (mélangées). Contrairement aux entrepôts classiques où tout le stock associé à un item est disponible dans une seule étagère, les entrepôts à étagères mixtes divisent le stock disponible d’un item en petites unités qui sont dispersées dans différentes étagères un peu partout dans l’entrepôt. La résolution de ce problème passe par la sélection des emplacements d’où récupérer les différents items avant de construire la tournée de collecte. Pour résoudre le problème, nous proposons une méthode exacte de décomposition de type “logic-based Benders” dans laquelle la sélection des emplacements de stockage se fait dans le problème maître et la construction de la tournée qui visite les emplacements sélectionnés dans le sous-problème. Nous proposons une coupe d’optimalité dont nous prouvons la validité. De plus, nous introduisons un ensemble d’améliorations, incluant une fonction dite de borne inférieure et des inégalités valides, qui jouent un rôle important dans l’efficacité de la méthode. Finalement, une comparaison avec une adaptation d’une méthode exacte, initialement proposée pour un problème de routage classique, au contexte des entrepôts à étagères mixtes démontre l’efficacité de notre méthode. Dans la dernière partie de cette thèse, nous étudions la combinaison de deux pratiques, à savoir le stockage à étagères mixtes et le découpage de l’espace de ramassage en plusieurs zones disjointes avec un seul préparateur opérant dans chaque zone. Nous considérons un problème de planification de collecte d’items de commandes par vague, où chaque préparateur effectue une tournée de collecte. L’objectif du problème est de sélectionner d’où récupérer chaque item et de définir la tournée associée à chaque préparateur de telle sorte à minimiser le temps de collecte (la plus longue tournée parmi tous les préparateurs). Pour résoudre le problème, nous proposons une adaptation de la méthode introduite dans la deuxième partie de la thèse et une simple adaptation d’une méthode de la littérature spécialisée pour une structure particulière d’entrepôts (1-bloc). Nous démontrons dans la partie expérimentale que l’implémentation d’une stratégie de zonage dans les entrepôts à étagères mixtes réduit considérablement les temps de collecte par rapport au zonage dans les entrepôts classiques (sans étagères mixtes). ABSTRACT: In the last decades, e-commerce activities have grown significantly throughout the world, leading to a highly competitive environment. To gain market share, companies are offering innovative services such as fast delivery. Implementing these services requires good management of the supply chain, more precisely, the storage and order picking policies inside the warehouses. These policies must be adapted to a new demand pattern characterized by a large number of orders to be prepared daily, each composed of a few items. Moreover, the orders come with deadlines which must be respected to ensure high service quality.To face these new requirements, some e-commerce warehouses implement automated systems in which order picking is mainly performed by robots. However, these systems generate high operating costs that are often difficult to handle for small and medium-sized companies. Most warehouses still follow the classic picker-to-part system in which order pickers start from a central depot, walk through the warehouse aisles to collect items contained in picklists, and bring them to the assembly unit. In order to adapt to the demand pattern of e-commerce, new storage and picking techniques are implemented in these warehouses at the tactical and operational levels. The general purpose of this thesis is to propose models and methods that optimize the order picking process in warehouses using these techniques and to study their impact. In the first part of this thesis, we study the impact of an emerging practice in e-commerce warehouses, i.e., the possibility of handling an order by several pickers (splitting an order). To this end, we assume a set of orders with preparation deadlines that must be handled by a set of pickers equipped with capacitated carts. We generalize the integrated orders batching, batch scheduling, and picker routing problem by allowing the orders splitting. To solve the problem, we propose a route-first schedule-second heuristic. In the routing phase, the heuristic divides the orders into clusters and designs the tours that retrieve the items of each cluster using a split-based procedure. In the scheduling phase, the constructed tours are assigned to pickers (and sequenced) using constraint programming. On a publicly available benchmark, we compare our results against a state-of-the-art iterated local search algorithm designed for the non-splitting order version of the problem. We show that splitting the orders using our algorithm reduces the picking time by 30% on average. In the second part of the thesis, we study the adaptation of the picker routing problem (PRP) , i.e., sequencing the storage locations that must be visited in a single tour such that the total travel distance is minimized, into a new type of warehouses, called mixed-shelves warehouses. Unlike conventional warehouses, where all the inventory associated with an item is available on a single shelf, mixed-shelves warehouses break up the total inventory into smaller units that are assigned to different shelves throughout the warehouse. Thus, the locations from where to retrieve the items must be selected before designing the picking tour. To solve the problem, we propose a logic-based Benders decomposition method in which the storage locations are selected in the master problem, and the tour that visits the selected locations is determined in the subproblem. We design tailored optimality cuts and prove their validity. In addition, we introduce a set of algorithmic enhancements, including a lower bounding function and a set of valid inequalities, that significantly improve the method. Finally, a comparison with an adaptation of an exact method, initially proposed for the PRP, to the context of mixed-shelves warehouses demonstrates the superiority of our method. In the last part of this thesis, we study the combination of two practices, namely mixed shelves storage and zone picking (dividing the picking area into disjoint zones with a picker operating in each zone). In our problem, a wave of orders must be prepared by collecting all the items of each order in the next tour of the pickers. The objective is to select from where to retrieve each item of the orders and to define the tour of each picker such that the makespan is minimized (the longest tour among the pickers). To solve the problem, we propose an adaptation of the method introduced in the second part of the thesis and an adaptation of another method from the literature for a particular warehouse shape (1-block). We demonstrate in the experimental part that implementing a zoning strategy in mixedshelves warehouses significantly reduces the makespan compared to zoning in conventional warehouses