Cette thèse apporte une généralisation du principe de recommandation des systèmes de recommandation. Au lieu de considérer une recommandation comme un item, elle est considérée comme une combinaison constituée de plusieurs items suivant un pattern donné. Une recommandation d'un seul item est alors un cas particulier de ce type de recommandation. L'architecture de système de recommandation proposé se base sur une architecture dérivée des travaux en systèmes hypermédia adaptatifs. Trois couches sont définies : une couche sémantique, une couche utilisateur et une couche intelligence. La couche sémantique est constituée de deux sous-couches, une sous-couche modélisant le contenu suivant la connaissance générale du domaine et une sous-couche modélisant le contenu suivant la connaissance spécifique à l'application, plus précisément spécifique aux possibles contraintes des utilisateurs dans l'application. Cette deuxième partie permet de prendre en compte le savoir-faire du fournisseur de l'offre dans les propositions du système de recommandation. La couche utilisateur modélise l'utilisateur au sein du système de recommandation et la couche intelligence contient le processus de recommandation. Nous proposons de décomposer ce dernier en deux sous-processus principaux, un processus dit de projection des individus du domaine sur les profils utilisateurs et un processus de recherche combinatoire. Le premier apporte une pondération, appelée note dans la plupart des systèmes de recommandation, donnant les intérêts probables des utilisateurs pour les différents items. Le processus de recherche combinatoire recherche parmi la multitude de combinaisons possibles, une solution convenable (optimale si possible) à proposer à l'utilisateur. Cette architecture de système de recommandation combinatoire est appliquée au domaine touristique pour l'entreprise Côte-d'Or Tourisme impliquée dans le contrat de recherche. Le but de cette application est de proposer à l'utilisateur un ensemble d'offres touristiques sous forme de séjour. Ce problème touristique amène à la définition formelle d'un problème d'optimisation combinatoire qui est une variante d'un sous-problème du problème de sac à dos. Pour résoudre ce genre de problème, il est nécessaire d'utiliser une métaheuristique afin de tendre vers une bonne solution en un temps raisonnable. Nous présentons un algorithme basé sur le recuit simulé et un algorithme multi-objectif pour la résolution de ce problème. L'instanciation de chaque couche de l'architecture pour le système touristique est décrite en détail. Enfin, cette thèse présente une application mobile faisant office d'interface utilisateur avec le système de recommandation touristique et elle présente les développements techniques nécessaires à ce projet, étant donné son contexte industriel.

