Les travaux présentés dans cette thèse visent à proposer des méthodes permettant de résoudre un problème de Transport à la Demande multicritère. Le premier travail réalisé dans cette thèse est l'étude d'un problème de Dial-a-Ride (DARP) statique multicritère. Trois critères qui peuvent être conflictuels ont été définis : le premier consiste à minimiser le coût de transport, le deuxième critère consiste à minimiser l'insatisfaction des passagers et enfin le troisième critère consiste à minimiser la quantité de CO2 émise par l'ensemble des véhicules. Nous avons développé une méthode évolutionnaire NSGA-II pour chercher un ensemble approximatif d'optimas de Pareto. Le second travail réalisé est l'étude d'un problème d'Optimal Timing dans une tournée. Ce problème consiste à calculer les dates de début de service optimales des points d'arrêts d'une tournée afin de minimiser l'insatisfaction des passagers. Le dernier travail de cette thèse a porté sur l'étude d'un problème de Transport à la Demande dynamique dans lequel de nouvelles requêtes à traiter arrivent en cours de journée. Deux méthodes ont été proposées pour résoudre ce problème : la première est une heuristique d'insertion rapide et la seconde est une méthode arborescente tronquée connue sous le nom de Recovering Beam Search. / The work presented in this thesis aims to propose methods to solve a multicriteria dial-a-ride problem (DARP). Three objective functions that have to be optimized in order to measure the potential efficiency of the DARP solution on different aspects : the cost for the transportation operator, the quality of service for users and the impact on the environment. The first work in this thesis is the study of static DARP for which a NSGA-II algorithm is developped to identify a good approximation of the Pareto optimal set. The second work deals with an optimal timing algorithm which computes pickup and delivery dates when the requests are sequenced on the vehicles, the objective is to minimize the total customer' dissatisfaction. The last problem studied in this thesis aims to solve the dynamic version of DARP for which two methods are proposed. The first one is a fast insertion heuristic based on an attractive index. However, the second methode uses a recovering beam search heuristic which unlike the insertion heuristic allows to modify the structure of the routes previously scheduled in order to schedule the new requests.

Organiser le secteur du transport pour offrir des solutions de déplacement efficaces est aujourd'hui un enjeu capital pour nos sociétés. La flexibilité, tendant à augmenter la qualité de service, constitue un des leviers pour améliorer les transports. Diverses formes de flexibilité apparaissent en effet dans l'offre actuelle. Dans cette thèse, nous appréhendons plus particulièrement des services opérant dans deux contextes sociétaux distincts :• d'une part, dans un pays industrialisé (la France) où le recours aux transports publics reste minoritaire car la dépendance à l'automobile est toujours très forte ;• d'autre part, dans un pays en voie de développement (le Sénégal) possédant des moyens financiers limités, mais où l'usage des transports collectifs est généralisé, impliquant une grande diversité des modes et une atomisation de l'offre.Nous proposons ainsi d'analyser et de comparer le fonctionnement des transports informels et artisanaux sénégalais (tels que les taxis collectifs) avec celui des systèmes considérés comme plus modernes en France, pour lesquels les capacités d'auto-organisation des individus ont été progressivement remplacées par des systèmes d’information et de communication de haut niveau technologique et logistique. Ces innovations semblent apporter plus d'immédiateté au transport flexible, mais nécessitent en contrepartie un encadrement fort de la part des autorités publiques générant des contraintes réglementaires et spatiales. À l'opposé, les services spontanés et dérégulés qui sont proposés au Sénégal bénéficient d'une plus grande souplesse, au détriment de la sécurité des passagers.L'objectif de la thèse est d'analyser ces services, les modéliser et les simuler afin d'évaluer les apports de la flexibilité. D'un point de vue méthodologique, notre recherche est basée sur un ensemble de modèles inspirés des transports observés en France et au Sénégal, puis implémentés en Systèmes Multi-Agents (SMA) dans l'environnement Netlogo. Certains modèles sont issus d'une analyse fonctionnelle de terrain et d'autres sont plus théoriques. Par l'analyse du comportement d'agents réalisant ces services en concurrence et/ou en coopération, nous identifions d'abord des seuils et des conditions de mise en œuvre en termes d'efficacité et de couverture spatiale. En simulant les modèles sur plusieurs configurations spatiales, nous explorons ensuite leur fonctionnement et nous analysons les atouts et les faiblesse de chacun. Nous les simulons ensuite simultanément pour évaluer leur capacité de complémentarité. Cela nous permet in fine de confronter des systèmes de transports analogues à ceux observés dans les deux contextes sociétaux et d'établir une grille de comparaison en fonction des niveaux de flexibilité identifiés.. / Organizing and developing efficient urban transportation services is a key issues for actual society. The flexibility appear as an important criteria to improve the services quality and to offer attractive transportation solutions. Different forms and levels of flexibility exist in the actual supply-side. For this research we focus on flexible transports operating in two society contexts:• in an industrial country (France) where the using rate of public transportation services islow because the automobile dependency is still high;• in a developing country (Senegal), where the financial resources are limited and theutilisation of public transports is generalized, leading to a diversity of services and anatomic supply-side. More precisely, we compare the functioning of senegalese para-transit services (as collectivetaxis) with french technological systems (as Demand Responsive Transport (DRT)). In France, auto-organization skills and collective behaviours have been replaced by the utilisation of highlevel information, communication and logistic systems. These innovations bring more immediacy and spontaneity in public transports, but it needs a strong supervision from authorities, causes regulatory ans spatial constraints of servicing. In contrast, in Senegal deregulated services benefit to more spontaneity and suppleness to the detriment of the passengers security.The objective of the thesis is to analyse, model and simulate these services to evaluate thecontributions of the flexibility. Regarding the methodology, our study is based on a group ofmodels inspired by transportation systems observed in France and Senegal and implemented inMulti-Agent Systems (MAS), in the NetLogo environnement. Some models are derived from a functional analysis and others are more theoretical. By analysing behaviours of agents performing these services in concurrency or incooperation, we highlight some thresholds and optimal conditions of coverage. Simulations invarious spatial configurations allow to explore model functioning and to analyse their strengthsand limitations. Then, we simulate models in parallel (two models by simulation) to evaluate their complementarity. We compare these combined models, all of them representing transportation services observed in two different contexts. Finally, we build a comparison matrix of clues according to the model performance and flexibility levels. To conclude, this research leads to a valuable reflection on how could be designed flexible transport services in the future.

