Compétition et complémentarité dans l'évolution des réseaux maritimes de transport de conteneurs : le cas de la façade est de l'Amérique du Nord

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Compétition et complémentarité dans l'évolution des réseaux maritimes de transport de conteneurs : le cas de la façade est de l'Amérique du Nord

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Planification et dimensionnement des réseaux optiques de longues distances

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau.

Évaluation de l’intégration "forme urbaine – transports durables" dans les trois grandes régions métropolitaines canadiennes : nouvelle approche exploratoire

La planification intégrée du développement urbain et des transports durables est aujourd’hui cruciale au double impératif d’une plus grande maîtrise des déplacements automobiles et d’une diminution de la « dépendance automobile », éléments essentiels au développement durable des grandes métropoles. La présente recherche visait l‘approfondissement des connaissances sur l‘évolution récente de la forme urbaine dans les trois régions métropolitaines canadiennes de Toronto, Montréal et Vancouver, sous l’angle particulier de l’intégration « forme urbaine – transports durables ». Notre stratégie de recherche a consisté en l’élaboration d’un cadre d‘analyse qui devait permettre une opérationnalisation complète du paradigme d‘aménagement à l‘étude ainsi qu’une évaluation de sa mise en œuvre. Ce cadre tire parti des opportunités analytiques qu‘offrent les systèmes d‘information géographique (SIG) ainsi que certains outils Internet courants de « visite virtuelle des lieux » tel que Google Earth. Il en est résulté une approche méthodologique originale, multidimensionnelle et multi-échelle. Son application a permis des analyses particulières de la forme urbaine pour chacune des trois régions cibles, structurées selon trois axes principaux : leur performance globale (autour de 2006), leur performance en périphérie métropolitaine ainsi que l’évolution de leur performance entre 2001 et 2006. De nos analyses comparatives, Vancouver se démarque avec des performances supérieures pour les trois axes, tout particulièrement pour l‘évolution de ses performances. Montréal arrive quant à elle troisième, en raison notamment de sa faible performance en périphérie. Globalement, les trois régions métropolitaines affichent de faibles niveaux d’intégration entre la forme urbaine et les réseaux de transport durable et souffrent d’une grande dépendance automobile structurelle, particulièrement en leur périphérie. Par ailleurs, en dépit d’objectifs de planification adéquats, les déficiences de leur forme urbaine et leurs progrès relativement modestes laissent présager une prédominance de la dépendance automobile qui perdurera au cours des prochaines années. Il nous apparaît primordial que tous les acteurs du domaine public fassent preuve d‘une plus grande « lucidité », voire maturité, face aux lourds constats exposant la difficile mise en œuvre de leurs objectifs ainsi que la dichotomie entre ce qui « se passe sur le terrain » et le contenu de leurs politiques. Une première étape obligée vers un raffinement des politiques et, peut-être, vers leur plus grande efficacité passe sans doute par la pleine reconnaissance des limites du paradigme d’aménagement actuel et de l‘immense défi que représente un inversement des tendances. Cela implique notamment une plus grande transparence en matière d‘évaluation des politiques ainsi que des efforts communs pour le développement et la diffusion de données de qualité dans les domaines connexes de la forme urbaine et des transports urbains, de meilleurs outils de monitoring, etc., qui pourraient aider à instituer une nouvelle synergie entre tous les acteurs impliqués tant dans la recherche urbaine, le développement urbain que les politiques d’aménagement et de transport. Le raffinement de notre propre approche méthodologique pourrait aussi bénéficier de telles avancées, approche qui constitue une des avenues possibles pour la poursuite de l‘exploration de l‘enjeu de l‘intégration « forme urbaine – transports durables » dans les régions métropolitaines canadiennes.

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.

La vulnérabilité face au risque cyclonique : le cas du wilayat Bawshar en Oman