Le problème de tournées de véhicules (VRP) implique de planifier les itinéraires d'une flotte de véhicules afin de desservir un ensemble de clients à moindre coût. Ce problème d'optimisation combinatoire NP-difficile apparait dans de nombreux domaines d'application, notamment en logistique, télécommunications, robotique ou gestion de crise dans des contextes militaires et humanitaires. Ces applications amènent différents contraintes, objectifs et décisions supplémentaires ; des "attributs" qui viennent compléter les formulations classiques du problème. Les nombreux VRP Multi-Attributs (MAVRP) qui s'ensuivent sont le support d'une littérature considérable, mais qui manque de méthodes généralistes capables de traiter efficacement un éventail significatif de variantes. Par ailleurs, la résolution de problèmes "riches", combinant de nombreux attributs, pose d'importantes difficultés méthodologiques. Cette thèse contribue à relever ces défis par le biais d'analyses structurelles des problèmes, de développements de stratégies métaheuristiques, et de méthodes unifiées. Nous présentons tout d'abord une étude transversale des concepts à succès de 64 méta-heuristiques pour 15 MAVRP afin d'en cerner les "stratégies gagnantes". Puis, nous analysons les problèmes et algorithmes d'ajustement d'horaires en présence d'une séquence de tâches fixée, appelés problèmes de "timing". Ces méthodes, développées indépendamment dans différents domaines de recherche liés au transport, ordonnancement, allocation de ressource et même régression isotonique, sont unifiés dans une revue multidisciplinaire. Un algorithme génétique hybride efficace est ensuite proposé, combinant l'exploration large des méthodes évolutionnaires, les capacités d'amélioration agressive des métaheuristiques à voisinage, et une évaluation bi-critère des solutions considérant coût et contribution à la diversité de la population. Les meilleures solutions connues de la littérature sont retrouvées ou améliorées pour le VRP classique ainsi que des variantes avec multiples dépôts et périodes. La méthode est étendue aux VRP avec contraintes de fenêtres de temps, durée de route, et horaires de conducteurs. Ces applications mettent en jeu de nouvelles méthodes d'évaluation efficaces de contraintes temporelles relaxées, des phases de décomposition, et des recherches arborescentes pour l'insertion des pauses des conducteurs. Un algorithme de gestion implicite du placement des dépôts au cours de recherches locales, par programmation dynamique, est aussi proposé. Des études expérimentales approfondies démontrent la contribution notable des nouvelles stratégies au sein de plusieurs cadres méta-heuristiques. Afin de traiter la variété des attributs, un cadre de résolution heuristique modulaire est présenté ainsi qu'un algorithme génétique hybride unifié (UHGS). Les attributs sont gérés par des composants élémentaires adaptatifs. Des expérimentations sur 26 variantes du VRP et 39 groupes d'instances démontrent la performance remarquable de UHGS qui, avec une unique implémentation et paramétrage, égalise ou surpasse les nombreux algorithmes dédiés, issus de plus de 180 articles, révélant ainsi que la généralité ne s'obtient pas forcément aux dépends de l'efficacité pour cette classe de problèmes. Enfin, pour traiter les problèmes riches, UHGS est étendu au sein d'un cadre de résolution parallèle coopératif à base de décomposition, d'intégration de solutions partielles, et de recherche guidée. L'ensemble de ces travaux permet de jeter un nouveau regard sur les MAVRP et les problèmes de timing, leur résolution par des méthodes méta-heuristiques, ainsi que les méthodes généralistes pour l'optimisation combinatoire. / The Vehicle Routing Problem (VRP) involves designing least cost delivery routes to service a geographically-dispersed set of customers while taking into account vehicle-capacity constraints. This NP-hard combinatorial optimization problem is linked with multiple applications in logistics, telecommunications, robotics, crisis management in military and humanitarian frameworks, among others. Practical routing applications are usually quite distinct from the academic cases, encompassing additional sets of specific constraints, objectives and decisions which breed further new problem variants. The resulting "Multi-Attribute" Vehicle Routing Problems (MAVRP) are the support of a vast literature which, however, lacks unified methods capable of addressing multiple MAVRP. In addition, some "rich" VRPs, i.e. those that involve several attributes, may be difficult to address because of the wide array of combined and possibly antagonistic decisions they require. This thesis contributes to address these challenges by means of problem structure analysis, new metaheuristics and unified method developments. The "winning strategies" of 64 state-of-the-art algorithms for 15 different MAVRP are scrutinized in a unifying review. Another analysis is targeted on "timing" problems and algorithms for adjusting the execution dates of a given sequence of tasks. Such methods, independently studied in different research domains related to routing, scheduling, resource allocation, and even isotonic regression are here surveyed in a multidisciplinary review. A Hybrid Genetic Search with Advanced Diversity Control (HGSADC) is then introduced, which combines the exploration breadth of population-based evolutionary search, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and a bi-criteria evaluation of solutions based on cost and diversity measures. Results of remarkable quality are achieved on classic benchmark instances of the capacitated VRP, the multi-depot VRP, and the periodic VRP. Further extensions of the method to VRP variants with constraints on time windows, limited route duration, and truck drivers' statutory pauses are also proposed. New route and neighborhood evaluation procedures are introduced to manage penalized infeasible solutions w.r.t. to time-window and duration constraints. Tree-search procedures are used for drivers' rest scheduling, as well as advanced search limitation strategies, memories and decomposition phases. A dynamic programming-based neighborhood search is introduced to optimally select the depot, vehicle type, and first customer visited in the route during local searches. The notable contribution of these new methodological elements is assessed within two different metaheuristic frameworks. To further advance general-purpose MAVRP methods, we introduce a new component-based heuristic resolution framework and a Unified Hybrid Genetic Search (UHGS), which relies on modular self-adaptive components for addressing problem specifics. Computational experiments demonstrate the groundbreaking performance of UHGS. With a single implementation, unique parameter setting and termination criterion, this algorithm matches or outperforms all current problem-tailored methods from more than 180 articles, on 26 vehicle routing variants and 39 benchmark sets. To address rich problems, UHGS was included in a new parallel cooperative solution framework called "Integrative Cooperative Search (ICS)", based on problem decompositions, partial solutions integration, and global search guidance. This compendium of results provides a novel view on a wide range of MAVRP and timing problems, on efficient heuristic searches, and on general-purpose solution methods for combinatorial optimization problems. / Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Les services de livraison express font face au défi d’optimiser les routes de leurs véhicules alors que ceux-ci circulent dans un réseau routier où les temps de parcours varient en fonction du moment de la journée et où ils doivent répondre à l’arrivée dynamique de requêtes consistant à récupérer et livrer des colis. Notre but ici est de proposer une modélisation et une méthode de type heuristique pour résoudre ce problème. Nous commençons par explorer les travaux menés précédemment au sujet de l’arrivée dynamique des requêtes, des temps de parcours variables selon le moment de la journée et des collectes et livraisons dans les problèmes de tournées de véhicules. Ensuite, nous décrivons le problème de manière formelle sur le graphe du réseau routier avec des requêtes deux-points où l’objectif est de minimiser le temps total de parcours des véhicules et les temps de retard aux points de service et au dépôt. Par la suite, nous détaillons l’implémentation d’une méthode de résolution basée sur la recherche tabou utilisant une structure de voisinage basée sur la réinsertion d’une requête. Cette méthode utilise également la structure Dominant Shortest Path (DSP) qui considère plusieurs chemins alternatifs entre chaque paire de sommets, contrairement à l’approche traditionnelle où un chemin unique est fixé a priori. Finalement, nous testons notre méthode à l’aide de 390 instances générées de manière synthétique afin d’évaluer son efficacité ainsi que l’impact de certains aspects du problème et de la méthode de résolution. Les résultats démontrent une amélioration particulièrement importante due à l’utilisation de la structure DSP. / Express delivery services face the challenge of optimizing the routes of their vehicles while they are moving in a road network where the travel times vary according to the time of day in order to serve dynamic requests which consist in collecting and delivering parcels. Our goal here is to propose a model and a heuristic method to solve this problem. We begin by exploring previous work on the topic of the dynamic arrival of requests, timedependent travel times and pickups and deliveries in vehicle routing problems. Afterwards, we describe the problem formally on the graph of the road network with the objective of minimizing the total travel time of the vehicles and lateness at the service points and at the depot. Then, we detail the implementation of a solving method based on tabu search using a neighbourhood structure based on the reinsertion of a request. This method also uses the Dominant Shortest Path (DSP) structure which considers multiple alternative paths between each pair of vertices, unlike the traditional approach where a single path is fixed a priori. Finally, we test our method using 390 instances generated synthetically in order to evaluate its efficiency as well as the impact of certain aspects of the problem and solution method. The results show a particularly significant improvement due to the use of the DSP structure.