Cette thèse pluridisciplinaire, géographique et informatique (géomatique), s'intéresse à la problématique du transport à la demande (TAD). Le TAD est un transport de personnes collectif terrestre activé seulement à la demande se situant à mi-chemin entre le taxi et le bus. L'idée porteuse de cette recherche est d'utiliser la structure polarisée des territoires pour faciliter une optimisation informatique d'un TAD en (multi)convergence, recourant, par exemple, aux Arbres Couvrants et au modèle gravitaire . Cette approche se traduit notamment par une rationalisation des coûts économiques du service (regroupement des clients, nombre de véhicules nécessaires, temps de parcours...). Par ailleurs, cette thèse donne des éléments méthodologiques pour déployer un TAD usant d'une part d'algorithmes à métaheuristiques (les algorithmes génétiques, i.e. NSGA-II) et d'autre part de modèles géographiques (la forme dite en convergence se basant sur le caractère polarisé du territoire). Des simulations permettent d'évaluer la capacité des méthodes développées à fournir de bonnes solutions dans un contexte opérationnel de forte montée en charge potentielle.<br /><br />Reposant sur le principe de convergence des flux, la méthode exploite la théorie des graphes pour définir les tournées des véhicules, elles-mêmes optimisées selon un algorithme génétique dédié, reposant sur une approche multicritères avec front de Pareto.<br /><br />La dernière partie de la thèse s'intéresse à l'influence du choix des métriques d'optimisation sur les solutions obtenues, compte tenu d'un territoire et d'une granularité spatiale donnés. Elle ouvre sur le questionnement suivant : quelle configuration d'optimisation pour quel territoire et pour quel usage ?

Organiser le secteur du transport pour offrir des solutions de déplacement efficaces est aujourd'hui un enjeu capital pour nos sociétés. La flexibilité, tendant à augmenter la qualité de service, constitue un des leviers pour améliorer les transports. Diverses formes de flexibilité apparaissent en effet dans l'offre actuelle. Dans cette thèse, nous appréhendons plus particulièrement des services opérant dans deux contextes sociétaux distincts :* d'une part, dans un pays industrialisé (la France) où le recours aux transports publics reste minoritaire car la dépendance à l'automobile est toujours très forte ;* d'autre part, dans un pays en voie de développement (le Sénégal) possédant des moyens financiers limités, mais où l'usage des transports collectifs est généralisé, impliquant une grande diversité des modes et une atomisation de l'offre.Nous proposons ainsi d'analyser et de comparer le fonctionnement des transports informels et artisanaux sénégalais (tels que les taxis collectifs) avec celui des systèmes considérés comme plus modernes en France, pour lesquels les capacités d'auto-organisation des individus ont été progressivement remplacées par des systèmes d'information et de communication de haut niveau technologique et logistique. Ces innovations semblent apporter plus d'immédiateté au transport flexible, mais nécessitent en contrepartie un encadrement fort de la part des autorités publiques générant des contraintes réglementaires et spatiales. À l'opposé, les services spontanés et dérégulés qui sont proposés au Sénégal bénéficient d'une plus grande souplesse, au détriment de la sécurité des passagers.L'objectif de la thèse est d'analyser ces services, les modéliser et les simuler afin d'évaluer les apports de la flexibilité. D'un point de vue méthodologique, notre recherche est basée sur un ensemble de modèles inspirés des transports observés en France et au Sénégal, puis implémentés en Systèmes Multi-Agents (SMA) dans l'environnement Netlogo. Certains modèles sont issus d'une analyse fonctionnelle de terrain et d'autres sont plus théoriques. Par l'analyse du comportement d'agents réalisant ces services en concurrence et/ou en coopération, nous identifions d'abord des seuils et des conditions de mise en œuvre en termes d'efficacité et de couverture spatiale. En simulant les modèles sur plusieurs configurations spatiales, nous explorons ensuite leur fonctionnement et nous analysons les atouts et les faiblesse de chacun. Nous les simulons ensuite simultanément pour évaluer leur capacité de complémentarité. Cela nous permet in fine de confronter des systèmes de transports analogues à ceux observés dans les deux contextes sociétaux et d'établir une grille de comparaison en fonction des niveaux de flexibilité identifiés..

