Aujourd'hui, le problème de stationnement devient l'un des enjeux majeurs de la recherche dans la planification des transports urbains et la gestion du trafic. En fait, les conséquences de l'absence de places de stationnement ainsi que la gestion inadéquate de ces installations sont énormes. L'objectif de cette thèse est de fournir des algorithmes efficaces et robustes afin que les conducteurs gagnent du temps et de l'argent et aussi augmenter les revenus des gestionnaires de parking. Le problème est formulé comme un problème d'affectation multi-objectifs dans des environnements statique et dynamique. Tout d'abord, dans l'environnement statique, nous proposons de nouvelles heuristiques en deux phases pour calculer une approximation de l'ensemble des solutions efficaces pour un problème bi-objectif. Dans la première phase, nous générons l'ensemble des solutions supportées par un algorithme dichotomique standard. Dans la deuxième phase, nous proposons quatre métaheuristiques pour générer une approximation des solutions non supportées. Les approches proposées sont testées sur le problème du plus court chemin bi-objectif et le problème d'affectation bi-objectif. Dans le contexte de l'environnement dynamique, nous proposons une formulation du problème sous forme d'un programme linéaire en nombres entiers mixtes qui est résolue à plusieurs reprises sur un horizon de temps donné. Les fonctions objectives considérées, permettent un équilibre entre la satisfaction des conducteurs et l'intérêt du gestionnaire de parking. Deux approches sont proposées pour résoudre ce problème d'affectation dynamique avec ou sans phase d'apprentissage. Pour renforcer la phase d'apprentissage, un algorithme à estimation de distribution est proposé pour prévoir la demande future. Pour évaluer l'efficacité des algorithmes proposés, des essais de simulation ont été effectués. Aussi une mise en œuvre pilote a été menée dans le parking à l'Université de Valenciennes en utilisant une plateforme existante, appelée Context Aware Transportation Services (CATS), qui permet le déploiement dynamique de services. Cette plate-forme peut dynamiquement passer d'une approche à l'autre en fonction du contexte. Enfin cette thèse s'inscrit dans le projet SYstem For Smart Road Applications ( SYFRA). / The parking problem is nowadays one of the major issues in urban transportation planning and traffic management research. In fact, the consequences of the lack of parking slots along with the inadequate management of these facilities are tremendous. The aim of this thesis is to provide efficient and robust algorithms in order to save time and money for drivers and to increase the income of parking managers. The problem is formulated as a multi-objective assignment problem in static and dynamic environments. First, for the static environment, we propose new two-phase heuristics to calculate an approximation of the set of efficient solutions for a bi-objective problem. In the first phase, we generate the supported efficient set with a standard dichotomic algorithm. In the second phase we use four metaheuristics to generate an approximation of the non-supported efficient solutions. The proposed approaches are tested on the bi-objective shortest path problem and the biobjective assignment problem. For the dynamic environment, we propose a mixed integer linear programming formulation that is solved several times over a given horizon. The objective functions consist of a balance between the satisfaction of drivers and the interest of the parking managers. Two approaches are proposed for this dynamic assignment problem with or without learning phase. To reinforce the learning phase, an estimation of distribution algorithm is proposed to predict the future demand. In order to evaluate the effectiveness of the proposed algorithms, simulation tests have been carried out. A pilot implementation has also been conducted in the parking of the University of Valenciennes, using an existing platform called framework for context aware transportation services, which allows dynamic deployment of services. This platform can dynamically switch from one approach to another depending on the context. This thesis is part of the project SYstem For Smart Road Applications (SYFRA).

