La sectorisation géographique vue par Mapotempo
La sectorisation est l’une des fonctionnalités clé de Mapotempo Web. Elle permet de créer des secteurs géographiques et de les attribuer à un véhicule selon deux modalités : manuelle ou automatique.
Dans un problème d’optimisation de tournées, la sectorisation est une contrainte supplémentaire à respecter : les points à visiter appartiennent à des groupes qui sont attribués à des véhicules en fonction de critères donnés.
Les fonctionnalités de sectorisation disponibles dans Mapotempo Web
La sectorisation manuelle :
L’utilisateur dessine des zones géographiques à main levée directement sur la carte. Ce mode de sectorisation permet au planificateur de tournées de mettre en œuvre et de représenter sa connaissance métier et terrain, par exemple :
- Attribuer aux chauffeurs les zones avec lesquelles ils sont le plus à l’aise.
- Réaffecter des zones en cas d’absence d’un chauffeur.
- Visualiser les tournées et assurer leur cohérence géographique.
La sectorisation automatique :
L’utilisateur génère automatiquement des zones/secteurs à partir de deux fonctionnalités :
- la première permet de définir un nombre de secteurs à générer. L’algorithme groupe les points par proximité à un centroïde (un point fictif moyen) et équilibrera le nombre de visites par secteurs. On obtient ainsi automatiquement une répartition des tournées par zones géographiques équilibrée par véhicules.
4 secteurs avec équlibrage en nombre de points.
Map data © OpenStreetMap contributors, © OpenMapTiles
Content © Mapotempo
- La seconde permet de générer ce que l’on appelle des isochrones ou des isodistances à partir des dépôts. Ici, on génère des secteurs qui partent des dépôts et dont la surface peut être atteinte dans le temps imparti ou dans la limite de distance donnée. Cette fonctionnalité est particulièrement utile pour estimer le positionnement de commerces ou de centre logistiques. Elle permet également de fournir la couverture à un client final dans le cadre d’un service de livraison par coursier.
Isochrone 20 minutes – Véhicule léger .
Map data © OpenStreetMap contributors, © OpenMapTiles
Content © Mapotempo
Nos méthodes mathématiques de sectorisation
Le clustering
De manière similaire à l’équilibrage de secteurs en nombre de points, nous développons des méthodes afin de les équilibrer en termes de quantité, de durée ou de distance totale estimée (puisque l’optimisation n’a pas encore été réalisée à ce stade). Par exemple, pour la durée totale nous devons prendre en compte l’éloignement au dépôt, les durées des visites et la dispersion des points dans le cluster. À cela, nous devons également déterminer le nombre de véhicule qui sera nécessaire pour livrer chaque cluster, puisque cela aura un impact conséquent notamment sur les temps d’approche et de retour des véhicules entre le dépôt et les points à visiter.
Deux modes de sectorisation s’opposent :
- Le premier consiste à diviser l’ensemble des points en groupes visitables de manière à remplir un ou plusieurs véhicules. On effectue ainsi une découpe dite macro,
- Le second moyen de les diviser est de générer de multiples petits groupes de points en grappes de manière à ne pas dépasser un certain taux de remplissage de véhicule. Ces micros-groupes sont ensuite agglomérés pour former des tournées complètes.
La découpe macro
Constituer des ensembles disjoints de points à un niveau macro présente plusieurs avantages que ce soit au niveau de l’exploitation du résultat que dans la réduction de la complexité du calcul. En effet, effectuer cette découpe pour générer le secteur d’un véhicule ou d’un nombre réduit de véhicules permet d’obtenir des tournées géographiquement distinctes. Cela apporte une bonne visibilité à l’exploitant sur les zones qui sont affectées à chaque agent de terrain, ceci rend les aléas plus facilement intelligibles. Cela permet également, dans le cas d’expéditions, d’affecter les colis aux bonnes travées lors de leur arrivée dans le dépôt. De plus, dans le cas d’une sectorisation répétée sur plusieurs jours, cela permet à un agent d’effectuer des visites de rattrapage sur les jours suivants. Enfin, la qualité de service est améliorée lorsque le client final a des interlocuteurs bien identifiés et réguliers, dans la mesure où cela humanise le service rendu.
Au niveau complexité, cette approche permet d’éviter de calculer le distancier entier entre tous les points de visites en utilisant dans la phase de découpe des distances à vol d’oiseau. Ceci permet déjà d’apporter un premier gain important en termes de temps d’exécution. De plus, découper le problème en ensembles disjoints permet de casser la complexité des problèmes de tournées avec une stratégie de type Divide and Conquer (Diviser pour mieux régner).
Optimisation équilibrée sur la durée .
Map data © OpenStreetMap contributors, © Mapbox
Content © Mapotempo
Cela n’empêche pas dans la suite de la phase d’optimisation d’apporter un peu de souplesse dans la prise en compte de ces secteurs en autorisant certaines permutations entres tournées proches afin de réduire la durée ou le kilométrage total.
Cette approche macro est partiellement disponible au travers de Mapotempo Web en utilisant l’optimisation. Nous allons également extraire le mécanisme de sectorisation automatique associé pour le rendre utilisable depuis l’outil de zonage.
Agglomération micro
Là où l’approche macro a peu de sensibilité aux contraintes topologiques telles que les fleuves ou les autoroutes du fait de l’utilisation de la distance à vol d’oiseau pour constituer des grands ensembles, la découpe micro autorise quelques pré-traitements pour considérer ces obstacles dans la constitution des grappes de points. En effet, nous effectuons dans un premier temps une recherche de ces obstacles qui pourraient être discriminants dans la constitution d’une tournée sans être complètement rédhibitoires. Nous répartissons les points dans des ensembles séparés en fonction du secteur topographique ainsi déterminé.
Grands secteurs topographiques.
Map data © OpenStreetMap contributors, © QGIS Team
Content © Mapotempo
Une fois cette première découpe effectuée nous pouvons utiliser la distance à vol d’oiseau pour grouper les points dans de petits clusters en étant assuré qu’une grande partie des obstacles sont éliminés. Nous pouvons ensuite appliquer une phase d’optimisation qui visera à agglomérer ces micro-secteurs avec un distancier réel ce qui permet de casser la complexité de l’optimisation, puisqu’elle n’a plus à considérer les points de manière individuelle, mais à les déplacer par grappe. Cela a également l’avantage de pouvoir considérer les contraintes topologiques dans la phase de sectorisation et de laisser l’optimisation déterminer s’il est pertinent d’associer deux groupes de points.
Cette fonctionnalité encore au stade de prototype de notre côté demande encore quelques ajustements afin de la rendre suffisamment efficace pour être utilisée en production. En effet, actuellement les secteurs topographiques sont générés à la volée, ce qui entraîne un temps de calcul inutile puisque ces contraintes sont les mêmes pour tous (sur un même secteur). Enfin, certaines zones topographiques sont inutiles, par exemple les terre-plein entre deux voies d’autoroute. Une génération unique ou régulière permettrait de supprimer ces éléments inutiles et ainsi d’alléger les calculs.
La représentation des cluster
Une fois la génération de cluster effectuée, comment peut-on les représenter ?
Enveloppe convexe
© Wikipedia contributors
Une façon simple de représenter un cluster est d’en déterminer l’enveloppe convexe. Imaginons un ensemble de punaises accrochées à un tableau en liège, nous plaçons un élastique autour de notre ensemble, en relâchant délicatement l’élastique, il entourera notre cluster de manière à ce que depuis n’importe quelle punaise on puisse joindre toutes les autres en ligne droite sans jamais sortir de l’enveloppe ainsi créée. Cette représentation est peu coûteuse à obtenir et est unique, il n’existe qu’une seule enveloppe convexe pour un ensemble de points.
Enveloppe concave
Dans le cas où plusieurs groupes de points sont proches, il n’est pas assuré que l’on puisse obtenir l’enveloppe convexe de l’un de ces groupes sans englober des points appartenant à un autre groupe. Pour réduire ce risque il est possible de générer des enveloppes concaves.
© QGIS Team
Pour en revenir à l’image utilisée plut tôt, on se permet ici de faire passer l’élastique sur l’une des punaises à l’intérieur de notre cluster. Contrairement à l’enveloppe convexe, elle n’est pas unique et il est possible de paramétrer cette génération pour passer par tous les points ou comme dans notre cas d’usage dans Mapotempo Web, uniquement effectuer les détours qui permettent d’éviter aux clusters de se chevaucher (quand c’est possible).
Diagramme de Voronoï
Les enveloppes convexes et concaves sont très utiles pour représenter des groupes de points qui sont stables dans le temps. Cependant, dans le cas où de nouveaux points peuvent apparaître régulièrement dans les données à traiter, on veut être certain qu’ils soient insérés dans un cluster adapté avec une approximation d’une qualité suffisante.
Si le besoin est de couvrir l’ensemble de l’espace à partir des données déjà présentes, il est possible d’utiliser un diagramme de Voronoï. L’idée est de créer un pavage qui détermine la zone dans laquelle un point est le plus proche. On trace alors des droites aux intersections de ces zones.
© Wikipedia contributors
À partir de ces zones générées pour chaque point, on agglomère les zones appartenant aux différents points d’un même secteur. Ce qui nous donne une couverture complète du secteur sur lequel les données sont présentes.
Il est également possible de générer cet assemblage de pavés de Voronoï au sein de secteurs topographiques.
Sectorisation topographique et par agglomération. Représentation avec diagramme de Voronoï
Map data © OpenStreetMap contributors, © Mapbox
Content © Mapotempo
Cette seconde partie dans laquelle nous vous présentions les méthodes mathématiques que nous utilisons pour la sectorisation est un aperçu de notre travail de R&D sur ce sujet.
Certaines de ces innovations sont déjà présentes directement dans Mapotempo Web. Pour les autres, nous travaillons à les déployer progressivement afin de répondre aux attentes de nos clients directs et partenaires intégrateurs.
