Routage efficace sur réseaux de transport multimodaux

Mobility is an important aspect of modern society. Consequently, there is a growing demand for services offering efficient route planning. In this thesis, we study multi-modal routing and the Dial-a-Ride system. Both respond to the need of a more efficient utilization of the available transportation infrastructure, which is an important component of sustainable development. Multi-modal route planning is complex because of the various modes of transportation which have to be combined. A generalization of Dijkstra's algorithm may be used to find shortest paths on multi-modal networks. However, its performance is not sufficient for real world applications. For this reason, this thesis introduces a new algorithm called SDALT. It is an adaption of the speed-up technique ALT. To evaluate the performance of SDALT, we produced a graph of a real-world multi-modal network based on transportation data of the French region Ile-de-France. It includes walking, public transportation, car, and bicycle, as well as timetable information and traffic data. Experiments show that SDALT performs well, with speed-ups of a factor 1.5 to 60 with respect to the basic algorithm. Other than finding shortest multi-modal paths that optimally combine the use of several modes of transportation, yet another problem arises: finding an optimal multi-modal return path or 2-way path. When using a private vehicle for parts of the outgoing path, it has to be picked up during the incoming path so that it can be taken to the starting location. For this reason, the parking must be chosen in such a way as to optimize the combined travel times of the outgoing and incoming path. We propose an efficient algorithm that solves this problem faster than previous techniques. The Dial-a-Ride system offers passengers the comfort and flexibility of private cars and taxis at a lower cost and higher eco-efficiency by combining similar transportation demands. It works as follows: passengers request the service by calling a central unit. They specify their pick-up point, their delivery point, the number of passengers, and some limitations on their service time (e.g., the earliest departure time). An algorithm then calculates the routes and schedules of the vehicles. We propose a new efficient and fast heuristic, a Granular Tabu Search, to produce good solutions in a short amount of time (up to 3 minutes). Our algorithm produces better results for more than half of the test instances after 60s of optimization time in comparison with other methods.La mobilité est un aspect important des sociétés modernes. Par conséquent, il y a une demande croissante pour des solutions informatiques de calcul d'itinéraire. Dans cette thèse, le routage multimodal et le système Dial-a-Ride sont étudiés. Ils contribuent à une utilisation plus efficace de l'infrastructure de transport disponible, élément déterminant dans la perspective d'un développement durable. La planification d'itinéraires multimodaux est rendus complexe en raison des différents modes de transport qui doivent être combinés. Une généralisation de l'algorithme de Dijkstra peut être utilisée pour trouver les chemins les plus courts sur un réseau multimodal. Cependant, sa performance n'est pas suffisante pour les applications industrielles. De ce fait, cette thèse introduit un nouvel algorithme appelé SDALT. Il s'agit d'une adaptation de la technique d'accélération ALT. Pour évaluer la performance de SDALT, un graphe a été construit à partir d'un réseau multimodal réel basé sur les données de transport de la région française Ile-de-France. Il inclut la marche, les transports en commun, la voiture, la bicyclette ainsi que des informations relative aux horaires les horaires et les conditions de circulation. Les tests de performance montrent que SDALT fonctionne bien, avec un temps de calcul réduit d'un facteur compris entre 1,5 et 60 par rapport à l'algorithme de base. Dans un contexte multimodal autre la question de la détermination du chemin le plus court, se pose celle de trouver un chemin aller-retour multimodal optimal entre un point de départ et un point d'arrivée. Un véhicule privé (voiture ou bicyclette) utilisé pour une première partie du trajet aller doit être récupéré au cours du trajet retour pour être ramené au point de départ. Pour cette raison, le parking doit être choisi de manière à optimiser les temps de déplacement du trajet aller et du trajet retour combinés. L'algorithme qui est proposé ici résout ce problème plus rapidement que les techniques actuelles. Le système Dial-a-Ride offre aux passagers le confort et la flexibilité des voitures privées et des taxis à un moindre coût et avec plus d'éco-efficacité car il regroupe les demandes de transport similaires. Il fonctionne de la manière suivante: les passagers demandent le service en appelant un opérateur. Ils communiquent leur point de départ, leur point de destination, le nombre de passagers, et quelques précisions sur les horaires de service. Un algorithme calcule ensuite les itinéraires et les horaires des véhicules. Cette thèse propose une nouvelle heuristique efficace et rapide de type Granular Tabu Search, capable de produire de bonnes solutions dans des délais courts (jusqu'à 3 minutes). Comparativement aux autres méthodes, et au regard des instances de test de la littérature, cet algorithme donne de bons résultats