Cette thèse développe une nouvelle approche de contrôle pour les avions à échelle réduite. Les lois de commande proposées exploitent un modèle non linéaire simple mais pertinent des forces aérodynamiques appliquées à l’aéronef. Ils reposent sur une structure hiérarchique de contrôle non linéaires, et sont synthétisées sur la base d’analyse de stabilité et de convergence théoriques. Ils sont conçus pour fonctionner sur un large domaine de vol. En particulier, ils évitent les singularités associées à la paramétrisation de l'attitude et la direction de la vitesse. Dans un premier temps, le problème de stabilisation de trajectoires de référence est résolu en étendant la méthode du "thrust vectoring", utilisée pour les véhicules à voilure tournante, au cas des aéronefs à voilure fixe. Dans le cas des avions, le principal défi est de prendre en compte les forces aérodynamiques dans la conception des systèmes de commande. Afin de résoudre ce problème, le contrôle proposé est conçu et analysé sur la base du modèle de forces aérodynamique proposé. Le domaine d'utilisation de cette loi de commande est élargi et englobe les trajectoires d'équilibre (trim trajectories) qui sont classiquement utilisées dans la littérature. Cette solution est ensuite adaptée au problème de suivi de chemin, afin de concevoir des lois de guidage cinématique et de contrôle dynamique applicables à presque tout chemin 3D régulier. Les lois de contrôle proposées contiennent des termes intégraux qui robustifient le contrôle vis-à-vis de dynamiques non modélisées. Plusieurs problèmes pratiques sont adressés et les lois de commande proposées sont validées par des simulations du type "hardware-in-the-loop". Enfin, des résultats d'essais en vol illustrent la performance des lois de contrôle proposées. / The present thesis develops a new control approach for scale-model airplanes. The proposed control solutions exploit a simple but pertinent nonlinear model of aerodynamic forces acting on the aircraft. Nonlinear controllers are based on a hierarchical structure, and are derived on the basis of theoretical stability and convergence analyses. They are designed to operate on a large spectrum of operating conditions. In particular, they avoid the singularities associated with the parameterization of the attitude and the heading of the vehicle, and do not rely on a decoupling between longitudinal and lateral dynamics. First, the trajectory tracking problem is addressed by extending the thrust vectoring method used for small rotor vehicles to the case of fixed wing vehicles. In the case of airplanes, the main challenge is to take into account the aerodynamic forces in the design of control systems. In order to solve this problem, the proposed control is designed and analyzed on the basis of the proposed aerodynamic forces model. The flight envelope is thus broadened beyond trim trajectories which are classically used in the literature. This solution is then adapted to the path following problem, and kinematic guidance and dynamic control laws are developed within a single coherent framework that applies to almost any regular 3D path. The proposed control laws incorporate integral terms that robustify the control with respect to unmodelled dynamics. Several practical issues are addressed and the proposed control laws are validated via hardware-in-the-loop simulations. Finally, successful flight test results illustrate the soundness and performance of the proposed control laws.

