Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

Le Problème de Transport à la Demande (PTD), consiste à prendre en charge le transport des personnes d'un lieu de départ vers un lieu d'arrivée. Il est caractérisé par un ensemble de demandes de transport et d'un nombre de véhicules disponible. L'ultime objectif dans ce travail de thèse est d'offrir une alternative optimisée au déplacement individuel et collectif. Le PTD est classé parmi les problèmes NP-difficile, la majorité des travaux de recherche ont été concentrés sur l'utilisation des méthodes approchées pour le résoudre.Ce problème est également multicritère, la solution proposée dans ce travail permet à la fois une réduction du temps de voyage et également de la distance parcourue. Dans cette thèse, nous proposons notre contribution à l'étude et à la résolution du problème de transport à la demande multicritère et dynamique en appliquant l'algorithme de recuit simulé multi-objectif. Une grande partie de notre travail concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un PTD. Ces approches utilisent une méthode multicritère qui s'appuie sur l'algorithme de recuit simulé. La modélisation du PTD est représentée par une architecture multi-acteurs. Cette architecture met en évidence l'aspect distribué du système ainsi que les interactions et les relations qui peuvent avoir lieu entre les différents acteurs. Nous présentons dans ce travail un Système Multi-Agents pour la planification des itinéraires des véhicules affectés au transport des voyageurs. Les agents de ce système utilisent le module d'optimisation développé dans la première partie

Durant ces dernières années, la congestion du trafic urbain et la pollution de l'air sont devenus d'énormes problèmes dans de nombreuses villes dans le monde. Afin de réduire cette congestion, nous pouvons investir dans l'amélioration des infrastructures de la ville. Toutefois, cette solution reste très coûteuse à entreprendre et de ne permet pas de réduire la pollution de l'air. C'est pourquoi nous travaillons sur la mobilité intelligente afin de disposer d'une meilleure utilisation de la voiture. L'application de nouvelles technologies de l'information, tels que les systèmes multi-agents appliqués au contrôle de l'information de la circulation urbaine, a permis de créer et de déployer une gestion plus intelligente du trafic comme le système DRT (transport à la demande). L'objectif des systèmes multi-agents basés sur le DRT est de gérer les taxis de manière intelligente, afin d'accroître le nombre de passagers dans chaque véhicule, et en même temps à réduire le nombre de véhicules dans les rues. Cela permettra de réduire les émissions de CO2 et la pollution de l'air causée par les véhicules, ainsi que la congestion du trafic et les coûts financiers associés. La simulation multi-agents est considérée comme un outil efficace pour les services dynamiques urbains de la circulation. Toutefois, le principal problème est de savoir comment construire un agent à base de modèle pour cette problématique. Ces travaux de recherche présente une solution basée sur les systèmes multi-agents réactifs pour la problématique du transport à la demande (DRT), qui adopte une approche multi-agent de planification urbaine en utilisant des services de contrôle qui satisfont aux principales contraintes : réduction de la période totale creuse, demandes spéciales du client, augmentation du nombre de places utilisées dans un même taxi, utilisation du nombre minimal de véhicules, etc. Dans cette thèse, nous proposons un modèle multi-agents multicouche hybride distribué pour des problématiques en temps réel. Dans la méthode proposée, un agent pour chaque véhicule trouve un ensemble de routes pour sa recherche locale, et choisit un itinéraire en coopérant avec d'autres agents se trouvant dans son domaine de planification. Nous avons examiné expérimentalement, l'efficacité de la méthode proposée. / In recent years, urban traffic congestion and air pollution have become huge problems in many cities in the world. In order to reduce congestion, we can invest in improving city infrastructures. Infrastructure improvements, however, are very costly to undertake and do not reduce air pollution. Hence we can work on intelligent mobility in order to have a more efficient car use. The application of new information technologies, such as multi-agent technologies to urban traffic information control, has made it possible to create and deploy more intelligent traffic management like DRT (Demand Responsive Transport) system. The objective of multi-agent based DRT system is to manage taxis in an intelligent way, to increase the efficient number of passengers in every vehicle, and at the same time to decrease the number of vehicles on streets. This will reduce the CO2 emissions and air pollution caused by the vehicles, as well as traffic congestion and financial costs. Multi-agent simulation has been looked as an efficient tool for urban dynamic traffic services. However, the main problem is how to build an agent-based model for it. This research presents a multi-agent based demand responsive transport (DRT) services model, which adopts a practical multi-agents planning approach for urban DRT services control that satisfies the main constraints: minimize total slack time, client’s special requests, increases taxis’ seats use ratio, and using minimum number of vehicle etc. In this thesis, we propose a multi-agent based multi-layer distributed hybrid planning model for the real-time problem. In the proposed method, an agent for each vehicle finds a set of routes by its local search, and selects a route by cooperation with other agents in its planning domain. By computational experiments, we examine the effectiveness of the proposed method. This research is supported by project “Gestion Temps Réel du Transport Collectif à la Demande” (CPER) Budgetthe French.

