SynthCharge: An Electric Vehicle Routing Instance Generator with Feasibility Screening to Enable Learning-Based Optimization and Benchmarking

Le papier présente SynthCharge, un générateur paramétrique de problèmes de routage pour véhicules électriques qui crée des instances diversifiées et vérifiées comme réalisables afin de permettre l'évaluation rigoureuse et le benchmarking des modèles d'optimisation basés sur l'apprentissage.

L'essentiel

Imaginez que vous êtes le chef d'orchestre d'une flotte de camions électriques qui doivent livrer des colis dans une grande ville. Votre mission est double : livrer tout le monde à l'heure (respecter les fenêtres de temps) et ne jamais laisser les camions tomber en panne de batterie en cours de route. C'est ce qu'on appelle le problème de routage de véhicules électriques (EVRPTW).

Le problème, c'est que pour créer des intelligences artificielles capables de résoudre ce casse-tête, les chercheurs ont besoin de milliers de scénarios d'entraînement. Mais jusqu'à présent, les "manuels d'exercices" existants étaient soit trop rigides, soit remplis d'énigmes impossibles à résoudre, ce qui rendait l'apprentissage de l'IA très difficile.

C'est là qu'intervient SynthCharge, l'outil présenté dans cet article. Voici une explication simple de ce qu'il fait, avec quelques analogies pour mieux visualiser.

1. Le Problème : Des exercices de maths "piégés"

Pensez aux anciens jeux vidéo. Parfois, le niveau est conçu de telle sorte que le joueur ne peut pas gagner, même avec les meilleures compétences, simplement parce que le niveau lui-même est cassé.
Dans le monde de la recherche, les chercheurs s'entraînaient sur des ensembles de données fixes. Si l'IA apprenait sur un type de ville très spécifique, elle échouait dès qu'on lui présentait une ville un peu différente. De plus, beaucoup de ces scénarios étaient infiniment difficiles (ou carrément impossibles) à cause de la géographie ou de la taille des batteries, ce qui faussait les résultats.

2. La Solution : SynthCharge, le "Générateur de mondes infinis"

SynthCharge est comme un architecte de jeux vidéo ultra-sophistiqué. Au lieu de donner aux chercheurs un seul niveau fixe, il peut en générer des millions, chacun étant légèrement différent.

Voici comment il fonctionne, étape par étape :

• La Géographie (Le Terrain de jeu) :
  Imaginez que vous devez placer des maisons (les clients) sur une carte. SynthCharge peut les placer de trois façons :

  • Aléatoire : Comme des gouttes de pluie tombant n'importe où.
  • Regroupée : Comme des villages dans une vallée (les maisons sont proches les unes des autres).
  • Mixte : Un mélange des deux.
    Cela permet de tester l'IA dans des environnements très différents.

• Les Bornes de Recharge (Les Stations-service) :
  C'est la partie la plus intelligente. Dans les anciens systèmes, les bornes de recharge étaient placées au hasard. Avec SynthCharge, c'est comme si l'architecte regardait la carte et disait : "Attends, ce camion ne peut pas atteindre la prochaine maison sans charger. Je vais donc placer une borne de recharge exactement à mi-chemin, là où le camion en a besoin."
  Il place les bornes de manière intelligente et réaliste, en fonction de la distance que le camion peut parcourir avec une batterie pleine.

• Le Filtre de Sécurité (Le Gardien de la réalité) :
  C'est le cœur du système. Avant de donner un scénario à l'IA, SynthCharge passe un filtre de sécurité en deux étapes :

  1. Le test rapide : Il vérifie si le scénario est théoriquement possible. "Est-ce que la maison est trop loin de la borne de recharge ? Si oui, on jette ce scénario."
  2. Le test de précision (pour les petits scénarios) : Pour les petits problèmes, il utilise un super-calculateur pour s'assurer à 100 % qu'il existe une solution.

  L'analogie : C'est comme un professeur qui ne donne un examen à un élève que s'il est sûr à 100 % que la réponse existe. Il ne perd pas de temps à demander à l'élève de résoudre une équation impossible.

