L’objectif de cette thèse est de développer, d’intégrer et de tester une nouvelle approche algorithmique d’aide au stationnement dans les centres urbains. Considérons différents types d’infrastructures déployées allant de la détection des entrées/sorties des véhicules jusqu'à la variation dans le temps du nombre de places de stationnement disponibles dans chaque portion de rue, nous montrons qu’il est possible de proposer une méthode efficace qui détermine un itinéraire qui minimise l’espérance de temps pour trouver une place de stationnement disponible et de prédire la disponibilité des placesde stationnement.Pour cela, la zone urbaine choisie sera donc considérée comme un ensemble de ressources de stationnement (segments de rues).Nous modélisons d’abord cette zone urbaine par un graphe où les sommets désignent les carrefours et les arcs représentent les portions de rues. Les paramètres essentiels pour notre modèle de réseau urbain sont la capacité de stationnement et le temps de parcours des portions de rue.L’originalité et l’aspect innovant de notre approche s’appuient sur deux principes.Le premier principe concerne le guidage comme une ressource : il ne s’agit pas de guider vers une place libre mais de proposer un parcours qui optimise l’espérance de temps de trouver une telle place. Pour cela nous déterminons dans une zone centrée sur une destination donnée, le parcours à effectuer par un véhicule pour minimiser son espérance de temps de trouver une place destationnement le plus rapidement possible.Ainsi nous avons mis en œuvre un algorithme d’apprentissage par renforcement basée sur la méthode LRI (Linear Reward Inaction) et la méthode Monte Carlo pour minimiser l’espérance de temps de trouver une place de stationnement en zone urbaine.Nous avons comparé cet algorithme avec une approche globale basée sur l’évaluation arborescente à profondeur bornée.Le second principe repose sur la prédiction des places de stationnement disponibles par périodes de temps homogènes où on ne s’intéresse pas à une place de stationnement en temps réel mais aux places de stationnement par zones. Il s’agit alors pour le système de pouvoir prédire le potentiel de places libres dans chacune des ressources pour les prochaines périodes. On ne vise donc pas ici la prédiction de la disponibilité de chaque place ; chaque ressource sera considérée comme une zone de stockage dont la disponibilité sera établie en grande partie en fonction des flux d’entrée et de sortie de la portion. Pour ce principe, nous avons donc déterminé par algorithmes de calculs et d’apprentissages la probabilité qu’il y ait au moins une place libre pour stationner dans un tronçon de rue pour un créneau de temps donné. Les principales données nécessaires pour effectuer ces calculs sont les séries temporelles d’entrée sortie de chaque véhicule aux intersections des rues et les variations des places de stationnement au cours du temps.Nous avons évalué les performances de notre approche par simulations sur des données générées aléatoirement et des données réelles obtenues sur un quartier de Versailles. / The objective of this thesis is to develop, to integrate and to test a new algorithmic approach to help parking in urban centers.Given the different types of deployed infrastructure : from input-output detection of vehicles to time variation of the number of available places within each street segment, we propose an efficient method to determine an itinerary that minimize the time expectation to find an available place and also to predict the availability of the parking places.We have chosen an urban area and we have considered it as a set of parking resources called street segments. More exactly, this urban area is considered as a graph where the vertexes represent the crossroads and the arcs represent the street segments. The essential parameters of our urban area model are the parking capacity and the time crossing of each street segment. The originality and the innovation of our approach are based on two principles.The first one is the guidance as a resource, i.e., it means that the proposed itinerary is not the one that lead to an available parking place but rather the one that minimized the time expectation to find an available parking place. In order to achieve that we determine, in a an area centered on a given destination, the itinerary to follow by the vehicle in order minimize its time expectation to find an available parking place as quickly aspossible.We have designed and realized a reinforcement learning algorithm based on the LRI method (Linear Reward Inaction) and a Monte Carlo method to minimize the time expectation to find an available parking place in the urban area. We have compared this algorithm to a global approach based on tree evaluation with bounded depth. The second principle is based on the prediction of the parking places by homogeneous time period where we are not interestedon a parking place in real time but rather on the parking places byarea. In other terms, the system predict the potential available parkingplaces by resource for the next time periods. Thus, we don’t aim to predict the availability of each parking place, i.e., each resource is considered as stock area and its availability is assessed in major part in function of the street segment input-output flow. For this principle, we have determined by a learning algorithm the probability that there is at least one available parking place in a street segment within a given time. The major data needed to compute this probability are the time series of input-output of each vehicle in street intersections, and the variation of the available parking places through the time.We have evaluated the performance of this approach by simulation based on random generated data and on real data of a district in Versailles.