L’informatique, le stockage des données et les applications à la demande font partie des services offerts par l’architecture informatique en Nuage. Dans ce cadre, les fournisseurs de nuage (FN) agissent non seulement en tant qu’administrateurs des ressources d'infrastructure mais ils profitent aussi financièrement de la location de ces ressources. Dans cette thèse, nous proposons trois modèles d'optimisation du processus d'allocation des ressources dans le nuage dans le but de réduire les coûts générés et d’accroitre la qualité du service rendu. Cela peut être accompli en fournissant au FN les outils formels nécessaires pour réduire au minimum le prix des ressources dédiées à servir les requêtes des utilisateurs. Ainsi, la mise en œuvre des modèles proposés permettra non seulement l’augmentation des revenus du FN, mais aussi l’amélioration de la qualité des services offerts, ce qui enrichira l’ensemble des interactions qui se produisent dans le nuage. A cet effet, nous nous concentrons principalement sur les ressources de l’infrastructure en tant que service (IaaS), lesquels sont contenus dans des centres de données (DCs), et constituent l'infrastructure physique du nuage. Comme une alternative aux immenses DCs centralisés, la recherche dans ce domaine comprend l’installation de petits centres de données (Edge DCs) placés à proximité des utilisateurs finaux. Dans ce contexte nous adressons le problème d’allocation des ressources et pour ce faire nous utilisons la technique d'optimisation nommée génération de colonnes. Cette technique nous permet de traiter des modèles d'optimisation à grande échelle de manière efficace. La formulation proposée comprend à la fois, et dans une seule phase, les communications et les ressources informatiques à optimiser dans le but de servir les requêtes de service d'infrastructure. Sur la base de cette formulation, nous proposons également un deuxième modèle qui comprend des garanties de qualité de service toujours sous la même perspective d'allocation des ressources d’infrastructure en tant que service. Ceci nous permet de fournir plusieurs solutions applicables à divers aspects du même problème, tels que le coût et la réduction des délais, tout en offrant différents niveaux de service. En outre, nous introduisons le scénario informatique en nuage multimédia, qui, conjointement avec l'architecture des Edge DCs, résulte en l'architecture Multimédia Edge Cloud (MEC). Dans ce cadre, nous proposons une nouvelle approche pour l'allocation des ressources dans les architectures informatique en nuage multimédia lors du positionnement de ces DCs afin de réduire les problèmes liés à la communication, tels que la latence et la gigue. Dans cette formulation, nous proposons également de mettre en œuvre des technologies optiques de réseau de fibres pour améliorer les communications entre les DCs. Plusieurs travaux ont proposé de nouvelles méthodes pour améliorer la performance et la transmission de données. Dans nos travaux, nous avons décidé de mettre en œuvre le multiplexage en longueur d'onde (WDM) pour renforcer l'utilisation des liens et les chemins optiques dans le but de grouper différents signaux sur la même longueur d'onde. Un environnement de simulation réel est également présenté pour l’évaluation des performances et de l'efficacité des approches proposées. Pour ce faire, nous utilisons le scénario spécifié pour les DCs, et nous comparons par simulation nos modèles au moyen de différents critères de performances tel que l'impact de la formulation optique sur la performance du réseau. Les résultats numériques obtenus ont montré que, en utilisant nos modèles, le FN peut efficacement réduire les coûts d'allocation en maintenant toujours un niveau satisfaisant quant à l'acceptation de requêtes et la qualité du service. / The cloud architecture offers on-demand computing, storage and applications. Within this structure, Cloud Providers (CPs) not only administer infrastructure resources but also directly benefit from leasing them. In this thesis, we propose three optimization models to assist CPs reduce the costs incurred in the resource allocation process when serving users’ demands. Implementing the proposed models will not only increase the CP’s revenue but will also enhance the quality of the services offered, benefiting all parties. We focus on Infrastructure as a Service (IaaS) resources which constitute the physical infrastructure of the cloud and are contained in datacenters (DCs). Following existing research in DC design and cloud computing applications, we propose the implementation of smaller DCs (Edge DCs) be located close to end users as an alternative to large centralized DCs. Lastly, we use the Column Generation optimization technique to handle large scale optimization models efficiently. The proposed formulation optimizes both the communications and information technology resources in a single phase to serve IaaS requests. Based on this formulation, we also propose a second model that includes QoS guarantees under the same Infrastructure as a Service resource allocation perspective, to provide different solutions to diverse aspects of the resource allocation problem such as cost and delay reduction while providing different levels of service. Additionally, we consider the multimedia cloud computing scenario. When Edge DCs architecture is applied to this scenario it results in the creation of the Multimedia Edge Cloud (MEC) architecture. In this context we propose a resource allocation approach to help with the placement of these DCs to reduce communication related problems such as jitter and latency. We also propose the implementation of optical fiber network technologies to enhance communication between DCs. Several studies can be found proposing new methods to improve data transmission and performance. For this study, we decided to implement Wavelength Division Multiplexing (WDM) to strengthen the link usage and light-paths and, by doing so, group different signals over the same wavelength. Using a realistic simulation environment, we evaluate the efficiency of the approaches proposed in this thesis using a scenario specifically designed for the DCs, comparing them with different benchmarks and also simulating the effect of the optical formulation on the network performance. The numerical results obtained show that by using the proposed models, a CP can efficiently reduce allocation costs while maintaining satisfactory request acceptance and QoS ratios.

