Spatial topology transformation-based path search optimization for multi-level transportation networks
The rational allocation of traffic flow is essential for ensuring the efficient operation of transportation
systems. Approximately 90% of the time in the entire traffic flow allocation process is
consumed during the path search. This becomes particularly challenging when the transportation
network is large, as path searches between all origin-destination (OD) pairs must be completed
within a very short time frame. This poses a significant challenge to existing path search methods.
Enhancing the efficiency of path searches, while ensuring accuracy, will directly improve the
rational allocation of traffic flow and the overall operational efficiency of the transportation system.
Moreover, with urbanization accelerating and population density increasing, highly concentrated,
large-volume travel demands have become increasingly prominent in daily transportation. This
not only increases the load on the transportation network but also places unprecedented pressure
on operators due to the massive volume of navigation requests. In this context, quickly and
accurately processing and responding to path search requests, while avoiding delays and service
interruptions, has become a major challenge for operators.
Simplification of station-line information in transportation networks is an effective method for
improving path search efficiency. However, due to the large scale, complex hierarchy, and diverse
modes of multi-level transportation networks, numerous challenges are faced in this process. Various
network simplification techniques (also referred to as preprocessing techniques) are currently
available; however, most of them lack a robust theoretical foundation and sufficient accuracy,
which can result in significant data loss. Therefore, the further development and optimization of
transportation network simplification techniques are particularly important. A rigorous theoretical
foundation can facilitate the retention of core information while enabling the effective extraction
and simplification of the transportation network’s topology. This can significantly reduce the
impact of redundant data on algorithmic efficiency, thus enabling more efficient path searches.
Based on complex network theory and geographic information systems, this study thoroughly
explores network simplification techniques. A systematic method for simplifying the topological
structure of the transportation network is derived from a theoretical perspective based on geographic
location information, providing a scientific basis for improving path search efficiency. The
research work includes the following aspects:
(1) Simplification of urban rail network station types and construction of a hierarchical network
model with multiple layers for shortest path search: First, spatial objects were constructed based on
the geographic location information of stations and lines in the urban rail network. Displacement
rules for these objects were also formulated. Subsequently, to simplify the station types in the
urban rail network, which include transfer and non-transfer stations, a rail non-transfer station
extraction algorithm was proposed. A path recovery algorithm was then designed to ensure that
the simplified network accurately reflects the original path information. Finally, the effectiveness
and efficiency of the proposed algorithms were validated using rail network data from six cities.
By conducting an in-depth analysis and utilizing spatial topology relationships within urban
rail transit networks, the model is able to efficiently identify and extract non-transfer stations, thus
reducing the number of station and enhancing path search efficiency. Unlike existing methods, this
study proposes a station extraction strategy based on spatial topology transformation, demonstrating
its wide applicability across different urban rail networks. Additionally, this method offers a
universally applicable theoretical framework for reducing station redundancy in transportation
networks with transfer structures.
(2) Multi-path search based on a simplified urban rail station-line network model: First, the
types of rail stations are simplified using the rail non-transfer station extraction algorithm. Next,
the rail links are reduced using the link filtering algorithm. Based on the simplified station and
link sets, a multi-path search algorithm (referred to as the K-shortest Path Search Algorithm), is
designed and implemented. Finally, the K-shortest paths with lower time costs between the OD
are generated. An experimental comparison with existing reference algorithms is conducted using
Beijing’s rail network data to verify the effectiveness and computational efficiency of the proposed
algorithm.
Through two-layer simplification of the station and link sets, the method significantly reduces
the data to be processed during the path search while retaining the core functions and key information
of the urban rail transit network. This is not only a key strategy for improving the
computational efficiency of path search algorithms, but also an essential approach for optimizing
traffic network management and enhancing system efficiency.
(3) Urban rail-bus transfer structure network model is constructed: A data storage list is first
established to store the geographical information of station and line in the rail-bus network. Rectangular and irregular areas, and mode transfer station extractor, are then constructed. Movement
rules and step length for the extractor within the unit rows are defined. A mode transfer station
extraction algorithm is subsequently designed, allowing the extractor to move gradually within the
unit row and accurately extract mode transfer stations. Finally, an integrated urban rail-bus transfer
network is constructed, and experimental evaluations are conducted to validate the effectiveness
of the proposed algorithm in accurately identifying mode transfer stations.
Unlike conventional approaches in traditional multimodal transportation supernetworks,
which simulate mode transfers by introducing virtual nodes and links, the urban rail-bus transfer
network proposed in this study adopts an independent transportation topology for greater clarity
and accuracy. This design avoids the introduction of virtual nodes, offering a more intuitive
and accurate transfer network model. The proposed mode transfer station extraction algorithm
simplifies the transfer structure in rail-bus transportation networks and opens a new avenue for
designing simplified models of these networks.
(4) Multi-path search based on the urban rail-bus hierarchical simplified network model:
Initially, an urban rail-bus hierarchical network model is developed, incorporating the urban rail
station line network, the bus mode station line network, the mode transfer station line network,
and the rail-bus composite network. Subsequently, three algorithmic components are introduced:
the rail mode non-transfer station extraction algorithm, the link filtering algorithm, and the path
recovery algorithm. Furthermore, four multi-mode multi-path search systems are designed and
developed to handle path search tasks for four different modes of OD. Finally, the computational
efficiency of the multi-mode multi-path search system is verified based on rail-bus data from
Beijing, Chengdu, London, and New York, and several comparative experiments are conducted.
Unlike traditional multimodal super-network path search methods, the multi-path search
system conducts path search tasks within a network model simplified through multiple layers. Not
only is the accuracy of the search results ensured, but computational efficiency is also significantly
improved. An efficient solution to the path search problem in complex multimodal transportation
networks is provided by this method, while crucial technical support for achieving a balanced
distribution of multimodal traffic flow is also offered.
Die rationale Zuweisung von Verkehrsflüssen gilt als ein Schlüsselfaktor für den effizienten
Betrieb moderner Transportsysteme. Dabei entfällt etwa 90 % der gesamten Berechnungszeit im
Zuweisungsprozess auf die Pfadsuche. Diese Aufgabe wird besonders herausfordernd, wenn das
Verkehrssystem großräumig ist, da Pfade zwischen sämtlichen Ursprung-Ziel-Paaren innerhalb
kürzester Zeit ermittelt werden müssen. Dies stellt eine erhebliche Belastung für bestehende
Pfadsuchalgorithmen dar. Eine Verbesserung der Effizienz bei gleichzeitiger Sicherstellung der
Genauigkeit der Pfadsuche kann die rationale Verkehrsflusszuweisung erheblich unterstützen und
somit die Gesamtleistung des Transportsystems direkt steigern. Zudem führen die fortschreitende
Urbanisierung und die zunehmende Bevölkerungsdichte zu stark konzentrierten und großvolumigen
Reisebedarfen im städtischen Raum. Diese Entwicklung erhöht nicht nur die Belastung der
Verkehrsinfrastruktur, sondern stellt auch die Betreiber vor große Herausforderungen: Die schiere
Anzahl an Navigationsanfragen erzeugt einen bislang beispiellosen Druck. In diesem Kontext
ist die schnelle und präzise Bearbeitung von Pfadsuchanfragen, bei gleichzeitiger Vermeidung
von Verzögerungen und Serviceunterbrechungen, zu einer zentralen Herausforderung im modernen
Verkehrsmanagement geworden. Die Vereinfachung von Linien- und Stationsinformationen
in Verkehrsnetzen stellt eine effektive Methode zur Steigerung der Effizienz von Pfadsuchalgorithmen
dar. Aufgrund der hohen Komplexität, der hierarchischen Struktur sowie der Vielfalt
der Verkehrsmittel in dreidimensionalen Verkehrsnetzen treten dabei jedoch zahlreiche Herausforderungen
auf. Zwar existieren bereits verschiedene Ansätze zur Netzvereinfachung (sogenannte
Vorverarbeitungstechniken), doch basieren viele dieser Methoden nicht auf soliden theoretischen
Grundlagen und weisen eine unzureichende Genauigkeit auf. Dies kann zu einem potenziellen
Informationsverlust führen. Daher kommt derWeiterentwicklung und Optimierung theoretisch
fundierter Vereinfachungstechniken eine besondere Bedeutung zu. Eine robuste theoretische
Basis ermöglicht es, zentrale Informationen des Verkehrsnetzes zu bewahren und gleichzeitig eine
effektive Extraktion und Reduktion der Netzwerktopologie durchzuführen. Dadurch kann der
Einfluss redundanter Daten auf die Rechenleistung von Algorithmen signifikant verringert und
die Effizienz von Pfadsuchen deutlich verbessert werden.
Ausgehend von der Theorie komplexer Netzwerke sowie den Methoden der Geoinformationssysteme
(GIS) wird in dieser Studie die Technik der Netzwerksimplifikation eingehend
untersucht. Ziel ist es, eine systematische Methode zur Vereinfachung der topologischen Struktur
von Verkehrsnetzen aus theoretischer Perspektive unter Einbeziehung geografischer Standortinformationen
zu entwickeln. Diese bildet eine wissenschaftlich fundierte Grundlage zur Steigerung
der Effizienz von Pfadsuchalgorithmen. Die vorliegende Forschungsarbeit konzentriert sich auf
folgende Aspekte:
(1) Vereinfachung der Stationstypen im städtischen Schienennetz und Konstruktion eines
hierarchischen Netzmodells mit mehreren Ebenen für die kürzeste Pfadsuche: Ausgehend
von den geografischen Standortinformationen der Stationen und Linien im städtischen
Schienennetz wurden zunächst räumliche Objekte modelliert und entsprechende Verschiebungsregeln
formuliert. Darauf aufbauend wurde ein Algorithmus zur Extraktion von
Nicht-Umsteigestationen entwickelt, um die Stationstypen – bestehend aus Umsteige- und
Nicht-Umsteigestationen – zu vereinfachen. Zur Wahrung der Pfadinformationen im vereinfachten
Netzwerk wurde ein Pfadwiederherstellungsalgorithmus konzipiert, der eine genaue
Rekonstruktion der ursprünglichen Routen gewährleistet. Die Effektivität und Effizienz
der vorgeschlagenen Algorithmen wurden anhand realer Schienennetzdaten aus sechs
Städten umfassend evaluiert. Durch eine detaillierte Analyse der räumlich-topologischen
Beziehungen innerhalb urbaner Schienennetze konnte das Modell Nicht-Umsteigestationen
präzise identifizieren und extrahieren. Dies führt zu einer signifikanten Reduktion der
Gesamtzahl der Stationen und damit zu einer spürbaren Effizienzsteigerung der Pfadsuche.
Im Gegensatz zu konventionellen Methoden schlägt diese Studie eine neuartige Strategie
zur Stationsextraktion vor, die auf räumlicher Topologietransformation basiert und ihre
breite Anwendbarkeit auf unterschiedliche städtische Schienennetzwerke belegt. Darüber
hinaus liefert die Methode einen theoretisch fundierten Rahmen zur Reduktion redundanter
Stationen in Verkehrsnetzen mit komplexen Umstrukturierungsstrukturen.
(2) Mehrpfadsuche auf Basis eines vereinfachten Modells des städtischen Schienennetzes:
Zunächst erfolgt eine Vereinfachung der Stationstypen mithilfe des zuvor entwickelten Algorithmus
zur Extraktion von Nicht-Umsteigestationen. Daraufhin wird das Verbindungsnetz
durch Anwendung eines Link-Filter-Algorithmus reduziert. Auf Grundlage des so vereinfachten
Stationen- und Linksets wird ein Mehrpfadsuchalgorithmus – konkret ein k-kürzeste-
Wege-Algorithmus – konzipiert und implementiert. Dieser generiert k Routen mit minimaler
Reisezeit zwischen einem gegebenen Ursprungs- und Zielpunkt. DieWirksamkeit und Recheneffizienz
des vorgeschlagenen Verfahrens wird durch einen experimentellen Vergleich
mit etablierten Referenzalgorithmen anhand realer Daten des Pekinger Schienennetzes validiert.
Durch die zweistufige Vereinfachung der Stationen- und Verbindungsdaten wird
die während der Pfadsuche zu verarbeitender Datenmenge signifikant reduziert, wobei
gleichzeitig die zentralen funktionalen Eigenschaften sowie die Schlüsselinformationen des
urbanen Schienenverkehrssystems erhalten bleiben. Dies stellt nicht nur eine effektive Strategie
zur Verbesserung der rechnerischen Effizienz von Pfadsuchalgorithmen dar, sondern
liefert zugleich einen essenziellen Beitrag zur Optimierung des Verkehrsnetzmanagements
und zur Erhöhung der Gesamteffizienz des Systems.
(3) Modellierung eines städtischen Schienen-Bus-Transfernetzwerks: Zunächst wird eine
strukturierte Datenspeicherliste eingerichtet, um die geografischen Informationen verschiedener
Stationstypen und Linien des Schienen-Bus-Systems zu erfassen. Im Anschluss
werden rechteckige sowie unregelmäßige Suchbereiche definiert und ein Extraktor zur Identifikation
von Modalwechselstationen (Modetransferstationen) konstruiert. Für die Extraktion
werden Bewegungsregeln und Schrittweiten innerhalb einheitlicher Raster festgelegt. Auf
dieser Grundlage wird ein Algorithmus entwickelt, der es dem Extraktor ermöglicht, sich
systematisch innerhalb dieser Raster zu bewegen und Transferstationen präzise zu identifizieren.
Darauf aufbauend wird ein integriertes städtisches Schienen-Bus-Transfernetz
generiert. Die Wirksamkeit des vorgeschlagenen Extraktionsalgorithmus wird durch experimentelle
Analysen validiert. Im Gegensatz zu herkömmlichen Ansätzen in traditionellen
multimodalen Verkehrsnetzwerken, bei denen der Modalwechsel typischerweise durch
das Einfügen virtueller Knoten und Kanten simuliert wird, basiert das in dieser Studie
entwickelte Schienen-Bus-Transfernetz auf einer eigenständigen Verkehrstopologie. Dieses
Design verzichtet bewusst auf die Einführung virtueller Elemente und bietet ein deutlich
intuitiveres sowie präziseres Modell zur Darstellung von Transferbeziehungen. Der entwickelte
Algorithmus zur Extraktion von Transferstationen ermöglicht eine strukturierte
Vereinfachung der Transferarchitektur in urbanen Verkehrsnetzwerken und eröffnet neue
Perspektiven für die Entwicklung vereinfachter, aber realitätsnaher Netzmodelle.
(4) Mehrpfadsuche basierend auf dem hierarchisch vereinfachten Schienen-Bus-Netzwerk -
modell: Zu Beginn wird ein hierarchisches Netzwerkmodell für das Schienen-Bus-System entwickelt,
das vier Subnetzwerke integriert: das Schienen-Stationsliniennetz, das Busmodus-
Stationsliniennetz, das Umsteigestationsliniennetz sowie ein zusammengesetztes Schienen-
Bus-Gesamtnetzwerk. Aufbauend darauf werden drei algorithmische Kernkomponenten
eingeführt: ein Algorithmus zur Extraktion von Nicht-Umsteigestationen im Stadtbahnmodus,
ein Link-Filterungsalgorithmus sowie ein Pfadwiederherstellungsalgorithmus.
Darüber hinaus werden vier multimodale Mehrpfadsuchsysteme konzipiert und realisiert,
die in der Lage sind, Pfadsuchaufgaben für verschiedene Kombinationen modaler Ursprung-
Ziel-Paare abzuwickeln. Die Recheneffizienz des vorgeschlagenen Mehrpfadsuchsystems
wird anschließend auf Basis realer Daten aus den Schienen-Bus-Systemen von Peking,
Chengdu, London und New York evaluiert. Mehrere Vergleichsexperimente bestätigen die
Leistungsfähigkeit des Systems.
Im Gegensatz zu traditionellen multimodalen Supernetzwerken, die häufig auf komplexen und
schwer zu verwaltenden Netzstrukturen basieren, operiert das hier vorgestellte Mehrpfadsuchsystem
auf einem mehrschichtig vereinfachten Netzwerkmodell. Dieses Vorgehen gewährleistet nicht
nur die Genauigkeit der Pfadsuchergebnisse, sondern verbessert auch signifikant die Recheneffizienz.
Damit stellt die Methode eine leistungsfähige Lösung für Pfadsuchprobleme in komplexen,
multimodalen Verkehrsnetzen dar und liefert gleichzeitig eine essenzielle technische Grundlage
zur Realisierung einer ausgewogenen Verteilung multimodaler Verkehrsflüsse.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
