Spelling suggestions: "subject:"nœuds"" "subject:"studs""
1 |
La théorie des noeuds : les invariants polynomiauxJacques, Annie 16 April 2018 (has links)
La théorie des noeuds est une branche de la topologie algébrique. On peut imaginer un noeud comme étant une corde nouée dont les extrémités sont collées ensemble et un entrelacs comme étant une collection de noeuds. On peut déformer un entrelacs (sans utiliser de ciseau) de plusieurs façons. Par exemple, on peut l'étirer, passer une section sous une autre, etc. Deux entrelacs sont dits équivalents si l'on peut déformer l'un d'eux de manière à ce qu'il soit identique à l'autre. Le problème fondamental de la théorie des noeuds est de distinguer des entrelacs non équivalents. Pour ce faire, on utilise des invariants. Les principaux invariants qui sont étudiés dans ce mémoire sont le déterminant et la signature d'un entrelacs, le polynôme d'Alexander, le polynôme de Conway, le polynôme crochet normalisé de Kauffman ainsi que le polynôme de Jones.
|
2 |
Gestion et surveillance d'un réseau sans fil de noeuds de capteurs dans le NordParadis, Guillaume 27 January 2024 (has links)
Les changements climatiques affectent grandement le climat partout sur la planète, mais plus particulièrement dans les zones nordiques, là où le pergélisol dégèle tranquillement. Les chercheurs tentent donc de suivre ces changements dans les zones à l'aide de collecteurs échantillonnant et sauvegardant les données. Cependant, la récupération de ces données est très coûteuse en déplacement et en temps étant donné l'isolement des villages où ces collecteurs se situent. Les réseaux sans fil de nœuds de capteurs sont une solution à ce problème. L'idée est donc de faire parvenir ces données automatiquement aux chercheurs en utilisant des moyens de communication. En 2017, un premier réseau sans fil de nœuds de capteurs a été installé dans le village de Salluit, au nord du Québec en utilisant des stations de collecte déjà existantes. Celui-ci a connu plusieurs problèmes de transfert des données et de collecte depuis son déploiement. Dans ce mémoire, nous examinons ces problèmes. Leurs causes ont été difficiles à déterminer puisque la conception des nœuds de collectes ne permet pas un bon suivi de l'état des nœuds. Les causes des problèmes ont tout de même été déterminées, mais sans certitude, ce qui est en soi un problème. C'est donc ce dernier problème qui nous a menés à proposer une architecture différente permettant de mieux diagnostiquer les problèmes des nœuds de collecte. Cette architecture déplace différentes fonctions effectuées par le collecteur dans le réseau de Salluit vers l'interface sans fil pour permettre un diagnostic plus individualisé de l'interface sans fil et du collecteur. Ce mémoire commence donc par détailler le fonctionnement des réseaux de collecte de données. Par la suite, il présente les installations de Salluit et procède à une analyse des capacités énergétiques des nœuds de collecte du réseau. Ensuite, il propose une architecture permettant de répondre aux lacunes du réseau de Salluit. Puis, le mémoire détaille une implémentation du nœud de collecte de cette architecture proposée. / Climate change greatly affects the climate all over the planet, but especially in northern areas, where permafrost is slowly thawing. Researchers are therefore trying to track changes in these areas using sampling sensors and saving the data locally. However, retrieving this data is very costly in travel and time given the isolation of the villages where these sensors are located. Wireless networks of sensor nodes are a possible solution to this problem. The idea is therefore to send this data automatically to researchers at Université Laval. In 2017, a first wireless network of sensor nodes was installed in the village of Salluit, in Northern Quebec, using already existing collection stations. The installation experienced several data transfer and collection issues since its deployment. In this thesis, we examine these failures in connectivity. Their origins have been difficult to determine since the nodes does not allow good monitoring of their state. This led to some uncertainty in our determination of all causes of failure. For this reason, we also propose a new architecture to better diagnose any future problems of the sensor nodes. This architecture shifts various functions currently performed by the sensor in Salluit's network to the wireless interface to allow more individualized diagnosis of the wireless interface and the sensor. This thesis therefore begins by detailing the operation of data collection networks. It then presents the Salluit facilities and analyze the energy capacities of the network's collection nodes. Thereafter, it proposes an architecture able to respond to the shortcomings of the Salluit network. Then, the thesis details an implementation of the collection node of this proposed architecture.
|
3 |
Quelques méthodes numériques pour le calcul de fonctions splines à une et plusieurs variables.Paihua Montes, Luis 11 May 1978 (has links) (PDF)
Etude de la stabilité numérique de deux méthodes utilisées pour l'obtention de fonctions splines.
|
4 |
A generalisation of property "R"Cebanu, Radu Andrei 03 1900 (has links) (PDF)
Nous étudions un problème de chirurgie de Dehn, à savoir la caractérisation des nœuds dans les espaces lenticulaires qui admettent des chirurgies intégrales homéomorphes à S1 x S2. Nous montrons que ces nœuds sont fibrés et qu'ils bordent des surfaces de Seifert planaires. De façon équivalente, les nœuds induits dans S1 x S2 sont isotopes à des tresses. Le principal outil que nous avons utilisé est l'homologie de Heegaard-Floer, un ensemble d'invariants de type théorie de jauge développés par Ozsváth-Szabó à partir de 2000. En outre, nous montrons que ces nœuds sont simples au sens de Floer, donc conjecturalement simples. Compte tenu de cette dernière conjecture, nous avons initié une étude de nœuds simples dans les espaces lenticulaires appropriés et nous avons donné une liste potentiellement complète de tous les nœuds simples avec des chirurgies intégrales S1 x S2. Ces nœuds se révèlent être les nœuds induits dans les espaces lenticulaires obtenues en effectuant une chirurgie de Dehn sur certains nœuds doublement primitifs dans S1 x S2, exactement ceux construits par Baker.
______________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : chirurgie de Dehn, espace lenticulaire, homologie de Heegaard-Floer, nœud fibré.
|
5 |
Sécurité et fiabilité des communications dans les réseaux d’essaims / Secure and reliable communications in swarm networksZaouche, Lotfi 08 February 2017 (has links)
L’émergence de véhicules aériens sans pilote, généralement appelés drones, petits et bon marché favorise leur utilisation dans le domaine des applications civiles. Ces drones sont équipés de différents capteurs et ont la capacité de communiquer via des liaisons sans fil et ont la particularité de se déplacer librement dans l’espace, révolutionnant la gestion des applications de surveillance. Un réseau ad hoc de drones, Flying Ad hoc Networks (FANET) en anglais, est composé d’une flotte de drones autonomes et est utilisé lors de missions dans des environnements hostiles pour la surveillance ou l’inspection de sites dangereux ou inconnus. Les FANETs peuvent être également utilisés pour suivre et filmer des événements spéciaux comme une course de vélos ou un match de football, dans ce cas les liaisons doivent garantir un minimum de qualité. Les FANETs nécessitent une attention particulière en ce qui concerne l’économie d’énergie des UAV dont les ressources en énergie sont limitées, mais aussi d’être immunisés contre des attaques malveillantes. Au cours de cette thèse, nous nous sommes concentrés sur le problème de suivi d’une cible mobile utilisant une flotte de drones pour la filmer. Étant donné que la cible se déplace, les drones doivent la suivre en continu, et une liaison vers la station terrestre doit être disponible. Dans ce contexte, nous proposons une solution qui permet la coordination d’un ensemble de drones afin de maintenir un chemin optimal entre la cible et la station terrestre. Notre solution se révèle efficace en matière de gain en temps et en énergie. Nous avons également proposé une solution basée sur des protocoles hiérarchiques pour économiser plus d’énergie dans le processus de communication avec la station terrestre. Nous avons également développé une autre solution qui permet d’économiser plus d’énergie en forçant les nœuds égoïstes à participer dans le réseau et d’assurer le relais de paquets lorsqu’ils sont sollicités. En effet, si un nœud égoïste refuse de router des paquets d’autres nœuds, cela induit une charge supplémentaire pour le reste des nœuds du réseau. Nous avons validé l’apport de l’ensemble de nos solutions par évaluation de performances à l’aide de simulations. / The emergence of small and inexpensive Unmanned Aerial Vehicles (UAVs) promotes their use in several applications. UAVs are usually equipped with different sensors and have the ability to communicate via wireless connections. Their capability to fly freely in the space offers new opportunities to monitoring and tracking applications. A Flying Ad hoc Network (FANET) is composed of a fleet of autonomous UAVs and is used for monitoring applications in hostile environments, surveillance or site inspection. FANETs could also be used for filming special events such as bike races or soccer matches, so, the connections must guarantee a minimum of quality of service. In FANETs, saving energy of UAVs that have limited battery is very challenging and protecting the network from malicious attacks is even more difficult. In this thesis, we focus on tracking and filming a moving target using a fleet of UAVs. Since the target is moving, the UAVs have to follow it continuously, and a path to the ground station must be available. In this context, we propose an efficient solution that allows the coordination of the UAVs to maintain an optimal path between the target and the ground station. The proposed solution is time and energy efficient. We also propose a solution based on hierarchical protocols to save more energy in the communication process with the ground station. Another solution that allows energy saving is to force selfish nodes to participate in the network to route received packets towards their destination. Indeed, a selfish node is concerned only about its own welfare, refusing to route packets of other node, causing an extra charge for the rest of nodes in the network. We validate our solutions through simulation campaigns.
|
6 |
Impact du changement du protocole de routage dans un réseau / Impact of changing the routing protocol in a networkBekono, Nina Pelagie 13 December 2018 (has links)
Les protocoles de routage dans les réseaux peuvent être amenés à changer pour de nombreuses raisons : la détection d'un événement particulier, un changement de topologie planifié ou non, la mobilité des nœuds, l'obsolescence de version, etc. Ces changements ne pouvant être simultanément détectés ou pris en compte par tous les nœuds du réseau, il est nécessaire de considérer le cas où certains nœuds utilisent le protocole de routage initial, tandis que d'autres ont migré vers le nouveau protocole de routage. Les travaux de cette thèse portent sur le problème de boucles de routage susceptibles d'apparaître dans ce contexte, et qui dégradent considérablement les performances du réseau. Nous proposons des solutions d'ordonnancement des nœuds, dans le but de contrôler la migration afin d'éviter ces boucles. Premièrement, nous considérons le contexte des réseaux statiques et des protocoles centralisés avec pour cas particulier le changement de métriques dans le réseau. Nous proposons deux solutions d'évitement des boucles centralisées : SCH-m (amélioration mineure d'un protocole existant), et ACH (nouvelle contribution), basées sur l'identification des boucles de routage dans les composantes connexes que contient l'union des deux protocoles de routage. Nous accélérons la migration du réseau par une opération de fusion étape par étape des différentes transitions produites. Deuxièmement, nous évoluons vers les protocoles distribués en conservant le contexte statique du réseau, et considérons le cas particulier du retrait ou de la panne d'un nœud. Nous proposons également deux solutions : RTH-d (amélioration mineure d'un protocole existant) et DLF (nouvelle contribution traitant les boucles de taille 2) basées sur un échange de messages entre les nœuds tant pour la détection de la panne que pour la notification de la migration. Troisièmement, nous considérons le contexte de mobilité des nœuds, et étudions les performances de DLF-k (version améliorée de DLF qui prend en compte les boucles de taille inférieures ou égales à k, avec k >= 2) sur deux types d'applications : les applications avec un unique nœud mobile qui est la destination, et les applications avec un groupe de nœuds mobiles. / Routing protocols in networks may change for many reasons: detection of a particular event, planned or unplanned change of topology, mobility of nodes, version obsolescence, etc. As these changes can not be simultaneously detected or taken into account by all nodes of the network, it is necessary to consider the case where some nodes use the initial routing protocol, while others have migrated to the new routing protocol. The work of this thesis deals with the problem of routing loops that may appear in this context, and which considerably degrade the performance of the network. We propose node scheduling solutions to control migration to avoid these loops. First, we consider the context of static networks and centralized protocols with the particular case of changing metrics. We propose two centralized avoidance solutions: SCH-m (minor improvement of an existing heuristic), and ACH (new contribution), based on the identification of the routing loops in the strongly connected components contained in the union of the two routing protocols. We accelerate the migration of the network by a step-by-step merge operation of the different transitions produced. Second, we evolve towards the distributed protocols while preserving the static context of the network, and consider the particular case of the withdrawal or breakdown of a node. We also propose two solutions: RTH-d (minor improvement of an existing heuristic) and DLF (new contribution for loops of size 2) based on message exchange of nodes for both failure detection and for migration notification. Thirdly, we consider the context of nodes mobility, and study the performance of DLF- k (improved version of DLF which takes into account loops of size less than or equal to k, with k >= 2) on two types of applications: applications with a single mobile node that is the destination, and applications with a group of mobile nodes.
|
7 |
Contribution à la formalisation unifiée des connaissances fonctionnelles et organisationnelles d'un système industriel en vue d'une évaluation quantitative des risques et de l'impact des barrières envisagéesLéger, Aurélie 28 May 2009 (has links) (PDF)
Depuis la révolution industrielle, l'Homme développe des systèmes industriels pour satisfaire ses exigences de production. Mais exploiter ces installations n'est pas sans risques pour les utilisateurs. De ce fait, l'analyse des risques s'est largement développée durant ces dernières décennies. En effet, si dans les années 70, les études se focalisaient sur les défaillances technologiques, des accidents ont souligné l'importance des facteurs humains et organisationnels dans leur occurrence. Si bien que dans les années 80, des méthodes consacrées à l'identification de ces facteurs ont émergées. Ces études, impliquant différentes disciplines, étaient jusqu'alors conçues et conduites séparément les unes des autres. Cet état de fait amène à une sectorisation des analyses et ne permet pas d'avoir une vision globale de la situation étudiée. Mais, depuis peu, des méthodologies proposent d'intégrer (partiellement) ces dimensions dans la démarche d'analyse. Le manque d'intégration constitue aujourd'hui une problématique, scientifique et industrielle, pour les exploitants de systèmes critiques. Ainsi, notre contribution porte sur le développement d'une méthodologie permettant l'analyse de risques de systèmes socio-techniques en exploitation. Ce type d'analyse vise à probabiliser le risque à des fins d'aide à la décision. En ce sens, nous proposons une démarche de formalisation, d'intégration, de représentation et de modélisation des différentes connaissances du système. Le modèle présenté permet d'identifier l'ensemble des causes menant à l'occurrence d'un événement critique, en considérant les données techniques du système et les données liées aux opérateurs et à l'organisation.
|
8 |
Quelques interactions de la topologie classique et quantique en dimension troisEisermann, Michael 14 December 2007 (has links) (PDF)
En 1984 Jones découvrit son invariant polynomial, qui ne ressemblait à aucun concept connu auparavant. En quelques années cette découverte a provoqué l'invention de nombreux autres invariants polynomiaux et des invariants dits quantiques ou de type fini, issus des représentations du groupe des tresses et souvent inspirés par des analogies avec la physique théorique. Malgré leurs mérites pour la théorie des nœuds et des 3-variétés, ces invariants restent peu compris du coté de la topologie algébrique, et parfois de la topologie tout court. Ce mémoire présente et discute quelques éléments de réponse.
|
9 |
Mechanisms of central nervous system nodes of Ranvier assembly / Mécanismes d'assemblage des nœuds de Ranvier dans le système nerveux centralFreeman, Sean 02 July 2015 (has links)
L'agrégation des canaux sodium (Nav) aux nœuds de Ranvier est une étape importante pour la propagation électrique saltatoire rapide le long des axones myélinisés. L'assemblage des nœuds dépend d'interactions neurones-cellules gliales myélinisantes, les oligodendrocytes dans le système nerveux central (SNC) et les cellules de Schwann dans le système nerveux périphérique (SNP). Bien décrits dans le SNP, les mécanismes cellulaires et moléculaires restent à caractériser dans le SNC. Lors de ma thèse, je me suis focalisé sur les étapes précoces d'assemblage des nœuds dans le SNC. Ce travail montre que des agrégats de protéines nodales (ou pré-nœuds) sont formés le long des axones de neurones GABAergiques avant la myélinisation dans des cultures neurones-glies d'hippocampe et également au cours du développement chez les rongeurs. La formation de pré-nœuds dépend de protéines sécrétées par les oligodendrocytes et de la protéine axonale d'échafaudage, ankyrineG. En outre, la transition des isoformes de Nav le long des axones est régulée par la présence des cellules gliales. Enfin, les pré-nœuds permettent d'accélérer la vitesse de conduction de l'influx nerveux par un facteur 1,5, indépendamment de la myélinisation et du calibre axonal. Globalement, ces résultats renforcent notre connaissance des mécanismes d'assemblage des nœuds de Ranvier dans le SNC et suggèrent une fonction développementale de l'agrégation nodale avant le début de la myélinisation. Si la vitesse de conduction a été décrite comme liée aux propriétés isolantes de la gaine de myéline, les résultats de cette thèse apportent un concept novateur de régulation de la conduction axonale en l'absence de myéline. / The clustering of sodium channels (Nav) at the nodes of Ranvier is an important step in permitting rapid saltatory conduction along myelinated axons. Nodal assembly is neuron-glia dependent, mediated by myelinating oligodendrocytes of the central nervous system (CNS) and Schwann cells in the peripheral nervous system (PNS). While the mechanisms of nodal assembly are currently best characterized in the PNS, cellular and molecular mechanisms underlying their assembly in the CNS are only partially understood. In the core of my PhD dissertation, I focused on the early developmental steps of nodal protein clustering in the CNS and show that clusters of nodal proteins, called prenodes, are detected before myelination along GABAergic axons in hippocampal neuron-glia cultures and also in the developing rodent hippocampus. Prenodal clustering requires extrinsic oligodendroglial secreted proteinaceous factors, and also the intrinsic axonal cytoskeletal scaffolding protein ankyrinG. Furthermore, the transition of sodium channels isoforms is tightly regulated along GABAergic axons during development, but this transition is lost in the absence of the physical presence of glial cells. Lastly, prenodes increase axonal conduction by a factor of 1.5x, independently of myelination and axonal caliber. Taken together, these results further our understanding of CNS nodes of Ranvier assembly mechanisms and the developmental function of nodal clustering prior to myelin ensheathment. While conduction velocity along axons has long been thought to mostly rely on the insulating properties of myelin, these results may shed light on a new concept of axonal conduction in the absence of myelination.
|
10 |
Time-dependent routing : models, algorithms, and the value of informationJaballah, Rabie 13 December 2023 (has links)
Le problème de tournées de véhicules (Vehicle routing problem - VRP), introduit il y a plus de 60 ans, demeure au cœur des systèmes de transport. Après des décennies de développement, le VRP, par son ensemble très riche de variantes, représente l'un des problèmes les plus étudiés dans la littérature. Pourtant, en raison du manque de données, deux hypothèses importantes font que le VRP ne s'adapte pas efficacement au trafic et à la congestion, deux éléments importants pour modéliser de façon réelle des problèmes pratiques. Une première hypothèse considère que la vitesse de déplacement est constante dans le temps. La seconde, considère que chaque paire de nœuds (clients) n'est reliée que par un arc, ignorant le réseau routier implicite (sous-jacent). La congestion de la circulation est l'un des plus grands défis des systèmes de transport. Ces systèmes étant directement affectés par la congestion, l'ensemble de la chaîne d'approvisionnement doit s'adapter à ce facteur, ce qui n'est pas simple. La croissance continue du fret au cours des dernières années aggrave encore la situation et une attention renouvelée à la mobilité, à l'environnement et à la logistique urbaine a mis en lumière ces questions. Récemment, les avancées technologiques en communication et en acquisition de données en temps réel ont permis de collecter plusieurs informations sur les véhicules telles que leur localisation, leur accélération, leur vitesse, leur décélération, etc. Ainsi, nous pouvons remettre en question la façon dont nous définissons, modélisons et résolvons les problèmes de transport. Ceci nous permet de surmonter les deux hypothèses mentionnées en intégrant non seulement les informations relatives à la congestion, mais aussi en considérant l'ensemble du réseau routier. Dans cette thèse nous considérons l'ensemble du réseau routier sous-jacent, ce qui signifie que nous avons les nœuds clients mais également tous les nœuds intermédiaires qui constituent ce réseau. Ensuite, nous modélisons le temps de trajet de chaque route individuellement au cours de la journée. En divisant une journée en petits intervalles, jusqu'à une précision de l'ordre de la seconde, nous prenons en considération des informations précises sur le trafic. Il en résulte un nouveau problème appelé le problème de tournées de véhicules à plus court chemin avec dépendance du temps (Time-dependant shortest path vehicle routing problem - TD-SPVRP), dans lequel nous combinons le problème du plus court chemin avec dépendance du temps et le VRP avec dépendance du temps, créant ainsi un problème plus général et très complexe. Le TD-SPVRP est plus proche des conditions réelles et il constitue le sujet du chapitre 2 où nous le formulons comme un modèle de programmation linéaire en nombres entiers mixtes et concevons une heuristique rapide et efficace pour le résoudre. Nous testons le modèle ainsi que l'heuristique sur des instances générées à partir de données réelles de circulation sur le réseau routier de la ville de Québec, Canada. Les résultats montrent que l'heuristique fournit des solutions de haute qualité avec un écart moyen de 5,66% par rapport aux bornes inférieures déterminées par le modèle. Cependant, le modèle mathématique ne parvient pas à trouver aucune solution pour les instances de données réelles. Pour pouvoir résoudre ce problème complexe, une grande attention a été portée à la performance de l'implantation des algorithmes proposés afin d'améliorer leur rapidité en termes de temps d'exécution. Le problème reste très compliqué, surtout lorsque nous considérons une grande partie du réseau routier sous-jacent avec des données de trafic très précises. Pour cela, nous avons utilisé différentes techniques pour optimiser l'effort de calcul afin de résoudre le problème en évaluant l'impact engendré sur la précision tout en évitant la perte de précieuses informations. Nous avons développé deux types d'agrégation de données couvrant deux niveaux d'information différents. Premièrement, nous avons manipulé la structure du réseau en réduisant sa taille, et deuxièmement en contrôlant le niveau d'agrégation temporel pour générer les données de trafic et pour déterminer la vitesse d'un véhicule à tout moment. Pour la structure du réseau, nous avons utilisé différentes techniques de réduction de graphe pour en réduire la taille. Nous avons étudié la valeur et le compromis de l'information spatiale. Les solutions générées en utilisant le graphe réduit sont analysées dans le Chapitre 3 pour évaluer la qualité et la perte d'information dû à la réduction. Cette analyse démontre également que la transformation classique du TD-SPVRP en un problème de tournées dépendant du temps (Time-dependant VRP - TD-VRP) équivalent résulte en un graphe plus grand qui nécessite un temps de traitement important ce qui a un impact sur la qualité de la solution. Notre développement montre que la résolution du TD-SPVRP nécessite en moyenne 1445 secondes tandis que la résolution du TD-VRP associé nécessite 41 181 secondes. Garder un haut niveau de précision et réussir à réduire la taille du graphe est possible. En particulier, deux procédures de réduction ont été développées, la réduction des nœuds et la réduction des arcs parallèles. Les deux techniques réduisent la taille du graphe. La réduction des nœuds conduit à une amélioration de 1,11%, la réduction des arcs parallèles donne un écart de 2,57% signifiant la présence d'une distorsion dans le graphe réduit. En ce qui concerne les informations sur le trafic, nous avons analysé les compromis entre une grande quantité de données très précises et un plus petit volume de données agrégées avec une perte potentielle d'information. Ceci est fait en analysant la précision des données agrégées sous différents modèles de détermination des temps de parcours. Ces approches sont présentées dans le Chapitre 4. Au niveau de la prévision des temps de parcours, il est important que chaque segment routier ait des observations de vitesse pour chaque intervalle de temps considéré, ce que nous appelons le niveau de couverture du réseau. Notre analyse indique qu'une couverture complète du réseau routier à tout moment de la journée est nécessaire pour atteindre un niveau de précision élevé. Le recours à une agrégation élevée (de grands intervalles de temps) permet de réduire la taille du problème et d'obtenir une meilleure couverture des données, mais au prix d'une perte d'information. Les modèles analysés, LTM (link travel mode) et FSM (flow speed model), partagent les mêmes performances lorsqu'on utilise un grand intervalle de temps (120, 300 et 600 secondes), donc un niveau d'agrégation plus élevé, avec un écart moyen absolu de 5,5% par rapport aux temps de parcours observés. Cependant, avec une courte période (1, 10, 30 et 60 secondes), FSM fonctionne mieux que LTM. Pour un intervalle d'une seconde, FSM donne un écart absolu moyen de 6,70%, tandis que LTM fournit un écart de 11,17%. Ce chapitre détermine ainsi sous quelles conditions les modèles d'estimation de temps de parcours fonctionnent bien et procurent des estimations fidèles des temps de parcours réalisés. Cette thèse est structurée de la manière suivante. À la suite d'une introduction générale dans laquelle nous présentons le cadre conceptuel de la thèse et son organisation, le Chapitre 1 présente une revue de la littérature pour les deux problèmes fondamentaux étudiés, le problème de plus court chemin (Shortest path problem - SPP) et le VRP et leurs variantes développées au cours des années. Le Chapitre 2 introduit une nouvelle variante du VRP, le TD-SPVRP. Le Chapitre 3 présente les différentes techniques développées pour réduire la taille du réseau en manipulant les informations spatiales du réseau routier. L'impact de ces réductions est évalué et analysé sur des instances réelles en utilisant plusieurs heuristiques. Le Chapitre 4 traite l'impact de l'agrégation des données temporelle et des modèles d'évaluation des temps de parcours. Le dernier chapitre constitue une conclusion et ouvre des perspectives de recherche relatives à nos travaux. / The vehicle routing problem (VRP), introduced more than 60 years ago, is at the core of transportation systems. With decades of development, the VRP is one of the most studied problems in the literature, with a very rich set of variants. Yet, primarily due to the lack of data, two critical assumptions make the VRP fail to adapt effectively to traffic and congestion. The first assumption considers that the travel speed is constant over time ; the second, that each pair of customers is connected by an arc, ignoring the underlying street network. Traffic congestion is one of the biggest challenges in transportation systems. As traffic directly affects transportation activities, the whole supply chain needs to adjust to this factor. The continuous growth of freight in recent years worsens the situation, and a renewed focus on mobility, environment, and city logistics has shed light on these issues. Recently, advances in communications and real-time data acquisition technologies have made it possible to collect vehicle data such as their location, acceleration, driving speed, deceleration, etc. With the availability of this data, one can question the way we define, model, and solve transportation problems. This allows us to overcome the two issues indicated before and integrate congestion information and the whole underlying street network. We start by considering the whole underlying street network, which means we have customer nodes and intermediate nodes that constitute the street network. Then, we model the travel time of each street during the day. By dividing the day into small intervals, up to a precision of a second, we consider precise traffic information. This results in a new problem called the time-dependent shortest path vehicle routing problem (TD-SPVRP), in which we combine the time-dependent shortest path problem (TD-SPP) and the time-dependent VRP (TD-VRP), creating a more general and very challenging problem. The TD-SPVRP is closer to what can be found in real-world conditions, and it constitutes the topic of Chapter 2, where we formulate it as a mixed-integer linear programming model and design a fast and efficient heuristic algorithm to solve this problem. We test it on instances generated from actual traffic data from the road network in Québec City, Canada. Results show that the heuristic provides high-quality solutions with an average gap of only 5.66%, while the mathematical model fails to find a solution for any real instance. To solve the challenging problem, we emphasize the importance of a high-performance implementation to improve the speed and the execution time of the algorithms. Still, the problem is huge especially when we work on a large area of the underlying street network alongside very precise traffic data. To this end, we use different techniques to optimize the computational effort to solve the problem while assessing the impact on the precision to avoid the loss of valuable information. Two types of data aggregation are developed, covering two different levels of information. First, we manipulated the structure of the network by reducing its size, and second by controlling the time aggregation level to generate the traffic data, thus the data used to determine the speed of a vehicle at any time. For the network structure, we used different reduction techniques of the road graph to reduce its size. We studied the value and the trade-off of spatial information. Solutions generated using the reduced graph are analyzed in Chapter 3 to evaluate the quality and the loss of information from the reduction. We show that the transformation of the TD-SPVRP into an equivalent TD-VRP results in a large graph that requires significant preprocessing time, which impacts the solution quality. Our development shows that solving the TD-SPVRP is about 40 times faster than solving the related TD-VRP. Keeping a high level of precision and successfully reducing the size of the graph is possible. In particular, we develop two reduction procedures, node reduction and parallel arc reduction. Both techniques reduce the size of the graph, with different results. While the node reduction leads to improved reduction in the gap of 1.11%, the parallel arc reduction gives a gap of 2.57% indicating a distortion in the reduced graph. We analyzed the compromises regarding the traffic information, between a massive amount of very precise data or a smaller volume of aggregated data with some potential information loss. This is done while analyzing the precision of the aggregated data under different travel time models, and these developments appear in Chapter 4. Our analysis indicates that a full coverage of the street network at any time of the day is required to achieve a high level of coverage. Using high aggregation will result in a smaller problem with better data coverage but at the cost of a loss of information. We analyzed two travel time estimation models, the link travel model (LTM) and the flow speed model (FSM). They both shared the same performance when working with large intervals of time (120, 300, and 600 seconds), thus a higher level of aggregation, with an absolute average gap of 5.5% to the observed route travel time. With short periods (1, 10, 30, and 60 seconds), FSM performs better than LTM. For 1 second interval, FSM gives an average absolute gap of 6.70%, while LTM provides a gap of 11.17%. This thesis is structured as follows. After a general introduction in which we present the conceptual framework of the thesis and its organization, Chapter 1 presents the literature review for the two main problems of our development, the shortest path problem (SPP) and the VRP, and their time-dependent variants developed over the years. Chapter 2 introduces a new VRP variant, the TD-SPVRP. Chapter 3 presents the different techniques developed to reduce the size of the network by manipulating spatial information of the road network. The impact of these reductions is evaluated and analyzed on real data instances using multiple heuristics. Chapter 4 covers the impact of time aggregation data and travel time models when computing travel times on the precision of their estimations against observed travel times. The conclusion follows in the last chapter and presents some research perspectives for our works.
|
Page generated in 0.0612 seconds