Innovativer Ansatz für die Gestaltung von Verkehrnetzen

Verkehrsunternehmen überall stehen vor Haushaltskürzungen. Um weiterhin guten Service zu bieten und gleichzeitig Geld zu sparen, müssen sie die Verkehrsnetze effizient gestalten. Allerdings ist die Planung von öffentlichen Verkehrswegen eine knifflige Aufgabe. Die besten Methoden bis jetzt nutzen Algorithmen, um verschiedene Optionen durch kleine zufällige Veränderungen an den Routen zu durchsuchen. Die Art und Weise, wie diese kleinen Veränderungen gestaltet werden, kann das Endergebnis stark beeinflussen. In dieser Arbeit wenden wir Deep Learning mit graphbasierten neuronalen Netzwerken an, um automatisch herauszufinden, wie man diese kleinen Änderungen vornimmt, anstatt sie von Hand zu machen. Diese neue Methode zeigt bessere Ergebnisse, wenn sie an Musterstädten mit vielen Knoten getestet wird, und sie schneidet bei der Senkung der Betriebskosten aussergewöhnlich gut ab. Sie verbessert auch eine Simulation des realen Verkehrsnetzes in Laval, Kanada, um einen grossen Prozentsatz und schafft es, Kosten im Vergleich zum bestehenden System zu sparen.

#Danksagungen

Wir schätzen die Hilfe der Laval Transport Society, die Karten- und Verkehrsdaten bereitgestellt hat, sowie der Metropolitan Transport Agency of Quebec, die die notwendigen Datensätze zur Verfügung gestellt hat. Diese Daten waren entscheidend für unsere Experimente. Wir danken auch unserer Förderagentur für die Unterstützung. Ausserdem sind wir einem Mitbewohner eines Autors dankbar, der Ideen geteilt und Feedback zu unseren Entwürfen gegeben hat.

#Kontext und Herausforderungen

Die COVID-19-Pandemie hat zu einem Rückgang der Anzahl der Menschen geführt, die in Städten weltweit öffentliche Verkehrsmittel nutzen. Diese Situation hat eine Finanzkrise für viele Verkehrsunternehmen verursacht, die das Gefühl haben, die Betriebskosten für Verkehrsleistungen senken zu müssen. Wenn Kostensenkungen zu einem Rückgang der Servicequalität führen, könnte das dazu führen, dass weniger Menschen öffentliche Verkehrsmittel nutzen wollen, was einen Kreislauf aus reduziertem Service und Einkommen schafft. Die Unternehmen müssen mehr Arbeit mit weniger Ressourcen leisten. Das macht die Gestaltung von Verkehrsnetzen sehr wichtig, da gute Planung Geld sparen kann, während sie trotzdem decenten Service bietet. Allerdings ist die Änderung eines Verkehrsnetzes keine leichte Aufgabe. Bei Schienensystemen kann es umfangreiche Veränderungen erfordern, die zu teuer sein können. Selbst bei Bussystemen kann die Neugestaltung von Routen kostspielig und störend sein. Daher ist es entscheidend, dass Verkehrsunternehmen ihre Netzdesigns beim ersten Mal richtig machen. Gute Algorithmen zur Gestaltung von Verkehrsnetzen können dabei sehr hilfreich sein.

#Das Problem der Verkehrsnetzgestaltung

Das Problem der Verkehrsnetzgestaltung (NDP) beschäftigt sich mit der Planung einer Reihe von Verkehrswegen für eine Stadt, die spezifische Ziele erfüllt, wie alle Verkehrsbedürfnisse zu bedienen und gleichzeitig die Betriebskosten niedrig zu halten. Dies ist ein komplexes, herausforderndes Problem. Aufgrund der Natur realer Städte, die oft viele potenzielle Haltepunkte haben, sind traditionelle Optimierungsansätze nicht praktikabel. Daher waren die erfolgreichsten Methoden zur Bewältigung des NDP bisher metahurstische Algorithmen. Diese Algorithmen wenden verschiedene einfache Regeln an, die zufällige Veränderungen an einem Netzwerk vornehmen und die Suche nach besseren Netzwerken über viele Iterationen durch einen Prozess wie natürliche Selektion leiten.

