Algorithmes utilisés par l'Extension ArcGIS Network Analyst.
Les calculateurs d'itinéraires dans l'Extension ArcGIS Network Analyst, à savoir, le calculateur d'itinéraire, l'analyseur de ressource la plus proche et l'analyseur de matrice de coût OD, s'appuient sur le célèbre algorithme de Dijkstra pour trouver les plus courts chemins. Chacun de ces trois solveurs implémente deux types d'algorithmes de recherche de chemins. Le premier type est le plus court chemin exact, et le second un solveur de chemin hiérarchique destiné à accélérer les performances. L'algorithme de Dijkstra classique résout un problème de plus court chemin sur un graphe non directionnel, non négatif et pondéré. Pour pouvoir être utilisé dans le contexte de données de transport de réelles, cet algorithme est modifié de manière à respecter des paramètres d'utilisateur tels que les restrictions de sens unique, les restrictions de tournants, les impédances de jonctions, les interruptions et les contraintes de côté de rue, tout en réduisant un attribut de coût spécifié par utilisateur. Les performances de l'algorithme de Dijkstra sont encore améliorées grâce à de meilleures structures de données telles que les d-heap. De plus, l'algorithme doit pouvoir modéliser les localisations sur n'importe quelle partie d'un tronçon, pas seulement sur les jonctions.
Algorithme de Dijkstra
L'algorithme de Dijkstra classique résout un problème de plus court chemin à source unique sur un diagramme sans pondération négative. Pour trouver un plus court chemin entre une localisation de départ s et une localisation de destination d, l'algorithme de Dijkstra fait appel à un ensemble de jonctions, S, dont le plus court chemin final à partir de s a déjà été calculé. L'algorithme trouve de manière répétée dans l'ensemble de jonctions une jonction dotée de la plus petite estimation de plus court chemin, l'ajoute à l'ensemble de jonctions S et actualise les estimations de plus court chemin de tous les voisins de cette jonction qui n'appartiennent pas à S. L'algorithme continue jusqu'à ce que la jonction de destination soit ajoutée à S.
Itinéraire
Cette fonction fait appel au célèbre algorithme de Dijkstra présenté ci-dessus.
Ressource la plus proche
Ce solveur utilise un algorithme à plusieurs origines et destinations qui s'appuie sur l'algorithme de Dijkstra. Il propose des options de calcul uniquement des plus courts chemins si ceux-ci se trouvent dans une limite spécifiée ou de calcul d'un nombre fixe de ressources les plus proches.
Pour en savoir plus sur la recherche de la ressource la plus proche
matrice de coût OD
Ce solveur utilise un algorithme à plusieurs origines et destinations qui s'appuie sur l'algorithme de Dijkstra. Il propose des options de calcul uniquement des plus courts chemins si ceux-ci se trouvent dans une limite spécifiée ou de calcul d'un nombre fixe de destinations les plus proches. Le solveur de matrice de coût OD est semblable au solveur de ressource la plus proche, à ceci près qu'il ne calcule pas la forme du plus court chemin résultant, afin de réduire le temps de traitement et d'améliorer les performances.
Pour en savoir plus sur la création d'une matrice de coût OD
Calcul d'itinéraire hiérarchique
La recherche du plus court chemin exact sur un jeu de données réseau concernant l'ensemble du pays est un processus long, en raison du grand nombre de tronçons concernés par les recherches. Pour améliorer les performances, les jeux de données réseau peuvent modéliser la hiérarchie naturelle d'un système de transport, où il est préférable de circuler sur une autoroute plutôt que sur des routes locales. Une fois qu'un réseau hiérarchisé a été créé, une modification de l'algorithme bidirectionnel de Dijkstra permet de calculer un itinéraire entre une origine et une destination.
L'objectif est de réduire l'impédance en favorisant les hiérarchies de niveau supérieur présentes dans le réseau. Pour ce faire, la fonction effectue une recherche simultanée à partir des emplacements d'origine et de destination ainsi que dans les points de connexion ou d'entrée sur les routes de niveau supérieur, puis dans les routes de niveau supérieur, jusqu'à ce que les segments provenant de l'origine et de la destination se rencontrent. La recherche est restreinte à la hiérarchie supérieure, les recherches se font dans un plus petit nombre de tronçons, ce qui accélère les performances. Notez qu'il s'agit là d'un algorithme heuristique, dont l'objectif est d'améliorer les performances et d'obtenir de solutions. Il ne garantit toutefois pas que le plus court chemin sera trouvé. Pour que cette heuristique aboutisse, la hiérarchie de niveau supérieur doit être connectée, car elle ne descend pas à un niveau inférieur si un arrêt brusque est atteint.
En règle générale, il est utile de faire appel à ce solveur sur un réseau hiérarchisé où les pondérations des tronçons sont basées sur le temps de déplacement. En effet, il imite la conduite normale sur un réseau d'autoroutes.
Pour en savoir plus sur l'analyse de réseau avec une hiérarchie
Option d'optimisation de tournée pour le calculateur d'itinéraire
Le calculateur d'itinéraire propose une option de création d'une séquence optimale de visite des localisations d'arrêts. Il s'agit de l'optimisation de tournée, ou TSP (Traveling Salesman Problem). Le TSP est un problème combinatoire, c'est-à-dire qu'il n'existe aucune méthode simple pour trouver la meilleure séquence. Les heuristiques permettent de trouver rapidement de bonnes solutions à ces types de problèmes. L'implémentation du TSP dans ArcGIS Network Analyst permet également de gérer les fenêtres horaires aux arrêts. En d'autres termes, le TSP trouve la séquence optimale pour visiter les arrêts avec un minimum de retard.
L'optimisation de tournée commence par créer une matrice de coût origine-destination entre tous les arrêts à séquencer et utilise un algorithme de recherche tabou pour trouver la meilleure séquence de visite des arrêts. La recherche tabou est un algorithme métaheuristique destiné à résoudre des problèmes combinatoires. Il appartient au domaine des algorithmes de recherche locaux. L'implémentation exacte de la recherche tabou est propriétaire, mais elle a fait l'objet de nombreuses recherches et de développement internes chez Esri pour donner de bons résultats rapidement.
Tournée de véhicules avec des fenêtres horaires
Le solveur tournée de véhicules (VRP) est une extension de l'optimisation de tournée. Dans un TSP, un ensemble d'arrêts est séquencé de manière optimale. Dans un VRP, un ensemble d'ordres doit être attribué à un ensemble d'itinéraires ou de véhicules de manière que le coût du chemin total soit réduit. Il doit aussi respecter des contraintes réelles, notamment la capacité des véhicules, les fenêtres horaires de livraison et les particularités des conducteurs. Le VRP produit une solution qui respecte ces contraintes tout en réduisant une fonction objective composée de coûts opérationnels et de préférences de l'utilisateur, comme l'importance du respect des fenêtres horaires.
Le solveur de tournées de véhicules commence par créer une matrice de coût origine-destination du plus court chemin entre toutes les localisations d'ordres et de dépôts le long du réseau. A l'aide de cette matrice de coût, il construit une solution initiale en insérant les ordres un par un sur l'itinéraire le plus approprié. Cette solution initiale est alors améliorée en reséquençant les ordres sur chaque itinéraire, en déplaçant des ordres d'un itinéraire vers un autre, et en échangeant des ordres entre itinéraires. L'heuristique propriétaire utilisée dans ce processus est basée sur une métaheuristique de recherche tabou. Elle fait l'objet de recherches et de développement en continu en interne chez Esri depuis de nombreuses années et donne rapidement de bons résultats.
Pour en savoir plus sur le calcul d'une tournée de véhicules
Zone de desserte
Le solveur de zone de desserte s'appuie aussi sur l'algorithme de Dijkstra pour traverser le réseau. Son objectif est de retourner un sous-ensemble d'entités de tronçons connectées se trouvant dans la distance de réseau ou la limite de coût spécifiées. De plus, il peut retourner les lignes classées selon un ensemble de valeurs de bornes dans lesquelles un tronçon peut se trouver. Le solveur de zone de desserte peut générer des lignes, des polygones entourant ces lignes, ou les deux.
Les polygones sont générés en plaçant la géométrie des lignes traversées par le solveur de zone de desserte dans des structures de données TIN. La distance de réseau le long des lignes sert de hauteur pour les localisations à l'intérieur du TIN. Les localisations non traversées par la zone de desserte sont placées avec une valeur de hauteur beaucoup plus importante. Un programme de création de polygones est utilisé avec ce TIN pour définir des régions qui comprennent des surfaces situées entre les valeurs de borne spécifiées. L'algorithme de création de polygones contient une logique supplémentaire pour produire les polygones généralisés ou détaillés et pour gérer les nombreux cas particuliers pouvant survenir.
Emplacement-allocation
L'emplacement-allocation est un solveur destiné au problème de localisation de ressources. Autrement dit, à partir de N ressources candidates et M points de demande avec une pondération, sélectionner un sous-ensemble de ressources, P, afin de minimiser la somme des distances pondérées de chaque élément M à l'élément P le plus proche. Il s'agit d'un problème combinatoire du type N sélectionner P et l'espace de solution devient extrêmement grand. Il est impossible d'obtenir des solutions optimales en examinant toutes les combinaisons. Par exemple, un petit problème comme 100 sélectionner 10 contient plus de 17 trillions de combinaisons. De plus, le solveur d'emplacement-allocation dispose d'options permettant de résoudre différents problèmes de localisation comme la minimisation de l'impédance pondérée, l'optimisation de la couverture ou l'atteinte d'une part de marché cible. Les problèmes d'emplacement-allocation sont résolus à l'aide de l'heuristique.
Le solveur d'emplacement-allocation commence par créer une matrice de coût origine-destination du plus court chemin entre toutes les ressources et les points de demande le long du réseau. Il construit ensuite une version modifiée de la matrice de coût à l'aide d'un processus connu comme modification de Hillsman. Ce processus de modification permet à la même heuristique de solveur générale de résoudre divers types de problème différents. Le solveur d'emplacement-allocation génère ensuite un ensemble de solutions semi-aléatoires et applique une heuristique de substitution de sommet (Teitz et Bart) pour affiner ces solutions afin de créer un groupe de bonnes solutions. Une métaheuristique effectue ensuite des combinaisons de ce groupe de bonnes solutions pour créer de meilleures solutions. Lorsqu'aucune amélioration supplémentaire n'est possible, la métaheuristique retourne la meilleure solution trouvée. La combinaison d'une matrice modifiée, de solutions initiales semi-aléatoires, d'une heuristique de substitution de sommets et d'une métaheuristique d'affinage permet d'obtenir rapidement des résultats proches de l'optimum.
Pour en savoir plus sur l'exécution d'une analyse d'emplacement-allocation