Les algorithmes probabilistes offrent de puissantes possibilités quant à la résolution de problèmes de planification de mouvements pour des robots complexes dans des environnements quelconques. Cependant, la qualité des chemins solutions obtenus est discutable. Cette thèse propose un outil pour optimiser ces chemins et en améliorer la qualité. La méthode se base sur l'optimisation numérique contrainte et la détection de collision pour réduire la longueur du chemin tout en évitant les collisions. La modularité des méthodes probabilistes nous a aussi inspirés pour réaliser un algorithme de génération de sauts pour des personnages. Cet algorithme est décrit par trois étapes de planifications, de la trajectoire du centre du personnage jusqu'à son mouvement corps-complet. Chaque étape bénéficie de la rigueur de la planification pour éviter les collisions et pour contraindre le chemin. Nous avons proposé des contraintes inspirées de la physique pour améliorer la plausibilité des mouvements, telles que du non-glissement, de la limitation de vitesse et du maintien de contacts. Les travaux de cette thèse ont été intégrés dans le logiciel "Humanoid Path Planner" et les rendus visuels effectués avec Blender. / Probabilistic algorithms offer powerful possibilities as for solving motion planning problems for complex robots in arbitrary environments. However, the quality of obtained solution paths is questionable. This thesis presents a tool to optimize these paths and improve their quality. The method is based on constrained numerical optimization and on collision checking to reduce the path length while avoiding collisions. The modularity of probabilistic methods also inspired us to design a motion generation algorithm for jumping characters. This algorithm is described by three steps of motion planning, from the trajectory of the character's center to the wholebody motion. Each step benefits from the rigor of motion planning to avoid collisions and to constraint the path. We proposed physics-inspired constraints to increase the plausibility of motions, such as slipping avoidance, velocity limitation and contact maintaining. The thesis works have been implemented in the software `Humanoid Path Planner' and the graphical renderings have been done with Blender.

Ce travail de thèse s’est intéressé au transport urbain de passagers dans un contexte d’offre de transport multimodale consistant en la coexistence de plusieurs modes de transport. Dans la pratique, un problème de transport multimodal nécessite la prise en compte de plusieurs objectifs et de contraintes spécifiques liées aux modes ou à la séquence de modes utilisés. De telles contraintes sont appelées contraintes de viabilité.Cette thèse CIFRE s’est déroulée en collaboration avec la société MobiGIS, spécialisée dans le conseil et le développement d’applications autour des Systèmes d’Information Géographiques.Le problème étudié dans cette thèse est celui de la recherche d’itinéraires viables multimodaux point à point bi-objectif pour lequel il s’agit à la fois de minimiser le temps de trajet et le nombre de changements de mode. Compte tenu notamment des objectifs considérés, ce problème est de complexité polynomiale.Sur la base d’une modélisation multi-couches des réseaux de transport multimodaux et d’une modélisation par un automate à états finis des contraintes de viabilité nous avons proposé différents algorithmes de résolution de ce problème basés sur le principe de fixation et extension de labels. Nous avons également proposé une règle de dominance basée sur les états de l’automate de viabilité et permettant d’élaguer le nombre de labels explorés par nos algorithmes. Des adaptations en bidirectionnel ou en utilisant le principe de la recherche A_ ont également été proposées.Les algorithmes proposés ont été évalués sur une partie du réseau de transport de la ville de Toulouse et les expérimentations ont mis en évidence l’intérêt de la règle de dominance basée sur les états ainsi que de l’approche bidirectionnelle développée.Un prototype logiciel implémentant différentes fonctionnalités des algorithmes de plus courts chemins a été développé. Il permet notamment de réaliser des calculs d’itinéraires point à point, des calculs d’accessibilité ou des calculs de distancier / This thesis focuses on urban passenger multimodal transportation. In practice, a multimodal transportation problem requires taking into account several objectives and specific constraints related to modes or sequence of used modes. Such constraints are called viability constraints. This work has been carried out in collaboration with MobiGIS, a company specialized in consulting and development of applications around Geographical Information Systems.The problem studied in this thesis is the bi-objective multimodal viable point-to-point shortest path, aiming at minimizing the total travel time and the total number of mode changes. Given the considered objectives, this problem is polynomial.On the basis of a multi-layered graph model of the multimodal transportation networks, and of a finite state automaton model of the viability constraints, we propose various algorithms for solving this problem, based on the principle of label setting and extension.We also proposed a new dominance rule based on the states of the automaton to reduce the number of labels explored by our algorithms. Bidirectional and A* variants are also proposed.The algorithms are evaluated the transportation network of the city of Toulouse and experiments demonstrate the interest of the proposed dominance rules and bidirectional approach. A prototype software implementing different features of the shortest path algorithms has been developed. It notably enables calculations of point-to-point routes, accessibility and origin-destination matrices