Es wurden verschiedene Ansätze vorgeschlagen, um diese Suche zu leiten, und zahlreiche einfache Regeln, die speziell für die Gestaltung von Verkehrsnetzen entwickelt wurden, wurden vorgeschlagen. Während diese Algorithmen in vielen Fällen gute Ergebnisse liefern können, werden die meisten realen Verkehrsnetze immer noch manuell entworfen.

Diese einfachen Regeln ändern das Netzwerk auf unterschiedliche Weise: Einige könnten zufällig Haltestellen von einer Route entfernen, während andere eine Haltestelle an einem Ende einer Route hinzufügen oder zwei Haltestellen auf einer Route austauschen könnten. Die meisten dieser einfachen Regeln sind ziemlich zufällig, was bedeutet, dass sie keine spezifischen Details über die Stadt oder das Netzwerk berücksichtigen, wenn sie entscheiden, welche Änderung vorzunehmen ist. Wir wollen herausfinden, ob ein Machine-Learning-System als intelligenterer Regel wirken könnte, indem es lernt, Informationen über die Stadt und das aktuelle Verkehrsnetz zu nutzen, um die besten Änderungen vorzunehmen.

In früheren Arbeiten haben wir ein neuronales Netzwerk trainiert, um ein Verkehrsnetz von Grund auf zu erstellen, was gezeigt hat, dass diese Methode die Qualität von Netzwerken verbessert, wenn sie mit zwei metahurstischen Algorithmen kombiniert wird. Dies beinhaltete das Generieren von Routen, indem die kürzesten Wege im Strassennetz einer Stadt verbunden werden, und das Verwenden des neuronalen Netzwerks, um zu entscheiden, welchen Weg man als Nächstes hinzufügen soll. Indem wir dies wiederholt gemacht haben, konnten wir ein vollständiges Verkehrsnetz zusammensetzen.

In fortlaufenden Forschungen haben wir untersucht, ob unser neuronales Netzwerk einen metahurstischen Algorithmus verbessern könnte, indem es als gelernte einfache Regel fungiert. Um dies zu testen, haben wir einen bestehenden evolutionären Algorithmus angepasst, indem wir eine seiner Standardregeln durch eine ersetzt haben, die das neuronale Netzwerk zur Planung einer neuen Route verwendet.

Die Ergebnisse zeigten erhebliche Verbesserungen in der Leistung für Städte mit vielen Knoten (70 oder mehr).

#Erweiterung der Ergebnisse

In dieser Arbeit bauen wir in mehreren Aspekten auf diesen Erkenntnissen auf. Wir präsentieren neue Ergebnisse, die mit einem aktualisierten Modell des neuronalen Netzwerks und einer neuen Version des evolutionären Algorithmus erzielt wurden. Ausserdem führen wir Studien durch, um die Bedeutung verschiedener Teile unseres kombinierten neuronalen-evolutionären Ansatzes zu bewerten. Einige dieser Studien beinhalten eine neue, nicht gelernte einfache Regel, bei der Wege mit gemeinsamen Endpunkten zufällig verknüpft werden, anstatt der Anleitung des neuronalen Netzwerks zu folgen. Interessanterweise hat diese nicht gelernte Regel bei der ausschliesslichen Fokussierung auf die Minimierung der Reisezeit der Passagiere sowohl die traditionellen Regeln als auch unsere neuronale Netzwerkregel übertroffen. In den meisten anderen Fällen lieferte jedoch unsere neuronale Netzwerkregel bessere Ergebnisse.

Wir vergleichen die Ergebnisse unserer gelernten und nicht gelernten Regeln mit anderen Ergebnissen auf Standard-Benchmark-Städten. Wir stellen fest, dass die nicht gelernte Regel Ergebnisse erzielt, die den besten bekannten Methoden ähnlich sind, wenn der Fokus rein auf der Minimierung der Reisezeit der Passagiere liegt, während unsere neuronale Netzwerkregel die vorherigen besten Methoden um bis zu 13% übertrifft, wenn es um die Minimierung der Betriebskosten geht.