Cette thèse souhaite fournir des outils pour qu’un utilisateur puisse contribuer activement à la sécurité de son usage d’un système informatique. Les activités de sensibilités différentes d’un utilisateur nécessitent tout d’abord d’être cloisonnées dans des domaines dédiés, par un contrôle d’accès s’ajustant aux besoins de l’utilisateur. Afin de conserver ce cloisonnement, celui-ci doit être en mesure d’identifier de manière fiable les domaines avec lesquels il interagit, à partir de l’interface de sa machine. Dans une première partie, nous proposons un nouveau mécanisme de cloisonnement qui peut s’adapter de manière transparente aux changements d’activité de l’utilisateur, sans altérer le fonctionnement des contrôles d’accès existants, ni dégrader la sécurité du système. Nous en décrivons une première implémentation, nommée StemJail, basée sur les espaces de noms de Linux. Nous améliorons ce cloisonnement en proposant un nouveau module de sécurité Linux, baptisé Landlock, utilisable sans nécessiter de privilèges. Dans un second temps, nous identifions et modélisons les propriétés de sécurité d’une interface homme-machine (IHM) nécessaires à la compréhension fiable et sûre du système par l’utilisateur. En particulier, il s’agit d’établir un lien entre les entités avec lesquelles l’utilisateur pense communiquer, et celles avec lesquelles il communique vraiment. Cette modélisation permet d’évaluer l’impact de la compromission de certains composants d’IHM et d’aider à l’évaluation d’une architecture donnée. / This thesis aims to provide end users with tools enhancing the security of the system they use. First, user activities of different sensitivities require to be confined in dedicated domains by an access control fitting the user’s needs. Next, in order to maintain this confinement, users must be able to reliably identify the domains they interact with, from their machine’s interface. In the first part, we present a new confinement mechanism that seamlessly adapts to user activity changes, without altering the behavior of existing access controls nor degrading the security of the system. We also describe a first implementation named StemJail, based on Linux namespaces. We improve this confinement tool by creating a new Linux security module named Landlock which can be used without requiring privileges. In a second step, we identify and model the security properties a human-computer interface (HCI) requires for the reliable and secure understanding of the system by the user. Precisely, the goal is to establish a link between the entities with which the users think they communicate, and those with which they actually communicate. This model enables to evaluate the impact of HCI components jeopardization and helps assessing a given architecture.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2016 / Alors qu’elle se trouve au Mont Parnasse, la narratrice du Chemin de Long Estude de Christine de Pizan affirme reconnaître l’endroit pour l’avoir déjà lu chez Dante. Cette mention surprend considérant la quasi absence de la Comédie dans la littérature française de la fin du Moyen Âge, et si la tradition critique a eu tendance à y voir la revendication d’un projet mimétique, où le poème de Christine de Pizan serait une tentative d’imitation de la Comédie, les nombreux échos dantesques de l’oeuvre témoignent à l’inverse d’un important travail d’appropriation, en mettant systématiquement l’accent sur l’acquisition du savoir et l’inscription dans une filiation intellectuelle. Plus qu’une recension, le présent mémoire aspire à faire le point sur les présences de la Comédie dans le Chemin de Long Estude de même qu’à inscrire ces dernières dans un réseau. Cela amène non seulement à considérer l’oeuvre de Christine de Pizan dans sa totalité, mais aussi en regard des considérations littéraires de l’époque. Dans le premier cas, les renvois à Dante permettent de réfléchir au projet général de l’oeuvre, alors que le poème italien, plus que de représenter un idéal à reproduire, participe à une conquête de l’ordre par le savoir, aux côtés de la Consolation de Philosophie de Boèce et du Chemin de Long Estude lui-même. Dans le second cas, le fait de fonder le travail d’écriture sur la lecture préalable d’un auteur italien témoigne de la bibliophilie du siècle et de l’importance de la lecture, mais aussi de l’émergence timide de nouvelles autorités vernaculaires. / While she is standing in front of Mount Parnassus, the narrator of the Chemin the Long Estude by Christine de Pizan says she recognizes the place for having already read about it in Dante’s book. This statement is surprising considering the near absence of the Comedy in the French literature of the late Middle Ages. The critical tradition has tended to see it as the claim of a mimetic project, where Christine de Pizan’s poem would be an attempt to imitate the Comedy. But the multiple references to Dante’s work in the French poem bear on the contrary witness to an important work of appropriation, systematically putting the emphasis on the acquisition of knowledge and on being part of an intellectual tradition. More than proposing a census, this thesis wishes to study the various presences of Dante’s Comedy in the Chemin de Long Estude as well as to include them in a network. This leads to considering not only the work of Christine de Pizan in its entirety, but also the literary context of the late Middle Ages. In the first case, the references to Dante inform about the general project of the work, while the Italian poem, more than representing an ideal to imitate, shows how knowledge can bring order, alongside Boethius’s Consolation of Philosophy and the Chemin de Long Estude itself. In the second case, Christine de Pizan’s writing process is highly influenced by the prior reading of the Italian author, which reveals the bibliophilia characteristic of the period and the importance of reading, but also the emergence of new vernacular authorities.