L’objectif de ce mémoire est de réaliser une étude descriptive et évaluative de la vulnérabilité du wilayat Bawshar (district du gouvernorat Mascate, capitale du Sultanat d’Oman), face au risque cyclonique et ce, dans le but de promouvoir la prévention et l’adaptation. À partir des diverses méthodes d’analyse de la vulnérabilité, présentées dans le cadre théorique, nous souhaitons développer une méthode basée sur la prémisse que la vulnérabilité est un système composé de plusieurs facteurs. Cette méthode sera ensuite adaptée au contexte du wilayat Bawshar en lien avec le risque cyclonique. Cette approche est réalisée autour de trois dimensions de la vulnérabilité : physique, sociale et institutionnelle. À la suite de l’application à notre cas d'étude des différentes théories et méthodes analytiques, réalisée grâce à une analyse qualitative et quantitative, générée par une recherche documentaire, des entrevues semi-dirigées, des données statistiques et géomatiques, une observation directe du terrain d’étude ainsi qu’un sondage, voici les importants résultats que nous avons obtenus : les cyclones affectant le gouvernorat de Mascate génèrent d’importants dommages tels que les pertes de vies humaines, la destruction des maisons et des principaux réseaux de transport, ainsi que d’autres perturbations, ceci dû principalement aux inondations émanant des cyclones. Cet endommagement s’explique par la combinaison et l’interaction de plusieurs facteurs tels que les changements océanographiques et atmosphériques affectant le pays ainsi que la topographie et l’hydrologie du site. Les facteurs tels que l’étalement urbain, l’urbanisation de zones à risques, l’explosion démographique, la non diversification de l’économie ainsi que les conditions socio-économiques amplifient la vulnérabilité face au risque cyclonique. Toutefois d’autres facteurs et changements réalisés par le Sultanat d’Oman dans les dernières années diminuent la vulnérabilité de sa population et réduisent l’endommagement à la suite de tels aléas. Parmi eux, nous retrouvons le développement que le pays a soutenu depuis 1970 dans plusieurs secteurs tels que la santé, l’éducation, les infrastructures et l’instauration de politiques de développement durable visant à diversifier l’économie. Depuis le passage des cyclones Gonu et Phet au Sultanat d’Oman, la gestion des risques est au centre même des priorités gouvernementales.

Pour une approche ressourcielle du développement durable

Cet article défend la thèse de la pertinence d’une approche « ressourcielle » du développement durable. Pour ce faire, l’article montre dans quelle mesure la gestion durable des systèmes de ressource – et notamment des ressources communes, que celles-ci soient naturelles, infrastructurelles ou encore culturelles – constitue une condition sine qua non de la durabilité ; ceci dans la mesure où les questions de ressources sont autant des questions « environnementales », que « sociales » et « économiques », et qu’elles concernent ou mieux, relient – en montrant leur interdépendance – les trois dimensions de la durabilité. Pour ce faire, l’article propose un cadre d’analyse fondé sur les concepts de « ressource » et de « régime institutionnel de ressource » et illustre ces deux concepts à l’aide d’une application empirique à des ressources infrastructurelles que sont les réseaux de transport aérien et ferroviaire.

Proceedings.

Some years have title: Compte-rendu des travaux.

Les interconnexions électriques entre la France et ses voisins européens depuis 1970 : un vecteur méconnu de l'intégration européenne

Les ouvrages de transport d’électricité ont d’abord été pensés un par un, reliant un excédent de production à un besoin de consommation. Ils ont ainsi parfois très naturellement et dès l’origine traversé les frontières des États pour répondre à leur raison d’être. Les secteurs électriques se structurant fortement lorsque le virage électrique fut pris, les interconnexions entre pays furent conçues par les techniciens comme une mesure élémentaire de sûreté et d’équilibre de ce produit atypique qu’est l’électricité. En France plus particulièrement, lorsque la production électronucléaire se développa à partir des années 1970, ces interconnexions devinrent petit à petit sources de revenus pour l’entreprise nationale, et d’équilibre pour la balance commerciale nationale. L’intérêt grandissant porté au secteur électrique par les institutions européennes à la fin des années 1990 vient ébranler les acteurs économiques géographiques verticaux, et rebat les cartes des enjeux à adresser à une maille plus large que l’État nation. Dans ces transformations successives, les interconnexions aux frontières, et particulièrement aux frontières françaises, jouent ainsi un rôle tout à fait spécifique et de plus en plus structurant pour les économies ouvertes des pays européens. Les réseaux de transport électriques continuent ainsi une mutation entamée dans les années 1970 qui les a conduits de la condition de mal nécessaire à celle de vecteurs indispensables de transformation des économies européennes. L’objet de ce mémoire est d’illustrer la très grande capacité d’adaptation de ces organes industriels, économiques, sociétaux et politiques, dont on pourrait faussement penser qu’ils sont immobilisés par leur nature capitalistique, à travers les enjeux portés par les interconnexions aux frontières françaises. Les sources sont à la fois issues de données des opérateurs techniques, de la documentation – encore peu fréquente – sur ces sujets, ainsi que des statistiques officielles du ministère français. Cette capacité d’innovation et de développement de « couches de services » permet aujourd’hui aux grands réseaux de transport de traverser les époques et la variabilité des orientations de leurs environnements, durablement.