Le transport à la demande (TAD) est un mode de transport public à mi-chemin entre le taxi et le bus. Longtemps considéré comme un mode marginal réservé à la desserte des espaces peu denses, le TAD connaît un fort développement en France et en Europe depuis la fin des années 1990. Il ressort de l'analyse d'une base de données de 615 services, que les TAD français investissent désormais de nouveaux territoires, aussi bien dans les espaces urbains, périurbains que ruraux. Les prestations qu'ils proposent se caractérisent par une grande variété d'offre et de fonctionnement. Celles-ci sont décrites à l'aide de plusieurs modélisations fonctionnelles, statistiques et graphiques. Une réflexion sur la flexibilité des TAD, ainsi qu'une enquête, viennent ensuite nourrir le débat sur les TAD de demain. Trois exemples illustrent les perspectives qu'ouvre la généralisation de TAD flexibles et innovants en matière de transport public pour les collectivités.

Durant ces dernières années, la congestion du trafic urbain et la pollution de l'air sont devenus d'énormes problèmes dans de nombreuses villes dans le monde. Afin de réduire cette congestion, nous pouvons investir dans l'amélioration des infrastructures de la ville. Toutefois, cette solution reste très coûteuse à entreprendre et de ne permet pas de réduire la pollution de l'air. C'est pourquoi nous travaillons sur la mobilité intelligente afin de disposer d'une meilleure utilisation de la voiture. L'application de nouvelles technologies de l'information, tels que les systèmes multi-agents appliqués au contrôle de l'information de la circulation urbaine, a permis de créer et de déployer une gestion plus intelligente du trafic comme le système DRT (transport à la demande). L'objectif des systèmes multi-agents basés sur le DRT est de gérer les taxis de manière intelligente, afin d'accroître le nombre de passagers dans chaque véhicule, et en même temps à réduire le nombre de véhicules dans les rues. Cela permettra de réduire les émissions de CO2 et la pollution de l'air causée par les véhicules, ainsi que la congestion du trafic et les coûts financiers associés. La simulation multi-agents est considérée comme un outil efficace pour les services dynamiques urbains de la circulation. Toutefois, le principal problème est de savoir comment construire un agent à base de modèle pour cette problématique. Ces travaux de recherche présente une solution basée sur les systèmes multi-agents réactifs pour la problématique du transport à la demande (DRT), qui adopte une approche multi-agent de planification urbaine en utilisant des services de contrôle qui satisfont aux principales contraintes : réduction de la période totale creuse, demandes spéciales du client, augmentation du nombre de places utilisées dans un même taxi, utilisation du nombre minimal de véhicules, etc. Dans cette thèse, nous proposons un modèle multi-agents multicouche hybride distribué pour des problématiques en temps réel. Dans la méthode proposée, un agent pour chaque véhicule trouve un ensemble de routes pour sa recherche locale, et choisit un itinéraire en coopérant avec d'autres agents se trouvant dans son domaine de planification. Nous avons examiné expérimentalement, l'efficacité de la méthode proposée.