Le présent mémoire fait état d'une recherche menée auprès d'élèves montagnais (n=20) et québécois (n=28) de niveau primaire âgés entre 8 et 12 ans. Cette recherche s'inscrit dans le cadre général de la psychologie scolaire tout en se situant à la limite de la psychologie interculturelle et de la psychométrie. Elle vise à jeter un regard nouveau sur les difficultés d'adaptation scolaire des élèves autochtones au Québec en tentant d'identifier leurs caractéristiques cognitives spécifiques, cela afin de distinguer celles qui relèvent des particularités culturelles montagnaises de celles qui émanent plus directement de problèmes d'adaptation scolaire. Pour ce faire, à partir de groupes appariés (2X2), les sujets ont été soumis à une batterie de tests: Kaufinan Assessment Battery for Children, Matrix Analogies Test-Short Form et Draw-APerson: Quantitative Scoring System ainsi qu'à une épreuve d'organisation spatiale (dessin Maison Arbre-Chemin:MAC). Pour cette dernière, une grille développementale a été élaborée dans le but de pouvoir comparer transculturellement les niveaux d'habiletés cognitives spécifiquement sollicitées dans l'expression graphique. La conceptualisation de l'intelligence utilisée pour cette recherche a été choisie à la lumière de théories transculturelles récentes (Beny, 1984; Dasen & De Ribaupierre, 1987). Elle fait appel au concept de "style cognitif' de même qu'à la théorie de Luria sur les hémisphères cérébraux. L'intelligence y est traitée en terme d'habiletés spécifiques, simultanées et séquentielles, de même que spatiales et perceptuelles. Les résultats indiquent des effets culturels et adaptatifs sur les performances cognitives. Ces effets montrent que les jeunes Montagnais sont plus simultanés que séquentiels dans leur appréhension d'une tâche donnée, qu'ils sont défavorisés par leurs difficultés verbales et qu'ils s'adaptent moins bien en général au système scolaire québécois. À ce stade de la recherche, les résultats obtenus à l'aide de la grille d'analyse du dessin MAC restent exploratoires.

