Un déploiement adéquat et une bonne gestion des ambulances amènent des temps de réponse plus courts lors d'un appel d'urgence et ainsi permettent de réduire la souffrance, la mortalité et les conséquences néfastes sur la santé des patients. Ce mémoire est divisé en deux parties et adresse sous forme de deux articles les problèmes de la localisation des ambulances et de leur gestion. L'objectif du premier article est de résoudre le problème de localisation d'ambulances multi-périodes en faisant l'hypothèse d'une demande déterministe, dynamique et cyclique. Un modèle mathématique ainsi que deux méthodes heuristiques sont proposés pour aider à résoudre ce problème. La première heuristique utilise de façon répétitive la version mono-période du modèle mathématique proposé alors que la deuxième est une heuristique itérative composée d'une phase de construction et une phase d'amélioration. L'efficacité de ces méthodes est démontrée par leur application pour résoudre des problèmes fictifs ainsi qu'un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus avec les deux méthodes heuristiques nous indiquent que ces méthodes, en plus d'être très rapides, donnent des plans de déploiement près du plan optimal. De plus, la méthode heuristique basée sur le modèle mono-période semble dominer la méthode heuristique itérative sur tous les points en plus d'être plus simple. L'objectif du deuxième article est d'évaluer l'efficacité de plusieurs règles de répartition dans le cadre de la gestion des demandes d'intervention d'un réseau de service ambulancier. Deux types de décisions font l'objet de cette étude : le choix d'une ambulance pour répondre à une demande d'intervention et le choix du poste d'attente où ce véhicule sera redéployé après son intervention. Les règles généralement utilisées en pratique sont comparées à des règles visant non seulement la réduction des temps d'attente mais aussi le maintient d'une bonne couverture territoriale. Différentes règles sont testées sur des problèmes fictifs ainsi que sur un problème réel fourni par la corporation Urgences-santé. Les résultats obtenus démontrent que l'application d'une règle d'assignation simple comme affecter l'ambulance qui peut se rendre le plus rapidement possible sur les lieux de la demande d'intervention peut être efficace seulement si un bon plan de déploiement et de redéploiement est maintenu. On démontre que l'utilisation d'une règle de redéploiement visant la maximisation de la couverture du territoire permet d'atteindre un bon niveau d'efficacité.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal. / Angoisse, agressivité, séduction, acceptation du conflit, désir, autant de sentiments et autant de questions qui sont au cœur de mon quotidien. Le praticien, enseignant éducateur, trouvera, je l'espère, dans cette recherche des éclairages qui semblent être à la base du métier d'enseignant tout comme peuvent l'être un certain nombre de théories de l'apprentissage ou d'approches didactiques. Aujourd'hui on touche une réalité qui n'a pas toujours existé : celle de la personne comme lieu d'ancrage réciproque de la liberté individuelle et du devenir de la société. Ainsi dans l'espace d'une classe, si la communauté importe avant tout, elle n'aurait à nier ni un sujet dans son individualité, ni les relations intersubjectives qui les lient puisque ce sont les différents sujets qui forment cette même communauté. Plusieurs auteurs ont noté l'importance de la relation enseignant-enseigné(s) en éducation. En effet, cette relation, développant chez l'enseigné ce qu'on appelle l'estime de soi, joue un rôle souvent décisif dans la motivation à l'apprentissage et, par le fait même, dans la réussite scolaire. Les mêmes auteurs, font du même coup état des pièges inhérents à la relation enseignant-enseigné(s), relation professionnelle dont la qualité propre tient à sa dimension éducative. L'objet de cette recherche est de vérifier la possibilité de baliser la relation enseignant-enseigné(s) par des règles d'hygiène relationnelle. La problématique de la recherche vient d'une expérience vécue dans mon rôle d'enseignant. La méthode utilisée fait partie d'une catégorie générale d'approche heuristiques. Mon approche implique une recherche à l'intérieur le soi. Je me suis inspirée de mon histoire de vie en tant qu'élève et enseignante, de certains auteurs et des entrevues effectuées auprès d'enseignants du primaire régulier et de classes spéciales. Dans un premier temps, je donne l'état de la question vu par différents auteurs. Ensuite, suivra un résumé théorique sur ce qu'est la relation éducative travers la relation enseignant-enseigné(s). J'enchaînerai sur les pièges, les exigences et les abus existants dans cette même relation enseignant-enseigné(s) et je terminerai le chapitre en donnant des informations concernant la professionnalisation de l'enseignement. Dans un deuxième temps, je donne un résumé des entrevues réalisées auprès d'enseignants concernant l'importance accordée à la relation enseignant-enseigné(s), l'apport de la formation initiale et continue pour favoriser cette relation, les conditions requises pour améliorer la relation enseignant-enseigné(s) et leur positionnement face à la création de règles pour baliser la relation enseignant-enseigné(s). Dans un troisième temps, je vous inviterai à entendre une partie de mon histoire de vie en tant qu'élève et aussi enseignante. Ce volet est très important puisque l'intérêt de la recherche s'est posé suite à mes propres expériences. À l'analyse de la recherche, je fais ressortir les liens existants entre mon histoire de vie et l'avis des enseignants, je donne un aperçu global de l’ensemble de cette étude et je conclus en dormant les résultats de toute cette démarche. Les résultats de cette recherche visent à favoriser une meilleure compréhension de ma réalité actuelle et à servir d'amorce à une réflexion. De plus, ils visent à trouver une solution possible pour améliorer la relation enseignant-enseigné(s). Dans ma recherche, j'essaie de réduire au maximum la distance chercheur-acteur en vivant simultanément ces deux réalités.