3. Pourquoi c'est révolutionnaire ?

Grâce à SynthCharge, les chercheurs peuvent maintenant :

• Varié les conditions : Ils peuvent dire : "Fais-moi 1000 scénarios avec des fenêtres de temps très serrées (comme une course-poursuite)" ou "Fais-moi des scénarios avec des batteries très petites".
• Éviter les pièges : Ils savent exactement quels scénarios sont solubles et lesquels ne le sont pas.
• Entraîner des IA robustes : Au lieu d'apprendre par cœur un seul type de ville, l'IA apprend à s'adapter à n'importe quelle configuration, rendant les systèmes de livraison futurs plus intelligents et plus fiables.

En résumé

SynthCharge est une machine à créer des simulations de livraison électriques réalistes et vérifiées. Il agit comme un entraîneur personnel pour les algorithmes d'IA, leur proposant des exercices adaptés à leur niveau, en s'assurant que chaque exercice a une solution, et en variant les défis pour que l'IA devienne un champion inébranlable, prêt à gérer le chaos de la vraie ville.

C'est un outil essentiel pour passer de la théorie à la réalité, afin que demain, nos camions électriques livrent nos colis sans jamais tomber en panne et toujours à l'heure.

Résumé technique

1. Problématique

Le Problème de Routage de Véhicules Électriques avec Fenêtres de Temps (EVRPTW) est une extension complexe du problème classique VRPTW. Il intègre des contraintes spécifiques aux véhicules électriques, notamment la capacité limitée de la batterie et la nécessité de décider où et quand recharger.

Les défis majeurs identifiés par les auteurs sont :

• Manque de benchmarks dynamiques : Les jeux de données existants sont souvent statiques, limités en nombre et manquent de vérification de faisabilité, ce qui entrave l'évaluation reproductible des modèles d'optimisation basés sur l'apprentissage (RL, réseaux de neurones).
• Problème de généralisation : Les modèles d'apprentissage entraînés sur des distributions fixes de données dégradent leurs performances lors de changements de structure spatiale, de taille du problème ou de paramètres de contraintes (décalage de distribution).
• Absence de contrôle paramétrique : Les suites de benchmarks actuelles ne permettent pas de varier systématiquement les caractéristiques structurelles (géométrie, contraintes énergétiques, fenêtres de temps) pour tester la robustesse des algorithmes.

2. Méthodologie : SynthCharge

Les auteurs proposent SynthCharge, un générateur d'instances paramétrique complet conçu pour produire des problèmes EVRPTW diversifiés, géométriquement conscients et filtrés pour la faisabilité.

A. Génération d'Instances

Le générateur crée des instances basées sur les paramètres suivants :

• Topologie Spatiale : Trois familles inspirées des instances de Solomon :
  • Aléatoire (R) : Coordonnées uniformes.
  • Regroupée (C) : Centres de clusters avec distribution gaussienne.
  • Mixte (RC) : Combinaison des deux.
• Infrastructure de Recharge : Contrairement aux modèles statiques, les stations de recharge sont placées dynamiquement selon des règles conscientes de la portée (range-aware) :
  • Si la distance entre deux clients dépasse 80 % de l'autonomie maximale ($R$), une station est insérée au milieu.
  • Si un client est trop loin du dépôt (> 70 % de $R$), une station est placée à 60 % de la distance pour assurer la connectivité.
• Paramètres Énergétiques Adaptatifs : La capacité de la batterie ($B$) n'est pas fixe mais mise à l'échelle en fonction de la dispersion spatiale maximale de l'instance ($d_{max}$), garantissant que les instances restent contraintes énergétiquement mais potentiellement réalisables.
• Fenêtres de Temps : Des régimes larges, moyens et serrés sont appliqués via un paramètre de fraction de largeur ($\phi$).

B. Procédure de Filtrage de Faisabilité (Deux Étapes)

Pour garantir la validité structurelle et éviter les instances triviales ou impossibles, SynthCharge applique un filtrage en deux étapes :

