Les travaux présentés dans cette thèse visent à proposer des méthodes de calcul d’itinéraires adaptés aux cyclistes à l’échelle d’une agglomération. Plusieurs critères sont considérés, comme la distance, la sécurité et l’effort. La difficulté est de calculer des chemins de compromis sous une contrainte de temps de quelques secondes pour pouvoir intégrer ce calculateur à un site web. Deux approches ont été abordées pour résoudre ce problème. L’approche a posteriori dans laquelle l’ensemble des solutions de compromis est calculé et l’approche a priori dans laquelle les préférences de l’utilisateur sont prises en compte et permettent d’orienter la recherche pour privilégier les chemins les plus prometteurs. Enfin, nous proposons de modéliser le réseau routier sous la forme d’un graphe adjoint pour pouvoir prendre en compte de nouveaux critères nécessitant, par exemple, des coûts sur les enchaînements d’arcs. L’ensemble de ce travail a permis de développer le service Géovélo qui est un calculateur d’itinéraires multiobjectif adaptés au vélo. Le service est disponible sous la forme d’un site web et d’applications mobiles. / The work presented in this thesis aims at proposing methods for computing bicycle paths across a metropolitan. Several criteria such as distance, safety and effort must be considered in the path computation. The difficulty is to compute paths under a time constraint of a few seconds, in order to integrate the computation in the respond-time of a web page.Two approaches were discussed to solve this problem. The first one is an a posteriori approach where all compromise solutions are computed and the second approach is an a priori method that takes user preferences into account to guide the search by the selection of the most promising sub-paths first. Finally, we propose to model the road network as a line graph to take into account new criteria,requiring costs on arc sequences for example. All this work was necessary to develop the service Géovélo, which is a multiobjective route planner adapted to bicycle. The service is available on a website and as mobile applications.

Les travaux présentés dans cette thèse visent à proposer des méthodes de calcul d'itinéraires adaptés aux cyclistes à l'échelle d'une agglomération. Plusieurs critères sont considérés, comme la distance, la sécurité et l'effort. La difficulté est de calculer des chemins de compromis sous une contrainte de temps de quelques secondes pour pouvoir intégrer ce calculateur à un site web. Deux approches ont été abordées pour résoudre ce problème. L'approche a posteriori dans laquelle l'ensemble des solutions de compromis est calculé et l'approche a priori dans laquelle les préférences de l'utilisateur sont prises en compte et permettent d'orienter la recherche pour privilégier les chemins les plus prometteurs. Enfin, nous proposons de modéliser le réseau routier sous la forme d'un graphe adjoint pour pouvoir prendre en compte de nouveaux critères nécessitant, par exemple, des coûts sur les enchaînements d'arcs. L'ensemble de ce travail a permis de développer le service Géovélo qui est un calculateur d'itinéraires multiobjectif adaptés au vélo. Le service est disponible sous la forme d'un site web et d'applications mobiles.

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.

L'objectif de cette thèse est le développement d'algorithmes et de modèles permettant l'optimisation d'itinéraires dans les réseaux routiers. Dans un premier temps, ce travail de recherche étudie le problème de l'interception d'un mobile dans un graphe. Dans ce contexte, l'objectif est de calculer un itinéraire optimal permettant de rejoindre une cible mobile dont la trajectoire est connue. Cette problématique est traitée pour plusieurs situations (un poursuivant/un objectif et plusieurs poursuivants/plusieurs objectifs) et pour plusieurs types de graphes (graphes statiques et graphes FIFO). Pour chaque cas, un algorithme de résolution est proposé et l'optimalité du résultat qu'il retourne est démontrée. De plus, un ensemble de simulations est réalisé afin de vérifier l'efficacité des algorithmes en termes de temps de calcul. Dans un deuxième temps, une nouvelle classe de graphes dynamiques est définie : les graphes dynamiques avec intervalles. La particularité de ces graphes est que le poids de chaque arc dépende du temps et qu'il est représenté par un intervalle. Pour ce nouveau type de graphes, le problème du plus court chemin est étudié. Ce problème peut être vu soit en tant que problème d'optimisation monocritère soit en tant que problème d'optimisation multicritère. Pour chaque cas, le problème est formulé et des approches pour la résolution sont proposées.

