Rolling Stock Planning Using the Quantum Approximate Optimization Algorithm

Cet article présente un cadre hybride de type « divise et impera » qui reformule la planification du matériel roulant en tant que problème d'ensemble indépendant de poids maximal et évalue l'algorithme d'optimisation approximative quantique (QAOA) sur des simulateurs classiques ainsi que sur le dispositif quantique IQM Emerald, démontrant que l'augmentation de la taille des sous-graphes au sein de cette approche comble efficacement l'écart entre les méthodes de résolution approximatives et exactes.

L'essentiel

Imaginez que vous soyez le chef de file d'une immense compagnie ferroviaire. Vous avez un emploi du temps comprenant 190 trajets de train spécifiques qui doivent avoir lieu sur deux jours. Votre tâche est de déterminer quel train physique effectuera quel trajet.

Mais il y a des règles :

1. Maintenance : Chaque train doit s'arrêter dans une station spécifique (comme Hambourg) pour une vérification de 2 heures tous les quelques milliers de kilomètres.
2. Continuité : Un train ne peut pas se téléporter par magie ; il doit terminer un trajet et commencer le suivant à partir de la même station.
3. Coût : Si un train doit se déplacer sans passagers (un trajet à vide) pour rejoindre sa prochaine mission, cela coûte de l'argent (carburant, usure). Vous voulez minimiser ces kilomètres à vide.

C'est le problème de la Planification du Matériel Roulant. C'est un puzzle géant où vous devez assembler des trajets en boucles (appelées "cycles") qui partent et reviennent au même endroit, tout en respectant les règles de maintenance et en minimisant les coûts.

Le Problème : Trop de Possibilités

Le nombre de façons dont vous pouvez organiser ces trains est astronomiquement élevé. C'est comme essayer de résoudre un puzzle de Sudoku où la grille est de la taille d'un terrain de football et où les règles changent constamment. Même les superordinateurs les plus rapides peinent à trouver l'arrangement parfait pour un emploi du temps aussi vaste.

La Solution : Une Stratégie Hybride de "Diviser pour Régner"

Les auteurs proposent une astuce ingénieuse. Au lieu d'essayer de résoudre tout ce puzzle géant d'un seul coup, ils le décomposent en morceaux plus petits et gérables.

Pensez à l'organisation d'une immense bibliothèque. Au lieu d'essayer de ranger tous les livres du monde à la fois, vous :

1. Choisissez une petite section de la bibliothèque.
2. Rangez parfaitement ces livres.
3. Les placez sur l'étagère.
4. Passez à la section suivante.

Ils appellent cela un algorithme de Diviser pour Régner (Divide-and-Conquer). Ils prennent le grand problème, en extraient une petite partie (un "sous-graphe"), résolvent cette partie, puis passent à la suite.

L'Arme Secrète : Les Ordinateurs Quantiques

C'est ici que la science-fiction entre en jeu. Pour résoudre ces petites parties, ils utilisent un mélange d'ordinateurs classiques et d'un nouveau type d'ordinateur appelé Ordinateur Quantique.

• L'Ordinateur Classique : C'est comme un bibliothécaire très rapide et logique. Il peut résoudre des petits puzzles rapidement, mais il se retrouve bloqué face aux problèmes gigantesques.
• L'Ordinateur Quantique (QAOA) : Considérez cela comme un bibliothécaire "super-intuitif". Il ne se contente pas d'examiner un chemin à la fois ; il explore de nombreuses possibilités simultanément. Il utilise une méthode appelée l'Algorithme d'Optimisation Approchée Quantique (QAOA).

Les chercheurs ont testé ce bibliothécaire quantique sur une véritable machine quantique (appelée IQM Emerald) et l'ont également simulé sur un ordinateur classique.

Comment Ils l'Ont Testé

Les chercheurs ont comparé trois façons de résoudre ces petites pièces du puzzle :

