Contributions to on-demand transport resolution based on multi-agent systems

Cette thèse porte sur le problème du transport à la demande (TAD). Nous proposons trois approches décentralisées basées sur les systèmes multi-agents pour résoudre ce problème. La première approche multi-agent utilise l'algorithme A* afin de trouver une solution optimale dans un réseau routier caractérisé par des vitesses de voyage constantes. Des expérimentations sont effectuées sur le réseau routier d'une ville libanaise appelée Tripoli et de bons résultats sont obtenus. Cependant, dans une ville comme Tripoli, les vitesses de voyage dépendent fortement de la situation dynamique du trafic routier. Pour cette raison, la deuxième approche multi-agent massif vient remédier à la première en tenant compte de l'évolution du trafic. Le réseau routier est considéré comme dynamique déterministe. Il se caractérise par des vitesses de voyages dépendantes de la situation habituelle du trafic. Ces vitesses sont pré-calculées en se basant sur des connaissances historiques du trafic routier. Les résultats expérimentaux montrent que le nombre de clients insatisfaits est supérieur à 50 % si les vitesses sont considérées comme constantes. Or, les connaissances historiques ne suffisent pas pour refléter la situation réelle du trafic surtout en cas d'apparition d'un événement imprévu tel qu'un accident sur le réseau. Pour cela, une troisième approche multi-agent massif auto-organisé est proposée. Le réseau routier est considéré comme dynamique stochastique caractérisé par des vitesses de voyage dépendantes de la situation réelle du trafic. Cette approche représente l'organisation dynamique du trafic à son échelle en se basant sur des connaissances historiques du trafic et sur des informations du trafic en temps réel. Les trajectoires des véhicules et leurs durées sont calculées et recalculées en ligne à chaque fois qu'un événement imprévu perturbe la situation habituelle du trafic. Les résultats expérimentaux montrent que jusqu'à 39 % des clients seront insatisfaits si un accident routier n'est pas considéré durant le traitement de leurs demandes. Autrement, 50 % à 100 % de ces clients sont satisfaits.This thesis addresses the problem of on-demand transport (ODT). We propose three decentralized approaches based on multi-agent systems to solve this problem. The first multi-agent approach uses the algorithm A* in order to find an optimal solution in a road network characterized by constant travel speeds. Experiments are carried out on the road network of a Lebanese city called Tripoli and good results are obtained. However, in a city like Tripoli, travel speeds depend heavily on the dynamic situation of road traffic. For this reason, the second multi-agent approach massif comes to remedy the first taking into account the evolution of traffic. The road network is considered as dynamic deterministic. It is characterized by travel speeds dependent on the usual traffic situation. These speeds are pre-calculated on the basis of historical knowledge of road traffic. The experimental results show that the number of dissatisfied customers is greater than 50 % if the speeds are considered to be constant. Nevertheless, historical knowledge is not sufficient to reflect the actual traffic situation, especially in case of an unexpected event (such as an accident) occurring on the network. For this, a self-organized massive multi-agent approach is proposed. The road network is considered as a dynamic stochastic characterized by travel speeds dependent on the actual traffic situation. This approach represents the dynamic organization of traffic on its scale based on historical traffic knowledge and real-time traffic information. Vehicle trajectories and their durations are calculated and recalculated online whenever an unexpected event disrupts the usual traffic situation. The experimental results show that up to 39 % of customers will be dissatisfied if a road accident is not considered during the processing of their demands. Otherwise, 50 % to 100 % of these customers are satisfied