Models and algorithms for the capacitated location-routing problem

Le problème de localisation-routage avec capacités (PLRC) apparaît comme un problème clé dans la conception de réseaux de distribution de marchandises. Il généralisele problème de localisation avec capacités (PLC) ainsi que le problème de tournées de véhicules à multiples dépôts (PTVMD), le premier en ajoutant des décisions liées au routage et le deuxième en ajoutant des décisions liées à la localisation des dépôts. Dans cette thèse on dévelope des outils pour résoudre le PLRC à l’aide de la programmation mathématique. Dans le chapitre 3, on introduit trois nouveaux modèles pour le PLRC basés sur des flots de véhicules et des flots de commodités, et on montre comment ceux-ci dominent, en termes de la qualité de la borne inférieure, la formulation originale à deux indices [19]. Des nouvelles inégalités valides ont été dévelopées et ajoutées aux modèles, de même que des inégalités connues. De nouveaux algorithmes de séparation ont aussi été dévelopés qui dans la plupart de cas généralisent ceux trouvés dans la litterature. Les résultats numériques montrent que ces modèles de flot sont en fait utiles pour résoudre des instances de petite à moyenne taille. Dans le chapitre 4, on présente une nouvelle méthode de génération de colonnes basée sur une formulation de partition d’ensemble. Le sous-problème consiste en un problème de plus court chemin avec capacités (PCCC). En particulier, on utilise une relaxation de ce problème dans laquelle il est possible de produire des routes avec des cycles de longueur trois ou plus. Ceci est complété par des nouvelles coupes qui permettent de réduire encore davantage le saut d’intégralité en même temps que de défavoriser l’apparition de cycles dans les routes. Ces résultats suggèrent que cette méthode fournit la meilleure méthode exacte pour le PLRC. Dans le chapitre 5, on introduit une nouvelle méthode heuristique pour le PLRC. Premièrement, on démarre une méthode randomisée de type GRASP pour trouver un premier ensemble de solutions de bonne qualité. Les solutions de cet ensemble sont alors combinées de façon à les améliorer. Finalement, on démarre une méthode de type détruir et réparer basée sur la résolution d’un nouveau modèle de localisation et réaffectation qui généralise le problème de réaffectaction [48].

Vérification temporelle des systèmes cycliques et acycliques basée sur l’analyse des contraintes

Nous présentons une nouvelle approche pour formuler et calculer le temps de séparation des événements utilisé dans l’analyse et la vérification de différents systèmes cycliques et acycliques sous des contraintes linéaires-min-max avec des composants ayant des délais finis et infinis. Notre approche consiste à formuler le problème sous la forme d’un programme entier mixte, puis à utiliser le solveur Cplex pour avoir les temps de séparation entre les événements. Afin de démontrer l’utilité en pratique de notre approche, nous l’avons utilisée pour la vérification et l’analyse d’une puce asynchrone d’Intel de calcul d’équations différentielles. Comparée aux travaux précédents, notre approche est basée sur une formulation exacte et elle permet non seulement de calculer le maximum de séparation, mais aussi de trouver un ordonnancement cyclique et de calculer les temps de séparation correspondant aux différentes périodes possibles de cet ordonnancement.

La logique déontique : une application de la logique à l'éthique et au discours juridique

Cet ouvrage a été rédigé en LaTeX, ce qui permet d'atteindre directement certaines sections, notes ou références bibliographiques par le biais des hyperliens.

Actuarial applications of multivariate phase-type distributions : model calibration and credibility

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal

Tarification logit dans un réseau