Les interconnexions électriques entre la France et ses voisins européens depuis 1970 : un vecteur méconnu de l'intégration européenne

Les ouvrages de transport d’électricité ont d’abord été pensés un par un, reliant un excédent de production à un besoin de consommation. Ils ont ainsi parfois très naturellement et dès l’origine traversé les frontières des États pour répondre à leur raison d’être. Les secteurs électriques se structurant fortement lorsque le virage électrique fut pris, les interconnexions entre pays furent conçues par les techniciens comme une mesure élémentaire de sûreté et d’équilibre de ce produit atypique qu’est l’électricité. En France plus particulièrement, lorsque la production électronucléaire se développa à partir des années 1970, ces interconnexions devinrent petit à petit sources de revenus pour l’entreprise nationale, et d’équilibre pour la balance commerciale nationale. L’intérêt grandissant porté au secteur électrique par les institutions européennes à la fin des années 1990 vient ébranler les acteurs économiques géographiques verticaux, et rebat les cartes des enjeux à adresser à une maille plus large que l’État nation. Dans ces transformations successives, les interconnexions aux frontières, et particulièrement aux frontières françaises, jouent ainsi un rôle tout à fait spécifique et de plus en plus structurant pour les économies ouvertes des pays européens. Les réseaux de transport électriques continuent ainsi une mutation entamée dans les années 1970 qui les a conduits de la condition de mal nécessaire à celle de vecteurs indispensables de transformation des économies européennes. L’objet de ce mémoire est d’illustrer la très grande capacité d’adaptation de ces organes industriels, économiques, sociétaux et politiques, dont on pourrait faussement penser qu’ils sont immobilisés par leur nature capitalistique, à travers les enjeux portés par les interconnexions aux frontières françaises. Les sources sont à la fois issues de données des opérateurs techniques, de la documentation – encore peu fréquente – sur ces sujets, ainsi que des statistiques officielles du ministère français. Cette capacité d’innovation et de développement de « couches de services » permet aujourd’hui aux grands réseaux de transport de traverser les époques et la variabilité des orientations de leurs environnements, durablement.

Identification des réseaux transcriptionnnels de résistance aux antifongiques chez Candida albicans

Plusieurs souches cliniques de Candida albicans résistantes aux médicaments antifongiques azolés surexpriment des gènes encodant des effecteurs de la résistance appartenant à deux classes fonctionnelles : i) des transporteurs expulsant les azoles, CDR1, CDR2 et MDR1 et ii) la cible des azoles 14-lanostérol déméthylase encodée par ERG11. La surexpression de ces gènes est due à la sélection de mutations activatrices dans des facteurs de transcription à doigts de zinc de la famille zinc cluster (Zn2Cys6) qui contrôlent leur expression : Tac1p (Transcriptional activator of CDR genes 1) contrôlant l’expression de CDR1 et CDR2, Mrr1p (Multidrug resistance regulator 1), régulant celle de MDR1 et Upc2p (Uptake control 2), contrôlant celle d’ERG11. Un autre effecteur de la résistance clinique aux azoles est PDR16, encodant une transférase de phospholipides, dont la surexpression accompagne souvent celle de CDR1 et CDR2, suggérant que les trois gènes appartiennent au même régulon, potentiellement celui de Tac1p. De plus, la régulation transcriptionnelle du gène MDR1 ne dépend pas seulement de Mrr1p, mais aussi du facteur de transcription de la famille basic-leucine zipper Cap1p (Candida activator protein 1), un régulateur majeur de la réponse au stress oxydatif chez C. albicans qui, lorsque muté, induit une surexpression constitutive de MDR1 conférant la résistance aux azoles. Ces observations suggèrent qu’un réseau de régulation transcriptionnelle complexe contrôle le processus de résistance aux antifongiques azolés chez C. albicans. L’objectif de mon projet au doctorat était d’identifier les cibles transcriptionnelles directes des facteurs de transcription Tac1p, Upc2p et Cap1p, en me servant d’approches génétiques et de génomique fonctionnelle, afin de i) caractériser leur réseau transcriptionnel et les modules transcriptionnels qui sont sous leur contrôle direct, et ii) d’inférer leurs fonctions biologiques et ainsi mieux comprendre leur rôle dans la résistance aux azoles. Dans un premier volet, j’ai démontré, par des expériences de génétique, que Tac1p contrôle non seulement la surexpression de CDR1 et CDR2 mais aussi celle de PDR16. Mes résultats ont identifié une nouvelle mutation activatrice de Tac1p (N972D) et ont révélé la participation d’un autre régulateur dans le contrôle transcriptionnel de CDR1 et PDR16 dont l’identité est encore inconnue. Une combinaison d’expériences de transcriptomique et d’immunoprécipitation de la chromatine couplée à l’hybridation sur des biopuces à ADN (ChIP-chip) m’a permis d’identifier plusieurs gènes dont l’expression est contrôlée in vivo et directement par Tac1p (PDR16, CDR1, CDR2, ERG2, autres), Upc2p (ERG11, ERG2, MDR1, CDR1, autres) et Cap1p (MDR1, GCY1, GLR1, autres). Ces expériences ont révélé qu’Upc2p ne contrôle pas seulement l’expression d’ERG11, mais aussi celle de MDR1 et CDR1. Plusieurs nouvelles propriétés fonctionnelles de ces régulateurs ont été caractérisées, notamment la liaison in vivo de Tac1p aux promoteurs de ses cibles de façon constitutive et indépendamment de son état d’activation, et la liaison de Cap1p non seulement à la région du promoteur de ses cibles, mais aussi celle couvrant le cadre de lecture ouvert et le terminateur transcriptionnel putatif, suggérant une interaction physique avec la machinerie de la transcription. La caractérisation du réseau transcriptionnel a révélé une interaction fonctionnnelle entre ces différents facteurs, notamment Cap1p et Mrr1p, et a permis d’inférer des fonctions biologiques potentielles pour Tac1p (trafic et la mobilisation des lipides, réponse au stress oxydatif et osmotique) et confirmer ou proposer d’autres fonctions pour Upc2p (métabolisme des stérols) et Cap1p (réponse au stress oxydatif, métabolisme des sources d’azote, transport des phospholipides). Mes études suggèrent que la résistance aux antifongiques azolés chez C. albicans est intimement liée au métabolisme des lipides membranaires et à la réponse au stress oxydatif.