Au Québec, près de 13 % des élèves âgés de 9 à 15 ans présentent des difficultés de compréhension en lecture (PIRLS, 2016 ; CMEC, 2019). Comme la compréhension en lecture est un outil d'apprentissage dans toutes les matières scolaires, ces élèves risquent d'éprouver des difficultés scolaires et de se retrouver en situation d'échec. Selon les résultats des évaluations internationales sur la lecture, le pourcentage d'élèves qui ne possèdent pas les habiletés de base pour comprendre ce qu'ils lisent n'a pas diminué depuis 2001 malgré la mise en place de programmes visant à valoriser la lecture (PIRLS, 2016). Le ministère de l'Éducation du Québec recommande d'organiser les services scolaires selon le modèle de réponse à l'intervention (RAI ; Gouvernement du Québec, 2020). Pour utiliser le modèle de RAI dans les écoles québécoises, l'enseignement dans les classes doit être de qualité et appuyé sur les données probantes issues de la recherche afin de permettre au plus grand nombre possible d'élèves de s'améliorer. De plus, les interventions offertes dans les classes doivent permettre d'identifier les élèves qui présentent des difficultés persistantes afin de les orienter vers des services individualisés (Desrochers et coll., 2016 ; Vaughn et coll., 2003). Pour favoriser l'utilisation du modèle de RAI en lecture, les enseignants ont donc besoin de tâches d'évaluation adaptées au contexte de leur classe afin d'identifier les élèves en difficulté et de baser leur enseignement sur les données probantes issues de la recherche. Évaluer l'efficacité des interventions mises en place dans des classes québécoises est aussi nécessaire afin de préciser quelles sont les pratiques qui ont les impacts les plus positifs sur les apprentissages en lecture. En s'appuyant sur le modèle heuristique de la compréhension en lecture (Snow, 2002) et sur la théorie de l'autodétermination (TAD ; Deci & Ryan, 2000, 2017), cette thèse permet de documenter et d'évaluer des pratiques efficaces en matière d'évaluation et d'intervention en compréhension de lecture chez les élèves de sixième année. Le premier article inclus dans cette thèse rapporte les résultats de la traduction, de l'adaptation et de la normalisation d'un test américain de dépistage des difficultés en lecture (TOSREC ; Wagner et coll., 2010) pouvant être distribué à l'ensemble des élèves d'une classe de sixième année à trois reprises durant l'année scolaire afin d'identifier les élèves à risque d'échouer à l'examen ministériel québécois de sixième année et de suivre leurs progrès. Le second article est une recension narrative systématique des études traitant d'interventions visant à améliorer la lecture des élèves de 10 à 21 ans. Enfin, le dernier article de cette thèse présente les résultats de la mise en place de deux interventions visant à développer la compréhension en lecture d'élèves de sixième année en soutenant leur motivation à lire et en favorisant l'implantation de pratiques pédagogiques visant le développement du vocabulaire et l'enseignement explicite de six stratégies principales en lecture. / In Quebec, nearly 13% of students between the ages of 9 and 15 have reading difficulties (PIRLS, 2016; CMEC, 2019). Since reading comprehension is a learning tool for all school subjects, these students might experience academic difficulties and risk failing. According to the results of international reading assessments, the percentage of students who do not have the basic skills to understand when they read has not decreased since 2001 despite the creation of programs to promote reading (PIRLS, 2016). The Ministry of Education recommends organizing school services according to the Response to Intervention (RTI) model. To use the RTI model in Quebec schools, classroom instruction must be of high quality and based on research evidence in order to allow as many students as possible to improve. In addition, the interventions offered in class must identify students who have persistent difficulties in order to guide them to individualize services (Desrochers et al., 2016, Vaughn et al., 2003). To promote the use of the RAI model in reading, teachers therefore need assessment tasks adapted to the context of their class in order to identify students in difficulty and need to base their teaching on evidence from research. Evaluating the effectiveness of Quebec's intervention programs is also necessary in order to specify the most effective practices that allow students to improve in reading. Based on the heuristic model of reading comprehension (Snow, 2002) and on the Self-Determination Theory (STD ; Ryan & Deci, 2000, 2017), this thesis documents and evaluates effective practices in the assessment and intervention of reading comprehension of sixth grade students. The first article included in this thesis reports the results of the translation, adaptation, and standardization of an American reading test (TOSREC; Wagner et coll., 2010) that can be distributed to an entire sixth-grade class three times during the school year in order to monitor student progress and identify students at risk of failing the ministerial exam. The second article is a systematic narrative review of research aimed at improving reading comprehension among students of 10 to 21 years old. Finally, the last article of this thesis presents the efficacy of the implementation of two interventions aimed at developing the reading comprehension of sixth grade students by supporting their motivation to read and by promoting the implementation of effective teaching practices such as vocabulary development and explicit teaching of six main reading strategies.