Le problème de tarification qui nous intéresse ici consiste à maximiser le revenu généré par les usagers d'un réseau de transport. Pour se rendre à leurs destinations, les usagers font un choix de route et utilisent des arcs sur lesquels nous imposons des tarifs. Chaque route est caractérisée (aux yeux de l'usager) par sa "désutilité", une mesure de longueur généralisée tenant compte à la fois des tarifs et des autres coûts associés à son utilisation. Ce problème a surtout été abordé sous une modélisation déterministe de la demande selon laquelle seules des routes de désutilité minimale se voient attribuer une mesure positive de flot. Le modèle déterministe se prête bien à une résolution globale, mais pèche par manque de réalisme. Nous considérons ici une extension probabiliste de ce modèle, selon laquelle les usagers d'un réseau sont alloués aux routes d'après un modèle de choix discret logit. Bien que le problème de tarification qui en résulte est non linéaire et non convexe, il conserve néanmoins une forte composante combinatoire que nous exploitons à des fins algorithmiques. Notre contribution se répartit en trois articles. Dans le premier, nous abordons le problème d'un point de vue théorique pour le cas avec une paire origine-destination. Nous développons une analyse de premier ordre qui exploite les propriétés analytiques de l'affectation logit et démontrons la validité de règles de simplification de la topologie du réseau qui permettent de réduire la dimension du problème sans en modifier la solution. Nous établissons ensuite l'unimodalité du problème pour une vaste gamme de topologies et nous généralisons certains de nos résultats au problème de la tarification d'une ligne de produits. Dans le deuxième article, nous abordons le problème d'un point de vue numérique pour le cas avec plusieurs paires origine-destination. Nous développons des algorithmes qui exploitent l'information locale et la parenté des formulations probabilistes et déterministes. Un des résultats de notre analyse est l'obtention de bornes sur l'erreur commise par les modèles combinatoires dans l'approximation du revenu logit. Nos essais numériques montrent qu'une approximation combinatoire rudimentaire permet souvent d'identifier des solutions quasi-optimales. Dans le troisième article, nous considérons l'extension du problème à une demande hétérogène. L'affectation de la demande y est donnée par un modèle de choix discret logit mixte où la sensibilité au prix d'un usager est aléatoire. Sous cette modélisation, l'expression du revenu n'est pas analytique et ne peut être évaluée de façon exacte. Cependant, nous démontrons que l'utilisation d'approximations non linéaires et combinatoires permet d'identifier des solutions quasi-optimales. Finalement, nous en profitons pour illustrer la richesse du modèle, par le biais d'une interprétation économique, et examinons plus particulièrement la contribution au revenu des différents groupes d'usagers.

Modélisation de l’exposition à la silice cristalline dans le secteur de la construction