Schliesslich gehen wir über unsere frühere Arbeit hinaus, indem wir unsere Regeln auf echte Daten aus Laval, Kanada anwenden, einem bedeutenden realen Fall. Unsere Erkenntnisse zeigen, dass unsere gelernte Regel verwendet werden kann, um Verkehrsnetze für Laval zu entwerfen, die das derzeitige Verkehrssystem der Stadt in Simulationen über drei Optimierungsziele übertreffen. Diese Ergebnisse deuten darauf hin, dass gelernte Regeln den Verkehrsunternehmen ermöglichen könnten, besseren Service zu niedrigeren Kosten zu bieten.

#Hintergrund und verwandte Arbeiten

#Deep Learning und Optimierungsprobleme

Deep Learning umfasst die Verwendung von Machine-Learning-Methoden, die tiefe künstliche neuronale Netzwerke beinhalten - also solche mit mehreren versteckten Schichten. Wenn sie mit Reinforcement Learning (RL) kombiniert werden, einem Zweig des Machine Learning, bei dem ein System Entscheidungen trifft und numerische Belohnungen erhält, kann es die Gesamtrückzahlung durch verschiedene Aktionen maximieren. Es gibt ein deutliches Interesse an der Anwendung von Deep Learning, insbesondere von Deep RL, auf kombinatorische Optimierungsprobleme wie das Traveling-Salesman-Problem (TSP).

Forschende haben verschiedene Modelle vorgeschlagen, wie Pointer Networks, die durch überwachtes Lernen trainiert werden, um TSP-Fälle zu lösen. Andere Studien haben auf diesen Erkenntnissen aufgebaut und ähnliche neuronale Netzwerkmodelle mit RL-Algorithmen eingesetzt, um Lösungen für TSP und andere Optimierungsherausforderungen zu schaffen. Einige neuere Studien haben rekursive neuronale Netzwerke trainiert, um Anfangspopulationen für einen genetischen Algorithmus zu generieren, was den Trainingsprozess weiter verbessert.

Diese Methoden fallen normalerweise unter „Konstruktionsmethoden“, die mit einer leeren Lösung beginnen und auf ihr aufbauen, während „Verbesserungsmethoden“ abgeschlossene Lösungen modifizieren, um nach besseren Optionen zu suchen. Evolutionäre Algorithmen gehören zu dieser Kategorie und können rechnerisch kostspielig sein, erzielen jedoch oft bessere Ergebnisse. Einige Arbeiten haben neuronale Netzwerke trainiert, um Züge in Verbesserungsmethoden auszuwählen, was beeindruckende Leistungen beim TSP und ähnlichen Problemen demonstriert. In diesem Kontext trainieren wir ein neuronales Netzwerk, um sich dem Problem der Verkehrsnetzgestaltung zu nähern, und verwenden es dann, um Lösungen innerhalb einer Verbesserungsmethode zu verbessern.

In den meisten dieser Forschungen sind die verwendeten neuronalen Netzwerkmodelle graphbasierte neuronale Netzwerke, die für die Arbeit mit grafisch strukturierten Daten entwickelt wurden. Diese Modelle haben Anwendung in verschiedenen Bereichen gefunden, darunter die Analyse grosser Webgraphen, die Schaltungsgestaltung und die Vorhersage molekularer Eigenschaften. Da das Problem der Verkehrsnetzgestaltung als ein Graphproblem beschrieben werden kann, verwenden wir ebenfalls graphbasierte neuronale Netzwerkmodelle.

#Optimierung des öffentlichen Verkehrs

Das Problem der Verkehrsnetzgestaltung ist NP-vollständig, was bedeutet, dass die Suche nach optimalen Lösungen in den meisten Fällen unpraktisch ist. Während analytische Optimierungstechniken bei kleinen Fällen funktioniert haben, kämpfen sie oft mit einer realistischen Darstellung des Problems. Daher haben metahurstische Ansätze an Bedeutung gewonnen.

Zu den weit verbreiteten Metahurstiken für das NDP gehören genetische Algorithmen, simuliertes Annealing und Ant Colony Optimization. Neuere Arbeiten haben auch Erfolge mit anderen Metahurstiken wie Hyperheuristiken, Beam Search und Partikelschwärmen gezeigt. Zahlreiche niedrigstufige Regeln werden in diesen metahurstischen Algorithmen verwendet, aber die meisten wählen aus möglichen Optionen gleichmässig zufällig aus.