Cette recherche introduit un modèle de décision multiobjectif qui aide le gestionnaire de projets à allouer les ressources à son projet. Le modèle comporte trois axes de décision représentant les compromis à faire entre la durée du projet, le coût du projet et les quantités de ressources allouées. L'allocation des ressources est déterminée en considérant le coût de chaque ressource. Le modèle incorpore le processus d'assignation des ressources, une problématique typique de l'affectation des ressources en gestion projets, à celui de !'ordonnancement des activités. Pour le résoudre, il a fallu concevoir et expérimenter de nouveaux algorithmes. La recherche comporte trois volets où chacun des volets alimente le volet suivant. Le premier volet propose de nouvelles procédures pour minimiser la durée du projet sous contraintes de disponibilités variables de ressources, dans le cas de problèmes ayant des activités avec un seul mode de réalisation ou de problèmes ayant des activités avec plusieurs modes de réalisation. Ces procédures comprennent une nouvelle règle de priorité selon un schème que nous qualifions d'ensembliste et une adaptation de la méthode Tabou. Les résultats de l'expérimentation montrent l'efficacité de la nouvelle règle de priorité et de l'adaptation de la méthode Tabou. Le deuxième volet propose des procédures pour minimiser le coût de disponibilité et le coût d'assignation des ressources allouées sous contrainte d'une date d'échéance du projet. La procédure incorpore l'adaptation de la méthode Tabou élaborée au volet précédent. Les résultats de l'expérimentation montrent la bonne performance des procédures développées. Le troisième volet propose une approche interactive par laquelle le gestionnaire de projets évalue des choix d'allocation de ressources afin de parvenir à une solution de compromis entre les trois axes de décision. Pour y parvenir, on évalue des solutions dans une région délimitée par les buts du gestionnaire de projets au lieu d'effectuer une approximation de la frontière efficace. L'expérimentation montre la faisabilité de l'approche interactive ainsi que l'efficacité de l'adaptation proposée de la méthode Tabou. Ces trois volets permettent d'élaborer l'architecture d'un Système Interactif d'Aide à la Décision pour l'allocation multiobjective des ressources en gestion de projets.

