| dc.contributor.advisor | Kappas, Martin Prof. Dr. | |
| dc.contributor.author | Hahn, Armin | |
| dc.date.accessioned | 2022-01-07T13:12:11Z | |
| dc.date.available | 2022-01-13T00:50:09Z | |
| dc.date.issued | 2022-01-07 | |
| dc.identifier.uri | http://hdl.handle.net/21.11130/00-1735-0000-0008-59E3-4 | |
| dc.identifier.uri | http://dx.doi.org/10.53846/goediss-9035 | |
| dc.identifier.uri | http://dx.doi.org/10.53846/goediss-9035 | |
| dc.language.iso | eng | de |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject.ddc | 510 | de |
| dc.title | Enhancing Geospatial Data for Passenger Transport Systems | de |
| dc.type | doctoralThesis | de |
| dc.contributor.referee | Kappas, Martin Prof. Dr. | |
| dc.date.examination | 2021-12-20 | |
| dc.description.abstractger | In dieser Dissertation werden neue Lösungen und entwickelte Software-Frameworks für Herausforderungen aus Sicht der Geoinformatik vorgestellt und bewertet, die sich aus der Teilnahme an demand responsive transport (DRT)-Projekten ergeben haben.
Dabei liegt der Fokus auf Geodaten, wie dem Straßennetz oder allgemeinen Kartendaten, die für ein Routing im Kontext von Personenbeförderungssystemen genutzt werden.
Solche DRT Systeme haben das Potenzial durch effizientere Mobilitätsangebote verschiedene Entwicklungen, wie den Verbrauch von endlichen Ressourcen (z.B. den Verbrauch von fossilen Treibstoffen für den meistens ineffizienten motorisierten Individualverkehr), Umweltverschmutzungen (z.B. Luftverschmutzung durch Feinstaub) oder Staus zu Stoßzeiten in urbanen Regionen zu reduzieren und können somit zeitgleich einen Beitrag zur Bekämpfung des anthropogenen Klimawandels leisten.
Im Rahmen dieser Arbeit werden zwei Hauptschwerpunkte untersucht.
Dabei wird insbesondere der übergeordnete Aspekt betrachtet, wie eine verbesserte Nutzung von Geodaten dazu beitragen kann, moderne Transportsysteme attraktiver zu gestalten. Die Interdisziplinarität der Geographie biete dabei den Vorteil, die Bereiche Mobilitätsforschung, Geoinformatik, Informatik und Mathematik (Graphentheorie) miteinander zu verbinden und somit disziplinübergreifende Probleme holistisch betrachten und lösen zu können.
Es wurde ein Ansatz zur performanten Bestimmung von Netzwerkdistanzen entwickelt, der die Nutzung der Euklidischen Distanz im Transportbereich und in der Mobilitätsforschung ersetzen könnte. Auch heutzutage wird noch die Euklidische Distanz zur Bestimmung der Distanz zwischen zwei Punkten im Straßennetz verwendet, um so eine rechenintensive Berechnung von exakten Netzwerkdistanzen zu vermeiden. Die Verwendung der Euklidischen Distanz kann jedoch zu sehr ungenauen Distanzen führen, wenn der tatsächliche Weg auf dem Straßennetz ein viel größerer Umweg als die Euklidische Distanz (Luftlinie) ist. Ein Beispiel für dieses Problem kann bei Flüssen auftreten, bei denen zwar eine geringe Euklidische Distanz zwischen einem Punkt auf der einen Seite des Flusses und einem Punkt auf der anderen Seite des Flusses ermittelt werden kann, aber es keine Brücke in unmittelbare Nähe gibt und somit ein größerer Umweg und eine größere Fahrzeit in Kauf genommen werden muss, als ursprünglich anhand der Euklidischen Distanz ermittelt wurde.
Ein weiteres Beispiel wo solche Probleme häufiger auftreten sind Straßennetze mit vielen Einbahnstraßen. Allgemein können diese Probleme jedoch überall auftreten. Der in dieser Dissertation neu entwickelte Ansatz liefert angenäherte Netzwerkdistanzen, ist aber weniger rechenintensiv als bisherige Algorithmen. Das kann nützlich sein, wenn keine exakten Netzwerkdistanzen benötigt werden, aber die Problematik bzw. die Ungenauigkeit der Euklidischen Distanz in einigen Fällen vermieden werden soll. Beispielsweise kann diese Ansatz für eine grobe Abschätzung oder Vorauswahl für die Berechnung von möglichen Fahrgemeinschaften Anwendung finden, wenn überprüft werden soll, ob zwei Reisewünsche für eine Fahrgemeinschaft berücksichtigt werden sollen oder nicht. Eine Berechnung der exakten Netzwerkdistanzen mit Routenplanern (basierend auf Kürzeste-Wege-Algorithmen) kann sehr rechenintensiv sein, insbesondere wenn viele Berechnungen parallel und iterativ für große Straßennetze durchgeführt werden. Eine Vorberechnung aller kürzesten Pfade ist zwar möglich und würde das Problem der benötigten Rechenleistung umgehen, jedoch ist das besonders bei großen Netzwerkgraphen nicht praktikabel. Daher wird in dem hier vorgestellten Ansatz das Straßennetz partitioniert und für jede Partition wird ein sogenannter Proxy definiert, der den Bereich seiner Partition repräsentiert.
Die Größe der Partitionen und damit auch die akzeptierte Ungenauigkeit bzw. der Grad der Generalisierung des Straßennetzes kann anhand eines Parameters bestimmt werden. Mithilfe der Proxies wird ein vollständiger Graph erstellt, dessen Daten in einer Lookup-Tabelle gespeichert werden und mit einem Suchalgorithmus können dann dort Netzwerkdistanzen aller kürzesten Wege ausgelesen werden. Die Performance dieses Ansatzes hängt dabei von dem Suchalgorithmus für die Lookup-Tabelle ab, der im schlechtesten Fall linear mit der Netzwerkgröße skaliert, während die meisten herkömmlichen Algorithmen zur Bestimmung von Netzwerkdistanzen mit großen Netzwerken schlechter skalieren. In der Auswertung zeigte dieser Ansatz Potenzial für eine zukünftige Anwendung.
Im Rahmen dieser Arbeit wurde auch das für DRT Projekte wichtige Problem des sogenannten road snappings bearbeitet. Dabei geht es um die Bestimmung von Haltepunkten am Anfang und Ende einer berechneten Route für zwei Adressen. Road snapping beschreibt also den Prozess zur Bestimmung von Referenzpunkten auf dem Straßennetz für Start- und Zielpunkte, die nicht direkt auf dem Straßennetz liegen. Herkömmliche Routenplaner nutzen für die Bestimmung die perpendikulare Distanz, wodurch es zu ungenügenden Haltepunkten kommen kann, da der tatsächliche Zugang zu den Adressen bzw. Gebäuden nicht berücksichtig wird. Im Kontext der begleiteten DRT Projekte bedeuteten ungenügende Haltepunkte zum Beispiel nicht nur gefährliche Abholorte an stark befahrenen Bundesstraßen, sondern auch Zeitverzögerungen, weil Busfahrer einen geeigneten Haltpunkt oder den Fahrgast suchen mussten, da die Fahrgäste einen anderen Haltepunkt erwarteten. Dieses Problem tritt besonders bei Mobilitätsangeboten auf, die zusätzlich auch Buchungen via Callcenter ermöglichen, sodass kein Abholort auf einer Karte angezeigt werden kann. Die dadurch entstehenden Zeitverzögerungen können dazu führen, dass darauffolgende Fahrten nicht nach Zeitplan stattfinden und sich Verzögerungen kaskadisch immer weiter vergrößern können. Es wurde eine Alternative entwickelt, die anhand von Fernerkundung und der Methode der Kostendistanz-Analyse den wahrscheinlichsten Zugang zu Gebäuden berechnet und somit sinnvolle Haltepunkte bestimmt. Dafür wurde die Annahme getroffen, dass der Zugang zu Gebäuden nur eine geringe Vegetationsbedeckung und eine minimale Steigung des Geländes aufweist sowie der ermittelte Pfad von der Straße zur berücksichtigten Adresse nicht durch andere Gebäude führt. Für die Bestimmung sogenannter günstigster Kostenpfade durch die Methode der Kostendistanz-Analyse wurden aus Open Source Daten folgende Parameter bestimmt: Die Vegetationsbedeckung (anhand eines Vegetationsindexes), die Steigungen eines hochauflösenden Geländemodells (anhand von light detection and ranging (LiDAR) Daten) sowie die Grundrisse der Gebäude (von OpenStreetMap). Die ermittelten Pfade repräsentieren den wahrscheinlichsten Weg von einem Gebäude zum Straßennetz. Durch den Schnittpunkt dieser Pfade mit dem Straßennetz sind somit optimierte Haltepunkte bestimmt worden, die den Weg zum Eingang von Gebäuden berücksichtigen. Für die Evaluation wurden die verwendeten Parameter in verschiedene Iterationen unterschiedlich gewichtet, wodurch als Resultat sinnvolle Gewichtungskombinationen der Parameter ermittelt werden konnten. Weiterhin wurden die Ergebnisse mit einem herkömmlichen Routenplaner, der die perpendikulare Distanz verwendet, verglichen und validiert. Die Haltepunkte von dem vorgestellten Ansatz erreichten je nach verwendeter Gewichtung eine Validierungs-Rate von bis zu 90.3%, wohingegen der Routenplaner nur eine Validierungs-Rate von 81.4% erreichte. Die Ergebnisse zeigen, dass der vorgestellte Ansatz zukünftig genutzt werden kann, um optimierte Haltepunkte vorzuberechnen, wodurch Missverstädnisse, Verzögerungen und gefährliche Haltepunkte im Rahmen von Personenbeförderungssystemen mit einem Tür-zu-Tür Angebot vermieden werden können. | de |
| dc.description.abstracteng | This thesis presents and evaluates new solutions and developed software frameworks to challenges from a geoinformatics perspective that have resulted from participation in demand responsive transport (DRT) projects.
Thereby, the focus is on geospatial data, such as the road network or general map data, which are used for routing in the context of passenger transportation systems.
Such DRT systems have the potential to reduce various detrimental effects, such as the consumption of finite resources (e.g. fossil fuels for the inefficient motorized private transport), environmental pollution (e.g. air pollution by particulate matter), or congestion at peak times in urban regions through more efficient mobility offers, and can thus simultaneously contribute to mitigating the anthropogenic climate change.
Within the scope of this work, the focus is set on two main points. We especially concentrate on the aspect of how an enhancement of geospatial data could contribute to improvements for passenger transport systems. The interdisciplinarity of geographers was also used in this work to combine the fields of mobility research, geoinformatics, computer science, and mathematics (graph theory), and thus to consider problems across disciplines.
First, a performant approach for determining network distances was developed that could be an alternative to the usage of Euclidean distance in transportation services and transportation research.
Even nowadays, the Euclidean distance is often used to determine the distance between two points on the road network to avoid a computationally costly calculation of exact network distances. However, the use of Euclidean distance can lead to inaccurate distances, if the actual path on the road network is a much larger detour than the beeline. A common example for this problem involves rivers, where a small Euclidean distance may be calculated between a point on one side of a river to a point on the other side of the river, but if there is no bridge in the immediate vicinity, a much larger detour, and thus a much larger travel time, must be taken than calculated by the Euclidean distance. Another example where such problems occur more frequently is road networks with many oneways. However, these problems can occur anywhere.
We present an approach, which provides approximated network distances. This can be useful if exact network distances are not required, e.g. for rough estimations or preselections in ride-pooling scenarios, to evaluate whether two requests can possibly be pooled. Calculating the exact network distances with routing engines (shortest path algorithms) can be very calculation-intensive, especially for many parallel (and iterative) calculations on large networks. Since a precalculation of all shortest path distances would be a reasonable solution but is not practical for large networks, we partition the road network and determine proxies for each partition. Proxies then represent the area for the respective partition. The size of the partition and hence the acceptable deviation (inaccuracy or the degree of generalization of the road network) can be set by a parameter. Based on the proxies, a complete graph is created, which data can be stored in a lookup table and network distances can be read easily. Thus, the performance for identifying network distances depends on the search algorithm, which scales linearly in the worst case, regardless of the network size, whereas conventional shortest path algorithms scale worse on large networks. In the evaluation, this approach showed potential use for the future.
Second, this work also deals with the problem of so-called road snapping. This is the determination of stop locations at the start and end of a calculated route between two addresses. Road snapping thus describes the process of determining reference points on the road network for given start and destination points that are not located directly on the road network.
Conventional routing engines use the perpendicular distance for the determination, which can lead to insufficient calculated snapping points, respectively stop locations, since the actual access to buildings is not taken into account. In the context of supported DRT projects, insufficient stop locations can not only be dangerous pick-up locations on highly trafficked highways but also can lead to delays in the time schedule, because bus drivers need to find a suitable spot for the boarding of passengers. Such time delays can interfere with future trips and the whole time schedule. We developed an alternative approach that uses remote sensing and the cost distance analysis method to determine the most likely access to buildings and thus more reasonable stop locations. Therefore, the assumption was made, that the access to buildings consists of few vegetation cover, minimal slope of the terrain and the calculated path should not cross building footprints. For this approach, open source data were used and the parameters for the cost distance analysis were determined by using a vegetation index, a high-resolution elevation model using light detection and ranging (LiDAR) data, and building footprints from OpenStreetMap. Thus, the so-called least cost path can be calculated, which reflects the most likely path from a building to the road network. Accordingly, optimized snapping points, respectively stop locations have been determined, that consider the actual access to the building, which conventional approaches do not consider.
For the evaluation, the used parameters were weighted differently, which allowed determining a suitable weight combination of these parameters. Furthermore, the results were compared and validated with a conventional routing engine, which uses the perpendicular distance. The presented approach achieves depending on the weight combinations a validation-rate up to 90.3%, whereas the routing engine only achieves a validation-rate of 81.4%. These results show that the presented approach could be used in the future to precompute optimized snapping points, thus avoiding misunderstandings, delays, and dangerous pick-up and drop-off locations in the context of passenger transportation systems with a to-door service. | de |
| dc.contributor.coReferee | Herminghaus, Stephan Prof. Dr. | |
| dc.subject.eng | Routing | de |
| dc.subject.eng | Road Network Generalization | de |
| dc.subject.eng | Passenger Transport | de |
| dc.identifier.urn | urn:nbn:de:gbv:7-21.11130/00-1735-0000-0008-59E3-4-6 | |
| dc.affiliation.institute | Fakultät für Mathematik und Informatik | de |
| dc.subject.gokfull | Informatik (PPN619939052) | de |
| dc.description.embargoed | 2022-01-13 | |
| dc.identifier.ppn | 1785244310 | |