Québec Université Laval, Bibliothèque 2013

Ce travail a pour objet la résolution d'un problème combinatoire posé dans le cadre de la régulation court terme (ou dynamique) du trafic aérien. On cherche à déterminer pour chaque vol régulable une trajectoire en 4 dimensions réalisable de manière à respecter les contraintes de capacité des secteurs tout en minimisant la somme des coûts des trajectoires choisies. Le problème est modélisé par un programme linéaire mixte. Une représentation ad hoc du système aérien sert de support à la modélisation fine des trajectoires. Un processus global de résolution basé sur la génération de colonnes couplée à la technique de branch-and-bound est détaillé. Les colonnes du problème représentant des trajectoires, la génération de colonnes par le sous problème de tarification se traduit par la recherche de chemins tridimensionnels sur un réseau continu et dynamique. Un algorithme spécifique basé sur les algorithmes de plus court chemin par marquage et sur la programmation dynamique est développé et testé. Toute la méthode est évaluée sur des instances réelles représentant l'espace aérien géré par la CFMU, l'organisme européen de gestion des flux de trafic aérien. Les résultats obtenus en un temps de calcul compatible avec le contexte opérationnel valident finalement la méthode

L'étude du domaine récent que constituent les problèmes d'optimisation combinatoires probabilistes (POCPs) forme le sujet de cette thèse. Les POCPs sont des généralisations des problèmes d'optimisation combinatoires classiques dont les formulations contiennent explicitement des éléments probabilistes. Plusieurs motivations ont provoqué cette étude. Deux d'entre elles sont particulièrement importantes. La première correspond au désir de formuler et d'analyser des modèles qui sont plus appropriés pour des problèmes pratiques pour lesquels l'aléatoire est une source constante de préoccupations, les modèles de nature probabiliste sont plus particulièrement attractifs comme abstraction mathématique des systèmes réels. La seconde motivation est d'analyser la stabilité des solutions optimales des problèmes déterministes lorsque les exemplaires sont perturbés : les perturbations sont simulées par la présence ou l'absence de sous-ensembles des données. Notre étude s'appuie sur certains de ces problèmes et en particulier : problème du voyageur de commerce; problème d'ordonnancement des travaux probabiliste et le problème du bin-packing probabiliste. Les questions soulevées et les résultats obtenus sont dans les domaines suivants : complexités des problèmes et analyse d'heuristiques pour les POCPs ; analyse du comportement asymptotique des problèmes lorsque les exemplaires correspondent à des problèmes de grandes tailles ; dégager une méthodologie générale d'étude de la stabilité des solutions des problèmes d'optimisation combinatoires classiques.