Dans l'industrie de la fabrication de planchers de bois pour les remorques, la qualité d'un plancher est directement liée à la position relative des lattes de bois. Le procédé de fabrication actuellement en place chez notre partenaire industriel utilise une main-d'oeuvre abondante. Les planchers sont produits en continu et puisque les décisions de positionnement de lattes doivent se prendre très rapidement (chaque employé doit placer une latte à toutes les 1,5 seconde), même des employés d'expérience peuvent commettre des erreurs. Dans ce mémoire, nous proposons des méthodes rapides et efficaces pouvant être utilisées par un processus d'assemblage mécanique. Ces méthodes ont été utilisées pour assembler des planchers à l'aide de simulation par ordinateur. Par comparaison à l'assemblage manuel, qui produit des planchers ayant environ 5% de joints défectueux, nos méthodes d'assemblage produisent des planchers presque parfaits.

Les problèmes d'optimisation combinatoire sont généralement NP-difficiles et les méthodes exactes demeurent inefficaces pour les résoudre rapidement. Les métaheuristiques sont des méthodes génériques de résolution connues et utilisées pour leur efficacité. Elles possèdent souvent plusieurs paramètres qui s'avèrent fastidieux à régler pour obtenir de bonnes performances. Il est alors intéressant de chercher à rendre plus évident, voire à automatiser, ce réglage des paramètres. Le paysage d'un problème d'optimisation combinatoire est une structure, basée sur la notion de voisinage, permettant de caractériser le problème puis de suivre la dynamique d'une méthode d'optimisation pour comprendre son efficacité. Les travaux de cette thèse portent sur l'analyse de paysage de problèmes d'optimisation combinatoire et le lien étroit avec certaines classes de métaheuristiques, basées sur une exploration du voisinage des solutions. Ainsi, nous montrons l'influence de la structure de paysage sur la dynamique d'une métaheuristique, pour deux problèmes issus de la logistique. Ensuite, nous analysons les caractéristiques du paysage qui permettent de concevoir et/ou paramétrer des métaheuristiques, principalement des recherches locales, efficaces. La neutralité est, en particulier, une caractéristique structurelle importante des paysages. De tels paysages présentent de nombreux plateaux bloquant la progression d'une recherche locale. Après une analyse fine des plateaux, nous prouvons que cette structure neutre ne doit pas être ignorée. Puis, nous utilisons plusieurs informations liées à la neutralité, et plus particulièrement aux plateaux bloquants, pour concevoir une première recherche locale simple à mettre en œuvre et efficace. Enfin, pour approfondir nos travaux sur les structures neutres, nous avons choisi d'exploiter la neutralité à tous les niveaux du paysage pour concevoir une nouvelle recherche locale basée sur la capacité des solutions d'un même plateau à produire une amélioration. Une stratégie de guidage vers cette solution est alors proposée. La thèse se termine par l'analyse comparative des deux méthodes d'optimisation proposées pour les problèmes neutres afin d'en exploiter de nouvelles caractéristiques, et ainsi, renforcer le lien entre l'analyse de paysage et la conception de méthodes efficaces.

