Th. 3e cycle--Math. pures--Besançon, 1977. N°: 274.

Th. doct.-ing.--Inform.--Nancy--I.N.P.L., 1984.

Th.--Sci. math.--Besançon, 1981. N°: 148.

Th. 3e cycle--Méthodes d'approximation et algorithmes en anal. et théor. des nombres--Besançon, 1979. N°: 330.

De nombreux problèmes d'optimisation issus du monde réel. notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés, En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte, Les métaheuristiques sont des candidats naturels pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques, Toutefois, le développent de métaheuristiques efficaces résulte en un processus d'ingénierie complexe, Le coeur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO, Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées, Enfin, la question de la prise en compte de l'incertitude est abordée dans le context de l'optimisation multiobjectif. / Many real-world optimization problems, especially in the field of logistics, have to face a lot of difficulties, Indeed, they are often characterized by large and complex search'spaces, multiple conflicting objective functions, and a host of uncertainties that have ta be taken into account. Metaheuristics are natural candidates ta solve those problems and make them preferable to classical optimization methods, However, the development of efficient metaheuristics results in a complex engineering process, The core subject of this work lies in the design, implementation and experimental analysis of metaheuristics for multiobjective optimization, together with theu applications to logis tic problems from routing and scheduling, Firstly, a unitïed view of such approaches is presented and then integrated into a software framework for their implementation, ParadisEO-MOEO, Next, sorne cooperative approaches combining metaheuristics for multiobjective optimization are proposed, At last, the issue of uncertainty handling is discussed in the context of multiobjective optimization.

Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.

L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.

Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.

Titre de l'écran-titre (visionné le 10 janvier 2024) / La Transformée de Burrows-Wheeler (BWT) permet d'effectuer une excellente compression de données grâce à son tri de la séquence des caractères sources, regroupant ainsi des données similaires pour améliorer la compression. Bien que l'algorithme Move-to-Front (MTF) ne cause pas de compression en soi, la synergie qu'elle a avec l'algorithme de Huffman, classique ou amélioré, améliore la performance de compression. MTF, en augmentant la fréquence des petites valeurs dans les données codées, combiné au réarrangement des caractères effectué par BWT, crée un cadre optimal pour un codage efficace de Huffman. Néanmoins, la version classique de MTF a ses limites, car elle promeut uniformément les symboles accédés à l'avant de la liste, négligeant éventuellement les structures présentes dans le texte d'entrée. En introduisant une politique de promotion optimale qui réordonne minutieusement les symboles selon les modèles de données inhérents, on peut accentuer l'asymétrie de la distribution des valeurs, renforçant la compatibilité avec l'algorithme de Huffman. Cette méthode améliorée a démontré sa capacité à compresser des images complexes, non linéaires, avec une efficacité notable, bien que l'avantage obtenu diminue chez des images à la géométrie plus simple. / The Burrows-Wheeler Transform (BWT) allows for excellent data compression due to its sorting of the source character sequence, grouping similar data to enhance compression. Although the Moveto-Front (MTF) algorithm does not cause compression in itself, its synergy with the classic or enhanced Huffman algorithm improves compression performance. MTF, by increasing the frequency of small values in coded data, combined with the character rearrangement performed by BWT, creates an optimal framework for efficient Huffman coding. However, the classic version of MTF has its limits, as it uniformly promotes accessed symbols to the front of the list, possibly neglecting structures present in the input text. By introducing an optimal promotion policy that carefully reorders symbols according to inherent data patterns, one can accentuate the asymmetry of value distribution, enhancing compatibility with the Huffman algorithm. This improved method has demonstrated its ability to compress complex, non-linear images with notable efficiency, although the advantage obtained decreases for images with simpler geometry.