L’industrie forestière est un secteur qui, même s’il est en déclin, se trouve au cœur du débat sur la mondialisation et le développement durable. Pour de nombreux pays tels que le Canada, la Suède et le Chili, les objectifs sont de maintenir un secteur florissant sans nuire à l’environnement et en réalisant le caractère fini des ressources. Il devient important d’être compétitif et d’exploiter de manière efficace les territoires forestiers, de la récolte jusqu’à la fabrication des produits aux usines, en passant par le transport, dont les coûts augmentent rapidement. L’objectif de ce mémoire est de développer un modèle de planification tactique/opérationnelle qui permet d’ordonnancer les activités pour une année de récolte de façon à satisfaire les demandes des usines, sans perdre de vue le transport des quantités récoltées et la gestion des inventaires en usine. L’année se divise en 26 périodes de deux semaines. Nous cherchons à obtenir les horaires et l’affectation des équipes de récolte aux blocs de coupe pour une année. Le modèle mathématique développé est un problème linéaire mixte en nombres entiers dont la structure est basée sur chaque étape de la chaine d’approvisionnement forestière. Nous choisissons de le résoudre par une méthode exacte, le branch-and-bound. Nous avons pu évaluer combien la résolution directe de notre problème de planification était difficile pour les instances avec un grand nombre de périodes. Cependant l’approche des horizons roulants s’est avérée fructueuse. Grâce à elle en une journée, il est possible de planifier les activités de récolte des blocs pour l’année entière (26 périodes). / Forest industry is a sector located at the heart of the debate on globalisation and sustainable development, even if it is in decline. For many countries like Canada, Sweden and Chile, the objectives are to maintain a flourishing sector without damaging the environment and to realize the finite nature of resources. It is important to be competitive and to operate effectively on forest territories, from harvesting to manufacturing products, through transport, in a context where costs increase rapidly. This master’s thesis is developing a tactical operational planning model to organize activities for a year to meet requests for factories, without losing sight of the transport of harvested quantities and inventory management factory. The year is divided into 26 periods of two weeks. We seek harvest teams schedules and assignment to harvest areas (units) for a year. The problem is formulated as a mixed integer programming model, whose structure is based on each stage of the forest supply chain. We choose to solve it by an exact method, branch-and-bound. We were able to assess how the direct resolution of our planning problem was difficult for instances with a large number of periods. However the rolling horizon approach has proved successful. In a day, we obtained the harvest activities planning for 26 periods.

