Sectoriser des points en zones par leurs coordonnées GPS

Dans le contexte des outils cartographiques, la sectorisation est une opération qui permet de regrouper des points par zones géographiques semblables. Il existe différentes possibilités pour regroupes les points selon les critères souhaités : par pays, par région, par code postal, par ville, … Ici nous utilisons les coordonnées GPS pour délimiter des zones rectangulaires.

Cet article s’adresse aux utilisateurs réguliers du service Open Street, qui connaissent l’ensemble des possibilités du service, et souhaitent aller plus loin. La parfaite maîtrise du tableur Excel (ou équivalent) est requise.

Introduction

Sectoriser ses points, une opération qui peut être utile dans bien des cas de figures liés à l’optimisation d’itinéraires routiers. Imaginez le cas de figure suivants : vous disposez d’une liste de 30 adresses pour des rendez-vous physiques, mais vous savez pertinemment qu’une seule personne itinérante ne pourra pas effectuer plus de 10 rendez-vous par jour en prenant en compte leur durée.

Deux possibilités apparaissent souvent dans la tête de nos utilisateurs :

1. Réaliser la tournée « fictive » avec les 30 points, tout en sachant qu’elle sera concrètement réalisée en plusieurs morceaux.
2. Sectoriser le fichier d’adresses, c’est à dire regrouper les adresses intelligemment par zones.

Nous déconseillons la première possibilité car elle consiste à calculer une optimisation qui ne sera pas représentative du trajet réellement effectué. La différence entre le calcul et la vie réelle peut alors être plus ou moins importante, généralement elle est pénalisante. Pour se donner une idée, le surcoût de cette méthode en distance parcourue peut très facilement atteindre ou dépasser la diagonale entière de la zone couverte par les points.

Le danger de négliger la sectorisation

Pour comprendre pourquoi il est déconseillé de réaliser une optimisation comportant l’ensemble de vos points tout en sachant qu’elle ne pourra pas être parcourue de la sorte, voici un fichier d’adresses réparties sur le territoire Français.

Cette liste d’adresses sera importée dans le service grâce à un import Excel, ou un import de fichier texte. Nous nous retrouvons donc avec la carte suivante. Un clic droit sur chaque marqueur bleu vous donnera accès à sa coordonnée GPS, coordonnée que l’on retrouve également sous forme de tableau dans le rapport de calcul.

Si on néglige la sectorisation, on peut tenter d’optimiser l’itinéraire en l’état. Ici nous avons calculé un itinéraire en boucle. Les points ont été positionnés sur la France que nous connaissons tous, dans le cas de cette étude nous émettrons l’hypothèse que 10 points peuvent être ralliés par journée quelque soit le kilométrage. Si cette hypothèse est douteuse à l’échelle du territoire, elle prendra tout son sens sur des optimisations plus locales à l’échelle d’une ville ou d’une région.

Que se passerait-il si nous tentions de suivre cet itinéraire du point n°0 au point n°29, tout en sachant que seulement 10 points peuvent être ralliés par journée ?

1. Premier trajet : du nord de Lyon vers le sud de Toulouse
2. Second trajet : du sud de Toulouse vers Caen
3. Troisième trajet : de Caen vers Besançon

Le problème apparaît ici clairement : le second trajet et le troisième trajet nous font quitter notre zone, on traverse donc toute la France en diagonale au lieu de rester cantonné à une zone puis à une autre zone. L’optimisation d’itinéraire est capable de tracer des itinéraire qui font le tour de la zone, une spirale, ou n’importe quelle forme prévisible ou incongrue afin de minimiser le temps de trajet et la distance parcourue. Le plus souvent, l’optimisation d’itinéraire emprunte les autoroutes.

Déterminer ses zones

La méthode de sectorisation traitée dans cet article fait appel aux coordonnées GPS. Nous utilisons ici le contour géographique le plus simple à exploiter : le rectangle défini par ses quatre coins. Nous avons besoin de connaître les coordonnées GPS des quatre points (latitude,longitude). Pour cela nous avons ici cherché une ville à l’endroit du coin idéal pour notre rectangle, et Open Street nous a donné les coordonnées GPS de cette ville. Il aurait été possible d’obtenir des coordonnées (latitude,longitude) depuis un GPS ou tout autre source de données géographique.

La latitude peut être représentée par l’axe de la hauteur et la longitude par l’axe de la largeur de notre rectangle.

Voici la proposition de zones qui est faite dans le cadre de cet exemple.

• Zone n°1, le nord de la France délimité par :
  • En haut à droite : Namur en Belgique avec les coordonnées 50.4673,4.8719
  • En bas à gauche : Kerbabic en Bretagne avec les coordonnées 47.9792,-4.1071
  • En haut à gauche on peut extrapoler la coordonnée 50.4673,-4.1071 (pas utile ici)
  • En bas à droite on peut extrapoler la coordonnée 47.9792,4.8719 (pas utile ici)
• Zone n°2, le centre de la France délimité par :
  • En haut à droite : Lure en France avec les coordonnées 47.6864,6.4942
  • En bas à gauche : Montpon-Ménéstérol en France avec les coordonnées 45.0092,0.1620
• Zone n°3, le sud de la France délimité par :
  • En haut à droite : Turin en Italie avec les coordonnées 45.0703,7.6868
  • En bas à gauche : Lannemezan en France avec les coordonnées 43.1255,0.3839