Le principal objet de cet thèse réside dans la modélisation et l’optimisation de services de transport à la demande aussi différents soient-ils (ou seront-ils). Les techniques de supervision doivent alors pouvoir supporter différents objectifs et différentes contraintes pour s’adapter aux services actuels et futurs. Ainsi, ce rapport de thèse développe différentes variantes du DARP - ang. Dial-a-Ride Problem -, le problème de Recherche Opérationnelle modélisant et optimisant un service classique de transport à la demande. Le DARP standard a été étendu de façon à prendre en compte des hypothèses de fonctionnement prometteuses, comme le fait de séparer les composants d’une même requête pour les dispatcher sur des véhicules différents ou encore la présence de mécanismes d’intermodalité. Cette thèse permet également d’inscrire les véhicules autonomes tels que les VIPA dans de nouvelles problématiques de la Recherche Opérationnelle tout en restant dans le domaine du transport à la demande. La modélisation puis l’optimisation de ces systèmes permet de créer les plannings de ces nouveaux véhicules. A long terme, l’évolution technologique devrait permettre de ne plus se soucier du fait qu’ils sont automatiques. Ces travaux tentent de fournir un cadre suffisamment générique permettant à la fois de fournir une solution exploitable aujourd’hui et qui soit adaptable demain. / The main objective of the thesis is modeling and optimization of several on-demand transportation services. Supervision techniques must be able to handle numerous criteria and numerous constraints to adapt to the current and future services. Thus, this research develops several types of DARP - Dial-a-Ride Problem -, the operation research problem modeling and optimizing an on-demand transportation system. The standard DARP has been adapted to promising systems, such as those allowing to split the components of the same request and the possibility to dispatch them on different vehicles or the presence of intermodal mechanisms. This thesis also formulates new Operations Research problems in order to integrate autonomous vehicles such as the VIPA in an optimized on-demand transportation system. Modeling and optimizing these systems create schedules of these new vehicles. In the future, technological evolutions are expected and the automatic feature of the vehicles will not be taken into account anymore. These studies attempt to provide a generic framework in order to provide a usable tool for today and an adaptable tool for tomorrow.

Nous étudions dans cette thèse un problème de construction de tournées de véhicules pour le transport de personnes à la demande (TAD) qui, combinant la souplesse des taxis à la capacité de regroupement des transports en commun, est une voie pour repenser nos pratiques en terme de mobilité. Après avoir défini puis classé plusieurs critères de qualité de service, nous en sélectionnons trois pour leur représentativité : la minimisation de la distance totale parcourue, la maximisation du taux de remplissage des véhicules et la minimisation du temps perdu en transport. La méthode d'optimisation utilisée est basée sur une approche par décomposition appelée génération de colonnes. Nous nous plaçons dans le cas statique où toutes les demandes sont connues par avance. L'adaptation de cette méthode exacte aux trois critères choisis induit des développements originaux, comme la modélisation du réseau par un p-graphe ou l'optimisation d'une fonction objectif fractionnaire. Cette étude est intégrée à un projet pluridisciplinaire piloté par des géographes qui a pour sujet d'expérimentation la mise en place d'un TAD opérationnel dans le Pays du Doubs Central (France). Un algorithme de résolution heuristique spécifique a été développé pour cette application. L'intégration des résultats des deux algorithmes à un Système d'Information Géographique permet une analyse des critères de qualité de service et de leurs interactions avec le territoire d'un point de vue géomatique. Il en découle une étude sur la forme des tournées et plus particulièrement sur différentes mesures de leur sinuosité.

