Théorie des graphes
Définition :
La théorie des graphes est une discipline qui étudie les graphes, c'est à dire des modèles abstraits de dessins de réseaux reliant des objets.
Les algorithmes de résolution élaborés ainsi sont utilisés dans de nombreux domaines (informatique, logistique...etc).
Chaque sommet représente une position géographique et est relié aux autres sommets par des arêtes.
Méthode : Principe
Dans le cas du routage, le trajet est décomposé en une multitude de points (sommets) reliés par des segments (arêtes), formant ainsi une grille.
Le trajet optimal est obtenu grâce à des algorithmes permettant de répondre à de multiples objectifs.
Remarque : Routage terrestre
Certaines applications de routage terrestre sont basées sur la théorie des graphes afin d'effectuer un trajet le plus rapidement possible. Dans ce cas, la grille est formée par le réseau routier.
Routage maritime
Dans le cas du routage maritime le problème est différent puisqu'il faut définir cette grille, préalablement au processus de routage.
En utilisant un modèle du navire, on compare pour chaque trajet possible le niveau de performances atteint en agissant sur plusieurs variables de contrôle comme le cap, la vitesse ou une combinaison des deux.