Titre de l'écran-titre (visionné le 2 octobre 2023) / 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. / In today's challenging and competitive global business environment, supply chains have become more complex and sensitive due to their dependence on constantly changing customer demands. Creating value for customers does not always refer to the quality or quantity of the product, it also refers to the availability of the product on time at the requested location. Leveraging a supply chain to provide high value to customers cannot be possible without effectively organized transportation. A better delivery service increases the availability of products to fulfill the demand of customers. Therefore, business practitioners consider it a very important factor in creating value for customers. Transportation is one of the key components in the entire supply chain, it has a critical role in maintaining a robust and resilient supply chain. Moreover, an efficient transportation network helps businesses to reduce operating costs, increase service levels, and gain a clear advantage over the competition. This increases research interest focused on transportation operations management. Throughout this research, we are interested in pickup and delivery problems (PDPs) which are a generalization of the classical vehicle routing problem (VRP). In general, the PDPs involve designing minimum-cost routes for a set of vehicles to satisfy all the pickup-delivery requests. Pairing and precedence relations of pickup and delivery locations must be respected. Variants of PDPs are found by adding side constraints such as time windows, vehicle capacity, etc. This class of optimization problems has applications in several real-life contexts, such as door-to-door passenger transportation, urban courier services, maritime shipping and freight transportation. PDPs have been widely addressed in the literature. However, modern delivery networks with more and more complex operations and special characteristics make conventional methods limited and/or inefficient. Hence, developing new innovative solution methods to tackle the new challenges of the transportation industry is crucial. In this research project, we tackle real-life PDPs arising from different contexts, such as last mile delivery and healthcare services. First, we study a new rich PDP in the context of last mile delivery known as the multi-pickup and delivery problem with time windows (MPDPTW). This problem finds many real-life applications, some of them are in the context of shared economy such as UBER EAT services, where a client is allowed to order food from different restaurants; the company must then perform all pickups at different places, before delivering all meals to the client location. We designed a new branch-and-cut algorithm for the MPDPTW providing the first dual bounds for the problem and obtaining tight solutions for large instances. In this work, two new formulations for the problem are introduced, a two-index formulation and the asymmetric representatives formulation (ARF). A transformation of the MPDPTW into a PDPTW is also proposed and tested. The mathematical formulations are then compared to define the best one for the problem. The second problem tackled in this research project is a PDP-related application in the context of healthcare logistics. Transportation activities in hospitals are now becoming more complex due to the wide variety of supplies and equipment used such as disposable items which are being used more frequently. This results in the expansion of the volume of transportation in hospitals. These factors justify the need for more efficiency and productivity of transportation systems in hospitals in order to meet the service level expected by patients without increasing costs. One of the most powerful ways of achieving these goals is the automation of logistics processes by using automated guided vehicles. We study the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands in the context of a real-life application with an industrial partner from the healthcare industry in Quebec City, Canada. We describe the problem, introduce a mathematical formulation for it, and propose a powerful matheuristic to solve it. Computational experiments are conducted on large and small instances generated based on real-data provided by our industrial partner. The third problem studied in this project is another application, this time in the context of ready-mixed concrete (RMC) delivery. Many challenging operational problems are faced by RMC suppliers such as scheduling production operations at production plants, creating daily and weekly drivers' schedules, loading operations scheduling, and delivering concrete to construction sites. In a business environment characterized by a fierce competition, innovative solutions are needed to tackle these problems in order to achieve operational efficiency and guarantee a competitive advantage. Although optimizing concrete delivery operations is essential for concrete companies, drivers' and customers' satisfaction should not be neglected. We study the personnel scheduling problem for RMC delivery in the context of a real-life application with a concrete company in Quebec, Canada. The goal is to help RMC suppliers build cost-effective and consistent (similar starting times over the week) drivers' schedules over a large planning horizon, under tight operational and regulatory constraints. The PSP-RMC embeds a PDP which is solved to create routes for drivers. We describe the problem and propose a two-stage metaheuristic algorithm to solve it. Computational experiments are conducted on artificial instances, and on instances generated based on real-data provided by our industrial partner. This thesis is structured as follows. A literature review on the pickup and delivery problems is presented after an introductory chapter. Chapter 2 is devoted to the multi-pickup and delivery problem with time windows, and Chapter 3 presents the fleet sizing and routing problem with synchronization of automated guided vehicles with dynamic demands. Chapter 4 presents the personnel scheduling problem for ready-mixed concrete delivery. The conclusion follows and summarizes the main contributions of this thesis in the last Chapter.