Cette thèse s’intéresse à trouver des solutions informatiques à certains problèmes de l’optimisation combinatoire, à savoir les problèmes de tournées de véhicules. Elle aborde les problèmes de Transport A la Demande (TAD). L’objectif principal visé dans cette thèse fait appel à certaines approches exactes et certaines approches méta-heuristiques pour résoudre des problèmes d’optimisation multi-objective de Transport A la Demande avec plusieurs véhicules. En effet, nos principaux objectifs de recherche consistent à : -I) Résoudre un problème multi-objectif de Transport A La Demande multi-véhicules basé sur la qualité de service ; - II) Résoudre un autre problème de Transport A la Demande multi-objectifs multi-véhicules. Ce problème traite un cas spécifique et qui consiste à l’application de ce problème aux domaines de l’Hospitalisation A Domicile (HAD). Nous avons appliqué des algorithmes exacts de "Branch and Bound" et des méthodes méta-heuristiques telles que l’algorithme évolutionnaire "Algorithme Génétique" et l’algorithme de "Colonie de Fourmis" pour apporter des solutions efficaces à ces différents problèmes. Un ensemble de résultats numériques est présenté pour chacune de ces méthodes pour montrer leurs capacités de produire des solutions de haute qualité en temps de calcul raisonnables. / This thesis focuses on finding computer science solutions for some combinatorial optimization problems, namely Vehicle Routing Problems (VRP). The thesis addresses the Dial A Ride Problems (DARP). Its main objective is to use some exact and meta-heuristics approaches to solve multi-objective optimization of Dial A Ride Problem with multi-vehicles. Hence, our main research aims are : - I)Solve a multi-objective Dial A Ride Problem with multi-vehicles based on quality of service, this problem treats a general case ; - II) Solve another multi-objective Dial A Ride Problem with multi-vehicles, this problem deals with a specific case which is an application of the Dial A Ride Problem in Home Health Care (HHC). We have also applied exact algorithms "Branch and Bound" and meta-heuristic algorithms such as evolutionary algorithms "Genetic Algorithm" and "Ant Colony" algorithm to provide effective solutions to these different problems. A set of numerical results are presented for each of these methods. Our results show that they produce high quality solutions in a reasonable execution time for all the treated problems.

Le Problème de Transport à la Demande (PTD), consiste à prendre en charge le transport des personnes d'un lieu de départ vers un lieu d'arrivée. Il est caractérisé par un ensemble de demandes de transport et d'un nombre de véhicules disponible. L'ultime objectif dans ce travail de thèse est d'offrir une alternative optimisée au déplacement individuel et collectif. Le PTD est classé parmi les problèmes NP-difficile, la majorité des travaux de recherche ont été concentrés sur l'utilisation des méthodes approchées pour le résoudre.Ce problème est également multicritère, la solution proposée dans ce travail permet à la fois une réduction du temps de voyage et également de la distance parcourue. Dans cette thèse, nous proposons notre contribution à l'étude et à la résolution du problème de transport à la demande multicritère et dynamique en appliquant l'algorithme de recuit simulé multi-objectif. Une grande partie de notre travail concerne la conception, le développement et la validation des approches qui permettent de donner des solutions optimales ou quasi optimales, pour un PTD. Ces approches utilisent une méthode multicritère qui s’appuie sur l’algorithme de recuit simulé. La modélisation du PTD est représentée par une architecture multi-acteurs. Cette architecture met en évidence l’aspect distribué du système ainsi que les interactions et les relations qui peuvent avoir lieu entre les différents acteurs. Nous présentons dans ce travail un Système Multi-Agents pour la planification des itinéraires des véhicules affectés au transport des voyageurs. Les agents de ce système utilisent le module d’optimisation développé dans la première partie / The Dial a Ride Problem (DRP) is to take passengers from a place of departures to places of arrivals. Different versions of the dynamic Dial a Ride Problem are found in every day practice; transportation of people in low-density areas, transportation of the handicapped and elderly persons and parcel pick-up and delivery service in urban areas. In the DRP, customers send transportation requests to an operator. A request consists of a specified pickup location and destination location along with a desired departure or arrival time. The ultimate aim is to offer an alternative to displacement optimized individually and collectively. The DRP is classified as NP-hard problem that’s why most research has been concentrated on the use of approximate methods to solve it. Indeed the DRP is a multi-criteria problem, the proposed solution of which aims to reduce both route duration in response to a certain quality of service provided. In this thesis, we offer our contribution to the study and solving the DRP in the application using a multi agent system based on the Multi-Objective Simulated Annealing Algorithm

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.