Groupage et protection du trafic dynamique dans les réseaux WDM

Avec les nouvelles technologies des réseaux optiques, une quantité de données de plus en plus grande peut être transportée par une seule longueur d'onde. Cette quantité peut atteindre jusqu’à 40 gigabits par seconde (Gbps). Les flots de données individuels quant à eux demandent beaucoup moins de bande passante. Le groupage de trafic est une technique qui permet l'utilisation efficace de la bande passante offerte par une longueur d'onde. Elle consiste à assembler plusieurs flots de données de bas débit en une seule entité de données qui peut être transporté sur une longueur d'onde. La technique demultiplexage en longueurs d'onde (Wavelength Division Multiplexing WDM) permet de transporter plusieurs longueurs d'onde sur une même fibre. L'utilisation des deux techniques : WDM et groupage de trafic, permet de transporter une quantité de données de l'ordre de terabits par seconde (Tbps) sur une même fibre optique. La protection du trafic dans les réseaux optiques devient alors une opération très vitale pour ces réseaux, puisqu'une seule panne peut perturber des milliers d'utilisateurs et engendre des pertes importantes jusqu'à plusieurs millions de dollars à l'opérateur et aux utilisateurs du réseau. La technique de protection consiste à réserver une capacité supplémentaire pour acheminer le trafic en cas de panne dans le réseau. Cette thèse porte sur l'étude des techniques de groupage et de protection du trafic en utilisant les p-cycles dans les réseaux optiques dans un contexte de trafic dynamique. La majorité des travaux existants considère un trafic statique où l'état du réseau ainsi que le trafic sont donnés au début et ne changent pas. En plus, la majorité de ces travaux utilise des heuristiques ou des méthodes ayant de la difficulté à résoudre des instances de grande taille. Dans le contexte de trafic dynamique, deux difficultés majeures s'ajoutent aux problèmes étudiés, à cause du changement continuel du trafic dans le réseau. La première est due au fait que la solution proposée à la période précédente, même si elle est optimisée, n'est plus nécessairement optimisée ou optimale pour la période courante, une nouvelle optimisation de la solution au problème est alors nécessaire. La deuxième difficulté est due au fait que la résolution du problème pour une période donnée est différente de sa résolution pour la période initiale à cause des connexions en cours dans le réseau qui ne doivent pas être trop dérangées à chaque période de temps. L'étude faite sur la technique de groupage de trafic dans un contexte de trafic dynamique consiste à proposer différents scénarios pour composer avec ce type de trafic, avec comme objectif la maximisation de la bande passante des connexions acceptées à chaque période de temps. Des formulations mathématiques des différents scénarios considérés pour le problème de groupage sont proposées. Les travaux que nous avons réalisés sur le problème de la protection considèrent deux types de p-cycles, ceux protégeant les liens (p-cycles de base) et les FIPP p-cycles (p-cycles protégeant les chemins). Ces travaux ont consisté d’abord en la proposition de différents scénarios pour gérer les p-cycles de protection dans un contexte de trafic dynamique. Ensuite, une étude sur la stabilité des p-cycles dans un contexte de trafic dynamique a été faite. Des formulations de différents scénarios ont été proposées et les méthodes de résolution utilisées permettent d’aborder des problèmes de plus grande taille que ceux présentés dans la littérature. Nous nous appuyons sur la méthode de génération de colonnes pour énumérer implicitement les cycles les plus prometteurs. Dans l'étude des p-cycles protégeant les chemins ou FIPP p-cycles, nous avons proposé des formulations pour le problème maître et le problème auxiliaire. Nous avons utilisé une méthode de décomposition hiérarchique du problème qui nous permet d'obtenir de meilleurs résultats dans un temps raisonnable. Comme pour les p-cycles de base, nous avons étudié la stabilité des FIPP p-cycles dans un contexte de trafic dynamique. Les travaux montrent que dépendamment du critère d'optimisation, les p-cycles de base (protégeant les liens) et les FIPP p-cycles (protégeant les chemins) peuvent être très stables.

