Les solveurs d’itinéraires dans ArcGIS Network Analyst extension (à savoir, le solveur d’itinéraire, le solveur de ressource la plus proche et le solveur de matrice de coût OD) s’appuient sur le célèbre algorithme de Dijkstra pour trouver les chemins les plus courts. Chacun de ces 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 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 le 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
La fonction Itinéraire fait appel au célèbre algorithme de Dijkstra présenté ci-dessus.
Ressource la plus proche
Le solveur Ressource la plus proche 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.
En savoir plus sur la recherche de la ressource la plus proche
Matrice de coût OD
La matrice de coût OD 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 de calcul d’itinéraire hiérarchique effectue une recherche simultanée à partir des emplacements d’origine et de destination ainsi que depuis les points de connexion ou d’entrée sur les routes de niveau supérieur, puis sur 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 des 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 solveur d’itinéraire propose une option de création d’une séquence optimale de visite des points d’arrêts. Cela permet de résoudre ce que l’on appelle le problème de l’optimisation de tournée ou TSP. Le TSP (de l’anglais Traveling Salesman Problem) 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 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 chez Esri pour donner de bons résultats rapidement.
Tournée de véhicules avec des fenêtres horaires
La tournée de véhicules (VRP) est un super ensemble du TSP. 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 service spécialisé 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. À 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 chez Esri depuis de nombreuses années et donne rapidement de bons résultats.
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 renvoyer un sous-ensemble d’entités tronçons connectées qui se trouvent dans la distance de réseau spécifiée ou la limite de coût. En outre, il peut renvoyer les lignes catégorisées par un ensemble de valeurs d’interruption dans lequel 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 régulant les lignes à l’aide d’une distance indiquée par l’utilisateur. L’utilisateur a également la possibilité de créer des polygones de haute qualité de façon à ce que les polygones englobent toute la zone la plus proche des lignes non traversées, jusqu’à une distance fournie par l’utilisateur.
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 choisit 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, même un petit problème comme 100 sélectionner 10 contient plus de 17 milliards 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, créant 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
Vous avez un commentaire à formuler concernant cette rubrique ?