Jumps in the Volatility of Financial Markets.

Recent work suggests that the conditional variance of financial returns may exhibit sudden jumps. This paper extends a non-parametric procedure to detect discontinuities in otherwise continuous functions of a random variable developed by Delgado and Hidalgo (1996) to higher conditional moments, in particular the conditional variance. Simulation results show that the procedure provides reasonable estimates of the number and location of jumps. This procedure detects several jumps in the conditional variance of daily returns on the S&P 500 index.

Le recours à des environnements numériques pour la diffusion de connaissances relatives au patrimoine bâti: une exploration du potentiel de la modélisation de systèmes typologiques

Un fichier intitulé Charbonneau_Nathalie_2008_AnimationAnnexeT accompagne la thèse. Il contient une séquence animée démontrant le type de parcours pouvant être effectué au sein des environnements numériques développés. Il s'agit d'un fichier .wmv qui a été compressé.

Dynamique du jeu des élites : rôle de l'élite syrienne dans l'arrivée du parti Baas au pouvoir (1941-1963)

Le 8 mars 1963, un coup d’État en Syrie permet à une secte minoritaire marginalisée au sein du parti Baas, à idéologie radicale et révolutionnaire, de s’emparer des rênes de l’État avec l’appui des militaires et de conserver le pouvoir depuis. Ainsi la Syrie, premier pays arabe à connaître le système pluraliste parlementaire dès 1919, sera soumise à un régime militaire et autoritaire pendant presque un demi siècle. Ce mémoire vise à expliquer comment cette faction, groupusculaire à l’origine, a su profiter des circonstances et des fenêtres d’opportunité politique ouvertes par les comportements de l’élite traditionnelle syrienne, au pouvoir depuis le Mandat français, s’étant trouvée affaiblie, isolée et illégitime aux yeux de la population. Cette fragmentation exprimée par des agitations internes, avait provoqué des décisions contradictoires, des conflits d’intérêts ainsi que des divisions de nature identitaire, générationnelle, sociale, économique, militaire et politique. La Syrie a de ce fait, depuis son indépendance en 1941, été victime du jeu de son élite, un jeu dont ce mémoire est consacré à étudier la dynamique. Cette étude, qui définit le concept de l’élite théoriquement, s’appuie sur l’état des liens entre élites, l’envergure et les modes de leur circulation, pour confirmer qu’une élite fragmentée s’affaibli, perd sa légitimité et mène la société à l’instabilité. Ceci soutien l’hypothèse centrale de l’étude que la fragmentation de l’élite syrienne traditionnelle a ouvert des fenêtres d’opportunité politique devant le parti Baas, minoritaire et radical, qui a su les saisir pour conquérir le pouvoir.

Applicabilité de la texture couleur à la différentiation des classes d’occupation du territoire sur des images satellitales multispectrales

