Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Intelligent Transportation System (ITS) provides a great platform for the planners to reduce environmental externalities from auto. We now have access to real time data. We have been using shortest path to provide route choice to the user. But we have the potential to add more variables in choosing routes. Real time data can be used to measure carbon di-oxide emission during a trip. Also, fuel efficiency can be measured using the real time data. Planners should use this potential of ITS to reduce the environmental impact. This paper thus try to evaluate if considering three variables shortest path, environmental impact and fuel efficiency together instead of only shortest path will change the route choice or not. It provides case studies on different types of routes and between different sets of origin /destination to evaluate the combined influence of these three variables on route choice.

La représentation des temps de parcours est un enjeu influençant la qualité de l’information transmise aux usagers des réseaux de transport. En particulier, la congestion constitue un inconvénient majeur dont la prise en compte n’est pas toujours maîtrisée au sein des calculateurs d’itinéraires. De même, les évènements comme les réductions de capacité, les perturbations climatiques, ou encore les pics de fréquentation incitent à dépasser la définition statique des temps de parcours. Des travaux antérieurs se sont focalisés sur des temps dynamiques, i.e. dépendants de la date de départ, de manière à affiner le détail de la représentation, et à prendre notamment en compte le caractère périodique des congestions. La considération d’informations en temps réel est aussi une amélioration indéniable, que ce soit lors de la préparation du trajet, ou lorsqu’il s’agit de s’adapter à des perturbations rencontrées en cours de route. Ceci dit, aussi fines qu’elles soient dans les calculateurs disponibles, ces modélisations présentent un inconvénient majeur : elles ne prennent pas en compte toutes les facettes de la variabilité des temps de parcours. Cette variabilité est très importante, en particulier si l’on considère le niveau d’aversion au risque des usagers. En outre, dans un réseau multimodal, les correspondances éventuelles rendent encore plus critique l’incertitude associée aux temps de parcours. En réponse à ces enjeux, les présents travaux de thèse ont ainsi été consacrés à l’étude de temps de parcours stochastiques, i.e. vus comme des variables aléatoires distribuées.Dans une première étape, nous nous intéressons à la modélisation statistique des temps de parcours et à la quantification de leur variabilité. Nous proposons l’utilisation d’un système de lois développé dans le domaine de l’hydrologie, la famille des lois de Halphen. Ces lois présentent les caractéristiques typiques des distributions de temps de parcours, elles vérifient par ailleurs la propriété de fermeture par l’addition sous certaines hypothèses afférentes à leurs paramètres. En exploitant les ratios de moments associés aux définitions de ces lois de probabilité, nous mettons également au point de nouveaux indicateurs de fiabilité, que nous confrontons avec la palette d’indicateurs classiquement utilisés. Cette approche holistique de la variabilité des temps de parcours nous semble ainsi ouvrir de nouvelles perspectives quant au niveau de détail de l’information, notamment à destination des gestionnaires de réseaux.Par la suite, nous étendons le cadre d’analyse aux réseaux, en utilisant les résultats obtenus à l’étape précédente. Différentes lois de probabilité sont ainsi testées dans le cadre de la recherche du plus court chemin stochastique. Cette première étude nous permet de dresser un panorama des chemins identifiés en fonction du choix de modélisation. S’il est montré que le choix du modèle est important, il s’agit surtout d’affirmer que le cadre stochastique est pertinent. Ensuite, nous soulevons la relative inefficacité des algorithmes de recherche du plus court chemin stochastique, ceux-ci nécessitant des temps de calcul incompatibles avec un passage à l’échelle industrielle. Pour pallier cette difficulté, un nouvel algorithme mettant en oeuvre une technique d’accélération tirée du cadre déterministe est développé dans la dernière partie de la thèse. Les résultats obtenus soulignent la pertinence de l’intégration de modèles stochastiques au sein des calculateurs d’itinéraires. / The travel time representation has a major impact on user-oriented routing information. In particular, congestion detection is not perfect in current route planners. Moreover, the travel times cannot be considered as static because of events such as capacity drops, weather disturbances, or demand peaks. Former researches focused on dynamic travel times, i.e. that depend on departure times, in order to improve the representation details, for example concerning the periodicity of congestions. Real-time information is also a significant improvement for users aiming to prepare their travel or aiming to react to on-line events. However these kinds of model still have an important drawback : they do not take into account all the aspects of travel time variability. This dimension is of huge importance, in particular if the user risk aversion is considered. Additionally in a multimodal network, the eventual connections make the travel time uncertainty critical. In this way the current PhD thesis has been dedicated to the study of stochastic travel times, seen as distributed random variables.In a first step, we are interested in the travel time statistical modeling as well as in the travel time variability. In this goal, we propose to use the Halphen family, a probability law system previously developed in hydrology. The Halphen laws show the typical characteristics of travel time distributions, plus they are closed under addition under some parameter hypothesis. By using the distribution moment ratios, we design innovative reliability indexes, that we compare with classical metrics. This holistic approach appears to us as a promising way to produce travel time information, especially for infrastructure managers.Then we extend the analysis to transportation networks, by considering previous results. A set of probability laws is tested during the resolution of the stochastic shortest path problem. This research effort helps us to describe paths according to the different statistical models. We show that the model choice has an impact on the identified paths, and above all, that the stochastic framework is crucial. Furthermore we highlight the inefficiency of algorithms designed for the stochastic shortest path problem. They need long computation times and are consequently incompatible with industrial applications. An accelerated algorithm based on a deterministic state-of-the-art is provided to overcome this problem in the last part of this document. The obtained results let us think that route planners might include travel time stochastic models in a near future.