Un protocole de diffusion des messages dans les réseaux véhiculaires

De nos jours, la voiture est devenue le mode de transport le plus utilisé, mais malheureusement, il est accompagné d’un certain nombre de problèmes (accidents, pollution, embouteillages, etc.), qui vont aller en s’aggravant avec l’augmentation prévue du nombre de voitures particulières, malgré les efforts très importants mis en œuvre pour tenter de les réduire ; le nombre de morts sur les routes demeure très important. Les réseaux sans fil de véhicules, appelés VANET, qui consistent de plusieurs véhicules mobiles sans infrastructure préexistante pour communiquer, font actuellement l’objet d'une attention accrue de la part des constructeurs et des chercheurs, afin d’améliorer la sécurité sur les routes ou encore les aides proposées aux conducteurs. Par exemple, ils peuvent avertir d’autres automobilistes que les routes sont glissantes ou qu’un accident vient de se produire. Dans VANET, les protocoles de diffusion (broadcast) jouent un rôle très important par rapport aux messages unicast, car ils sont conçus pour transmettre des messages de sécurité importants à tous les nœuds. Ces protocoles de diffusion ne sont pas fiables et ils souffrent de plusieurs problèmes, à savoir : (1) Tempête de diffusion (broadcast storm) ; (2) Nœud caché (hidden node) ; (3) Échec de la transmission. Ces problèmes doivent être résolus afin de fournir une diffusion fiable et rapide. L’objectif de notre recherche est de résoudre certains de ces problèmes, tout en assurant le meilleur compromis entre fiabilité, délai garanti, et débit garanti (Qualité de Service : QdS). Le travail de recherche de ce mémoire a porté sur le développement d’une nouvelle technique qui peut être utilisée pour gérer le droit d’accès aux médias (protocole de gestion des émissions), la gestion de grappe (cluster) et la communication. Ce protocole intègre l'approche de gestion centralisée des grappes stables et la transmission des données. Dans cette technique, le temps est divisé en cycles, chaque cycle est partagé entre les canaux de service et de contrôle, et divisé en deux parties. La première partie s’appuie sur TDMA (Time Division Multiple Access). La deuxième partie s’appuie sur CSMA/CA (Carrier Sense Multiple Access / Collision Avoidance) pour gérer l’accès au medium. En outre, notre protocole ajuste d’une manière adaptative le temps consommé dans la diffusion des messages de sécurité, ce qui permettra une amélioration de la capacité des canaux. Il est implanté dans la couche MAC (Medium Access Control), centralisé dans les têtes de grappes (CH, cluster-head) qui s’adaptent continuellement à la dynamique des véhicules. Ainsi, l’utilisation de ce protocole centralisé nous assure une consommation efficace d’intervalles de temps pour le nombre exact de véhicules actifs, y compris les nœuds/véhicules cachés; notre protocole assure également un délai limité pour les applications de sécurité, afin d’accéder au canal de communication, et il permet aussi de réduire le surplus (overhead) à l’aide d’une propagation dirigée de diffusion.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.