Heuristics and exact algorithms for synchronized pickup and delivery problems

Dans l'environnement commercial mondial concurrentiel d'aujourd'hui, les chaînes d'approvisionnement sont devenues plus complexes et plus sensibles en raison de leur dépendance vis-à-vis des demandes des clients en constante évolution. La création de valeur pour les clients ne réfère pas toujours à la qualité ou à la quantité du produit, elle réfère également à la disponibilité du produit à temps à l'endroit demandé. Tirer parti d'une chaîne d'approvisionnement pour fournir une valeur élevée aux clients ne peut être possible sans un transport organisé de manière efficace. Les professionnels considèrent qu'un service de livraison amélioré est crucial pour répondre à la demande des clients et augmenter la disponibilité des produits. En effet, un tel service est considéré comme un facteur clé dans la création de valeur pour les clients dans le monde des affaires. Le transport est l'un des éléments clés de la chaîne d'approvisionnement, car il joue un rôle essentiel dans le maintien d'une chaîne d'approvisionnement robuste et résiliente. De plus, un réseau de transport efficace aide les entreprises à réduire leurs coûts d'exploitation, à augmenter les niveaux de service et à obtenir un avantage sur la concurrence. Cela augmente l'intérêt de la recherche axée sur la gestion des opérations de transport et de la distribution. Tout au long de cette recherche, nous nous intéressons aux problèmes de cueillettes et de livraisons (ou Pickup and Delivery problems (PDPs)) qui sont une généralisation du problème classique de tournées de véhicules (Vehicle Routing Problem). En général, les PDPs impliquent la conception d'itinéraires à coût minimum pour un ensemble de véhicules afin de satisfaire toutes les requêtes de cueillettes et de livraisons. Les relations d'appariement et de précédence entre les lieux de cueillette et de livraison doivent être respectées. Plusieurs variantes de PDPs sont créées en ajoutant différents types de contraintes telles que les fenêtres de temps, la capacité des véhicules, etc. Cette classe de problèmes d'optimisation trouve des applications dans plusieurs contextes réels, tels que le transport de passagers porte-à-porte, les services de courrier urbain, le transport maritime et le transport de marchandises. Les PDPs ont été largement abordés dans la littérature. Cependant, les réseaux de distribution modernes avec des opérations de plus en plus complexes et des caractéristiques spéciales rendent les méthodes conventionnelles limitées et/ou inefficaces. Par conséquent, il est essentiel de développer de nouvelles méthodes et des solutions innovantes pour relever les nouveaux défis de l'industrie des transports. Dans ce projet de recherche, nous aborderons des PDPs réels issus de différents contextes tels que la livraison du dernier kilomètre et les services de santé. Tout d'abord, nous étudions un nouveau PDP dans le contexte de la livraison du dernier kilomètre connu sous le nom multi-pickup and delivery problem with time windows (MPDPTW), c'est un problème de cueillettes multiples et de livraison avec fenêtres de temps. Ce problème trouve de nombreuses applications concrètes, comme dans le domaine de l'économie du partage avec les services UBER EAT, où un client est autorisé à commander de la nourriture de différents restaurants; l'entreprise doit ensuite effectuer des cueillettes à différents endroits, avant de livrer tous les repas au client. Nous avons conçu de nouveaux algorithmes exacts pour le MPDPTW, fournissant les premières bornes inférieures et obtenant des solutions optimales pour les grandes instances. Dans ce travail, deux nouvelles formulations pour le problème sont introduites, une formulation à deux indices et la formulation des représentants asymétriques (asymmetric representatives formulation). Une transformation du MPDPTW en PDPTW est également proposée et testée. Les formulations mathématiques sont ensuite comparées pour trouver le meilleur algorithme pour le problème. Le deuxième problème abordé dans ce projet de recherche est une application liée au PDP dans le contexte de la logistique des soins de santé. Les activités de transport dans les hôpitaux sont de plus en plus complexes en raison de la grande variété de fournitures et d'équipements utilisés, tels que les articles jetables qui sont utilisés plus fréquemment. Cela se traduit par une augmentation du volume de transport dans les hôpitaux. Ces facteurs justifient le besoin de plus d'efficacité et de productivité des systèmes de transport dans les hôpitaux afin de répondre au niveau de service attendu par les patients sans augmenter les coûts. Un moyen efficace pour atteindre ces objectifs est l'automatisation des processus logistiques à l'aide de véhicules autoguidés (automated guided vehicles). Nous étudions le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands (FSRPS-AGV), c'est un problème de dimensionnement de flotte de véhicules autoguidés dans un environnement dynamique avec des contraintes de synchronization. Ce problème est dans le cadre d'une application réelle avec un partenaire de l'industrie de la santé à la ville de Québec. Nous décrivons le problème, nous introduisons une formulation mathématique et proposons une matheuristique pour le résoudre. Les tests sont menés sur des instances petites et grandes générées à partir de données réelles fournies par notre partenaire industriel. La troisième problématique étudiée dans ce projet est une application dans le contexte de la livraison de béton prêt à l'emploi (BPE). De nombreux problèmes opérationnels difficiles sont rencontrés par les fournisseurs du BPE, tels que la planification des opérations de production dans les usines de production, la planification des horaires quotidiens et hebdomadaires des chauffeurs, la planification des opérations de chargement, et la livraison du béton sur les chantiers de construction. Dans un environnement commercial caractérisé par une concurrence féroce, des solutions innovantes sont nécessaires pour résoudre ces problèmes afin d'atteindre l'exellence opérationnelle et de garantir un avantage concurrentiel. Bien que l'optimisation des opérations de livraison de béton soit essentielle pour les entreprises de béton, la satisfaction des chauffeurs et des clients ne doit pas être négligée. Nous étudions le personnel scheduling problem for ready-mixed concrete delivery (PSP-RMC) dans le contexte d'une application réelle avec une entreprise de béton au Québec, Canada. L'objectif est d'aider les fournisseurs de BPE à planifier des horaires de chauffeurs rentables et consistents (heures de début de travail similaires au cours de la semaine) sur un large horizon de planification sous des contraintes opérationnelles et réglementaires strictes. Des problèmes de PDPs sont résolus à l'intérieur même du PSP-RMC pour obtenir des routes pour les chauffeurs. Nous décrivons le problème et proposons un algorithme métaheuristique en deux étapes pour le résoudre. Les tests sont menées sur des instances artificielles et sur des instances générées à partir de données réelles fournies par notre partenaire industriel. Cette thèse est structurée comme suit. Une revue de la littérature sur les problèmes de cueillettes et de livraisons est présentée après un chapitre d'introduction. Le chapitre 2 est consacré au multi-pickup and delivery problem with time windows, et le chapitre 3 présente le fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Le chapitre 4 présente le personnel scheduling problem for ready-mixed concrete delivery. La conclusion suit et résume les principales contributions de cette thèse dans le dernier chapitre.

Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.