Cette thèse porte sur les relations entre la limite supérieure de la zone sismogène et la construction et la structuration du prisme de Nankai, au Sud-Est du Japon. La détermination des contraintes dans le prisme à partir des données d’ovalisation de puits montrent une permutation des contraintes au dessus d’un hors séquence, appelé splay fault, situé à la limite de la zone sismogène. Le régime de contrainte est extensif dans cette zone et décrochant dans le reste du prisme. L’étude de la compaction des sédiments à partir des données de porosité corrigée de l’effet des argiles permet de quantifier l’érosion récente des sédiments de pentes, et montre l’existence d’une érosion plus ancienne au dessus des chevauchements majeurs. L’étude des styles de déformations des sédiments montre que l’érosion peut rendre compte de la répartition des structures de déformation dans le prisme. Enfin, la modélisation mécanique de la marge montre que l’activité de la splay fault, très faible depuis le dernier million d’années, et la présence d’une zone d’extension en arrière de cette faille s’expliquent par l’arrêt de l’accrétion et un décollement faible dans le prisme frontal. / This study is focused on the upper limit of the seismogenic zone in the Kumano transect of the Nankai margin in relation with the construction of the wedge. The first step was to determine the stress orientations and amplitude within the wedge from borehole breakouts analysis. We show the striking presence of a trench normal extension zone behind the splay fault in a wedge dominated by a strike-slip stress regime. Locally an extensional stress regime is also observed in the slope sediment of the outer part of the wedge. In a second part of this work, we used porosity corrected from water bound to clay minerals to study the compaction state of the sediments and to quantify the amount of erosion in the slope sediments. Results also highlight the existence of past erosion related to the activity of the splay fault. In a third part, the observation of deformation style within sediments showed that erosion could explain the distribution of dilatant and compactive structures within the wedge. Finally, we show, based on mechanical modeling, that the splay fault slow slip rate over the last million year, and the presence of an extension zone landward of the splay fault, could both be explained by a pause in the accretion and a weak décollement beneath the outer wedge.

La présente thèse est consacrée à l’étude de la probabilité du chemin d’un mouvement aléatoire sur la base d’une extension de la mécanique Hamiltonienne/Lagrangienne à la dynamique stochastique. La probabilité d’un chemin est d’abord étudiée par simulation numérique dans le cas du mouvement stochastique Gaussien des systèmes non dissipatifs. Ce modèle dynamique idéal implique que, outre les forces aléatoires Gaussiennes, le système est seulement soumis à des forces conservatrices. Ce modèle peut être appliqué à un mouvement aléatoire réel de régime pseudo-périodique en présence d’une force de frottement lorsque l’énergie dissipée est négligeable par rapport à la variation de l’énergie potentielle. Nous constatons que la probabilité de chemin décroît exponentiellement lorsque le son action augmente, c’est à dire, P(A) ~ eˉγA, où γ est une constante caractérisant la sensibilité de la dépendance de l’action à la probabilité de chemin, l’action est calculée par la formule A = ∫T0 Ldt, intégrale temporelle du Lagrangien. L = K–V sur une période de temps fixe T, K est l’énergie cinétique et V est l’énergie potentielle. Ce résultat est une confirmation de l’existence d’un analogue classique du facteur de Feynman eiA/ħ pour le formalisme intégral de chemin de la mécanique quantique des systèmes Hamiltoniens. Le résultat ci-dessus est ensuite étendu au mouvement aléatoire réel avec dissipation. A cet effet, le principe de moindre action doit être généralisé au mouvement amorti de systèmes mécaniques ayant une fonction unique de Lagrange bien définie qui doit avoir la simple connexion habituelle au Hamiltonien. Cela a été fait avec l’aide du Lagrangien suivant L = K − V − Ed, où Ed est l’énergie dissipée. Par le calcul variationnel et la simulation numérique, nous avons prouvé que l’action A = ∫T0 Ldt est stationnaire pour les chemins optimaux déterminés par l’équation newtonienne. Plus précisément, la stationnarité est un minimum pour les mouvements de régime pseudo-périodique, un maximum pour les mouvements d’amortissement apériodique et une inflexion dans le cas intermédiaire. Sur cette base, nous avons étudié la probabilité du chemin du mouvement stochastique Gaussien des systèmes dissipatifs. On constate que la probabilité du chemin dépend toujours de façon exponentielle de l’action Lagrangien pour les mouvements de régime pseudo-périodique, mais dépend toujours de façon exponentielle de l’action cinétique A = ∫T0 Kdt pour régime apériodique. / The present thesis is devoted to the study of path probability of random motion on the basis of an extension of Hamiltonian/Lagrangian mechanics to stochastic dynamics. The path probability is first investigated by numerical simulation for Gaussian stochastic motion of non dissipative systems. This ideal dynamical model implies that, apart from the Gaussian random forces, the system is only subject to conservative forces. This model can be applied to underdamped real random motion in the presence of friction force when the dissipated energy is negligible with respect to the variation of the potential energy. We find that the path probability decreases exponentially with increasing action, i.e., P(A) ~ eˉγA, where γ is a constant characterizing the sensitivity of the action dependence of the path probability, the action is given by A = ∫T0 Ldt, a time integral of the Lagrangian L = K–V over a fixed time period T, K is the kinetic energy and V is the potential energy. This result is a confirmation of the existence of a classical analogue of the Feynman factor eiA/ħ for the path integral formalism of quantum mechanics of Hamiltonian systems. The above result is then extended to real random motion with dissipation. For this purpose, the least action principle has to be generalized to damped motion of mechanical systems with a unique well defined Lagrangian function which must have the usual simple connection to Hamiltonian. This has been done with the help of the following Lagrangian L = K – V – Ed, where Ed is the dissipated energy. By variational calculus and numerical simulation, we proved that the action A = ∫T0 Ldt is stationary for the optimal paths determined by Newtonian equation. More precisely, the stationarity is a minimum for underdamped motion, a maximum for overdamped motion and an inflexion for the intermediate case. On this basis, we studied the path probability of Gaussian stochastic motion of dissipative systems. It is found that the path probability still depends exponentially on Lagrangian action for the underdamped motion, but depends exponentially on kinetic action A = ∫T0 Kdt for the overdamped motion.

