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

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.

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.