L’exposition prolongée par inhalation à des poussières de taille respirable contenant de la silice cristalline est reconnue pour causer des maladies respiratoires dont le cancer du poumon et la silicose. De nombreuses études ont relevé la surexposition des travailleurs de la construction à la silice cristalline, puisque ce composé est présent dans de nombreux matériaux utilisés sur les chantiers. L’évaluation de l’exposition à la silice cristalline dans cette industrie constitue un défi en raison de la multitude de conditions de travail et de la nature éphémère des chantiers. Afin de mieux cerner cette problématique, une banque de données d’exposition professionnelle compilée à partir de la littérature a été réalisée par une équipe de l’Université de Montréal et de l’IRSST, et constitue le point de départ de ce travail. Les données présentes dans la banque ont été divisées en fonction de la stratégie d’échantillonnage, résultant en deux analyses complémentaires ayant pour objectif d’estimer les niveaux d’exposition sur le quart de travail en fonction du titre d’emploi, et selon la nature de la tâche exécutée. La méthode de Monte Carlo a été utilisée pour recréer les échantillons provenant de données rapportées sous forme de paramètres de synthèse. Des modèles Tobit comprenant les variables de titre d’emploi, tâche exécutée, durée, année et stratégie d’échantillonnage, type de projet, secteur d’activité, environnement et moyens de maîtrise ont été développés et interprétés par inférence multimodèle. L’analyse basée sur le quart de travail a été réalisée à partir de 1346 données d’exposition couvrant 11 catégories de titre d’emploi. Le modèle contenant toutes les variables a expliqué 22% de la variabilité des mesures et la durée, l’année et la stratégie d’échantillonnage étaient d’importants prédicteurs de l’exposition. Les chantiers de génie civil et les projets de nouvelle construction étaient associés à des expositions plus faibles, alors que l’utilisation de moyens de maîtrise diminuait les concentrations de 18% à l’extérieur et de 24% à l’intérieur. Les moyennes géométriques les plus élevées prédites pour l’année 1999 sur 8 heures étaient retrouvées chez les foreurs (0.214 mg/m3), les travailleurs souterrains (0.191 mg/m3), les couvreurs (0.146 mg/m3) et les cimentiers-applicateurs (0.125 mg/m3). 1566 mesures réparties en 27 catégories de tâches étaient contenues dans la seconde analyse. Le modèle contenant toutes les variables a expliqué 59% des niveaux d’exposition, et l’ensemble des variables contextuelles étaient fortement prédictives. Les moyennes géométriques prédites pour l’année 1998 et selon la durée médiane par tâche dans la banque de données étaient plus élevées lors du bouchardage du béton (1.446 mg/m3), du cassage de pièces de maçonnerie avec autres outils (0.354 mg/m3), du décapage au jet de sable (0.349 mg/m3) et du meulage de joints de brique (0.200 mg/m3). Une diminution importante des concentrations a été observée avec les systèmes d’arrosage (-80%) et d’aspiration des poussières (-64%) intégrés aux outils. L’analyse en fonction des titres d’emploi a montré une surexposition généralisée à la valeur guide de l’ACGIH et à la norme québécoise, indiquant un risque à long terme de maladies professionnelles chez ces travailleurs. Les résultats obtenus pour l’évaluation en fonction de la tâche exécutée montrent que cette stratégie permet une meilleure caractérisation des facteurs associés à l’exposition et ainsi de mieux cibler les priorités d’intervention pour contrôler les niveaux d’exposition à la silice cristalline sur les chantiers de construction durant un quart de travail.

Processus de coalescence dans une population subdivisée avec possibilité de coalescences multiples

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Suivi des changements des utilisations/occupations du sol en milieu urbain par imagerie satellitale de résolution spatiale moyenne : le cas de la région métropolitaine de Montréal

