II.1 Introduction - TEL (Thèses-en-ligne)

N° d'ordre : 37
Ecole Centrale de Lille
Université des Sciences et Technologies de Lille THESE présentée en vue d'obtenir le grade de DOCTEUR Spécialité : Automatique et Informatique Industrielle par Kamel ZIDI Doctorat délivré conjointement par l'Université des Sciences et
Technologies de Lille et l'Ecole Centrale de Lille Système Interactif d'Aide au Déplacement Multimodal (SIADM) Soutenu publiquement le 13 décembre 2006 devant le jury : |Président : |Daniel JOLLY |Professeur, Université d'Artois |
|Rapporteurs :|Patrick SIARRY |Professeur, Université de Paris 12 |
| |Christian TAHON |Professeur, Université de Valenciennes |
|Examinateur :|Khaled GHEDIRA |Professeur, ENSI Université Manouba |
| | |(Tunisie) |
|Directeur : |Slim HAMMADI |Professeur, Ecole Centrale de Lille |
|Co-directeur |Pierre BORNE |Professeur, Ecole Centrale de Lille |
|: | | |
Thèse préparée dans le laboratoire LAGIS à l'Ecole Centrale de Lille et
l'Université des Sciences et Technologies de Lille. Résumé
L'objectif de notre travail est la réalisation d'un système interactif
d'aide aux déplacements, en mode normal, et en mode dégradé de
fonctionnement du réseau de transport en commun. Ce système vise par
ailleurs à minimiser le temps d'attente des voyageurs, en mode dégradé,
dans les pôles d'échanges et à leur assurer, dans la mesure du possible, la
continuité des déplacements dans les réseaux multimodaux. Il s'agit donc
d'améliorer la qualité du service rendu aux voyageurs et les maintenir
informés. Une grande partie du travail de cette thèse concerne la
conception, le développement et la validation des approches qui permettent
de donner des solutions optimales ou quasi optimales, pour un réseau de
transport normal et perturbé. Ces approches utilisent une méthode
multicritère de recherche d'itinéraire qui s'appuie sur une hybridation
entre un algorithme de Dijkstra modifié et un algorithme génétique, pour
générer une population de chemins minimums . L'algorithme de Dijkstra
modifié nous donne un ensemble de solutions servant de population initiale
pour l'algorithme génétique. La modélisation du réseau de transport est représentée par une architecture
multi-zones . Cette architecture nous montre l'aspect distribué du système,
les interactions et les relations qui peuvent avoir lieu entre les
différenttes zones. Nous présentons dans ce travail un Système Multi-Agent
d'Aide au Déplacement, SMAAD. Les agents de ce système utilisent le module
d'optimisation développé dans la première partie. Notre travail est réalisé
dans le cadre du projet « VIATIC-MOBILITE », qui est le projet 6 du pôle de
compétitivité I-Trans. Mots-clés
Optimisation multi-objectif, thiéorie des graphes, algorithme génétique,
système multi-agent, transport multimodal, perturbation ...
Abstract
The objective of this work is the realization of a system allowing to
assist the travellers, and to facilitate their movement in normal and
degraded functioning of the transport network. This system aims to minimize
the waiting time of the travellers, in degraded mode, at exchanges stations
and to assure them, as well as possible, the continuity of their journey in
the multimodal transport networks. So it improves the quality of the
service returned to the travellers in order to inform them. A first part of
the work in this thesis concerns conception, development and validation of
our approach which allows giving optimal or almost optimal solutions for a
normal and disrupted transport system. This approach uses a multi-objective
method of search for optimal route which leans on a hybridization between a
modified Dijkstra algorithm and a genetic algorithm. The modified Dijkstra
algorithm gives us a set as solutions serving of initial population for the
genetic algorithm.
The modelling of the transport system is represented by multi-zones
architecture. This architecture shows us the distributed aspect of the
system, and the interactions and the relations which can take place among
various zones. We present in this work a Multi-agent system of Help to the
Movement. These agents use the module of optimization developed in the
first part. Our work is realized within the framework of the "VIATIC-
MOBILITE" project, which is the project 6 of the I-Trans Competitiveness
cluster.
Key-words Multi-objective optimization, graphs theory, genetic algorithm, multi-agent
system, multimodal transport, Disturbance ...
A mes chers parents et grand-mère,
à mes frères et s?urs,
à toute ma grande famille
et à la mémoire de mariem.
Remerciements
La première personne qui me vient à l'esprit et que je tiens à remercier
profondément est le Professeur Slim HAMMADI, Professeur à l'Ecole Centrale
de Lille et directeur de cette thèse, pour l'énorme soutien scientifique et
moral qu'il a su m'adresser pendant ces trois années au sein du LAGIS. Je
le remercie aussi pour ses qualités humaines et scientifiques et de m'avoir
toujours encouragée à aller de l'avant. Je tiens également à exprimer ma profonde gratitude au Professeur Pierre
BORNE, Professeur et directeur scientifique à l'Ecole Centrale de Lille, et
co-directeur de cette thèse, pour sa rigueur scientifique et son aide
précieuse et pour m'avoir accueillie au sein de l'équipe ID du LAGIS. Que Professeur Daniel JOLLI, Professeur à l'université d'Artois et
Directeur du laboratoire de Génie Informatique et d'Automatique de
l'Artois, reçoive mes plus sincères remerciements pour l'honneur qu'il m'a
fait en présidant ce jury. Professeur Christian TAHON, Professeur à Université de Valenciennes, et
Professeur Patrick SIARRY, Professeur à Université de Paris 12, m'ont fait
l'honneur d'accepter le rôle de rapporteur de cette thèse malgré un emploi
du temps surchargé en cette période de fin d'année. Je les en remercie,
leurs différentes suggestions, leurs précieux conseils et remarques m'ont
permis d'améliorer la qualité de la version finale de ce document. Pour m'avoir fait l'honneur d'accepter d'être examinateurs de cette thèse
et de participer à ce jury, un grand merci s'adresse à Professeur Khaled
GHEDIRA, Professeur et directeur de l'Ecole Nationale des Sciences de
l'Informatique à Tunis, ENSI. Ces remerciements ne seraient pas complets si je n'y associais pas toutes
les personnes qui ont contribué de près ou de loin à la réalisation de
cette thèse, en particulier, tout le personnel du LAGIS et de l'Ecole
Centrale de Lille que j'ai côtoyé durant ma thèse, pour leur bonne humeur
et leur disponibilité. Je n'oublie pas d'adresser mes vifs remerciements à mes Collègues : Med
Mahmoud Ould Sidi, Rayan Kammarti, Inaam Ben Khaled, Med Amine et Sana
Kammoun, Besma Glaa, Nacime Ihdaden etc. Aussi mes sincères remerciements à
Françoise dont les nombreuses relectures ont permis que cette thèse soit
présentable et écrite dans un français correct. Finalement, je ne peux qu'être infiniment reconnaissant envers mes parents
pour leur soutien indescriptible, leur patience, leur confiance et leurs
nombreux sacrifices. Je leur dédie avec plaisir ce travail ainsi qu'à ma
grand-mère Baha, mes deux frères Tarek et Salah, mes s?urs Radhiya,
Souleyma, Zakia et Chagra sans oublier mon oncle Thabet et mon grand frère
Mongi ainsi que toute ma grande famille. Qu'ils sachent que je suis
conscient de ce que je leurs dois et j'espère être un jour en mesure de
leur prouver mon affection !
Table des matières Table des matières 1
Table des Figures 4 Introduction générale 6 Chapitre I 11
Les problèmes de transport multimodaux centrés autour des services et des
clients de transport 11
I.1 Introduction 11
I.2 Multimodalité 11
I.3 Problème de recherche en transport pour aider à la régulation 12
I.3.1 Planification du trafic 13
I.3.2 Régulation du trafic 14
I.4 Problématique de recherche en transport pour aider les clients 15
I.5 Les applications existantes 17
I.6 Les applications en projet 21
I.7 Les limites des systèmes existants 24
I.8 Conclusion 24 Chapitre II 25
Etat de l'art en modélisation et optimisation dans le domaine du transport
25
II.1 Introduction 25
II.2 Modélisation graphique 25
II.3 Introduction du problème NP-complet 28
II.4 Optimisation combinatoire 29
II.5 Optimisation multicritère 30
II.6 Heuristiques 33
II.7 Les métaheuristiques 34
II.7.1 Le recuit simulé 35
II.7.2 Méthode Tabou 35
II.7.3 Algorithme de colonies de fourmis (ACF) 36
II.8 Les Algorithmes évolutionnaires 37
II.8.1 Principe général 37
II.8.2 Architecture des algorithmes évolutionnaires 39
II.8.3 Mise en ?uvre des algorithmes évolutionnaires 39
II.8.3.1 Choix d'un codage 40
II.8.3.2 Opérateur de sélection 41
II.8.3.3 Opérateur de croisement 42
II.8.3.4 Opérateur de mutation 44
II.8.3.5 Caractéristiques des algorithmes évolutionnai