A travers cette thèse nous apportons un éclairage sociologique au débat engagé depuis des décennies sur la problématique de la mise en vente des bois publics. A ce titre, nous étudions, dans la première partie de la thèse, le système d’enchères qui reste encore le principal mode de vente utilisé par l’Office National des Forêts. Nous identifions les conditions d’encastrement de ces ventes, considérant que les comportements des participants sont déterminés par l’interaction complexe de facteurs économiques, socio-structuraux, politiques, cognitifs, institutionnels formels et informels. Nous montrons à cette occasion que l’intérêt accordé à l’enchère réside dans sa capacité à trouver collectivement un consensus sur la valeur et l’allocation des lots de bois. Dans la deuxième partie de la thèse, nous analysons l’évolution récente du cadre institutionnel appliqué aux ventes de bois publics en nous appuyant sur les notions de construction sociale des institutions et de dépendance au chemin. Nous y démontrons que, malgré le verrouillage institutionnel organisé autour de l’enchère pendant plusieurs siècles, le développement des contrats d’approvisionnement, à la suite des tempêtes de 1999 et de l’action concertée d’une partie de la filière bois, marque l’émergence d’un embranchement institutionnel en matière de vente de bois publics. La présentation des facteurs économiques et non économiques mis en avant par les partisans de chacun des deux modes de vente nous amène à conclure que la double trajectoire institutionnelle (enchères/contrats d’approvisionnement) devrait dans l’avenir permettre de répondre aux différentes problématiques d’approvisionnement propres à la filière bois. / This thesis gives a sociological perspective on a debate that started more than thirty years ago, concerning the choice of methods for selling public timber. For this reason, the first part of the thesis focuses on the study of the auction system − the main selling method still used by the French National Forest Service. We have identified the conditions of the embeddedness of auctions, considering that during the exchanges actors are influenced by the complex interaction of economic, socio-structural, politic, cognitive, formal and informal institutional factors. We have shown that the point in using auctions has to do with its capacity to collectively find a consensus about the value and the distribution of timber lots. In the second part of the thesis, we have analyzed the recent evolution of the institutional framework applied to the public timber sales by leaning on the concepts of “the social construction of institutions” and “path dependence”. We have demonstrated that, despite the institutional lock-in that has been organized around the auction (since) for many centuries, the raise of supply contracts − due to the storms of 1999 and the planned action of a part of the timber industry − has indicated the outbreak of an institutional junction regarding the selling methods of public timber. After the presentation of the economic and non-economic factors underlined by the supporters of both selling methods we have concluded that in the future the double trajectory (auction/supply contracts) should be kept, since it should make it easier to find solutions to the various supply-related problems of the timber industry.