1. Filtrage Structurel (Linéaire) : Vérifie les conditions nécessaires en temps $O(N)$ :
   • Chaque client doit être accessible depuis le dépôt ou une station dans la portée maximale $R$.
   • Le retour au dépôt doit être possible dans l'horizon de temps $H$.
   • Chaque client doit avoir au moins une station de recharge accessible.
   • Les instances échouant à cette étape sont rejetées et régénérées.
2. Vérification Exacte (MILP) : Pour les petites instances ($N \le 10$), un solveur de Programmation Linéaire en Nombres Entiers (MILP) vérifie l'existence d'une solution réalisable respectant toutes les contraintes de flux, de temps et d'énergie.

C. Outils et Sorties

• Interface Graphique (GUI) : Permet une configuration interactive et une visualisation en temps réel.
• Métadonnées : Chaque instance générée est accompagnée d'un fichier JSON détaillant la configuration et le statut de faisabilité.
• Taux d'Acceptation ($\gamma$) : Une métrique clé indiquant la proportion d'instances validées, servant d'indicateur de fiabilité des données.

3. Résultats Expérimentaux

Les expériences ont été menées sur des instances allant de 5 à 100 clients, avec différentes combinaisons de topologies et de contraintes temporelles.

• Taux d'Acceptation ($\gamma$) :
  • Les fenêtres de temps serrées réduisent le taux d'acceptation, particulièrement dans les régimes regroupés (C).
  • Le taux moyen varie entre ~37 % et ~47 % selon les régimes, démontrant que le filtrage élimine une part significative d'instances structurellement non réalisables.
• Efficacité de Génération :
  • Pour $N \le 10$, le temps de génération est d'environ 0,10 s (incluant la vérification MILP coûteuse).
  • Pour $N > 10$, le temps chute drastiquement (< 0,01 s) car seule la vérification structurelle linéaire est utilisée.
  • SynthCharge peut générer des milliers d'instances par heure, idéal pour l'entraînement de modèles d'apprentissage.
• Validation Pratique :
  • Une méta-heuristique de base (Recherche Voisinage Variable / Tabou) a réussi à trouver des routes réalisables pour 100 % des instances filtrées par SynthCharge, confirmant que le filtrage structurel est un excellent indicateur de faisabilité réelle.
  • L'analyse montre que le resserrement des fenêtres de temps et la dispersion spatiale augmentent linéairement la distance parcourue et la taille de la flotte nécessaire.

4. Contributions Clés

1. Infrastructure de Benchmarking Dynamique : SynthCharge comble le vide entre les benchmarks statiques et les besoins des méthodes d'apprentissage en permettant une variation systématique des paramètres (espace, temps, énergie).
2. Génération Consciente de la Faisabilité : L'intégration d'un filtrage explicite (structurel et exact) garantit que les données d'entraînement et de test sont valides, évitant le bruit dans l'évaluation des modèles.
3. Adaptation Géométrique de l'Énergie : Le couplage de la capacité de batterie avec la géométrie de l'instance empêche la génération d'instances triviales (trop faciles) ou systématiquement impossibles.
4. Transparence et Reproductibilité : La publication du code source, de la GUI et des métadonnées complètes suit les meilleures pratiques pour les jeux de données en IA (type "Datasheets for Datasets").

5. Signification et Perspectives

Ce travail est crucial pour l'avancement de l'optimisation combinatoire par apprentissage dans les systèmes de transport intelligents (ITS). En fournissant un environnement de test contrôlé et reproductible, SynthCharge permet :

• D'évaluer la robustesse des modèles de routage neuronal face aux changements de distribution.
• De développer des politiques d'apprentissage par curriculum (augmentation progressive de la complexité).
• De standardiser l'évaluation des algorithmes EVRPTW au-delà des suites de benchmarks historiques.

Limitations actuelles et travaux futurs :
Actuellement, le générateur se limite à un seul dépôt, à une géométrie euclidienne, à des temps de trajet déterministes et à une recharge complète. Les auteurs prévoient d'étendre l'outil pour inclure des dépôts multiples, des courbes de charge non linéaires, des dynamiques stochastiques et des géométries de réseaux routiers réels.