Eine Ausnahme bilden Autoren, die ein einfaches Modell entwarfen, um zu prüfen, wie sich jede Veränderung auf die Qualität auswirken könnte. Dieses einfache Modell übersieht jedoch Fahrten der Passagiere, die Umstiege beinhalten, und Nutzerpräferenzen. Im Gegensatz dazu lernt unsere Methode ein Modell, um diese Auswirkungen zu bewerten, während sie einen umfangreicheren Satz von Eingaben berücksichtigt.

Während neuronale Netzwerke oft für prädiktive Probleme in der städtischen Mobilität eingesetzt wurden, bleibt ihre Anwendung auf das NDP begrenzt, ebenso wie Reinforcement Learning. Zwei neuere Beispiele haben RL für die Routenplanung in einer kleinen Benchmarkstadt mit nur wenigen Haltestellen genutzt. Diese Methoden passen sich jedoch nicht gut an grössere Fälle an. Unser Ansatz kann gute Lösungen für grössere NDP-Fälle finden, die mehr als 600 Knoten umfassen, und kann für bisher unbekannte Fälle genutzt werden.

#Problemformulierung

Wir definieren das Problem der Verkehrsnetzgestaltung in Bezug auf einen Stadtgraphen mit einer Sammlung von Knoten und Kanten. Jeder Knoten stellt potenzielle Haltestellen dar, während die Kanten sie mit Gewichten verbinden, die Reisezeiten angeben. Das Ziel ist es, ein Verkehrsnetz anzubieten, das die Reisebedürfnisse erfüllt und dabei die Kosten minimiert.

Das Netzwerk muss Nachfragepaare verbinden und gleichzeitig eine festgelegte Anzahl von Routen aufrechterhalten, während es Einschränkungen wie Haltestellenlimits einhält und Zyklen vermeidet. Wir konzentrieren uns auf symmetrisches NDP, was bedeutet, dass alle Anforderungen und Routen in beiden Richtungen gleich funktionieren.

#Formulierung des Markov-Entscheidungsprozesses

Ein Markov-Entscheidungsprozess (MDP) bietet eine Möglichkeit, RL-Probleme zu definieren. Ein Agent interagiert über verschiedene Zeitstufen mit einer Umgebung. Zu jedem Zeitpunkt befindet sich die Umgebung in einem bestimmten Zustand, und der Agent wählt Aktionen, die zu neuen Zuständen führen, wobei er basierend auf den getroffenen Entscheidungen Belohnungen erhält. In unserem MDP-Ansatz zum NDP besteht der Zustand aus abgeschlossenen Routen und einer Route, die derzeit entworfen wird. Der Agent wechselt zwischen dem Vergrössern dieser Route oder der Entscheidung, die Route zu beenden.

#Kostenfunktion

Unsere NDP-Kostenfunktion hat mehrere Komponenten. Die erste Komponente stellt die durchschnittliche Zeit dar, die Passagiere im Netzwerk verbringen, während die zweite Komponente die gesamte Fahrzeit der Routen berücksichtigt. Der dritte Teil stellt sicher, dass die Einschränkungen respektiert werden, indem der Anteil der Nachfragepaare gezählt wird, die unverbunden bleiben. Auf diese Weise balanciert die Kostenfunktion die Passagier- und Betriebskosten, während sie Anpassungen ermöglicht.

#Lernen, ein Netzwerk zu konstruieren

Wir trainieren ein graphbasiertes neuronales Netzwerk, um die kumulative Rendite innerhalb unserer MDP-Formulierung zu maximieren. Durch die Anwendung dieser gelernten Strategie in einer Stadt können wir Verkehrsnetze generieren, die wir "gelernte Konstruktion" nennen. Mehrmaliges Ausführen hilft uns, verschiedene Netzwerke zu erhalten, sodass wir das mit den niedrigsten Kosten auswählen können.

Der zentrale Teil des Strategienetzwerks ist ein Graph-Attention-Netzwerk, das die Stadt als vollständig verbundenen Graph betrachtet. Jeder Knoten und jede Kante enthält relevante Informationen über den Standort, die Nachfrage und bestehende Verkehrsverbindungen. Die Ausgabe besteht aus Knoten-Embeddings, die die Entscheidung informieren, zwischen Erweiterungen zu wählen oder die Konstruktion abzubrechen.