Ce mémoire propose une étude des pièces Les Muses orphelines et Le Chemin des passes-dangereuses de Michel Marc Bouchard sous l'angle de la pragmatique de la communication. L'analyse vise à démontrer que les personnages évoluent au sein de systèmes familiaux complexes dans lesquels l'incompréhension occupe une place prépondérante. Ils forment une microsociété particulière qui instaure ses propres règles communicationnelles : celles du pouvoir, du silence, du mépris. L'étude des interactions démontre que dans ces univers marginaux et dysfonctionnels, les personnages entretiennent entre eux et avec un être absent des relations pathologiques, haineuses, voire destructrices. La mise en scène de l'absent-présent (respectivement la mère et le père) est bien l'expression d'un dysfonctionnement familial profond. En tant que figure déterminante à l'évolution des systèmes familiaux, l'absent provoque et oriente les discours et les comportements des protagonistes. Le mémoire analyse les indices de la présence de l'absent et ses répercussions sur les dynamiques relationnelles. Seule voie de communication entre les interactants, l'absent-présent plane sur toutes les relations et il met en péril la survie des systèmes en cause. À travers les mensonges et les accusations, nous assistons véritablement à la crise de cette cellule universelle qu'est la famille, vue ici à travers le filtre de la société québécoise.

Dans cette thèse, nous nous sommes intéressés à des problèmes d'ordonnancement sous contrainte d'énergie, puisque la réduction de l'énergie est devenue une nécessité, tant sur le plan économique qu'écologique. Dans le premier chapitre, nous exhibons des bornes strictes sur l'énergie d'un algorithme classique qui minimise le temps d'exécution de tâches indépendantes. Dans le second chapitre, nous ordonnançons plusieurs applications chaînées de type « streaming », et nous étudions des problèmes contraignant l'énergie, la période et la latence. Nous effectuons une étude de complexité exhaustive, et décrivons les performances de nouvelles heuristiques. Dans le troisième chapitre, nous étudions le problème de placement de répliques dans un réseau arborescent. Nous nous plaçons dans un cadre dynamique, et nous bornons à minimiser l'énergie. Après une étude de complexité, nous confirmons la qualité de nos heuristiques grâce à un jeu complet de simulations. Dans le quatrième chapitre, nous revenons aux applications « streaming », mais sous forme de graphes série-parallèles, et nous tentons de les placer sur un processeur multi-cœur. La découverte d'un algorithme polynomial sur un problème simple nous permet la conception d'heuristiques sur le problème le plus général dont nous avons établi la NP-complétude. Dans le cinquième chapitre, nous étudions des bornes énergétiques de politiques de routage dans des processeurs multi-cœurs, en comparaison avec le routage classique XY, et développons de nouvheuristiques de routage. Dans le dernier chapitre, nous étudions expérimentalement le placement d'applications sous forme de DAG sur des machines réelles. / In this thesis we have tackled a few scheduling problems under energy constraint, since the energy issue is becoming crucial, for both economical and environmental reasons. In the first chapter, we exhibit tight bounds on the energy metric of a classical algorithm that minimizes the makespan of independent tasks. In the second chapter, we schedule several independent but concurrent pipelined applications and address problems combining multiple criteria, which are period, latency and energy. We perform an exhaustive complexity study and describe the performance of new heuristics. In the third chapter, we study the replica placement problem in a tree network. We try to minimize the energy consumption in a dynamic frame. After a complexity study, we confirm the quality of our heuristics through a complete set of simulations. In the fourth chapter, we come back to streaming applications, but in the form of series-parallel graphs, and try to map them onto a chip multiprocessor. The design of a polynomial algorithm on a simple problem allows us to derive heuristics on the most general problem, whose NP-completeness has been proven. In the fifth chapter, we study energy bounds of different routing policies in chip multiprocessors, compared to the classical XY routing, and develop new routing heuristics. In the last chapter, we compare the performance of different algorithms of the literature that tackle the problem of mapping DAG applications to minimize the energy consumption.