De nos jours les cartes d’utilisation/occupation du sol (USOS) à une échelle régionale sont habituellement générées à partir d’images satellitales de résolution modérée (entre 10 m et 30 m). Le National Land Cover Database aux États-Unis et le programme CORINE (Coordination of information on the environment) Land Cover en Europe, tous deux fondés sur les images LANDSAT, en sont des exemples représentatifs. Cependant ces cartes deviennent rapidement obsolètes, spécialement en environnement dynamique comme les megacités et les territoires métropolitains. Pour nombre d’applications, une mise à jour de ces cartes sur une base annuelle est requise. Depuis 2007, le USGS donne accès gratuitement à des images LANDSAT ortho-rectifiées. Des images archivées (depuis 1984) et des images acquises récemment sont disponibles. Sans aucun doute, une telle disponibilité d’images stimulera la recherche sur des méthodes et techniques rapides et efficaces pour un monitoring continue des changements des USOS à partir d’images à résolution moyenne. Cette recherche visait à évaluer le potentiel de telles images satellitales de résolution moyenne pour obtenir de l’information sur les changements des USOS à une échelle régionale dans le cas de la Communauté Métropolitaine de Montréal (CMM), une métropole nord-américaine typique. Les études précédentes ont démontré que les résultats de détection automatique des changements dépendent de plusieurs facteurs tels : 1) les caractéristiques des images (résolution spatiale, bandes spectrales, etc.); 2) la méthode même utilisée pour la détection automatique des changements; et 3) la complexité du milieu étudié. Dans le cas du milieu étudié, à l’exception du centre-ville et des artères commerciales, les utilisations du sol (industriel, commercial, résidentiel, etc.) sont bien délimitées. Ainsi cette étude s’est concentrée aux autres facteurs pouvant affecter les résultats, nommément, les caractéristiques des images et les méthodes de détection des changements. Nous avons utilisé des images TM/ETM+ de LANDSAT à 30 m de résolution spatiale et avec six bandes spectrales ainsi que des images VNIR-ASTER à 15 m de résolution spatiale et avec trois bandes spectrales afin d’évaluer l’impact des caractéristiques des images sur les résultats de détection des changements. En ce qui a trait à la méthode de détection des changements, nous avons décidé de comparer deux types de techniques automatiques : (1) techniques fournissant des informations principalement sur la localisation des changements et (2)techniques fournissant des informations à la fois sur la localisation des changements et sur les types de changement (classes « de-à »). Les principales conclusions de cette recherche sont les suivantes : Les techniques de détection de changement telles les différences d’image ou l’analyse des vecteurs de changements appliqués aux images multi-temporelles LANDSAT fournissent une image exacte des lieux où un changement est survenu d’une façon rapide et efficace. Elles peuvent donc être intégrées dans un système de monitoring continu à des fins d’évaluation rapide du volume des changements. Les cartes des changements peuvent aussi servir de guide pour l’acquisition d’images de haute résolution spatiale si l’identification détaillée du type de changement est nécessaire. Les techniques de détection de changement telles l’analyse en composantes principales et la comparaison post-classification appliquées aux images multi-temporelles LANDSAT fournissent une image relativement exacte de classes “de-à” mais à un niveau thématique très général (par exemple, bâti à espace vert et vice-versa, boisés à sol nu et vice-versa, etc.). Les images ASTER-VNIR avec une meilleure résolution spatiale mais avec moins de bandes spectrales que LANDSAT n’offrent pas un niveau thématique plus détaillé (par exemple, boisés à espace commercial ou industriel). Les résultats indiquent que la recherche future sur la détection des changements en milieu urbain devrait se concentrer aux changements du couvert végétal puisque les images à résolution moyenne sont très sensibles aux changements de ce type de couvert. Les cartes indiquant la localisation et le type des changements du couvert végétal sont en soi très utiles pour des applications comme le monitoring environnemental ou l’hydrologie urbaine. Elles peuvent aussi servir comme des indicateurs des changements de l’utilisation du sol. De techniques telles l’analyse des vecteurs de changement ou les indices de végétation son employées à cette fin.

Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

L’extraction de phrases en relation de traduction dans Wikipédia

Afin d'enrichir les données de corpus bilingues parallèles, il peut être judicieux de travailler avec des corpus dits comparables. En effet dans ce type de corpus, même si les documents dans la langue cible ne sont pas l'exacte traduction de ceux dans la langue source, on peut y retrouver des mots ou des phrases en relation de traduction. L'encyclopédie libre Wikipédia constitue un corpus comparable multilingue de plusieurs millions de documents. Notre travail consiste à trouver une méthode générale et endogène permettant d'extraire un maximum de phrases parallèles. Nous travaillons avec le couple de langues français-anglais mais notre méthode, qui n'utilise aucune ressource bilingue extérieure, peut s'appliquer à tout autre couple de langues. Elle se décompose en deux étapes. La première consiste à détecter les paires d’articles qui ont le plus de chance de contenir des traductions. Nous utilisons pour cela un réseau de neurones entraîné sur un petit ensemble de données constitué d'articles alignés au niveau des phrases. La deuxième étape effectue la sélection des paires de phrases grâce à un autre réseau de neurones dont les sorties sont alors réinterprétées par un algorithme d'optimisation combinatoire et une heuristique d'extension. L'ajout des quelques 560~000 paires de phrases extraites de Wikipédia au corpus d'entraînement d'un système de traduction automatique statistique de référence permet d'améliorer la qualité des traductions produites. Nous mettons les données alignées et le corpus extrait à la disposition de la communauté scientifique.

