Algorithme génétique : genèse d’une nouvelle sectorisation automatique

Sectorisation automatique avec un algorithme genetique

Nous l’avons annoncée dans notre page « Nouveautés » en date du 9 décembre 2019 [1] : une nouvelle sectorisation automatique, qui utilise un algorithme génétique, a été déployée fin 2019 en version bêta dans Cartes & Données Online et Articque Platform. Fruit d’une intense réflexion au sein de notre équipe R&D, cette sectorisation s’inspire de la théorie de l’évolution des espèces développée par Darwin. Elle est conçue pour augmenter la pertinence des sectorisations. Désormais disponible en version stable, elle complète ainsi l’offre de sectorisation automatique classique basée sur la méthode heuristique. Nous retraçons dans cet article la genèse de cet algorithme génétique.

1. Pourquoi utiliser un algorithme génétique ?

La révision de notre algorithme de sectorisation automatique a été engagée suite aux remarques récurrentes de la part de nos formateurs, de nos clients ou encore de notre équipe Projets. En effet, la méthode heuristique, qui est centrée sur des pôles de départ (agences ou lieux d’habitation des commerciaux par exemple), produit parfois des secteurs qui ne possèdent pas une forme idéale (biscornue ou non-homogène sur le plan géographique), ce qui complique fortement le travail sur le terrain (voir l’exemple n°1). Certains territoires délimités ne peuvent pas être couverts efficacement par une équipe commerciale par exemple. Dans ce cas, l’utilisateur doit retravailler manuellement ces secteurs a posteriori.

Il était donc urgent de repenser la sectorisation automatique pour qu’elle soit davantage exploitable et rationnelle. L’équipe R&D d’Articque s’est fixé les objectifs suivants :

– améliorer la compacité et l’équilibre des secteurs

– donner la possibilité de créer une sectorisation sans point de départ (ce qui n’est pas possible avec la méthode heuristique)

L’équipe R&D a donc travaillé simultanément dans 2 directions :

a) l’amélioration de la sectorisation automatique existante (méthode heuristique) en ajoutant:

– des contraintes de compacité pour obtenir des secteurs aussi compacts que possible (voir l’exemple n°2)

– une phase de rééquilibrage afin d’optimiser l’équilibre des données sur la zone géographique.

b) l’élaboration d’une nouvelle sectorisation basée sur un algorithme génétique. La démarche a été menée durant plusieurs mois :

– en dressant d’abord un état de l’art

– puis en s’appuyant sur les travaux universitaires publiés (comme ceux d’Éric Pellerin ou de Wen-Yang Lin)

– et en réalisant enfin une phase intensive de tests, qui se sont avérés concluants.

L’algorithme génétique répondait au double objectif de départ. Il a été intégré dans la fonctionnalité « Sectorisation automatique » présente dans le logiciel Cartes & Données.

Exemple 1 : sectorisation automatique par méthode heuristique

sectorisation-methode-heuristique

Paramètres initiaux : 5 points de départ, 5 secteurs à créer et 4 types de commerces à répartir (commerce d’alimentation générale, supérette, supermarché, hypermarché)

Résultats : les secteurs créés sont relativement bien équilibrés en nombre de commerces mais les secteurs bleu et vert n’ont pas une bonne compacité.

Les scores obtenus dans le logiciel Cartes & Données :
Score global : 57,78%
Score de compacité : 35,89%
Score d’équilibrage des données : 79,67%
Commerces d’alimentation générale : 72,3%
Supérettes : 81,05%
Supermarchés : 91,46%
Hypermarchés : 73,88%

2. Qu’est-ce qu’un algorithme génétique ?

La méthode génétique s’inspire de la théorie de Darwin sur l’évolution des espèces et sur la sélection naturelle : il s’agit de s’appuyer sur les caractéristiques génétiques de l’espèce qui s’adapte le mieux pour assurer sa survie, par élimination des espèces qui sont les moins aptes à le faire. Ce nouvel algorithme permet de réaliser une multitude de sectorisations différentes (100, 200, 300 ou 1000 itérations – voir l’exemple n°3). Ces sectorisations sont générées de manière aléatoire selon les paramètres définis par l’utilisateur du logiciel (nombre d’itérations choisi et temps alloué pour réaliser le traitement). Grâce à un scoring (compacité et équilibrage), les sectorisations qui possèdent les meilleures caractéristiques sont conservées pour être ensuite dupliquées (en fonction du nombre d’itérations défini initialement). La reproduction de générations de sectorisations a pour finalité la définition d’un optimum, c’est-à-dire d’une sectorisation la plus proche de l’objectif de l’utilisateur du logiciel. Cet algorithme génétique vise l’amélioration constante des sectorisations, en sélectionnant les meilleures d’entre elles.

De plus, une part de machine learning et d’Intelligence Artificielle a été intégrée : la meilleure sectorisation est conservée, même lorsque le traitement dans Cartes & Données est relancé. Elle est alors réutilisée et intégrée au début d’une nouvelle sectorisation automatique (c’est en tout cas une possibilité laissée à l’utilisateur).