De nombreux problèmes pratiques qui se posent dans dans le domaine de la logistique, peuvent être modélisés comme des problèmes de tournées de véhicules. De façon générale, cette famille de problèmes implique la conception de routes, débutant et se terminant à un dépôt, qui sont utilisées pour distribuer des biens à un nombre de clients géographiquement dispersé dans un contexte où les coûts associés aux routes sont minimisés. Selon le type de problème, un ou plusieurs dépôts peuvent-être présents. Les problèmes de tournées de véhicules sont parmi les problèmes combinatoires les plus difficiles à résoudre. Dans cette thèse, nous étudions un problème d’optimisation combinatoire, appartenant aux classes des problèmes de tournées de véhicules, qui est liée au contexte des réseaux de transport. Nous introduisons un nouveau problème qui est principalement inspiré des activités de collecte de lait des fermes de production, et de la redistribution du produit collecté aux usines de transformation, pour la province de Québec. Deux variantes de ce problème sont considérées. La première, vise la conception d’un plan tactique de routage pour le problème de la collecte-redistribution de lait sur un horizon donné, en supposant que le niveau de la production au cours de l’horizon est fixé. La deuxième variante, vise à fournir un plan plus précis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de l’horizon considéré. Dans la première partie de cette thèse, nous décrivons un algorithme exact pour la première variante du problème qui se caractérise par la présence de fenêtres de temps, plusieurs dépôts, et une flotte hétérogène de véhicules, et dont l’objectif est de minimiser le coût de routage. À cette fin, le problème est modélisé comme un problème multi-attributs de tournées de véhicules. L’algorithme exact est basé sur la génération de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxième partie, nous concevons un algorithme exact pour résoudre la deuxième variante du problème. À cette fin, le problème est modélisé comme un problème de tournées de véhicules multi-périodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donné. De nouvelles stratégies sont proposées pour résoudre le problème de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulière étant donné la caractéristique multi-périodes du problème général. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. La troisième partie propose un algorithme de recherche adaptative à grands voisinages où de nombreuses nouvelles stratégies d’exploration et d’exploitation sont proposées pour améliorer la performances de l’algorithme proposé en termes de la qualité de la solution obtenue et du temps de calcul nécessaire. / Many practical problems arising in real-world applications in the field of logistics can be modeled as vehicle routing problems (VRP). In broad terms, VRPs deal with designing optimal routes for delivering goods or services to a number of geographically scattered customers in a context in which, routing costs are minimized. Depending on the type of problem, one or several depots may be present. Routing problems are among the most difficult combinatorial optimization problems. In this dissertation we study a special combinatorial optimization problem, belonging to the class of the vehicle routing problem that is strongly linked to the context of the transportation networks. We introduce a new problem setting, which is mainly inspired by the activities of collecting milk from production farms and distributing the collected product to processing plants in Quebec. Two different variants of this problem setting are considered. The first variant seeks a tactical routing plan for the milk collection-distribution problem over a given planning horizon assuming that the production level over the considered horizon is fixed. The second variant aims to provide a more accurate plan by taking into account potential variations in terms of production level, which may occur during the course of a horizon. This thesis is cast into three main parts, as follows: In the first part, we describe an exact algorithm for the first variant of the problem, which is characterized by the presence of time windows, multiple depots, and a heterogeneous fleet of vehicles, where the objective is to minimize the routing cost. To this end, the problem is modeled as a multi-attribute vehicle routing problem. The exact algorithm proposed is based on the column generation approach, coupled with an elementary shortest path algorithm with resource constraints. In the second part, we design an exact framework to address the second variant of the problem. To this end, the problem is modeled as a multi-period vehicle routing problem, which explicitly takes into account potential production level variations over a horizon. New strategies are proposed to tackle the particular structure of the multi-period elementary shortest path algorithm with resource constraints. To solve realistic instances of the second variant of the problem in reasonable computation times, a heuristic approach is required. In the third part of this thesis, we propose an adaptive large neighborhood search, where various new exploration and exploitation strategies are proposed to improve the performance of the algorithm in terms of solution quality and computational efficiency.

