Un algorithme simple de calcul de
route
Introduction
Le calcul et l'optimisation
d'itinéraires est une application naturelle des systèmes d'information
géographique.
Nous présentons dans cet article un algorithme
élémentaire de calcul d'un chemin reliant un point à un autre le long d'un
réseau existant.
Cet algorithme fait appel aux
fonctionnalités les plus générales d'un SIG, comme le contrôle de
l'intersection point-polyligne.
Contexte
Nous disposons d'un réseau représenté
par une table de polylignes. Nous rappelons qu'un objet polyligne est un objet géographique défini par une liste
finie de points (nœuds), représentant une ligne brisée.
Chaque polyligne est accrochée à une autre,
en un point d'accrochage qui constitue un nœud commun aux deux polylignes.
De plus, il est souhaitable que chaque
objet polyligne du fichier ne comporte que deux nœuds ; néanmoins, la plupart
des réseaux de rues proposés aux utilisateurs ne vérifient pas cette condition,
et l'algorithme pourra fonctionner dans de nombreux cas même si elle n'est pas
remplie.
On définit un point de départ (D) et un
point d'arrivée (A). Chacun de ces points est accroché à une polyligne du
réseau : par exemple, il peut coïncider avec un nœud.
Compte tenu des hypothèses retenues, il
existe au moins un chemin qui relie le point D au point A en suivant le réseau.
Description de l'algorithme
L'algorithme est fondé sur la méthode
intuitive suivante :
Un point courant accroché sur le réseau
de polylignes sélectionne, par sa seule position géographique, un ensemble de
polylignes.
Chacune des polylignes sélectionnées
peut comporter des nœuds "candidats" pour poursuivre la route, c'est
à dire des nœuds qui offrent une porte de sortie, c'est à dire encore des
nœuds, qui, par leur seule position géographique, sélectionnent au moins deux
enregistrements de la table des polylignes.
Pour pouvoir "avancer", il
conviendra évidemment d'exclure le point courant de la liste des nœuds
candidats.
Parmi l'ensemble des nœuds candidats
appartenant aux polylignes sélectionnés par le point courant, on choisit le
nœud le plus proche à vol d'oiseau du point d'arrivée. Ce nœud devient alors le
point courant qui permet de poursuivre l'itération.
Ce premier algorithme présente néamoins
une faille importante : un point pourra "tourner en rond"
indéfiniment sans avancer, comme le montre l'exemple suivant. Dans cet exemple,
chacune des polylignes du réseau comporte seulement deux nœuds. Compte tenu des
règles choisies, le point courant ne peut qu'osciller entre les points B et C.
Si l'on se contente de ce premier
algorithme, le point courant peut donc se retrouver "piégé" dans les
"puits d'attraction" que constituent les nœuds les plus proches du
point d'arrivée. Pour parer à ce risque, il suffit d'interdire au point de
parcourir plus de deux fois la même polyligne, et de préférer, à chaque
itération, passer par une polyligne qui n'a jamais été parcourue auparavant.
Cette règle classique dans les algorithmes de recherche opérationnelle
permettra ainsi de rebrousser chemin lorsque les règles de l'algorithme ont
conduit à s'engager dans un cul-de-sac, et interdira de s'engager deux fois
dans le même cul-de-sac.
En revanche, le risque existe que l'algorithme
tombe en échec, c'est à dire que le point courant ne puisse sélectionner aucun
tronçon qui n'ait pas été parcouru moins de deux fois, notamment si la table
des polylignes comporte des objets comportant plusieurs nœuds. Le schéma
ci-dessous donne l'exemple d'une telle mise en échec. Dans cette exemple, la
polyligne issue du point de départ D possède quatre nœuds D, B, C, E. Le point
courant, initialement en D, va occuper successivement les positions B et C. Il
ne pourra ensuite plus avancer puisqu'il aura déjà parcouru deux fois la
polyligne issue du point D.
C'est
la raison pour laquelle nous recommandons à l'utilisateur d'appliquer cet
algorithme sur un fichier de polylignes à deux nœuds.
Nous
sommes à présent en mesure d'écrire l'algorithme définitif.
Algorithme
Nous définissons un booléen found initialisé à la valeur FALSE, deux
listes L0 et L1, une liste des tronçons parcourus T et un dictionnaire D.
La liste T est initialisée à la valeur
de la liste vide.
Le point courant p prend la valeur du point de départ D.
On itère
indéfiniment les traitements suivants :
Les listes L0
et L1 sont initialisées à la valeur de la liste vide.
Pour
chaque
enregistrement r de la table des polylignes sélectionné par le point courant p, on applique les traitements suivants :
On recherche l'enregistrement r dans le
dictionnaire D.
Si la polyligne
d'index r a déjà été parourue deux fois, on passe immédiatement à la polyligne
suivante de la sélection.
Sinon :
On commence par vérifier si le point d'arrivée
A présente une intersection avec la polyligne r, auquel cas on a terminé : on
stocke dans la liste des tronçons le couple (r,p,A)
et on positionne le booléen found à
la valeur TRUE. On quitte l'itération parcourant la sélection des polylignes.
Sinon :
Pour chaque nœud n distinct de p de la polyligne r, on teste le nombre d'enregistrements de
la table des polylignes sélectionnés par n. Si ce nombre est au moins égal à 2,
on stocke le couple (r,n) dans la liste L0 si la polyligne d'index r n'a jamais
été parcourue, dans la liste L1 si la polyligne d'index r a été parcourue une
fois.
Une fois cette
opération effectuée pour chaque enregistrement r sélectionné par le point p,
la liste des candidats L prend la
valeur de la liste L0 si celle-ci n'est pas vide. A défaut, la liste des
candidats prend la valeur de la liste L1.
Si la liste L est vide (cas où
l'algorithme tombe en échec) ou bien si le booléen found est à TRUE, on quitte l'itération principale
inconditionnelle.
Dans le cas contraire, on complète la
liste des tronçons T avec le triplet (r,p,n) défini par
le nœud n le plus proche du point d'arrivée et son objet polyligne
d'appartenance r . La polyligne r a été parcourue une fois de plus : le
dictionnaire D est mis à
jour en conséquence. Le point courant p est
réinitialisé avec la valeur du point n. L'itération inconditionnelle est
poursuivie.
Si le booléen found est à FALSE, un message d'erreur
informant l'utilisateur de l'échec de l'opération est affiché.
Sinon, on constitue
le parcours global par concaténation des polylignes intermédiaires de la liste
T qui n'ont pas été parcourues plus d'une fois (sauf si la polyligne passe par
le point de départ), que l'on découpe avec les deux points courants de la liste
T qui définissent le tracé.
Deux remarques s'imposent :
1/ il est souhaitable d'ôter de
cette polyligne les éventuelles boucles disjointes
2/ la polyligne qui résulte de
l'opération peut comporter une erreur autour du point de départ : rien
n'empêche le tracé défini par l'algorithme de commencer par s'éloigner du point
de départ dans un sens, avant de rebrousser chemin dans l'autre sens en
traversant à nouveau le point de départ. La concaténation conduit dans ce cas à
une polyligne qui "déborde". Il conviendra donc de redécouper la polyligne
finale au niveau du point de départ lorsque nécessaire (c'est-à-dire lorsqu'au
moins un tronçon intermédiaire passant par le point de départ a été parcouru
deux fois) .
Auteur : Christophe Faivre Duboz
Date : 21/9/1999