La texture est un élément clé pour l’interprétation des images de télédétection à fine résolution spatiale. L’intégration de l’information texturale dans un processus de classification automatisée des images se fait habituellement via des images de texture, souvent créées par le calcul de matrices de co-occurrences (MCO) des niveaux de gris. Une MCO est un histogramme des fréquences d’occurrence des paires de valeurs de pixels présentes dans les fenêtres locales, associées à tous les pixels de l’image utilisée; une paire de pixels étant définie selon un pas et une orientation donnés. Les MCO permettent le calcul de plus d’une dizaine de paramètres décrivant, de diverses manières, la distribution des fréquences, créant ainsi autant d’images texturales distinctes. L’approche de mesure des textures par MCO a été appliquée principalement sur des images de télédétection monochromes (ex. images panchromatiques, images radar monofréquence et monopolarisation). En imagerie multispectrale, une unique bande spectrale, parmi celles disponibles, est habituellement choisie pour générer des images de texture. La question que nous avons posée dans cette recherche concerne justement cette utilisation restreinte de l’information texturale dans le cas des images multispectrales. En fait, l’effet visuel d’une texture est créé, non seulement par l’agencement particulier d’objets/pixels de brillance différente, mais aussi de couleur différente. Plusieurs façons sont proposées dans la littérature pour introduire cette idée de la texture à plusieurs dimensions. Parmi celles-ci, deux en particulier nous ont intéressés dans cette recherche. La première façon fait appel aux MCO calculées bande par bande spectrale et la seconde utilise les MCO généralisées impliquant deux bandes spectrales à la fois. Dans ce dernier cas, le procédé consiste en le calcul des fréquences d’occurrence des paires de valeurs dans deux bandes spectrales différentes. Cela permet, en un seul traitement, la prise en compte dans une large mesure de la « couleur » des éléments de texture. Ces deux approches font partie des techniques dites intégratives. Pour les distinguer, nous les avons appelées dans cet ouvrage respectivement « textures grises » et « textures couleurs ». Notre recherche se présente donc comme une analyse comparative des possibilités offertes par l’application de ces deux types de signatures texturales dans le cas spécifique d’une cartographie automatisée des occupations de sol à partir d’une image multispectrale. Une signature texturale d’un objet ou d’une classe d’objets, par analogie aux signatures spectrales, est constituée d’une série de paramètres de texture mesurés sur une bande spectrale à la fois (textures grises) ou une paire de bandes spectrales à la fois (textures couleurs). Cette recherche visait non seulement à comparer les deux approches intégratives, mais aussi à identifier la composition des signatures texturales des classes d’occupation du sol favorisant leur différentiation : type de paramètres de texture / taille de la fenêtre de calcul / bandes spectrales ou combinaisons de bandes spectrales. Pour ce faire, nous avons choisi un site à l’intérieur du territoire de la Communauté Métropolitaine de Montréal (Longueuil) composé d’une mosaïque d’occupations du sol, caractéristique d’une zone semi urbaine (résidentiel, industriel/commercial, boisés, agriculture, plans d’eau…). Une image du satellite SPOT-5 (4 bandes spectrales) de 10 m de résolution spatiale a été utilisée dans cette recherche. Puisqu’une infinité d’images de texture peuvent être créées en faisant varier les paramètres de calcul des MCO et afin de mieux circonscrire notre problème nous avons décidé, en tenant compte des études publiées dans ce domaine : a) de faire varier la fenêtre de calcul de 3*3 pixels à 21*21 pixels tout en fixant le pas et l’orientation pour former les paires de pixels à (1,1), c'est-à-dire à un pas d’un pixel et une orientation de 135°; b) de limiter les analyses des MCO à huit paramètres de texture (contraste, corrélation, écart-type, énergie, entropie, homogénéité, moyenne, probabilité maximale), qui sont tous calculables par la méthode rapide de Unser, une approximation des matrices de co-occurrences, c) de former les deux signatures texturales par le même nombre d’éléments choisis d’après une analyse de la séparabilité (distance de Bhattacharya) des classes d’occupation du sol; et d) d’analyser les résultats de classification (matrices de confusion, exactitudes, coefficients Kappa) par maximum de vraisemblance pour conclure sur le potentiel des deux approches intégratives; les classes d’occupation du sol à reconnaître étaient : résidentielle basse et haute densité, commerciale/industrielle, agricole, boisés, surfaces gazonnées (incluant les golfs) et plans d’eau. Nos principales conclusions sont les suivantes a) à l’exception de la probabilité maximale, tous les autres paramètres de texture sont utiles dans la formation des signatures texturales; moyenne et écart type sont les plus utiles dans la formation des textures grises tandis que contraste et corrélation, dans le cas des textures couleurs, b) l’exactitude globale de la classification atteint un score acceptable (85%) seulement dans le cas des signatures texturales couleurs; c’est une amélioration importante par rapport aux classifications basées uniquement sur les signatures spectrales des classes d’occupation du sol dont le score est souvent situé aux alentours de 75%; ce score est atteint avec des fenêtres de calcul aux alentours de11*11 à 15*15 pixels; c) Les signatures texturales couleurs offrant des scores supérieurs à ceux obtenus avec les signatures grises de 5% à 10%; et ce avec des petites fenêtres de calcul (5*5, 7*7 et occasionnellement 9*9) d) Pour plusieurs classes d’occupation du sol prises individuellement, l’exactitude dépasse les 90% pour les deux types de signatures texturales; e) une seule classe est mieux séparable du reste par les textures grises, celle de l’agricole; f) les classes créant beaucoup de confusions, ce qui explique en grande partie le score global de la classification de 85%, sont les deux classes du résidentiel (haute et basse densité). En conclusion, nous pouvons dire que l’approche intégrative par textures couleurs d’une image multispectrale de 10 m de résolution spatiale offre un plus grand potentiel pour la cartographie des occupations du sol que l’approche intégrative par textures grises. Pour plusieurs classes d’occupations du sol un gain appréciable en temps de calcul des paramètres de texture peut être obtenu par l’utilisation des petites fenêtres de traitement. Des améliorations importantes sont escomptées pour atteindre des exactitudes de classification de 90% et plus par l’utilisation des fenêtres de calcul de taille variable adaptées à chaque type d’occupation du sol. Une méthode de classification hiérarchique pourrait être alors utilisée afin de séparer les classes recherchées une à la fois par rapport au reste au lieu d’une classification globale où l’intégration des paramètres calculés avec des fenêtres de taille variable conduirait inévitablement à des confusions entre classes.

