Traduire :

Vous êtes ici : Accueil  >  Recherche IRSEEM  >  Pôle Instrumentation, Informatique et Systèmes  >  Thèses soutenues  >  2006 - Thèse soutenue par Tahar BERRADIA

Services aux étudiants

Thèses soutenues

2006 - Thèse soutenue par Tahar BERRADIA

Publié le 10-04-2006

Contribution au problème du plus court chemin pour le transport des matières dangereuses

Le transport des marchandises et plus particulièrement des matières dangereuses (HazMat) est d'une grande importance pour l'économie. Ainsi, un système de transport efficace est nécessaire. Le choix d'itinéraires et le suivi des véhicules sont indispensables. Les travaux présentés dans cette thèse porte sur la recherche des meilleurs itinéraires à emprunter pour transporter des HazMat d'un point de départ à une destination spécifiée. Le temps de parcours et le risque de parcours sont des critères indissociables pour la recherche de chemins optimaux pour le transport de HazMat.

Pour ce faire, nous avons représenté le réseau routier par un graphe dynamique stochastique. Chaque arc est pondéré par son temps de parcours et son risque de parcours qui sont connus avec une marge d'incertitudes. Ces deux valeurs sont données par des variables aléatoires continues dont les densités de probabilité dépendent du temps. Ces variables aléatoires peuvent être de même type de lois ou de lois différentes. Une représentation "réaliste" du temps de parcours consiste en l'introduction de l'état de la circulation. Pour simplifier, nous supposons que chaque route a 4 états : circulation fluide, circulation difficile, circulation très difficile et circulation dense. Pour chaque état, le temps de parcours est une variable aléatoire connue. Le passage d'un état à un autre se fait avec une probabilité donné a priori. Cette représentation nous a donné une vision différente du problème que celle formulée en problème combinatoire.

D'une manière similaire, le risque de parcours qui est fonction de la probabilité d'accident et des conséquences résultantes (population, environnement) est connu avec incertitudes. Ce risque est une somme pondérée des risques sur la population et sur l'environnement. Ces pondérations sont fonctions de la matière dangereuse transportée, du type de la route, des conditions météorologiques et du temps. On introduit la même notion d'état pour une représentation du risque de parcours.

Le graphe ainsi défini est dynamique stochastique. Nous nous intéressons à la recherche du plus court chemin multiobjectif, dans un tel graphe.

Bien que les problèmes de recherche du plus court chemin en variables aléatoires continues soient très courants, ils sont peu étudiés. La plupart des algorithmes rencontrés dans la littérature sont en effet proposés dans le domaine combinatoire. Dès lors, la mise en oeuvre d'algorithmes pour les problèmes continus est profitable à un grand nombre de cas réels.

Les méthodes dites métaheuristiques constituent une classe d'algorithmes efficaces pour la résolution de beaucoup de problèmes combinatoires multiobjectif. L'avantage de ces méthodes réside dans leur capacité à fournir des solutions approchées en un temps raisonnable. L'objectif de notre étude est l'adaptation d'une métaheuristique (algorithme évolutionniste) à la recherche du plus court chemin dans un graphe dynamique stochastique et son application au transport des HazMat.

L'algorithme évolutionniste (AE) proposé permet de déterminer l'ensemble des solutions Pareto optimales, dans le cas de variables aléatoires de mêmes lois ou de lois différentes.

Dans le cas de variables aléatoires de même type de lois, la dominance stochastique s'écrit simplement en fonction de la valeur moyenne et de la variance. L'AE permet de fournir les chemins Pareto optimaux. Le choix des paramètres de l'AE conditionne l'efficacité de l'algorithme.

Pour les variables aléatoires de lois quelconques, l'ordre stochastique est difficile à mettre en oeuvre. L'introduction d'un critère supplémentaire et l'utilisation de l'AE combinée à une simulation des distributions permet d'approximer le front Pareto optimal.

La validation des approches proposées est effectuée sur des jeux de données aléatoires obtenus par une générateur de graphe que nous avons développé.

  Retour