Cette thèse porte sur les problèmes de tournées de véhicules avec fenêtres de temps où un gain est associé à chaque client et où l'objectif est de maximiser la somme des gains recueillis moins les coûts de transport. De plus, un même véhicule peut effectuer plusieurs tournées durant l'horizon de planification. Ce problème a été relativement peu étudié en dépit de son importance en pratique. Par exemple, dans le domaine de la livraison de denrées périssables, plusieurs tournées de courte durée doivent être combinées afin de former des journées complètes de travail. Nous croyons que ce type de problème aura une importance de plus en plus grande dans le futur avec l'avènement du commerce électronique, comme les épiceries électroniques, où les clients peuvent commander des produits par internet pour la livraison à domicile. Dans le premier chapitre de cette thèse, nous présentons d'abord une revue de la littérature consacrée aux problèmes de tournées de véhicules avec gains ainsi qu'aux problèmes permettant une réutilisation des véhicules. Nous présentons les méthodologies générales adoptées pour les résoudre, soit les méthodes exactes, les méthodes heuristiques et les méta-heuristiques. Nous discutons enfin des problèmes de tournées dynamiques où certaines données sur le problème ne sont pas connues à l'avance. Dans le second chapitre, nous décrivons un algorithme exact pour résoudre un problème de tournées avec fenêtres de temps et réutilisation de véhicules où l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problème est modélisé comme un problème de tournées avec gains. L'algorithme exact est basé sur une méthode de génération de colonnes couplée avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour résoudre des instances de taille réaliste dans des temps de calcul raisonnables, une approche de résolution de nature heuristique est requise. Le troisième chapitre propose donc une méthode de recherche adaptative à grand voisinage qui exploite les différents niveaux hiérarchiques du problème (soit les journées complètes de travail des véhicules, les routes qui composent ces journées et les clients qui composent les routes). Dans le quatrième chapitre, qui traite du cas dynamique, une stratégie d'acceptation et de refus des nouvelles requêtes de service est proposée, basée sur une anticipation des requêtes à venir. L'approche repose sur la génération de scénarios pour différentes réalisations possibles des requêtes futures. Le coût d'opportunité de servir une nouvelle requête est basé sur une évaluation des scénarios avec et sans cette nouvelle requête. Enfin, le dernier chapitre résume les contributions de cette thèse et propose quelques avenues de recherche future. / This thesis studies vehicle routing problems with time windows, where a gain is associated with each customer and where the objective is to maximize the total gain collected minus the routing costs. Furthermore. the same vehicle might be assigned to different routes during the planning horizon. This problem has received little attention in the literature in spite of its importance in practice. For example, in the home delivery of perishable goods (like food), routes of short duration must be combined to form complete workdays. We believe that this type of problem will become increasingly important in the future with the advent of electronic services, like e-groceries, where customers can order goods through the Internet and get these goods delivered at home. In the first chapter of this thesis, we present a review of vehicle routing problems with gains, as well as vehicle routing problems with multiple use of vehicles. We discuss the general classes of problem-solving approaches for these problems, namely, exact methods, heuristics and metaheuristics. We also introduce dynamic vehicle routing problems, where new information is revealed as the routes are executed. In the second chapter, we describe an exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles, where the first objective is to maximize the number of served customers. To this end, the problem is modeled as a vehicle routing problem with gains. The exact algorithm is based on column generation, coupled with an elementary shortest path algorithm with resource constraints. To solve realistic instances in reasonable computation times, a heuristic approach is required. The third chapter proposes an adaptative large neighborhood search where the various hierarchical levels of the problem are exploited (i.e., complete vehicle workdays, routes within workdays and customers within routes). The fourth chapter deals with the dynamic case. In this chapter, a strategy for accepting or rejecting new customer requests is proposed. This strategy is based on the generation of multiple scenarios for different realizations of the requests in the future. An opportunity cost for serving a new request is then computed, based on an evaluation of the scenarios with and without the new request. Finally, the last chapter summarizes the contributions of this thesis and proposes future research avenues.