Généralement, les problèmes de conception de réseaux consistent à sélectionner les arcs et les sommets d’un graphe G de sorte que la fonction coût est optimisée et l’ensemble de contraintes impliquant les liens et les sommets dans G sont respectées. Une modification dans le critère d’optimisation et/ou dans l’ensemble de contraintes mène à une nouvelle représentation d’un problème différent. Dans cette thèse, nous nous intéressons au problème de conception d’infrastructure de réseaux maillés sans fil (WMN- Wireless Mesh Network en Anglais) où nous montrons que la conception de tels réseaux se transforme d’un problème d’optimisation standard (la fonction coût est optimisée) à un problème d’optimisation à plusieurs objectifs, pour tenir en compte de nombreux aspects, souvent contradictoires, mais néanmoins incontournables dans la réalité. Cette thèse, composée de trois volets, propose de nouveaux modèles et algorithmes pour la conception de WMNs où rien n’est connu à l’ avance. Le premiervolet est consacré à l’optimisation simultanée de deux objectifs équitablement importants : le coût et la performance du réseau en termes de débit. Trois modèles bi-objectifs qui se différent principalement par l’approche utilisée pour maximiser la performance du réseau sont proposés, résolus et comparés. Le deuxième volet traite le problème de placement de passerelles vu son impact sur la performance et l’extensibilité du réseau. La notion de contraintes de sauts (hop constraints) est introduite dans la conception du réseau pour limiter le délai de transmission. Un nouvel algorithme basé sur une approche de groupage est proposé afin de trouver les positions stratégiques des passerelles qui favorisent l’extensibilité du réseau et augmentent sa performance sans augmenter considérablement le coût total de son installation. Le dernier volet adresse le problème de fiabilité du réseau dans la présence de pannes simples. Prévoir l’installation des composants redondants lors de la phase de conception peut garantir des communications fiables, mais au détriment du coût et de la performance du réseau. Un nouvel algorithme, basé sur l’approche théorique de décomposition en oreilles afin d’installer le minimum nombre de routeurs additionnels pour tolérer les pannes simples, est développé. Afin de résoudre les modèles proposés pour des réseaux de taille réelle, un algorithme évolutionnaire (méta-heuristique), inspiré de la nature, est développé. Finalement, les méthodes et modèles proposés on été évalués par des simulations empiriques et d’événements discrets. / Generally, network design problems consist of selecting links and vertices of a graph G so that a cost function is optimized and all constraints involving links and the vertices in G are met. A change in the criterion of optimization and/or the set of constraints leads to a new representation of a different problem. In this thesis, we consider the problem of designing infrastructure Wireless Mesh Networks (WMNs) where we show that the design of such networks becomes an optimization problem with multiple objectives instead of a standard optimization problem (a cost function is optimized) to take into account many aspects, often contradictory, but nevertheless essential in the reality. This thesis, composed of three parts, introduces new models and algorithms for designing WMNs from scratch. The first part is devoted to the simultaneous optimization of two equally important objectives: cost and network performance in terms of throughput. Three bi-objective models which differ mainly by the approach used to maximize network performance are proposed, solved and compared. The second part deals with the problem of gateways placement, given its impact on network performance and scalability. The concept of hop constraints is introduced into the network design to reduce the transmission delay. A novel algorithm based on a clustering approach is also proposed to find the strategic positions of gateways that support network scalability and increase its performance without significantly increasing the cost of installation. The final section addresses the problem of reliability in the presence of single failures. Allowing the installation of redundant components in the design phase can ensure reliable communications, but at the expense of cost and network performance. A new algorithm is developed based on the theoretical approach of "ear decomposition" to install the minimum number of additional routers to tolerate single failures. In order to solve the proposed models for real-size networks, an evolutionary algorithm (meta-heuristics), inspired from nature, is developed. Finally, the proposed models and methods have been evaluated through empirical and discrete events based simulations.

La transformation de modèles consiste à transformer un modèle source en un modèle cible conformément à des méta-modèles source et cible. Nous distinguons deux types de transformations. La première est exogène où les méta-modèles source et cible représentent des formalismes différents et où tous les éléments du modèle source sont transformés. Quand elle concerne un même formalisme, la transformation est endogène. Ce type de transformation nécessite généralement deux étapes : l’identification des éléments du modèle source à transformer, puis la transformation de ces éléments. Dans le cadre de cette thèse, nous proposons trois principales contributions liées à ces problèmes de transformation. La première contribution est l’automatisation des transformations des modèles. Nous proposons de considérer le problème de transformation comme un problème d'optimisation combinatoire où un modèle cible peut être automatiquement généré à partir d'un nombre réduit d'exemples de transformations. Cette première contribution peut être appliquée aux transformations exogènes ou endogènes (après la détection des éléments à transformer). La deuxième contribution est liée à la transformation endogène où les éléments à transformer du modèle source doivent être détectés. Nous proposons une approche pour la détection des défauts de conception comme étape préalable au refactoring. Cette approche est inspirée du principe de la détection des virus par le système immunitaire humain, appelée sélection négative. L’idée consiste à utiliser de bonnes pratiques d’implémentation pour détecter les parties du code à risque. La troisième contribution vise à tester un mécanisme de transformation en utilisant une fonction oracle pour détecter les erreurs. Nous avons adapté le mécanisme de sélection négative qui consiste à considérer comme une erreur toute déviation entre les traces de transformation à évaluer et une base d’exemples contenant des traces de transformation de bonne qualité. La fonction oracle calcule cette dissimilarité et les erreurs sont ordonnées selon ce score. Les différentes contributions ont été évaluées sur d’importants projets et les résultats obtenus montrent leurs efficacités. / Model transformations take as input a source model and generate as output a target model. The source and target models conform to given meta-models. We distinguish between two transformation categories. Exogenous transformations are transformations between models expressed using different languages, and the whole source model is transformed. Endogenous transformations are transformations between models expressed in the same language. For endogenous transformations, two steps are needed: identifying the source model elements to transform and then applying the transformation on them. In this thesis, we propose three principal contributions. The first contribution aims to automate model transformations. The process is seen as an optimization problem where different transformation possibilities are evaluated and, for each possibility, a quality is associated depending on its conformity with a reference set of examples. This first contribution can be applied to exogenous as well as endogenous transformation (after determining the source model elements to transform). The second contribution is related precisely to the detection of elements concerned with endogenous transformations. In this context, we present a new technique for design defect detection. The detection is based on the notion that the more a code deviates from good practice, the more likely it is bad. Taking inspiration from artificial immune systems, we generate a set of detectors that characterize the ways in which a code can diverge from good practices. We then use these detectors to determine how far the code in the assessed systems deviates from normality. The third contribution concerns transformation mechanism testing. The proposed oracle function compares target test cases with a base of examples containing good quality transformation traces, and assigns a risk level based on the dissimilarity between the two. The traces help the tester understand the origin of an error. The three contributions are evaluated with real software projects and the obtained results confirm their efficiencies.