Das Training der Strategie beinhaltet das Durchführen von Episoden in synthetischen Städten. Jede Stadt wird zufällig generiert, während die Parameter während des Trainings konstant gehalten werden, was dem neuronalen Netzwerk ermöglicht, aus verschiedenen Szenarien zu lernen.

#Evolutionärer Algorithmus

Wir prüfen, ob unsere gelernte Strategie effektiv als niedere Regel innerhalb eines metahurstischen Algorithmus dienen kann. Der Basis-evolutionäre Algorithmus funktioniert auf einer Population von Lösungen und wechselt zwischen Mutations- und Auswahlphasen. Für die Mutationsphase wenden wir zwei Arten von Mutatoren auf zufällig ausgewählte Teilmengen der Population an. Wenn das mutierte Netzwerk besser abschneidet als sein Vorgänger, ersetzt es das Elternnetzwerk.

Unser neuronaler evolutionärer Algorithmus modifiziert dies, indem er unsere gelernte Strategie anstelle eines der Standardmutatoren verwendet. Dieser Ansatz ermöglicht fortschrittlichere Veränderungen und fördert bessere Lösungen durch die Kombination bestehender und gelernter Heuristiken.

#Experimente und Ergebnisse

Wir bewerten unsere Methode an verschiedenen Benchmark-Datensätzen, einschliesslich Mandl- und Mumford-Städten. Jede Stadt weist unterschiedliche Parameter auf, und jedes Experiment läuft mehrere Iterationen, um robuste Ergebnisse zu sammeln. Der neuronale evolutionäre Algorithmus wird gegen den Basis-evolutionären Ansatz getestet, um seine Wirksamkeit zu bestimmen.

#Vergleich mit dem Basisalgorithmus

In unseren Experimenten erzielt der neuronale evolutionäre Algorithmus deutlich bessere Ergebnisse, insbesondere in grösseren Städten. Die Verbesserungen werden ausgeprägter, je grösser die Städte werden, mit deutlichen Verbesserungen sowohl bei den Betriebskosten als auch bei den Reisezeiten der Passagiere.

#Ablationsstudien

Um unser Verständnis der einzelnen Komponenten des Algorithmus zu verbessern, führen wir Ablationsstudien durch, um die Auswirkungen verschiedener Teile innerhalb unseres Systems zu analysieren. Dies umfasst den Vergleich unseres neuronalen Mutators mit einer Version ohne ihn, um seinen Beitrag zur Gesamtleistung zu bewerten.

#Anwendung auf reale Szenarien

Wir wenden unseren Ansatz auf Daten aus Laval, Kanada, an, um seine Wirksamkeit in einem realen Setting zu bewerten. Der Strassengraph stammt aus verschiedenen Quellen, darunter geografische Daten, bestehende Verkehrsnetze und Nachfragematrizen. Jeder dieser Komponenten informiert unser Design und stellt sicher, dass das neue Netzwerk alle notwendigen Passagierfahrten verbindet.

#Ergebnisse in Laval

Unsere Experimente zeigen, dass die gelernte Strategie Netzwerke in Laval entwickeln kann, die das bestehende Verkehrssystem übertreffen, indem die Betriebzeiten erheblich reduziert und die Passagiererfahrungen verbessert werden. Die Erkenntnisse deuten auf potenzielle Kosteneinsparungen für das Verkehrsunternehmen hin, während die Servicequalität verbessert wird.

#Fazit

Diese Forschung zeigt, dass die Verwendung von Deep Reinforcement Learning zum Lernen von Heuristiken die Gestaltung von Verkehrsnetzen im Vergleich zu traditionellen Methoden erheblich verbessern kann. Der Ansatz ermöglicht es Verkehrsunternehmen, besseren Service zu reduzierten Kosten zu erreichen, was sich in realen Szenarien als vorteilhaft erweist. In Zukunft könnte die Erkundung verschiedener metahurstischer Algorithmen und die Verfeinerung des Lernprozesses noch grössere Verbesserungen in der Netzwerkgestaltung und -leistung bringen.