1. L'Approche Gloutonne (Greedy) : Une méthode simple et rapide qui choisit l'option la plus "avantageuse" immédiatement, sans regarder plus loin. (Comme choisir le livre le plus proche sans vérifier s'il correspond au genre).
2. Le Solveur Exact : Une méthode lente et parfaite qui vérifie chaque possibilité pour trouver la réponse absolue.
3. Le Solveur Quantique (QAOA) : L'approche "intuitive" qui tente de trouver une très bonne réponse rapidement.

Ce Qu'Ils Ont Découvert

1. De plus gros morceaux sont meilleurs : Lorsqu'ils ont rendu les "petites pièces" du puzzle plus grandes, la solution globale s'est améliorée. C'est comme si, en organisant un rayon entier d'un coup plutôt qu'une seule étagère, vous pouviez voir l'ensemble du tableau et faire des choix plus intelligents.
2. Le Quantique est prometteur : Le solveur quantique (QAOA) a presque aussi bien performé que le "Solveur Exact" (qui est lent et parfait), mais beaucoup plus rapidement. Même si l'ordinateur quantique était petit et pas encore parfait, il a montré qu'il pouvait trouver des solutions de haute qualité, très proches des meilleures possibles.
3. L'étape d'Élagage (Pruning) : Parfois, l'ordinateur quantique donne une réponse désordonnée (comme suggérer que deux trains aillent au même endroit au même moment). Les auteurs utilisent un outil d'élagage pour nettoyer ces erreurs, supprimant les conflits pour rendre la solution valide.

L'Essentiel à Retenir

Ce document ne prétend pas que les ordinateurs quantiques ont déjà résolu les problèmes ferroviaires mondiaux. Au contraire, il présente une feuille de route.

Ils ont prouvé qu'en décomposant un problème massif et impossible en morceaux plus petits et en utilisant un ordinateur quantique pour résoudre ces morceaux, on peut obtenir de très bons résultats. C'est un pont entre les méthodes lentes et parfaites du passé et les méthodes rapides et puissantes du futur.

En résumé : ils ont pris un emploi du temps ferroviaire géant et désordonné, l'ont découpé, ont utilisé un ordinateur quantique pour mettre de l'ordre dans les petites parties, et ont démontré que cette approche hybride fonctionne mieux que de simplement deviner ou n'utiliser que des ordinateurs classiques.

Résumé technique

Résumé technique : Planification du matériel roulant à l'aide de l'algorithme d'optimisation quantique approximative

Définition du problème
L'article traite du problème de la planification du matériel roulant, un défi d'optimisation complexe dans la gestion ferroviaire. L'objectif est d'assigner des trains physiques à un horaire de trajets programmés tout en minimisant les coûts opérationnels, définis ici comme les « kilomètres à vide » (distance parcourue sans passagers). L'instance de problème considérée implique 190 trajets sur deux jours à travers cinq stations, soumis à des contraintes strictes :

• Opération cyclique : Chaque train doit compléter un cycle qui le ramène à sa station de départ.
• Maintenance : Chaque cycle doit inclure un arrêt de maintenance obligatoire dans une station désignée pour une durée fixe.
• Limites de distance : Les cycles ne peuvent pas dépasser une distance maximale ($l_{max}$) avant que la maintenance ne soit requise.
• Trajets à vide : Les trains peuvent effectuer des « trajets à vide » (mouvements non programmés) pour relier des trajets programmés ou atteindre des stations de maintenance, ce qui engendre un coût mais garantit la faisabilité.

Les auteurs notent que bien que le problème soit contraint, ils ne modélisent pas les contraintes de capacité du réseau (par exemple, les limites de stationnement en gare ou la congestion des voies), supposant une capacité illimitée pour le cadre de cette étude.

Méthodologie
Les auteurs proposent un algorithme hybride quantique-classique de type "diviser pour régner" pour faire face à la complexité computationnelle du problème, qui croît de manière exponentielle avec le nombre de trajets.

1. Mappage vers l'ensemble indépendant de poids maximal (MWIS) :
   Le problème est d'abord reformulé comme un problème MWIS sur un graphe.

• Nœuds : Représentent les cycles de trains réalisables générés à partir de l'horaire.
• Arêtes : Relient les nœuds si les cycles correspondants sont mutuellement incompatibles (c'est-à-dire qu'ils desservent tous deux le même trajet programmé).
• Poids : Assignés aux nœuds sur la base d'une fonction objectif heuristique ($w_i = 2d_{full} - d_{empty}$), privilégiant la couverture des trajets de passagers plutôt que la simple réduction des coûts.
• Objectif : Trouver un ensemble indépendant (un ensemble de cycles non conflictuels) ayant le poids total maximal.

2. Stratégie de génération de cycles :
   Pour gérer l'explosion des cycles possibles, les auteurs emploient un processus de génération à deux modes :

• Mode 1 : Génère des cycles en utilisant uniquement des trajets programmés (sans trajets à vide).
• Mode 2 : Activé lorsque le nombre de trajets non desservis tombe en dessous d'un seuil (40 trajets) ou lorsqu'aucun autre cycle du Mode 1 ne peut être formé. Ce mode autorise les trajets à vide, élargissant considérablement l'espace de recherche pour garantir que tous les trajets restants puissent être couverts.

3. Cadre hybride "diviser pour régner" :
   Puisque le graphe MWIS complet est trop grand pour les solveurs actuels, l'algorithme résout de manière itérative des sous-graphes plus petits :

• Sélection de sous-graphe : Une heuristique sélectionne un sous-graphe de taille $k$ (par exemple, 20 à 300 nœuds). La stratégie de sélection privilégie les cycles qui desservent le plus grand nombre de trajets complets, équilibrant la qualité de la solution et la diversité.
• Résolution du sous-graphe : Le problème MWIS sur le sous-graphe sélectionné est résolu à l'aide de diverses méthodes :
  • Solveur exact classique : Utilisé comme référence (baseline).
  • Algorithme glouton (Greedy) : Une référence classique sélectionnant les nœuds selon le ratio poids/degré.
  • QAOA (Algorithme d'optimisation quantique approximative) : Implémenté avec une profondeur $p=1$ et $p=5$. Le problème est mappé sur un Hamiltonien de type verre de spin diagonal avec un terme de pénalité pour les violations d'arêtes.
  • Échantillonnage aléatoire : Utilisé comme référence de borne inférieure.
• Élagage (Pruning) : Comme le QAOA et l'échantillonnage aléatoire peuvent produire des ensembles invalides (contenant des nœuds connectés), une procédure d'élagage supprime les nœuds ayant les plus faibles ratios poids/degré jusqu'à ce qu'un ensemble indépendant valide soit formé.
• Mise à jour globale : Les cycles sélectionnés sont ajoutés à la solution globale, et les nœuds conflictuels sont retirés du graphe global. Le processus se répète jusqu'à ce que tous les trajets soient desservis.

Résultats clés
Les auteurs ont évalué l'algorithme en utilisant une simulation classique et une exécution sur le dispositif quantique IQM Emerald.

• Comparaison des solveurs (taille de sous-graphe fixe) : Avec une petite taille de sous-graphe ($k=20$), la différence de performance entre l'algorithme glouton, les solveurs classiques exacts et le QAOA ($p=1, p=5$) était négligeable. Cependant, les résultats ont montré que le QAOA à plus grande profondeur ($p=5$) avait tendance à approcher la qualité de solution du solveur exact, malgré le fait qu'il s'agisse d'un algorithme de temps polynomial comparé au solveur exact de temps exponentiel.
• Impact de la taille du sous-graphe : Une conclusion critique fut la corrélation positive entre la taille du sous-graphe et la qualité de la solution. À mesure que la taille du sous-graphe augmentait (jusqu'à 300 nœuds), le nombre de kilomètres à vide diminuait de manière significative (pente négative avec $p \approx 10^{-9}$). Cela suggère que la résolution de sous-problèmes plus larges produit de meilleures solutions globales, même si le solveur de sous-graphe lui-même est approximatif.
• Exécution quantique : L'article rapporte des résultats issus de l'exécution du QAOA $p=1$ sur l'ordinateur quantique IQM Emerald, démontrant la faisabilité de l'exécution de l'algorithme sur le matériel actuel, bien que la qualité de la solution soit comparable à la simulation classique et à l'échantillonnage aléatoire pour les paramètres testés.

Signification et affirmations
L'article positionne ses travaux comme une voie pratique pour appliquer les ordinateurs quantiques de l'ère NISQ (Near-term Intermediate-Scale Quantum) à des problèmes d'optimisation industriels réalistes, avant que le matériel ne soit capable de résoudre directement le problème complet.

• Combler le fossé : Le cadre hybride comble efficacement le fossé entre les solveurs rapides et approximatifs de temps polynomial (comme les algorithmes gloutons) et les méthodes exactes lentes de temps exponentiel.
• Scalabilité : Les auteurs soutiennent que leur approche permet aux algorithmes quantiques d'être appliqués à des sous-problèmes compatibles avec les limitations matérielles actuelles, tandis qu'une boucle externe classique orchestre l'optimisation globale.
• Potentiel d'avantage quantique : Les résultats suggèrent un scénario où la profondeur de l'algorithme QAOA ($p$) n'a besoin de croître que de manière polynomiale avec la taille du sous-graphe pour atteindre des solutions approximativement optimales, offrant un potentiel d'avantage quantique par rapport aux méthodes classiques exactes pour les instances à grande échelle.
• Modestie : Les auteurs reconnaissent les limites, notant que l'étape actuelle de génération de cycles est un goulot d'étranglement pour les horaires plus vastes et que l'efficacité de la procédure d'élagage peut se dégrader à mesure que la taille des sous-graphes augmente. Ils ne prétendent pas que le QAOA surpasse actuellement les solveurs classiques exacts sur le problème complet, mais plutôt que l'architecture hybride permet l'exploration d'espaces de solutions plus vastes que ce qui était possible auparavant avec les seules ressources quantiques.