Le besoin de se déplacer est un besoin fondamental dans la vie de tous les jours. Avec l’extension continue des zones urbaines, l’augmentation de la population et l’amélioration du niveau de vie des citoyens, le nombre de voitures ne cesse d’augmenter. Ceci étant, la plupart des transports publics proposés aujourd’hui obéissent à des règles qui manquent de souplesse et qui incluent rarement le caractère dynamique, en temps et en espace, de la demande. Cela réduit ainsi l’attractivité de ces services et les rendant même parfois difficilement supportables. De ce fait, la majorité des usagers utilisent encore leur propre véhicule. Ce grand nombre de véhicules, qui est en augmentation continue sur les réseaux routiers, provoque de nombreux phénomènes de congestion induisant une surconsommation de carburant, des émissions inutiles de gaz à effet de serre et une perte de temps importante. Pour y remédier, nous proposons dans cette thèse de nouveaux systèmes de déplacement des usagers avec différents modèles d’optimisation pour la mobilité partagée (covoiturage et taxis-partagés) ainsi que la combinaison de la mobilité partagée avec les transports publics. Les expérimentations sont réalisées sur de vrais réseaux routiers ainsi que sur des données réelles. Ces nouveaux systèmes améliorent considérablement la qualité de service des systèmes classiques existants en termes de coût et de flexibilité tout en ayant un temps de calcul raisonnable. / The travelling is a fundamental part of everyday life. The continuous expansion of urban areas combined with the population increasing and the improvement of life standards increases the need of mobility and the use of private cars. Furthermore, the majority of public transportations are subject to rules lacking of flexibility and rarely taking into account the dynamic context. The attractiveness of public transportation is therefore reduced and, as a consequence, its financial support, resulting in a further deterioration of the public services quality and flexibility. Therefore, the majority of users still use their own vehicles. The number of vehicles is continuously increasing on road networks causing important phenomena of congestion, high fuel consumption and emissions of greenhouse gases, time loss. This unpleasant situation forces communities to consider alternative solutions for the mobility such as ride-sharing, an interesting alternative to solo car use. The overall objective of this thesis is to propose new travel systems for users through the introduction of optimization models for shared mobility (ride-sharing and taxi-sharing) and the combination of shared mobility and public transportation. The computational experiments are carried out on real road networks and real data. Our numerical results show the effectiveness of our approach, which improves the quality of service compared to the traditional systems in terms of cost and flexibility. The running time remains reasonable to allow using our framework in real-time transportation applications.

Software engineering projects that utilize inappropriate pathfinding algorithms carry a significant risk of poor runtime performance for customers. Using social network theory, this experimental study examined the impact of algorithms, frameworks, and map complexity on elapsed time and computer memory consumption. The 1,800 2D map samples utilized were computer random generated and data were collected and processed using Python language scripts. Memory consumption and elapsed time results for each of the 12 experimental treatment groups were compared using factorial MANOVA to determine the impact of the 3 independent variables on elapsed time and computer memory consumption. The MANOVA indicated a significant factor interaction between algorithms, frameworks, and map complexity upon elapsed time and memory consumption, F(4, 3576) = 94.09, p < .001, h2 = .095. The main effects of algorithms, F(4, 3576) = 885.68, p < .001, h2 = .498; and frameworks, F(2, 1787) = 720,360.01, p .001, h2 = .999; and map complexity, F(2, 1787) = 112,736.40, p < .001, h2 = .992, were also all significant. This study may contribute to positive social change by providing software engineers writing software for complex networks, such as analyzing terrorist social networks, with empirical pathfinding algorithm results. This is crucial to enabling selection of appropriately fast, memory-efficient algorithms that help analysts identify and apprehend criminal and terrorist suspects in complex networks before the next attack.

The aim of the research project that is the subject of this thesis is to apply mathematical techniques, especially those in the area of operations research, to the problem of maritime minefield transit. We develop several minefield models applicable to different aspects of the minefield problem. These include optimal mine clearance, shortest time traversal and time constrained traversal. We hope the suite of models and tools developed will help make mine field clearance and traversal both safer and more efficient and that exposition of the models will bring a clearer understanding of the mine problem from a mathematical perspective. In developing the solutions to mine field models, extensive use is made of network path planning algorithms, particularly the Weight Constrained Shortest Path Problem (WCSPP) for which the current state-of-the-art algorithm is extended. This is done by closer integration of Lagrangean relaxation and preprocessing to reduce the size of the network. This is then integrated with gap-closing algorithms based on enumeration to provide optimal or near optimal solutions to the path planning problem. We provide extensive computational evidence on the performance of our algorithm and compare it to other algorithms found in the literature. This tool then became fundamental in solving various separate minefield models. Our models can be broadly separated into obstacle models in which mine affected regions are treated as obstacles to be avoided and continuous threat in which each point of space has an associated risk. In the later case, we wish to find a path that minimizes the integral of the risk along the path while constraining the length of the path. We call this the Continuous Euclidean Length Constrained Minimum Cost Path Problem (C-LCMCPP), for which we present a novel network approach to solving this continuous problem. This approach results in being able to calculate a global lower bound on a non-convex optimization problem.