La structure de Jordan des matrices de transfert des modèles de boucles et la relation avec les hamiltoniens XXZ

Les modèles sur réseau comme ceux de la percolation, d’Ising et de Potts servent à décrire les transitions de phase en deux dimensions. La recherche de leur solution analytique passe par le calcul de la fonction de partition et la diagonalisation de matrices de transfert. Au point critique, ces modèles statistiques bidimensionnels sont invariants sous les transformations conformes et la construction de théories des champs conformes rationnelles, limites continues des modèles statistiques, permet un calcul de la fonction de partition au point critique. Plusieurs chercheurs pensent cependant que le paradigme des théories des champs conformes rationnelles peut être élargi pour inclure les modèles statistiques avec des matrices de transfert non diagonalisables. Ces modèles seraient alors décrits, dans la limite d’échelle, par des théories des champs logarithmiques et les représentations de l’algèbre de Virasoro intervenant dans la description des observables physiques seraient indécomposables. La matrice de transfert de boucles D_N(λ, u), un élément de l’algèbre de Temperley- Lieb, se manifeste dans les théories physiques à l’aide des représentations de connectivités ρ (link modules). L’espace vectoriel sur lequel agit cette représentation se décompose en secteurs étiquetés par un paramètre physique, le nombre d de défauts. L’action de cette représentation ne peut que diminuer ce nombre ou le laisser constant. La thèse est consacrée à l’identification de la structure de Jordan de D_N(λ, u) dans ces représentations. Le paramètre β = 2 cos λ = −(q + 1/q) fixe la théorie : β = 1 pour la percolation et √2 pour le modèle d’Ising, par exemple. Sur la géométrie du ruban, nous montrons que D_N(λ, u) possède les mêmes blocs de Jordan que F_N, son plus haut coefficient de Fourier. Nous étudions la non diagonalisabilité de F_N à l’aide des divergences de certaines composantes de ses vecteurs propres, qui apparaissent aux valeurs critiques de λ. Nous prouvons dans ρ(D_N(λ, u)) l’existence de cellules de Jordan intersectorielles, de rang 2 et couplant des secteurs d, d′ lorsque certaines contraintes sur λ, d, d′ et N sont satisfaites. Pour le modèle de polymères denses critique (β = 0) sur le ruban, les valeurs propres de ρ(D_N(λ, u)) étaient connues, mais les dégénérescences conjecturées. En construisant un isomorphisme entre les modules de connectivités et un sous-espace des modules de spins du modèle XXZ en q = i, nous prouvons cette conjecture. Nous montrons aussi que la restriction de l’hamiltonien de boucles à un secteur donné est diagonalisable et trouvons la forme de Jordan exacte de l’hamiltonien XX, non triviale pour N pair seulement. Enfin nous étudions la structure de Jordan de la matrice de transfert T_N(λ, ν) pour des conditions aux frontières périodiques. La matrice T_N(λ, ν) a des blocs de Jordan intrasectoriels et intersectoriels lorsque λ = πa/b, et a, b ∈ Z×. L’approche par F_N admet une généralisation qui permet de diagnostiquer des cellules intersectorielles dont le rang excède 2 dans certains cas et peut croître indéfiniment avec N. Pour les blocs de Jordan intrasectoriels, nous montrons que les représentations de connectivités sur le cylindre et celles du modèle XXZ sont isomorphes sauf pour certaines valeurs précises de q et du paramètre de torsion v. En utilisant le comportement de la transformation i_N^d dans un voisinage des valeurs critiques (q_c, v_c), nous construisons explicitement des vecteurs généralisés de Jordan de rang 2 et discutons l’existence de blocs de Jordan intrasectoriels de plus haut rang.

Bootstrap for panel data models with an application to the evaluation of public policies