Le Transport A la Demande (TAD) est un système de transport qui propose un usage collectif des véhicules automobiles, par opposition à l’usage des véhicules personnels (VP). Situé entre le fonctionnement des taxis et celui des transports en commun classiques, il propose un service à la fois flexible dans le temps et dans l'espace à la manière des taxis, favorisant le partage des véhicules, comme les transports en commun. Il est ainsi présenté comme une réponse pour une mobilité durable. Dans les esprits, les TAD sont souvent associés à une réduction des émissions de polluants et sont mis en place principalement dans des territoires ruraux. Pourtant, le simple regroupement effectué par les TAD suffit-il pour que la mise en place des TAD soit profitable à l’environnement ? Dans ce travail de recherche de doctorat, un outil d’évaluation de l'impact environnemental d’un système de Transports À la Demande (TAD) destiné aux collectivités territoriales a été mis au point. Pour que choix soit durable, au sens du développement durable, le service doit être le plus adapté au contexte local en minimisant les émissions de substances dans l’atmosphère proche tout en conservant une qualité de service suffisante pour concurrencer l'usage du véhicule personnel. Un paramètre, directement impliqué dans les émissions de polluant, est souvent négligé dans les approches : le réseau routier. On cherche donc à identifier des lois et des seuils relatifs aux émissions de polluants produites par le fonctionnement d’un TAD : dans quelle mesure le réseau routier influe-t-il sur les performances environnementales des TAD ou sur la capacité de regroupement des clients dans les véhicules ? Selon quelles caractéristiques de service (fenêtres de temps autorisées) ? Plus globalement, est-ce que l’optimisation d’un même type de TAD est équivalente d’un réseau routier à un autre, du point de vue des émissions de polluants ? Aucun outil intégré permettant d’effectuer cette tâche n’étant disponible, nous avons mis au point une chaîne de traitement géomatique permettant d’estimer les quantités de polluants émises sur les tronçons de route dans le cadre du fonctionnement particulier des TAD et de les cartographier pour analyser leur répartition spatiale. Cet outil associe un SIG à un modèle d’émission que nous avons adapté à notre problématique (GREEN-DRT). Il est ressorti des différents scénarios simulés que les TAD ne sont pas systématiquement une solution pertinente dans un objectif de réduction globale des émissions de polluants sur un territoire donné. Le constat de la faible pertinence environnementale de ce mode de transport sur les territoires les moins denses (type zones rurales) a été fait, pourtant, ce sont sur ces territoires que les TAD sont développés en France. À défaut d’engendrer une réduction des émissions, ils ont souvent un rôle social important en se positionnant non pas comme une alternative à la voiture personnelle, mais en permettant à des populations captives de se déplacer. Il s’agit de ce cas de minimiser les émissions de polluants provoquées par le fonctionnement du service. / The Demand Responsive Transport (DRT) is a transportation system which offers a collective use of motor vehicles, in opposite of personal vehicles use. Between the functioning of taxis and classical public transport, it offers a service that is flexible in time and space like taxis, promoting the sharing of vehicles, like public transports. It is why it is present as a solution for a sustainable mobility. In the minds, DRT are often associated to a reduction of exhaust emissions and so are developed in rural areas. However, is grouping travellers enough to make DRT gainful for environment?In this doctoral research, an assessment tool of the environmental impact of DRT systems has been developed. To ensure that choice is sustainable in the sense of sustainable development, the service must be adapted to the local context by minimising emissions of substances in the near atmosphere while maintaining a sufficient quality of service when competing against personal vehicle use. A parameter directly involved in pollutant emissions, is often overlooked in approaches: the road network. We therefore search for identify laws and thresholds relating to pollutant emissions generated by the functioning of a DRT: how the road network does it affect the environmental performance of DRT or on the skill to grouping customers in vehicles? Depending on what service features (time windows allowed)? More generally, is that the optimization of the same type of DRT is equivalent to a road network to another, from the perspective of pollutant emissions? As any integrated tool to perform this task is available, we have developed a geomatics processing to estimate the quantities of pollutants emitted on road sections within the particular functioning of DRT and to cartography it to analyse their spatial distribution. This tool combines a GIS to an exhaust emissions model that we have adapted to our questioning (GREEN-DRT).