Dans le cadre de cette thèse, nous nous sommes intéressés à la mise en œuvre d'algorithmes auto-adaptatifs d'Intelligence Collective pour la résolution de problèmes d'optimisation modélisés dans un langage de Programmation par contraintes (PPC). Nous avons porté une attention particulière à la famille d'algorithmes de type " Ant Colony Optimization " (ACO). Nous avons développé trois contributions, à savoir : (1) Intégration des algorithmes de type ACO dans un langage de programmation par contraintes pour la résolution de problèmes de satisfaction de contraintes; (2) Proposition d'un algorithme hybride et générique où ACO est couplé à une approche complète pour résoudre des problèmes d'optimisation combinatoires (3) Proposition d'une stratégie capable d'adapter dynamiquement les paramètres de ACO.

.

L'effet protecteur de la circoncision masculine (CM) contre l'acquisition hétérosexuelle du VIH chez les hommes a été démontré dans trois essais contrôlés randomisés menés en Afrique australe et de l'Est, et sa généralisation a été recommandée par l'OMS et l'ONUSIDA comme une composante complémentaire importante des stratégies de prévention du VIH dans les pays à forte incidence du virus et bas taux de CM. Cependant, la généralisation de la CM dans les communautés ou elle n'est pas une norme sociale pose de nombreux défis en ce qui concerne son acceptabilité, son implémentation, son acceptation et son impact sur les comportements sexuels ainsi que sur les connaissances, attitudes et pratiques concernant la CM. Le projet ANRS 12126 Bophelo Pele a été implémenté à la suite des recommandations internationales dans la communauté d'Orange Farm, en Afrique du Sud, site du premier essai randomisé contrôlé sur la CM, et communauté cible de cette stratégie. Les activités de recherche menées au sein du projet prouvent que la généralisation de la CM est acceptable et réalisable rapidement dans une communauté à ressources limitées, selon les directives des instances internationales, de manière sure et coût-efficace. Son acceptation parmi les hommes non-circoncis est satisfaisante. De plus, trois ans après l'implémentation du projet, et bien que les connaissances envers la CM et son effet sur le risque du VIH restent à être améliorées, aucune différence de comportement sexuel n'a été décelée entre les hommes circoncis et les hommes non-circoncis ainsi qu'entre les partenaires des hommes circoncis et celles des hommes non-circoncis. La CM comme méthode de prévention du VIH dans les communautés hyperendémiques est donc une stratégie qui promet d'avoir un impact considérable sur l'épidémie en Afrique australe et de l'Est.

