Gestion des interventions : Optimisez les transports grâce aux algorithmes génétiques

La planification optimale des transports demeure un défi de taille dans certains secteurs comme ceux de l’industrie, de l’approvisionnement ou des services. La plupart du temps, dans le cadre de la gestion des interventions de terrain, les déplacements de personnel, appareils et outils d’un point A vers un point B nécessitent le recours à des véhicules. Apparaît alors un défi évident : définir les itinéraires les plus optimaux entre deux points pour gagner du temps, réduire la consommation de carburant, servir davantage de clients et récupérer des objets dans différents entrepôts. Ce casse-tête est connu depuis des années et est même appelé « problème de tournées de véhicules » (VRP). Il s’agit en fait de l’un des problèmes d’optimisation les plus fréquemment analysés. Plus général que le « problème du voyageur de commerce » (TSP), problème très connu, il a pour objectif de trouver un ensemble d’itinéraires (potentiellement mais pas nécessairement les plus courts) entre différents lieux pour un ensemble de véhicules.

Ce problème appartient à la catégorie des problèmes NP-difficiles (non déterministe polynomial). Cela signifie donc qu’il n’existe pas d’algorithme efficace capable de trouver une solution dans un délai raisonnable pour l’ensemble des facteurs impliqués (techniciens, tâches, ressources, etc.) En réalité, ce problème s’avère parfois plus complexe à cause de contraintes supplémentaires telles que des créneaux horaires, la capacité des véhicules ou une limitation des ressources (par exemple, la disponibilité d’une ressource dans les dépôts, le nombre de véhicules disponibles à partager ou le besoin d’aller faire le plein). Chaque critère supplémentaire complique l’optimisation et la rend plus chronophage. Dans les cas les plus extrêmes, on en vient parfois à recourir à des processeurs graphiques (GPU) comme co-processeurs très efficaces pour la parallélisation du travail.

Comment les algorithmes génétiques parviennent-ils à optimiser les transports dans le cadre de la gestion des interventions ?

Afin d’optimiser les transports pour les services de terrain, l’équipe Comarch a opté pour l’utilisation d’un algorithme génétique (AG), un algorithme de recherche basé sur le processus de sélection naturelle. Ainsi, une solution potentielle au problème des itinéraires est présentée sous forme d’analogie avec des chromosomes, où chaque gène est porteur de sens pour un aspect précis de la solution (par exemple, pour les tâches attribuées à un technicien spécifique). Se déplaçant à travers plusieurs populations (ce que l’on appelle « évolution »), le système, grâce à ses opérateurs inspirés de la biologie comme l’enjambement, la mutation ou la sélection, est capable d’explorer différentes solutions sans analyser l’ensemble des combinaisons possibles. L’opérateur « enjambement » permet à l’algorithme de mener l’évolution dans la direction souhaitée, soit en direction de la solution optimale. La « mutation » vient également en aide à l’évolution, car elle empêche l’algorithme génétique (AG) de se retrouver bloqué sur une solution dans laquelle la population ne pourrait évoluer sur base du matériel génétique disponible (tout comme dans la réalité, il est impossible de faire naître un lapin bleu si aucun matériel génétique « bleu » n’existe au sein de la population de lapins).

Chaque solution présentée sous la forme d’un chromosome est notée à l’aide d’une fonction d’évaluation. La solution espérée sera quasiment optimale, mais ses coûts seront significativement moins élevés. Évidemment, la solution optimale peut parfois aussi être la meilleure. De plus, il est bien plus facile d’exprimer toutes les contraintes dans une fonction d’évaluation que de concevoir un algorithme capable de tenir compte de l’ensemble de ces contraintes. Ajouter une nouvelle condition ou coder un ensemble de conditions pour un nouveau client ne nécessite alors que la création de simples fonctions attribuant des scores à toutes les solutions précédemment calculées. Plus une solution obtient de points (ou moins elle en obtient s’il s’agit de pénalités), meilleure elle est. Cela signifie qu’elle a la probabilité la plus élevée de voir ses chromosomes utilisés pour former de nouveaux individus (héritage). Néanmoins, ajuster un algorithme standard représente parfois un défi. En effet, vu le nombre élevé de conditions, il est facile de briser un ensemble de règles en en ajoutant une nouvelle (régression).

Les avantages de l’optimisation des services de terrain

Les tests de performance et les mises en œuvre précédentes ont démontré que cette approche est bien plus extensible que les approches classiques fondées sur des algorithmes. Elle peut être facilement adoptée par des organisations de plusieurs milliers d’employés et utilisée pour gérer le travail devant être planifié et assuré dans un laps de temps court, mais organisé en vrac. En effet, cette solution garantit aux clients de Comarch que le travail sera assuré en respectant l’ensemble des restrictions, règles et contraintes de temps. La répartition automatisée du travail soulage également les employés du service d’appui, qui ne doivent plus s’atteler à des tâches répétitives au quotidien. Grâce aux algorithmes génétiques, un nombre réduit de responsables de la répartition parvient à assister davantage de techniciens pour des tâches nécessitant des interactions humaines ou pour des cas inhabituels qui ne peuvent pas être traités par le système seul. La conclusion la plus importante sera sans doute que les AG sont capables d’analyser des quantités gigantesques de conditions (juridiques, contractuelles, physiques, etc.) et d’optimiser la planification des services mobiles ainsi que le transport des équipes mobiles de différentes manières, imaginées sur mesure pour chaque client.