Etude
d’une plateforme SIG : mise en oeuvre d’algorithmes pour le
routage.
Laboratoire de Génie Informatique et Automatique de l’Artois - LGI2A
Encadrement : Gilles Goncalves (PR), Tienté Hsu (MCF), Remy Dupas (MCF)
Contexte
Le
domaine des transports constitue un
secteur clef pour tous les secteurs de l'économie. Du point
scientifique les
problèmes de routage afférents à ce domaine et
connus sous le nom de problèmes
d'élaboration de tournées de véhicules ou Vehicle Routing Problem sont dans le cas
général des problèmes NP-difficiles.
Chaque véhicule
doit visiter un certain nombre de clients en respectant les contraintes
du
problème. L’objectif est de minimiser un ou plusieurs
critères comme la
distance parcourue, le nombre de véhicules utilisé, le
temps d’attente des
clients etc … De nombreuses
méthodes heuristiques ou méta-heuristiques
ont été consacrées à la résolution
de ce
type de problème. C'est le cas des méthodes
évolutionnistes qui regroupent
plusieurs approches inspirées par les mécanismes de
l'évolution naturelle. Les
problèmes de routage en dynamique quant à eux se
caractérisent par le fait que
l'information concernant le problème est dépendante du
temps et que les
solutions sont déterminées dans le temps en fonction de
l'arrivée de ces
informations: il n'y a donc pas de solutions a priori.
Le laboratoire LGI2A a développé depuis 2 ans, une plateforme évolutionniste pour la gestion dynamique de tournées de véhicules. Cette plateforme fournit pour chaque véhicule une liste de clients à visiter sur la base d’un graphe virtuel représentant les clients à servir. On désire dans ce projet apporter plus de réalisme à cette plateforme en lui adossant un SIG qui permettrait de prendre en compte de réels réseaux routiers.
Participation de l'étudiant
L’objectif de ce mémoire est de recenser dans un premier temps les différents SIG disponibles gratuitement (free GIS) sur le Web et de faire une rapide étude comparative sur leurs avantages et inconvénients. Il s’agit ensuite d’en sélectionner un et de l’installer sur une station du LGI2A.
Il faut ensuite créer une base de donnée support pour définir un réseau routier adapté à notre problème. A partir de cette base, il est demandé d’écrire une bibliothèque de routage permettant de calculer des distances entre clients ou des temps de trajets et de simuler le suivi d’un véhicule dans le réseau.
Mots Clefs : routage, optimisation, méthodes évolutionnistes, SIG.
Contact : goncalves@univ-artois.fr