Méthodes exactes et heuristiques pour le problème de tournées de véhicules avec fenêtres de temps et réutilisation de véhicules

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.

Impacts potentiels d’un changement climatique sur le pergélisol dans le nord canadien

Les fichiers video (d'animation) sont dans un format Windows Media (.wmv)

Modélisation procédurale par composants

Le réalisme des images en infographie exige de créer des objets (ou des scènes) de plus en plus complexes, ce qui entraîne des coûts considérables. La modélisation procédurale peut aider à automatiser le processus de création, à simplifier le processus de modification ou à générer de multiples variantes d'une instance d'objet. Cependant même si plusieurs méthodes procédurales existent, aucune méthode unique permet de créer tous les types d'objets complexes, dont en particulier un édifice complet. Les travaux réalisés dans le cadre de cette thèse proposent deux solutions au problème de la modélisation procédurale: une solution au niveau de la géométrie de base, et l’autre sous forme d'un système général adapté à la modélisation des objets complexes. Premièrement, nous présentons le bloc, une nouvelle primitive de modélisation simple et générale, basée sur une forme cubique généralisée. Les blocs sont disposés et connectés entre eux pour constituer la forme de base des objets, à partir de laquelle est extrait un maillage de contrôle pouvant produire des arêtes lisses et vives. La nature volumétrique des blocs permet une spécification simple de la topologie, ainsi que le support des opérations de CSG entre les blocs. La paramétrisation de la surface, héritée des faces des blocs, fournit un soutien pour les textures et les fonctions de déplacements afin d'appliquer des détails de surface. Une variété d'exemples illustrent la généralité des blocs dans des contextes de modélisation à la fois interactive et procédurale. Deuxièmement, nous présentons un nouveau système de modélisation procédurale qui unifie diverses techniques dans un cadre commun. Notre système repose sur le concept de composants pour définir spatialement et sémantiquement divers éléments. À travers une série de déclarations successives exécutées sur un sous-ensemble de composants obtenus à l'aide de requêtes, nous créons un arbre de composants définissant ultimement un objet dont la géométrie est générée à l'aide des blocs. Nous avons appliqué notre concept de modélisation par composants à la génération d'édifices complets, avec intérieurs et extérieurs cohérents. Ce nouveau système s'avère général et bien adapté pour le partionnement des espaces, l'insertion d'ouvertures (portes et fenêtres), l'intégration d'escaliers, la décoration de façades et de murs, l'agencement de meubles, et diverses autres opérations nécessaires lors de la construction d'un édifice complet.

Génération de lignées de poissons zébrés exprimant le gène muté TARDBP

La sclérose latérale amyotrophique (SLA) est une maladie neurodégénérative due à une dégénérescence des motoneurones. Plus de 40 mutations du gène TARDBP ont été identifiées chez des patients SLA. Les défauts biochimiques de ces mutations étant encore inconnus, les modèles animaux sont présentement la seule mesure possible d’un phénotype. Pour étudier les conséquences physiopathologiques d’une de ces mutations, nous avons développé deux lignées transgéniques de poisson zébré, exprimant le gène humain TARDBP soit de type sauvage, soit avec la mutation G348C liée à la SLA, sous le contrôle d’un promoteur de choc thermique. Ces lignées ont été étudiées sur trois générations, après avoir établi un protocole de choc thermique induisant une expression ubiquitaire du transgène. Les embryons transgéniques de la génération F2 de la lignée exprimant la mutation développent un phénotype moteur suite à un choc thermique de 38.5°C pendant 30 minutes lorsque les embryons sont à 18 heures post-fertilisation. 60% des embryons ont une réponse anormale au toucher. De plus, une réduction de 28% de la longueur de pré-branchement des axones des motoneurones est observée. Ces résultats indiquent que notre lignée exprimant la protéine mutante TDP-43 est un modèle génétique de la SLA prometteur, qui ouvre des perspectives pour la compréhension de la physiopathologie de la maladie et la découverte de molécules thérapeutiques.

Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d'horaires

Thèse réalisée en cotutelle entre l'Université de Montréal et l'Université de Technologie de Troyes

Excitabilité du système miroir : une étude de stimulation magnétique transcrânienne sur le chant et le langage

La perception de mouvements est associée à une augmentation de l’excitabilité du cortex moteur humain. Ce système appelé « miroir » sous-tendrait notre habileté à comprendre les gestes posés par une tierce personne puisqu’il est impliqué dans la reconnaissance, la compréhension et l’imitation de ces gestes. Dans cette étude, nous examinons de quelle façon ce système miroir s’implique et se latéralise dans la perception du chant et de la parole. Une stimulation magnétique transcrânienne (TMS) à impulsion unique a été appliquée sur la représentation de la bouche du cortex moteur de 11 participants. La réponse motrice engendrée a été mesurée sous la forme de potentiels évoqués moteurs (PÉMs), enregistrés à partir du muscle de la bouche. Ceux-ci ont été comparés lors de la perception de chant et de parole, dans chaque hémisphère cérébral. Afin d’examiner l’activation de ce système moteur dans le temps, les impulsions de la TMS ont été envoyées aléatoirement à l’intérieur de 7 fenêtres temporelles (500-3500 ms). Les stimuli pour la tâche de perception du chant correspondaient à des vidéos de 4 secondes dans lesquelles une chanteuse produisait un intervalle ascendant de deux notes que les participants devaient juger comme correspondant ou non à un intervalle écrit. Pour la tâche de perception de la parole, les participants regardaient des vidéos de 4 secondes montrant une personne expliquant un proverbe et devaient juger si cette explication correspondait bien à un proverbe écrit. Les résultats de cette étude montrent que les amplitudes des PÉMs recueillis dans la tâche de perception de chant étaient plus grandes après stimulation de l’hémisphère droit que de l’hémisphère gauche, surtout lorsque l’impulsion était envoyée entre 1000 et 1500 ms. Aucun effet significatif n’est ressorti de la condition de perception de la parole. Ces résultats suggèrent que le système miroir de l’hémisphère droit s’active davantage après une présentation motrice audio-visuelle, en comparaison de l’hémisphère gauche.

Publicité sur Internet et Protection du consommateur

La cyberpublicité abonde sur Internet. Bandeaux publicitaires, fenêtres pop-up et « pourriels » font partie du quotidien des internautes. Pourtant, bien qu’il puisse sembler que l’anarchie y soit la règle, la publicité sur le web est encadrée, comme elle l’est d’ailleurs dans les médias traditionnels. Nous analyserons la législation qui s’applique au Québec à la publicité sur Internet : il s’agit de la Loi sur la concurrence, adoptée par le légistaleur canadien, et de la Loi sur la protection du consommateur que l’on doit au législateur québécois. Ces deux lois laissent cependant quelque chose à désirer puisqu’elles ne régissent que le contenu du message et non les formes qu’il prend sur Internet, et qu’elles ne tiennent pas compte non plus de la situation créée par la nature particulière de ce média. Pour garantir aux cyberconsommateurs une protection similaire à celle dont ils bénéficient à l’égard des autres médias, il faudra créer de nouvelles sources normatives. L’adéquation des normes avec la réalité reste toujours l’idéal à atteindre.

Développement de composés conjugués en étoile de première génération incluant des liens azométhines et études électrochimiques et photophysiques

Les matériaux conjugués sont de nos jours très utilisés dans de nombreuses applications ainsi qu’en recherche. L’enchainement des liaisons π-σ-π permet la délocalisation des électrons et d’obtenir différentes propriétés comme la conduction, la fluorescence, la chélation, etc. Ainsi, de nombreux dispositifs utilisent ces caractéristiques en vue d’obtenir de nouveaux matériaux révolutionnaires comme les cellules solaires, les transistors à effet de champs, les dispositifs électrochromiques, etc.. Les dispositifs électrochromiques font partie des dispositifs en vogue. Ils sont capables de changer de couleur selon le potentiel électrique appliqué. Ils se distinguent par la simplicité du mode de conception et ils ne nécessitent pas de fonctionner dans des conditions drastiques comme une atmosphère contrôlée. Ces dispositifs sont actuellement utilisés et commercialisés comme fenêtre intelligente, camouflage, papier électronique et carte de visite personnalisée pour n’en nommer que quelques-uns. Deux propriétés sont essentielles pour que des composés puissent être utilisés dans ces familles de dispositifs : la réversibilité à l’oxydation et la stabilité à l’air et à la lumière. Dans le groupe de recherche du professeur W.G. Skene, l’axe principal de recherche est basé sur la conception de nouveaux matériaux conducteurs comportant des liaisons azométhines. Les principaux matériaux étudiés sont des dérivés de thiophènes et de fluorènes. De précédents résultats ont montré que plusieurs produits issus de la réaction de condensation entre les dérivés du 2,5-diaminothiophène et de thiophènes diformylés menaient à des produits possédant d’excellentes propriétés photophysiques et électrochimiques. C’est en partant de ces résultats encourageants qu’il a été choisi de synthétiser une nouvelle famille de produits avec un nouveau substrat fonctionnalisé. Ce dernier possède d’excellentes propriétés électrochimiques et photophysiques : la triphénylamine. Deux familles de produits ont été synthétisées qui possèdent toutes comme cœur une triphénylamine. Cette dernière a été modifiée de façon à créer une, deux ou trois liaisons azométhines avec différents thiophènes. Deux dérivés du thiophène ont été choisis afin d’étudier l’influence des groupements donneurs et accepteurs sur ces nouveaux types de composés encore jamais étudiés. Les résultats des différentes synthèses et analyses ont été effectués par RMN, spectrométrie de masse, spectrométrie d’absorbance UV-Visible, fluorescence et voltampérométrie cyclique sont rapportées dans le présent recueil.

Étude du traitement visuel simple et complexe chez les enfants autistes

Les personnes ayant un trouble du spectre autistique (TSA) manifestent des particularités perceptives. En vision, des travaux influents chez les adultes ont mené à l’élaboration d’un modèle explicatif du fonctionnement perceptif autistique qui suggère que l’efficacité du traitement visuel varie en fonction de la complexité des réseaux neuronaux impliqués (Hypothèse spécifique à la complexité). Ainsi, lorsque plusieurs aires corticales sont recrutées pour traiter un stimulus complexe (e.g., modulations de texture; attributs de deuxième ordre), les adultes autistes démontrent une sensibilité diminuée. À l’inverse, lorsque le traitement repose principalement sur le cortex visuel primaire V1 (e.g., modulations locales de luminance; attributs de premier ordre), leur sensibilité est augmentée (matériel statique) ou intacte (matériel dynamique). Cette dissociation de performance est spécifique aux TSA et peut s’expliquer, entre autre, par une connectivité atypique au sein de leur cortex visuel. Les mécanismes neuronaux précis demeurent néanmoins méconnus. De plus, on ignore si cette signature perceptuelle est présente à l’enfance, information cruciale pour les théories perceptives de l’autisme. Le premier volet de cette thèse cherche à vérifier, à l’aide de la psychophysique et l’électrophysiologie, si la double dissociation de performance entre les attributs statiques de premier et deuxième ordre se retrouve également chez les enfants autistes d’âge scolaire. Le second volet vise à évaluer chez les enfants autistes l’intégrité des connexions visuelles descendantes impliquées dans le traitement des textures. À cet effet, une composante électrophysiologique reflétant principalement des processus de rétroaction corticale a été obtenue lors d’une tâche de ségrégation des textures. Les résultats comportementaux obtenus à l’étude 1 révèlent des seuils sensoriels similaires entre les enfants typiques et autistes à l’égard des stimuli définis par des variations de luminance et de texture. Quant aux données électrophysiologiques, il n’y a pas de différence de groupe en ce qui concerne le traitement cérébral associé aux stimuli définis par des variations de luminance. Cependant, contrairement aux enfants typiques, les enfants autistes ne démontrent pas une augmentation systématique d’activité cérébrale en réponse aux stimuli définis par des variations de texture pendant les fenêtres temporelles préférentiellement associées au traitement de deuxième ordre. Ces différences d’activation émergent après 200 ms et engagent les aires visuelles extrastriées des régions occipito-temporales et pariétales. Concernant la connectivité cérébrale, l’étude 2 indique que les connexions visuelles descendantes sont fortement asymétriques chez les enfants autistes, en défaveur de la région occipito-temporale droite. Ceci diffère des enfants typiques pour qui le signal électrophysiologique reflétant l’intégration visuo-corticale est similaire entre l’hémisphère gauche et droit du cerveau. En somme, en accord avec l’hypothèse spécifique à la complexité, la représentation corticale du traitement de deuxième ordre (texture) est atypiquement diminuée chez les enfants autistes, et un des mécanismes cérébraux impliqués est une altération des processus de rétroaction visuelle entre les aires visuelles de haut et bas niveau. En revanche, contrairement aux résultats obtenus chez les adultes, il n’y a aucun indice qui laisse suggérer la présence de mécanismes supérieurs pour le traitement de premier ordre (luminance) chez les enfants autistes.

Tactical Vehicle Routing Planning with Application to Milk Collection and Distribution

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.

Meta-heuristic Solution Methods for Rich Vehicle Routing Problems

Le problème de tournées de véhicules (VRP), introduit par Dantzig and Ramser en 1959, est devenu l'un des problèmes les plus étudiés en recherche opérationnelle, et ce, en raison de son intérêt méthodologique et de ses retombées pratiques dans de nombreux domaines tels que le transport, la logistique, les télécommunications et la production. L'objectif général du VRP est d'optimiser l'utilisation des ressources de transport afin de répondre aux besoins des clients tout en respectant les contraintes découlant des exigences du contexte d’application. Les applications réelles du VRP doivent tenir compte d’une grande variété de contraintes et plus ces contraintes sont nombreuse, plus le problème est difficile à résoudre. Les VRPs qui tiennent compte de l’ensemble de ces contraintes rencontrées en pratique et qui se rapprochent des applications réelles forment la classe des problèmes ‘riches’ de tournées de véhicules. Résoudre ces problèmes de manière efficiente pose des défis considérables pour la communauté de chercheurs qui se penchent sur les VRPs. Cette thèse, composée de deux parties, explore certaines extensions du VRP vers ces problèmes. La première partie de cette thèse porte sur le VRP périodique avec des contraintes de fenêtres de temps (PVRPTW). Celui-ci est une extension du VRP classique avec fenêtres de temps (VRPTW) puisqu’il considère un horizon de planification de plusieurs jours pendant lesquels les clients n'ont généralement pas besoin d’être desservi à tous les jours, mais plutôt peuvent être visités selon un certain nombre de combinaisons possibles de jours de livraison. Cette généralisation étend l'éventail d'applications de ce problème à diverses activités de distributions commerciales, telle la collecte des déchets, le balayage des rues, la distribution de produits alimentaires, la livraison du courrier, etc. La principale contribution scientifique de la première partie de cette thèse est le développement d'une méta-heuristique hybride dans la quelle un ensemble de procédures de recherche locales et de méta-heuristiques basées sur les principes de voisinages coopèrent avec un algorithme génétique afin d’améliorer la qualité des solutions et de promouvoir la diversité de la population. Les résultats obtenus montrent que la méthode proposée est très performante et donne de nouvelles meilleures solutions pour certains grands exemplaires du problème. La deuxième partie de cette étude a pour but de présenter, modéliser et résoudre deux problèmes riches de tournées de véhicules, qui sont des extensions du VRPTW en ce sens qu'ils incluent des demandes dépendantes du temps de ramassage et de livraison avec des restrictions au niveau de la synchronization temporelle. Ces problèmes sont connus respectivement sous le nom de Time-dependent Multi-zone Multi-Trip Vehicle Routing Problem with Time Windows (TMZT-VRPTW) et de Multi-zone Mult-Trip Pickup and Delivery Problem with Time Windows and Synchronization (MZT-PDTWS). Ces deux problèmes proviennent de la planification des opérations de systèmes logistiques urbains à deux niveaux. La difficulté de ces problèmes réside dans la manipulation de deux ensembles entrelacés de décisions: la composante des tournées de véhicules qui vise à déterminer les séquences de clients visités par chaque véhicule, et la composante de planification qui vise à faciliter l'arrivée des véhicules selon des restrictions au niveau de la synchronisation temporelle. Auparavant, ces questions ont été abordées séparément. La combinaison de ces types de décisions dans une seule formulation mathématique et dans une même méthode de résolution devrait donc donner de meilleurs résultats que de considérer ces décisions séparément. Dans cette étude, nous proposons des solutions heuristiques qui tiennent compte de ces deux types de décisions simultanément, et ce, d'une manière complète et efficace. Les résultats de tests expérimentaux confirment la performance de la méthode proposée lorsqu’on la compare aux autres méthodes présentées dans la littérature. En effet, la méthode développée propose des solutions nécessitant moins de véhicules et engendrant de moindres frais de déplacement pour effectuer efficacement la même quantité de travail. Dans le contexte des systèmes logistiques urbains, nos résultats impliquent une réduction de la présence de véhicules dans les rues de la ville et, par conséquent, de leur impact négatif sur la congestion et sur l’environnement.