Le but de cette thèse est d étendre la théorie du bootstrap aux modèles de données de panel. Les données de panel s obtiennent en observant plusieurs unités statistiques sur plusieurs périodes de temps. Leur double dimension individuelle et temporelle permet de contrôler l 'hétérogénéité non observable entre individus et entre les périodes de temps et donc de faire des études plus riches que les séries chronologiques ou les données en coupe instantanée. L 'avantage du bootstrap est de permettre d obtenir une inférence plus précise que celle avec la théorie asymptotique classique ou une inférence impossible en cas de paramètre de nuisance. La méthode consiste à tirer des échantillons aléatoires qui ressemblent le plus possible à l échantillon d analyse. L 'objet statitstique d intérêt est estimé sur chacun de ses échantillons aléatoires et on utilise l ensemble des valeurs estimées pour faire de l inférence. Il existe dans la littérature certaines application du bootstrap aux données de panels sans justi cation théorique rigoureuse ou sous de fortes hypothèses. Cette thèse propose une méthode de bootstrap plus appropriée aux données de panels. Les trois chapitres analysent sa validité et son application. Le premier chapitre postule un modèle simple avec un seul paramètre et s 'attaque aux propriétés théoriques de l estimateur de la moyenne. Nous montrons que le double rééchantillonnage que nous proposons et qui tient compte à la fois de la dimension individuelle et la dimension temporelle est valide avec ces modèles. Le rééchantillonnage seulement dans la dimension individuelle n est pas valide en présence d hétérogénéité temporelle. Le ré-échantillonnage dans la dimension temporelle n est pas valide en présence d'hétérogénéité individuelle. Le deuxième chapitre étend le précédent au modèle panel de régression. linéaire. Trois types de régresseurs sont considérés : les caractéristiques individuelles, les caractéristiques temporelles et les régresseurs qui évoluent dans le temps et par individu. En utilisant un modèle à erreurs composées doubles, l'estimateur des moindres carrés ordinaires et la méthode de bootstrap des résidus, on montre que le rééchantillonnage dans la seule dimension individuelle est valide pour l'inférence sur les coe¢ cients associés aux régresseurs qui changent uniquement par individu. Le rééchantillonnage dans la dimen- sion temporelle est valide seulement pour le sous vecteur des paramètres associés aux régresseurs qui évoluent uniquement dans le temps. Le double rééchantillonnage est quand à lui est valide pour faire de l inférence pour tout le vecteur des paramètres. Le troisième chapitre re-examine l exercice de l estimateur de différence en di¤érence de Bertrand, Duflo et Mullainathan (2004). Cet estimateur est couramment utilisé dans la littérature pour évaluer l impact de certaines poli- tiques publiques. L exercice empirique utilise des données de panel provenant du Current Population Survey sur le salaire des femmes dans les 50 états des Etats-Unis d Amérique de 1979 à 1999. Des variables de pseudo-interventions publiques au niveau des états sont générées et on s attend à ce que les tests arrivent à la conclusion qu il n y a pas d e¤et de ces politiques placebos sur le salaire des femmes. Bertrand, Du o et Mullainathan (2004) montre que la non-prise en compte de l hétérogénéité et de la dépendance temporelle entraîne d importantes distorsions de niveau de test lorsqu'on évalue l'impact de politiques publiques en utilisant des données de panel. Une des solutions préconisées est d utiliser la méthode de bootstrap. La méthode de double ré-échantillonnage développée dans cette thèse permet de corriger le problème de niveau de test et donc d'évaluer correctement l'impact des politiques publiques.

Démystifier la problématique de l’épaule douloureuse

Travail d'intégration réalisé dans le cadre du cours PHT-6113.

Le développement d’une grille d’évaluation du risque d’agression physique en communauté. L’implantation de G.E.R.A.C. à l’Urgence-Psychosociale-Justice.

Rapport de stage présenté à la Faculté des arts et des sciences en vue de l’obtention du grade de maîtrise en criminologie (option intervention).

Heuristic solution methods for multi-attribute vehicle routing problems

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.