Cette thèse porte sur le problème de l'estimation des temps de parcours, de véhicules, par section de route dans un contexte urbain, en utilisant les données GPS à faible densité d’échantillon. L'un des défis de cette thèse est d'utiliser ce genre de données. Dans le cadre de ce travail de recherche, j'ai développé une carte numérique avec son nouveau système d'information géographique (SIG), qui traite la problématique du map-matching, où nous avons apporté des améliorations, ainsi que le problème du plus court chemin.La thèse s'inscrit dans le cadre du projet PUMAS (Plate-forme Urbaine de Mobilité Avancée et Soutenable), ce qui est un avantage pour nos recherches en ce qui concerne le processus de collecte de données réelles sur le terrain ainsi que pour faire nos tests. Le projet PUMAS est un projet préindustriel qui a pour objectif d'informer sur la situation du trafic mais également de développer et de mettre en œuvre une plate-forme de mobilité durable afin de l'évaluer dans la région, notamment à Rouen, France. Le résultat offre un cadre pour tout contrôleur de la situation, gestionnaire ou chercheur pour accéder à de vastes réserves de données sur l'estimation du flux du trafic, sur les prévisions et sur l'état du trafic. / This dissertation is concerned with the problem of estimating travel time per links in urban context using sparsely sampled GPS data. One of the challenges in this thesis is use the sparsely sampled data. A part of this research work, i developed a digital map with its new geographic information system (GIS), dealing with map-matching problem, where we come out with an enhancement tecnique, and also the shortest path problem.The thesis research work was conduct within the project PUMAS, which is an avantage for our research regarding the collection process of our data from the real world field and also in making our tests. The project PUMAS (Plate-forme Urbaine de Mobilité Avancée et Soutenable / Urban Platform for Sustainable and Advanced Mobility) is a preindustrial project that has the objective to inform about the traffic situation and also to develop an implement a platform for sustainable mobility in order to evaluate it in the region, specifically Rouen, France. The result is a framework for any traffic controller or manager and also estimation researcher to access vast stores of data about the traffic estimation, forecasting and status.

Les travaux présentés dans cette thèse, qui s’inscrivent dans le cadre du projet franco-allemand DSS_Evac_Logistic, visent à proposer des méthodes permettant de calculer des plans d’évacuation macroscopiques d’une ville lors d’une catastrophe majeure. Deux problèmes d’évacuations sont considérés dans cette thèse : le problème d’évacuation par bus et le problème d’évacuation par bus et voitures. Le problème d’évacuation par bus a pour objectif de définir un plan d’évacuation afin de mettre à l’abri les évacués. Dans cette thèse, nous nous sommes intéressés à l’étude de trois versions du problème d’évacuation par bus. La première version est monocritère où nous cherchons à minimiser la date de fin d’évacuation. Puis, dans le second problème et afin d’assurer la sécurité des évacués, nous avons considéré une version bicritère qui généralise le cas monocritère, en incluant le risque encouru lors de l’évacuation des personnes. Les deux critères à minimiser sont la date de fin d’évacuation et le risque. La troisième version est une version robuste bicritère qui permet d’appréhender l’incertitude sur les données. Le but est de minimiser à la fois la date de fin d’évacuation et les modifications apportées sur une solution, de sorte qu’elle soit réalisable pour n’importe quel scénario de données. Pour résoudre ces problèmes d’évacuation par bus, nous avons proposé des méthodes exactes et des méthodes heuristiques. / The work presented in this thesis, which is a part of the Franco-German project DSS_Evac_Logistic, aims at proposing methods to calculate macroscopic evacuation plans for mid-size towns after a tremendous disaster. Two evacuation problems have been tackled in this thesis : the bus evacuation problem and bus-and-vehicle evacuation problem. The bus evacuation problem aims at calculating an evacuation plan to relocate evacuees outside the endangered area. In this thesis, we consider three versions of the bus evacuation problem. The first one is a monocriterion problem, where the objective is to minimize the maximum evacuation time. In order to guarantee the safety of evacuees, we have considered a bicriteria problem, which is a generalization of the monocriterion version, in which we take into consideration the risk exposure of the evacuees. Consequently, the bicriteria problem is solved by minimizing the total evacuation time and the risk. The third version is a bicriteria robust version because most of the planning data is subject to uncertainty. The goal is to minimize both the evacuation time and the vulnerability of the schedule that is subject to different evacuation circumstances. To solve all the versions of the bus evacuation problem, we have developed exact solutions based on mathematical formulation to address small instances and heuristic solutions to deal with larger instances.

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières. / In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs.