Approche innovante pour la conception de réseaux de transport

Les agences de transit partout dans le monde font face à des coupes budgétaires. Pour continuer à offrir un service de qualité tout en économisant de l'argent, elles doivent concevoir des réseaux de transit de manière efficace. Cependant, planifier les itinéraires de transport public est un vrai casse-tête. Les meilleures méthodes jusqu'ici utilisent des algorithmes qui examinent différentes options en faisant de petits changements aléatoires dans les itinéraires. La manière dont ces petits changements sont conçus peut grandement influencer le résultat final. Dans ce travail, on applique l'apprentissage profond avec des réseaux neuronaux graphiques pour apprendre à faire ces petits changements automatiquement, au lieu de le faire à la main. Cette nouvelle méthode montre de meilleurs résultats lorsqu'elle est testée sur des villes échantillons avec beaucoup de nœuds, et elle performe exceptionnellement bien en réduisant les coûts d'exploitation. Elle a aussi amélioré une simulation du vrai réseau de transit à Laval, au Canada, de manière significative et a réussi à économiser sur les coûts par rapport au système existant.

#Remerciements

On remercie la Société de transport de Laval pour avoir fourni des cartes et des données de transport, et l'Agence métropolitaine de transport du Québec pour les ensembles de données nécessaires. Ces données étaient cruciales pour nos expériences. On remercie aussi notre agence de financement pour le soutien. De plus, on est reconnaissant à un des colocataires de l'auteur pour avoir partagé des idées et donné des retours sur nos conceptions.

#Contexte et défis

La pandémie de COVID-19 a causé une chute du nombre de personnes utilisant le transit dans les villes du monde entier. Cette situation a créé une crise financière pour de nombreuses agences de transit, les poussant à chercher à réduire les coûts de leurs services. Si la réduction des coûts entraîne une baisse de la qualité du service, ça pourrait décourager encore plus de gens d'utiliser le transit, créant un cycle de service réduit et de revenus en baisse. Les agences doivent faire plus de travail avec moins de ressources. Cela rend la configuration des réseaux de transit très importante, puisque une bonne planification peut économiser de l'argent tout en fournissant un service décent. Cependant, changer un réseau de transit n'est pas à prendre à la légère. Pour les systèmes ferroviaires, ça peut nécessiter des changements étendus, ce qui peut être trop coûteux. Même pour les systèmes de bus, redessiner les itinéraires peut être coûteux et perturbant. Ainsi, il est crucial pour les agences de transit d'obtenir les conceptions de leur réseau correctement du premier coup. De bons algorithmes pour concevoir des réseaux de transit peuvent être très utiles à cet égard.

#Le problème de conception du réseau de transit

Le problème de conception du réseau de transit (NDP) concerne la planification d'un ensemble d'itinéraires de transport pour une ville qui répondent à des objectifs spécifiques, comme satisfaire tous les besoins de déplacement tout en maintenant les coûts d'exploitation bas. C'est un problème complexe et difficile. En raison de la nature des villes réelles, qui ont souvent de nombreux points d'arrêt potentiels, les approches d'optimisation traditionnelles ne sont pas pratiques. Donc, les méthodes les plus réussies pour traiter le NDP jusqu'à présent ont été des algorithmes métaheuristiques. Ces algorithmes appliquent différentes règles simples qui apportent des modifications aléatoires à un réseau, guidant la recherche de meilleurs réseaux sur de nombreuses itérations en utilisant un processus semblable à la sélection naturelle.

Différentes approches ont été suggérées pour guider cette recherche, et de nombreuses règles simples, spécifiquement taillées pour la conception de réseaux de transit, ont été proposées. Bien que ces algorithmes puissent donner de bons résultats dans de nombreux cas, la plupart des réseaux de transit réels sont encore conçus manuellement.

Ces règles simples modifient le réseau de différentes manières : certaines pourraient supprimer aléatoirement des arrêts d'un itinéraire, tandis que d'autres pourraient ajouter un arrêt à chaque extrémité d'un itinéraire, ou échanger deux arrêts sur un itinéraire. La plupart de ces règles simples sont assez aléatoires, ce qui signifie qu'elles ne tiennent pas compte de détails spécifiques sur la ville ou le réseau lors de la décision du changement à apporter. On veut savoir si un système d'apprentissage automatique pourrait agir comme une règle plus intelligente, apprenant à utiliser les informations sur la ville et le réseau de transit actuel pour faire les meilleurs changements.

Dans des travaux précédents, on a entraîné un réseau neuronal pour créer un réseau de transit à partir de zéro, démontrant que cette méthode améliorait la qualité des réseaux lorsqu'elle était associée à deux algorithmes métaheuristiques. Cela impliquait de générer des itinéraires en reliant les chemins les plus courts dans le réseau routier d'une ville, et d'utiliser le réseau neuronal pour choisir quel chemin ajouter ensuite. En répétant cela, on pouvait assembler un réseau de transit complet.

Dans des recherches continues, on a exploré si notre réseau neuronal pouvait améliorer un algorithme métaheuristique en servant de règle simple apprise. Pour tester cela, on a adapté un algorithme évolutif existant en remplaçant une de ses règles standards par une qui utilise le réseau neuronal pour planifier un nouvel itinéraire.

Les résultats ont montré des améliorations considérables en performance pour les villes avec de nombreux nœuds (70 ou plus).

#Approfondissement des résultats

Dans ce travail, on s'appuie sur ces découvertes de plusieurs manières. On présente de nouveaux résultats obtenus avec un modèle de réseau neuronal mis à jour et une nouvelle version de l'algorithme évolutif. On effectue aussi des études pour évaluer l'importance de différentes parties de notre approche combinée neuronale-évolutive. Certaines de ces études impliquent une nouvelle règle simple non apprise, où des chemins avec des points d'arrêt communs sont liés au hasard au lieu de suivre les conseils du réseau neuronal. Fait intéressant, en se concentrant strictement sur la minimisation du temps de trajet des passagers, cette règle non apprise a surpassé à la fois les règles traditionnelles et notre règle de réseau neuronal. Cependant, dans la plupart des autres cas, notre règle de réseau neuronal a donné de meilleurs résultats.

On compare les résultats de nos règles apprises et non apprises avec d'autres découvertes sur des villes étalon standard. On constate que la règle non apprise obtient des résultats similaires aux meilleures méthodes connues lorsqu'elle se concentre uniquement sur la minimisation du temps de trajet des passagers, tandis que notre règle de réseau neuronal dépasse les meilleures méthodes précédentes jusqu'à 13 % en minimisant les Coûts opérationnels.

Enfin, on va au-delà de nos travaux précédents en appliquant nos règles à des données réelles de Laval, au Canada, un cas réel significatif. Nos découvertes montrent que notre règle apprise peut être utilisée pour concevoir des réseaux de transit pour Laval qui surpassent le système de transit actuel de la ville dans des simulations sur trois objectifs d'optimisation. Ces résultats indiquent que les règles apprises pourraient permettre aux agences de transit d'offrir un meilleur service à moindre coût.

#Contexte et travaux connexes

#Apprentissage profond et problèmes d'optimisation

L'apprentissage profond consiste à utiliser des méthodes d'apprentissage automatique qui comportent des réseaux neuronaux artificiels profonds-ceux avec plusieurs couches cachées. Lorsqu'il est combiné avec l'apprentissage par renforcement (RL), une branche de l'apprentissage automatique où un système fait des choix et reçoit des récompenses numériques, il peut maximiser la récompense totale à travers diverses actions. Il y a un intérêt croissant pour l'application de l'apprentissage profond, et plus spécifiquement du RL profond, à des problèmes d'optimisation combinatoire comme le Problème du Voyageur de Commerce (TSP).

Des chercheurs ont proposé différents modèles, tels que les Réseaux de Pointeurs, formés par apprentissage supervisé pour résoudre des instances de TSP. D'autres études ont construit sur ces découvertes, utilisant des modèles de réseaux neuronaux similaires avec des algorithmes RL pour créer des solutions pour le TSP et d'autres défis d'optimisation. Certaines études récentes ont formé des réseaux neuronaux récurrents pour générer des populations de solutions initiales pour un algorithme génétique, améliorant encore le processus d'entraînement.

Ces méthodes tombent généralement sous les méthodes de "construction" qui commencent avec une solution vide et se construisent dessus, tandis que les méthodes d'"amélioration" modifient des solutions complètes pour rechercher de meilleures options. Les algorithmes évolutifs appartiennent à cette catégorie et peuvent être coûteux en termes de calcul, mais produisent souvent de meilleurs résultats. Certains travaux ont formé des réseaux neuronaux à sélectionner des mouvements dans des méthodes d'amélioration, montrant des performances impressionnantes sur le TSP et des problèmes similaires. Dans ce contexte, notre travail entraîne un réseau neuronal pour aborder le problème de conception du réseau de transit, puis l'utilise pour améliorer des solutions dans une méthode d'amélioration.

Dans la plupart de cette recherche, les modèles de réseaux neuronaux utilisés sont des réseaux neuronaux graphiques, conçus pour travailler avec des données de type graphique. Ces modèles ont trouvé des applications dans divers domaines, y compris l'analyse de grands graphes web, la conception de circuits imprimés, et la prédiction des propriétés moléculaires. Étant donné que le problème de conception du réseau de transit peut être décrit comme un problème graphique, on utilise aussi des modèles de réseaux neuronaux graphiques.

#Optimisation du transport public

Le problème de conception du réseau de transit est NP-complet, ce qui signifie que trouver des solutions optimales est impraticable dans la plupart des cas. Bien que les techniques d'optimisation analytiques aient fonctionné sur de petites instances, elles luttent souvent pour représenter la réalité du problème. Par conséquent, les approches métaheuristiques ont gagné en popularité.

Les métaheuristiques largement utilisées pour le NDP incluent les algorithmes génétiques, le recuit simulé et l'optimisation par colonies de fourmis. Des travaux récents ont montré du succès avec d'autres métaheuristiques comme les hyper-métaheuristiques, la recherche en faisceau et les essaims de particules. De nombreuses règles de bas niveau sont utilisées dans ces algorithmes métaheuristiques, mais la plupart sélectionnent parmi les options possibles uniformément au hasard.

Une exception existe où des auteurs ont conçu un modèle simple pour examiner comment chaque changement pourrait impacter la qualité. Cependant, ce modèle simple néglige les trajets des passagers impliquant des correspondances et les préférences des utilisateurs. En revanche, notre méthode apprend un modèle pour évaluer ces impacts tout en prenant en compte un ensemble d'entrées plus riche.

Bien que les réseaux neuronaux aient souvent été employés pour des problèmes prédictifs dans la mobilité urbaine, leur application au NDP reste limitée, tout comme l'apprentissage par renforcement. Deux exemples récents ont utilisé le RL pour la conception d'itinéraires sur une petite ville étalon avec seulement quelques arrêts de transit. Cependant, ces méthodes ne s'adaptent pas bien à des instances plus larges. Notre approche peut trouver de bonnes solutions pour des cas plus larges de NDP, dépassant 600 nœuds, et peut être utilisée pour des instances non vues.

#Formulation du problème

On définit le problème de conception du réseau de transit en termes d'un graphe de ville avec une collection de nœuds et d'arêtes. Chaque nœud représente des arrêts de transit potentiels, tandis que les arêtes les relient avec des poids indiquant les temps de trajet. L'objectif est d'offrir un réseau de transit qui répond à la demande de déplacement tout en se concentrant sur la minimisation des coûts.

Le réseau doit connecter les paires de demande tout en maintenant un nombre défini d'itinéraires tout en respectant des contraintes comme les limites d'arrêts et en évitant les cycles. On se concentre sur le NDP symétrique, ce qui signifie que toutes les demandes et itinéraires fonctionnent de manière égale dans les deux sens.

#Formulation du processus de décision de Markov

Un processus de décision de Markov (MDP) offre un moyen de définir des problèmes de RL. Un agent interagit avec un environnement sur diverses étapes de temps. À chaque étape de temps, l'environnement est dans un état particulier, et l'agent choisit des actions qui mènent à de nouveaux états, recevant des récompenses en fonction des actions effectuées. Dans notre approche MDP au NDP, l'état consiste en des itinéraires complétés et un itinéraire en cours de conception. L'agent alterne entre l'extension de cet itinéraire ou décider d'arrêter l'itinéraire.

#Fonction de coût

Notre fonction de coût NDP a plusieurs parties. Le premier composant représente le temps moyen que les passagers passent à voyager à travers le réseau, tandis que le deuxième composant tient compte du temps total de conduite des itinéraires. La troisième partie garantit que les contraintes sont respectées en comptant la fraction des paires de demande qui restent non connectées. De cette façon, la fonction de coût équilibre les coûts des passagers et d'exploitation tout en permettant des ajustements.

#Apprendre à construire un réseau

On entraîne un réseau neuronal graphique à maximiser le retour cumulatif dans notre formulation MDP. En appliquant cette politique apprise parmi une ville, on peut générer des réseaux de transit, que l'on appelle "construction apprise." En le faisant plusieurs fois, on peut obtenir divers réseaux, ce qui nous permet de choisir celui avec le coût le plus bas.

La partie centrale du réseau de politique est un réseau d'attention graphique qui traite la ville comme un graphe entièrement connecté. Chaque nœud et arête contient des informations pertinentes sur la localisation, la demande et les connexions de transit existantes. La sortie consiste en des embeddings de nœuds qui informent la décision de choisir parmi les extensions ou d'arrêter la construction.

L'entraînement de la politique implique de faire tourner des épisodes à travers des villes synthétiques. Chaque ville est générée aléatoirement, tandis que les paramètres restent constants pendant l'entraînement, permettant au réseau neuronal d'apprendre de divers scénarios.

#Algorithme évolutif

On évalue si notre politique apprise peut servir efficacement comme une règle de bas niveau dans un algorithme métaheuristique. L'algorithme évolutif de base fonctionne sur une population de solutions, alternant entre les phases de mutation et de sélection. Pour la phase de mutation, on applique deux types de mutateurs à des sous-ensembles choisis au hasard de la population. Si le réseau muté performe mieux que son prédécesseur, il remplace le réseau parent.

Notre algorithme évolutif neuronal modifie cela en utilisant notre politique apprise à la place de l'un des mutateurs standards. Cette approche permet des changements plus avancés, encourageant de meilleures solutions grâce à la combinaison d'heuristiques existantes et apprises.

#Expériences et résultats

On évalue notre méthode sur divers ensembles de données de référence, y compris les villes de Mandl et Mumford. Chaque ville présente des paramètres distincts, et chaque expérience tourne plusieurs itérations pour recueillir des résultats robustes. L'algorithme évolutif neuronal est mis en concurrence avec l'approche évolutive de base pour déterminer son efficacité.

#Comparaison avec l'algorithme de base

Dans nos expériences, l'algorithme évolutif neuronal obtient des résultats significativement meilleurs, notamment dans les grandes villes. Les améliorations deviennent plus prononcées à mesure que les villes grandissent, avec des améliorations distinctes tant dans les coûts opérationnels que dans les temps de trajet des passagers.

#Études d'ablation

Pour améliorer notre compréhension de chaque composant de l'algorithme, on réalise des études d'ablation pour analyser l'impact de diverses parties de notre système. Cela inclut la comparaison de notre mutateur neuronal avec une version sans lui, afin de nous aider à évaluer sa contribution à la performance globale.

#Application à des scénarios réels

On applique notre approche à des données de Laval, Canada, pour évaluer son efficacité dans un cadre réel. Le graphe de rue dérive de diverses sources, y compris des données géographiques, des réseaux de transit existants et des matrices de demande. Chacun de ces composants informe notre conception tout en s'assurant que le nouveau réseau connecte tous les trajets de passagers nécessaires.

#Résultats à Laval

Nos expériences montrent que la politique apprise peut développer des réseaux à Laval qui surpassent le système de transit actuel, réduisant significativement les temps d'exploitation et améliorant l'expérience des passagers. Les résultats indiquent des économies potentielles pour l'agence de transit tout en améliorant la qualité du service.

#Conclusion

Cette recherche démontre qu'utiliser l'Apprentissage par renforcement profond pour apprendre des heuristiques peut améliorer considérablement la conception de réseaux de transit par rapport aux méthodes traditionnelles. L'approche permet aux agences de transit d'atteindre un meilleur service à coût réduit, prouvant son utilité dans des scénarios réels. À l'avenir, explorer différentes algorithmes métaheuristiques et affiner le processus d'apprentissage pourrait engendrer des améliorations encore plus grandes dans la conception et la performance des réseaux.