Le problème de la classification non supervisée (clustering) a été largement étudié dans le contexte de l'analyse de données, où la structure naturelle des données est dévoilée en groupant des objets similaires tout en séparant ceux qui ne le sont pas. L'Aide Multicritère à la Décision (AMCD) modélise les préférences de décideurs et les aide à choisir une solution appropriée parmi un ensemble d'alternatives. Dans ce contexte, les problématiques du choix, du tri et du rangement ont été largement étudiés, alors que celle du clustering l'a été bien moins. De plus, la plupart de ces approches de résolution en AMCD utilisent des mesures de similarité et n'exploitent pas l'information préférentielle supplémentaire qui est disponible. Dans cette thèse nous étudions ce problème du clustering en AMCD en faisant d'abord un parallèle entre l'analyse de données et l'AMCD pour ensuite proposer le problème de la classification non supervisée en AMCD. Différents modèles sont alors proposés pour résoudre ce problème, ainsi que des algorithmes de résolution, qui sont validés sur un grand nombre de problèmes générés artificiellement. Pour terminer, nous envisageons différentes applications via l'utilisation de différentes mesures descriptives des classes, ainsi que l'extension des algorithmes à des volumes de données importants. Une application est résolue à la fin de la thèse pour illustrer l'intérêt des outils proposés.

Condition essentielle de l’exercice des libertés individuelles et collectives, la sécurité intérieure est au centre des préoccupations des citoyens et de leurs gouvernants. Dès lors, la criminalité contemporaine, phénomène multi-causal, a considérablement évolué, tant par son ampleur que par sa nature, nécessitant, dans le respect des libertés fondamentales, la mise en oeuvre d’une politique ambitieuse. Pour parer aux menaces ou aux manifestations de la criminalité contemporaine, des lois nombreuses et récentes sont venues reformuler le caractère prioritaire des orientations de l’Etat en matière de sécurité intérieure et de justice. Elles s’articulent autour des réformes structurelles, placées sous le signe d’une coopération approfondie entre les acteurs de la sécurité, mais aussi d’une volonté de leur fournir un cadre administratif et juridique rénové. Complétant ce dispositif global de lutte contre la criminalité contemporaine, la criminalité apparaît également comme un instrument qui joue un rôle indispensable dans la conduite des enquêtes pénales. Désormais, elle contribue, dans une large mesure, à l’administration de la preuve pénale, en cas de présomption de crime et d’autres infractions, au sein du dispositif global de sécurité intérieure. Mais, au-delà d’une simple aide apportée à la science de l’enquête, son avenir réside dans une meilleure exploitation, et donc efficacité de celle-ci. Ainsi, c’est par une politique s’appuyant aussi bien sur une rénovation ambitieuse du cadre institutionnel et juridique que sur les avancées concomitantes de la criminalistique que l’Etat pourra parvenir à infléchir la criminalité contemporaine. / The essential condition for the exercise of individual and collective freedoms roots itself in the notion of security, it is the cornerstone of the republican contract and the main concern of our leaders and citizens. It must be said that contemporary crime, a multi-causal phenomenon, has changed considerably, in its scope and in its basic nature, requiring, in respect of fundamental freedoms, the implementation of an ambitious security policy. Thus, some current legislation has been formulated on order to highlight the areas of highest priority for internal security and justice. Those legislations are base on one hand around some structural reforms under the sign of deepened cooperation between security bodies, and on the other hand, through a willing to provide an overall new legal and administrative framework. Adding to this throughout system which stands to fight against contemporary crime, criminalistics appears to be a key instrument. Notably playing an indispensable role in the conduct of criminal investigations, it is a leading force, to a large extent in the repression of crime and offenses in general within the overall system of internal security. Hence and notwithstanding the administration of criminal evidence by criminalistics is presented as a rational solution in the treatment of physical evidence in order to discover the truth. It is only a complementary solution and a simple help given to support the science of investigation. The future of the system lies in a greater exploration of this resource as it will enable the system to become more efficient. Thus, it is only through an uncompromising stance, utilizing knowledge from criminalistics and an ambitious advanced renovation of the institutional and legal framework, that the state will curb contemporary crime.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.