En prévision de notre formule Excel, on sait que si la latitude d’un point arbitraire est comprise dans l’intervalle [47.9792,50.4673] et que sa longitude est comprise dans l’intervalle [-4.1071,4.8719], alors le point appartient à notre Zone n°1.

Une autre formulation plus mathématique est :

• si latitude > 47.9792 ET latitude < 50.4673 ET longitude > -4.1071 ET longitude < 4.8719 alors le point appartient à Zone n°1.
• si latitude > 45.0092 ET latitude < 47.6864 ET longitude > 0.1620 ET longitude < 6.4942 alors le point appartient à Zone n°2.
• si latitude > 43.1255 ET latitude < 45.0703 ET longitude > -0.3839 ET longitude < 7.6868 alors le point appartient à Zone n°3.

Si nous devions représenter graphiquement nos trois zones, voici ce que nous obtiendrions. Ici un logiciel de manipulation d’images a été utilisé.

Importer les coordonnées GPS dans Excel

Quelque soit la méthode de saisie des adresses qui a été utilisée, vous pouvez exporter les coordonnées GPS en lot grâce au rapport, dès lors que les points ont été positionnés sur la carte. Pour cela, cherchez le « Tableau des données géographiques » et le lien « CSV » permettant de télécharger un fichier compatible Excel. Vous pouvez consulter notre article dédié au géocodage et coordonnées.

Comme souvent avec Excel pour l’ouverture d’un fichier CSV il faudra utiliser l’assistant d’import de données texte dans le menu Données > A partir du texte en choisissant un encodage (Unicode UTF-8) et un séparateur de champs (virgule). Le tableur LibreOffice sera capable d’ouvrir les fichiers sans assistance.

Le fichier CSV créé par Open Street contient les champs suivants : identifiant (id), adresse comprise par le service et formatée (address_formatted), adresse saisie (address_typed), latitude (lat), longitude (lng).

Excel n’est pas capable de comprendre que le point est un séparateur de décimales donc il faudra remplacer les points par des virgules avec la fonction « rechercher et remplacer ».

Les formules utilisées dans les colonnes F, G et H sont respectivement :

• =SI(ET(D2>47,9792;D2<50,4673;E2>-4,1071;E2<4,8719);1;0)
• =SI(ET(D2>45,0092;D2<47,6864;E2>0,1620;E2<6,4942);1;0)
• =SI(ET(D2>43,1255;D2<45,0703;E2>-0,3839;E2<7,6868);1;0)

Nous utilisons dans le cadre de cet article une mise en forme conditionnelle qui respecte la couleur rouge pour la Zone 1, Vert pour la Zone 2 et Bleu pour la Zone 3. Puis le tableau est trié selon les colonnes F, G et H.

Les trois derniers point n’appartiennent à aucune zone, cela signifie qu’ils devaient être limitrophes aux zones que nous avons précédemment définies « à la louche ». Pour corriger cela nous pourrions modifier nos zones ou encore les réintégrer manuellement à l’une de nos trois zones. C’est ce second choix de facilité que nous retiendrons : Foix est dans la zone 3, Angoulême et La Rochelle sont dans la zone 2.

Nos trois zones pourrons ainsi donner lieu à trois imports de points, et trois optimisations différentes.

Cas simplifié : découpage en 4 zones selon un point central

Nous avons vu comment déterminer 3 zones arbitraires et créer les formules Excel correspondantes.

Il existe un cas de figure couramment rencontré et plus simple à gérer : le découpage en 4 zones selon un point central. L’idée est de choisir un point central arbitraire qui déterminera une zone Nord-Est, une zone Nord-Ouest, une zone Sud-Est et une zone Sud-Ouest.

Si on prend le point central 48.951,2.035 les 4 formules Excel pour les 4 zones sont :

• =SI(ET(D2>48,951;E2>2,035);1;0)
• =SI(ET(D2>48,951;E2<2,035);1;0)
• =SI(ET(D2<48,951;E2>2,035);1;0)
• =SI(ET(D2<48,951;E2<2,035);1;0)

Voici un exemple téléchargeable d’un tel fichier Excel.

Conclusion

Une critique évidente à l’exemple que nous avons choisi dans le cadre de cette exemple est la distance trop importante que représente chaque zone. De plus, dans les cas concrets il y aurait probablement un point à intégrer dans chacune des zones : le domicile du conducteur ou encore le lieu de stockage de marchandises.

Nous avons donc sectorisé des points pour leur appartenance à une zone au contour rectangulaire en utilisant le service Open Street et des outils bureautique communs. La recherche de coins qui délimitent cette zone reste une opération fastidieuse car elle nécessite de trouver une adresse approchante et à en extraire les coordonnées grâce à l’application en ligne ou tout autre service équivalent.

La sectorisation de points par coordonnées GPS n’est pas la seule méthode existante, loin de là. Plus simple, vous pouvez regrouper des points par code postal par exemple. Plus abouti, nous pourrions délimiter des zones complexes au contour non rectangulaire, en tenant compte de la densité de points par unité de surface. Il existe des logiciels très performant pour réaliser de telles opérations, ils portent le nom de « systèmes d’informations géographiques » (SIG) et certains d’entre eux sont plutôt coûteux.

Néanmoins cette méthode logique et puissante pourra rendre service dans des cas de figure concrets.