3. L’algorithme génétique : quels bénéfices pour la sectorisation automatique ?

Le bénéfice concret de cette nouvelle méthode de sectorisation automatique est d’abord de s’assurer d’obtenir un résultat plus convaincant, notamment au niveau de la compacité des secteurs. Cet algorithme génétique augmente considérablement la pertinence des sectorisations réalisées dans les logiciels Cartes & Données Online et Articque Platform : les nouveaux secteurs créés sont concrètement exploitables dans la pratique car ils sont rationnels. En implémentant un scoring de compacité et d’équilibrage plus pertinent qu’avant, l’équipe R&D d’Articque a mis en place la possibilité de parvenir à des résultats plus fiables (voir l’exemple n°4). Grâce à ce scoring, la comparaison entre deux sectorisations se fait très simplement en un coup d’œil.

Le potentiel de la sectorisation automatique par la méthode génétique est grand : elle permet de découper un territoire de manière équilibrée et optimisée entre différents acteurs qui vont y exercer un service, l’administrer, le gérer ou le prospecter. Par exemple, un territoire peut être réparti efficacement entre différents techniciens ou commerciaux, en fonction de leurs compétences ou de façon à ce qu’ils aient tous une charge de travail équivalente.

Exemple 2 : sectorisation automatique par méthode heuristique avec contrainte de compacité

Sectorisation par methode heuristique avec contrainte de compacite

Paramètres initiaux : 5 points de départ, 5 secteurs à créer et 4 types de commerces à répartir (commerce d’alimentation générale, supérette, supermarché, hypermarché)

Résultats : la compacité des secteurs créés est meilleure. Mais le score global, tout comme celui de l’équilibrage des données, sont moins bons. Le secteur bleu est très nettement inférieur aux autres.

– Les scores obtenus dans le logiciel Cartes & Données :
Score global : 54,32%
Score de compacité : 39,86%
Score d’équilibrage des données : 68,78%
Commerces d’alimentation générale : 68,42%
Supérettes : 68,04%
Supermarchés : 73,04%
Hypermarchés : 65,6%

Exemple 3 : sectorisation automatique par méthode génétique

sectorisation-algorithme-genetique-1

Paramètres initiaux :
5 points de départ, 5 secteurs à créer, 4 types de commerces cibles à répartir (commerce d’alimentation générale, supérette, supermarché, hypermarché)
500 itérations, temps maximum : 20 secondes, 100 sectorisations aléatoires étudiées à chaque itération, 10% d’élitisme

Résultats : la répartition est beaucoup plus équilibrée et la composition en types de commerces des 5 secteurs est beaucoup plus ressemblante. En revanche, la forme des secteurs et leur compacité ne sont pas optimales.

Les scores obtenus dans le logiciel Cartes & Données :
Score global : 86,51%
Score de compacité : 96,99%
Score d’équilibrage des données : 76,02%
Commerces d’alimentation générale : 80,54%
Supérettes : 71,93%
Supermarchés : 81,11%
Hypermarchés : 70,51%

Exemple 4 : sectorisation automatique par méthode génétique

Sectorisation par algorithme genetique 3

Paramètres initiaux :
5 points de départ, 5 secteurs à créer, 4 types de commerces cibles à répartir (commerce d’alimentation générale, supérette, supermarché, hypermarché)
2000 itérations, temps maximum : 240 secondes, 1000 sectorisations aléatoires étudiées à chaque itération, 10% d’élitisme

Résultats : les secteurs créés sont géographiquement cohérents et relativement compacts. Le ratio entre compacité et équilibrage est bon.

– Les scores obtenus dans le logiciel Cartes & Données :
Score global : 72,94%
Score de compacité : 71,55%
Score d’équilibrage des données : 74,48%
Commerce d alimentation générale : 85,75%
Supérettes : 64,29%
Supermarchés : 78,79%
Hypermarchés : 69,1%

Conclusion

L’équipe R&D d’Articque n’a de cesse d’améliorer le logiciel Cartes & Données et de perfectionner ses fonctionnalités. Preuve en est avec cette nouvelle sectorisation automatique basée sur l’algorithme génétique. Cette méthode de sectorisation garantit des résultats très positifs et prometteurs en termes de découpage territorial et de compétitivité.

Elle complète la sectorisation automatique par méthode heuristique, dont la compacité a été améliorée. Cette dernière permet maintenant d’assurer une compacité minimale en prenant en compte un découpage homogène. Les développements que nous avons décrits dans cet article sont pensés pour booster votre activité. Ils constituent des raisons supplémentaires d’adopter notre logiciel de cartographie statistique Cartes & Données.

Ces contenus peuvent vous intéresser :

Comment fonctionne le module de Sectorisation automatique ?

miniature-sectorisation-automatique

Webinar : comment optimiser votre sectorisation commerciale

Miniature webinar sectorisation automatique

À propos de l’auteur : Mathieu Boisseau

Webmarketeur

J’ai rejoint Articque en mai 2019 comme webmarketeur afin de créer des contenus dédiés au monde de la cartographie statistique.