Le Problème de Tournées de Véhicules (PTV) est une clé importante pour gérér efficacement des systèmes logistiques, ce qui peut entraîner une amélioration du niveau de satisfaction de la clientèle. Ceci est fait en servant plus de clients dans un temps plus court. En terme général, il implique la planification des tournées d'une flotte de véhicules de capacité donnée basée à un ou plusieurs dépôts. Le but est de livrer ou collecter une certain quantité de marchandises à un ensemble des clients géographiquement dispersés, tout en respectant les contraintes de capacité des véhicules. Le PTV, comme classe de problèmes d'optimisation discrète et de grande complexité, a été étudié par de nombreux au cours des dernières décennies. Étant donné son importance pratique, des chercheurs dans les domaines de l'informatique, de la recherche opérationnelle et du génie industrielle ont mis au point des algorithmes très efficaces, de nature exacte ou heuristique, pour faire face aux différents types du PTV. Toutefois, les approches proposées pour le PTV ont souvent été accusées d'être trop concentrées sur des versions simplistes des problèmes de tournées de véhicules rencontrés dans des applications réelles. Par conséquent, les chercheurs sont récemment tournés vers des variantes du PTV qui auparavant étaient considérées trop difficiles à résoudre. Ces variantes incluent les attributs et les contraintes complexes observés dans les cas réels et fournissent des solutions qui sont exécutables dans la pratique. Ces extensions du PTV s'appellent Problème de Tournées de Véhicules Multi-Attributs (PTVMA). Le but principal de cette thèse est d'étudier les différents aspects pratiques de trois types de problèmes de tournées de véhicules multi-attributs qui seront modélisés dans celle-ci. En plus, puisque pour le PTV, comme pour la plupart des problèmes NP-complets, il est difficile de résoudre des instances de grande taille de façon optimale et dans un temps d'exécution raisonnable, nous nous tournons vers des méthodes approcheés à base d’heuristiques. / The Vehicle Routing Problem (VRP) is an important key to efficient logistics system management, which can result in higher level of customer satisfaction because more customers can be served in a shorter time. In broad terms, it deals with designing optimal delivery or collection routes from one or several depot(s) to a number of geographically scattered customers subject to side constraints. The VRP is a discrete optimization and computationally hard problem and has been extensively studied by researchers and practitioners during the past decades. Being complex problems with numerous and relevant potential applications, researchers from the fields of computer science, operations research and industrial engineering have developed very efficient algorithms, both of exact and heuristic nature, to deal with different types of VRPs. However, VRP research has often been criticized for being too focused on oversimplified versions of the routing problems encountered in real-life applications. Consequently, researchers have recently turned to variants of the VRP which before were considered too difficult to solve. These variants include those attributes and constraints observed in real-life planning and lead to solutions that are executable in practice. These extended problems are called Multi-Attribute Vehicle Routing Problems (MAVRPs). The main purpose of this thesis is to study different practical aspects of three multi-attribute vehicle routing problems which will be modeled in it. Besides that, since the VRP has been proved to be NP-hard in the strong sense such that it is impossible to optimally solve the large-sized problems in a reasonable computational time by means of traditional optimization approaches, novel heuristics will be designed to efficiently tackle the created models.

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes / 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.