Trip planning is a well cited problem for which various solutions have been reported in the literature. This problem has been typically addressed, to a large extent, as a shortest distance path planning problem. In some scenarios, the concept of shortest path is extended to reflect temporal objectives and/or constraints. This work takes an alternative perspective to the trip planning problem in the sense it being situation aware. Thus, allowing multitudes of traveler centric objectives and constraints, as well as aspects of the environment as they pertain to the trip and the traveler. The work in this thesis introduces TSADA (Traveler Situation Awareness and Decision Aid) system. TSADA is designed as a modular system that combines linguistic situation assessment with user-centric decision-making. The trip planning problem is modeled as a graph G. The objective is to find a route with the minimum cost. Both hard and soft objective/attributes are incorporated. Soft objective/attributes such as safety, speed and driving comfortability are described using a linguistic framework and processed using hierarchical fuzzy inference engine. A user centric situation assessment is used to compute feasible routes and map them into route recommendation scheme: recommended, marginally recommended, and not recommended. In this work, we introduce traveler's doctrines concept. This concept is proposed to make the process of situation assessment user centric by being driven by the doctrine that synthesizes the user's specific demands. Hard attributes/objectives, such as the time window and trip monitory allowances, are included in the process of determining the final decision about the trip. We present the underline mathematical formulation for this system and explain the working of the proposed system to achieve optimal performance. Results are introduced to show how the system performs under a wide range of scenarios. The thesis is concluded with a discussion on findings and recommendations for future work.

Energy is a limited source in wireless sensor networks and in most applications, it is non-renewable / so designing energy-effcient communication patterns is very important. In this thesis, we de

Disasters (e.g. earthquakes) and emergencies (e.g. fire) threaten the safety of occupants in the buildings and cause injuries and mortalities. These harmful effects are even more dangerous when secondary hazards (e.g. post-earthquake fires) emerge and it is commonly observed that the disasters/emergencies trigger secondary hazards.An effective indoor emergency guidance and navigation approach for occupants and first responders can decrease the number of injuries and mortalities during building emergencies by improving the evacuation process and response operations. For this reason, this research will propose a model-based guidance and vulnerability assessment approach for facilities that are under the threat of multi-hazard emergencies. The approach can be used to guide occupants from the facility affected by disasters/emergencies to safer zones and to direct the first responders by supplying them necessary building related information such as identified vulnerable locations in the indoor environments. An integrated utilization of Building Information Modeling tools, sensors, shortest path algorithms, and vulnerability assessment algorithms is proposed for the system in this research. The research steps of this thesis include (1) determination of requirements of an indoor navigation during emergency response and disaster management,(2) review, comparison, and evaluation of shortest path algorithms from an emergency response and disaster management point of view, (3) proposing a vulnerability assessment approach, and (4) proposing a real-time indoor emergency guidance and navigation system framework for buildings under the threat of multi-hazard emergencies. The findings of the research can be used in future studies on emergency response and disaster management domains.

Trip planning is a well cited problem for which various solutions have been reported in the literature. This problem has been typically addressed, to a large extent, as a shortest distance path planning problem. In some scenarios, the concept of shortest path is extended to reflect temporal objectives and/or constraints. This work takes an alternative perspective to the trip planning problem in the sense it being situation aware. Thus, allowing multitudes of traveler centric objectives and constraints, as well as aspects of the environment as they pertain to the trip and the traveler. The work in this thesis introduces TSADA (Traveler Situation Awareness and Decision Aid) system. TSADA is designed as a modular system that combines linguistic situation assessment with user-centric decision-making. The trip planning problem is modeled as a graph G. The objective is to find a route with the minimum cost. Both hard and soft objective/attributes are incorporated. Soft objective/attributes such as safety, speed and driving comfortability are described using a linguistic framework and processed using hierarchical fuzzy inference engine. A user centric situation assessment is used to compute feasible routes and map them into route recommendation scheme: recommended, marginally recommended, and not recommended. In this work, we introduce traveler's doctrines concept. This concept is proposed to make the process of situation assessment user centric by being driven by the doctrine that synthesizes the user's specific demands. Hard attributes/objectives, such as the time window and trip monitory allowances, are included in the process of determining the final decision about the trip. We present the underline mathematical formulation for this system and explain the working of the proposed system to achieve optimal performance. Results are introduced to show how the system performs under a wide range of scenarios. The thesis is concluded with a discussion on findings and recommendations for future work.