Le contexte écologique et économique actuel incite les autorités et le public à la réduction des émissions de CO2 et les dépendances vis-à-vis des hydrocarbures. Le transport représente 23 % des émissions de polluants dans le monde, et ce chiffre passe à 39 % pour la France. L’adoption de nouvelles solutions de transport est primordiale pour la réduction de ces émissions. L’électromobilité représente une alternative viable aux véhicules thermiques conventionnels. Si les véhicules électriques permettent une mobilité avec zéro émission, certaines de leurs caractéristiques empêchent leur développement. Les principaux freins à l’adoption de ce type de véhicules sont l’autonomie limitée, le faible déploiement des stations de recharge en milieu urbain (et extra urbain) ainsi que les temps de recharge importants. Aussi, afin de promouvoir l’usage de ce type de mobilité, il incombe de développer des outils visant à optimiser la consommation électrique tenant compte des caractéristiques liées à ce type de mobilité. C’est l’objectif de ce travail de thèse qui se focalise sur le développement d’outils permettant d’optimiser l’usage de véhicules électriques. Pour ce faire, trois grands axes sont définis : la modélisation des véhicules électriques, l’affectation des stations de recharge et le choix d’éco-itinéraires. La première partie de cette thèse s’intéresse à l’estimation de la consommation des véhicules électriques ainsi qu’à la présentation de la librairie de modèles dynamiques VEHLIB d’estimation de la consommation de ce type de véhicules. La seconde partie est consacrée à l’affectation optimale des stations de recharge. Une méthodologie de déploiement d’infrastructures de recharge est proposée pour la ville de Lyon avec prise en compte de la demande de mobilité issue des enquêtes ménages déplacements. La troisième partie de la thèse s’intéresse à la thématique du choix d’éco-itinéraire (green routing). Celle-ci aboutit à la proposition d’une méthodologie multi-objectif de recherche de stations de recharge afin de déterminer des itinéraires optimaux avec déviation vers ces stations lorsque l’état de charge de la batterie du véhicule ne permet pas de terminer le trajet. Pour finir, une expérimentation a été réalisée à l’aide d’un véhicule électrique équipé de capteurs de position et de consommation pour d’une part valider les méthodologies proposées et d’autre part analyser les facteurs exogènes qui influent sur la consommation des véhicules électriques. / The current ecological and economic context encourages the authorities and the public to reduce CO2 emissions and oil dependence. The transportation is responsible for 23% of pollutants emissions in the world, and this proportion increases up to 37% in France/ The adoption of new transport solutions is primordial to reduce these emissions. Electro mobility is a viable alternative to conventional vehicles. While electric vehicles offer mobility with zero emissions, some of their characteristicds impede their development. The main obtacle to the adoption of these vehicles is the limited autonomy, a sparse distribution of charging stations in urban areas as well as a significant charging time. Also, to promote the use of this type of mobility, it is primordial to develop tools that optimize the energy consumption and take in to account the characteristics associated with this type of mobility. To achieve this, three areas are difined: modeling of electric vehicles, optimized charging station deployment and eco routing. The first part of this theis focuses on the consumption estimation of the electric vehicles and the presentation of the dynamic model library VEHLIB. The second part is dedicated to optimal allocation of charging stations; A methodology for the deployment of electric vehicle charging infrastructures is proposed for the urban area o fthe city of Lyon, taking into account the mobility demand derived from the household travel surveys.The third part of the thesis deals with the eco-routing (green routing). A multi-objective methodology for eco routing with recharge en-route is proposed. The solutions take into account battery state does not permit to finish the trip.Finally, an experiment was carried out using an electric vehicle equipped with position and consumption sensors in order to validate the proposed methodologies and analyze exogenous factor that impact the electric vehicle consumption.