Original paper
Algorithms of Multi-Modal Route Planning Based on the Concept of Switch Point
Liu, Lu; Meng, Liqiu
Photogrammetrie - Fernerkundung - Geoinformation Jahrgang 2009 Heft 5 (2009), p. 431 - 444
published: Nov 1, 2009
DOI: 10.1127/1432-8364/2009/0031
ArtNo. ESP172200905004, Price: 29.00 €
Abstract
The paper addresses the task of generically finding the shortest path in multi modal networks with the multi-modal route planning problem in transportation field as a special case. The multi modal networks can be modelled by a data structure based on the core concept of Switch Point which abstracts the places where it is allowed for changing from one mode to another. Two routing algorithms Multi-Modal Bellman-Ford (MMBF) and Multi-Modal Dijkstra (MMD) were elicited which are respectively rooted in the classical label-correcting and label-setting methods. Both MMBF and MMD are capable of finding in multi modal networks the shortest paths in spite of different computing complexity. The feasibility of the approach was verified in our prototype system. The results of our experiments conducted on real transportation networks showed the differences between the proposed algorithms in terms of computing performance.
Kurzfassung
Der Beitrag befasst sich mit der Aufgabe zum Auffinden der kürzesten Route in einem multi mo dalen Netzwerk, wobei die multi modale Routen planung aus dem Bereich der Verkehrstechnik als eine spezielle Anwendung betrachtet wird. Die Modellierung eines multi-modalen Netzwerks basiert auf dem Kernkonzept Schaltpunkt. Bei einem Schaltpunkt handelt es sich um eine Stelle, wo eine Modalität auf eine andere umgeschaltet werden darf. Zwei Routenalgorithmen Multi Modal Bell man-Ford (MMBF) und Multi-Modal Dijkstra (MMD) wurden dargestellt. Als Grundlage dazu dienen zwei klassische Methoden - ,,Label-Korrektur und ,,Label-Einstellung. Beide MMBF und MMD sind in der Lage, die kürzeste Route in einem beliebigen multi modalen Netzwerk aufzufinden. Die Machbarkeit des Ansatzes zur multimodalen Routenplanung wurde in einem Prototypensystem bestätigt. Ergebnisse aus unseren Untersuchungen der realen Verkehrsnetzwerke zeigen jedoch, dass sich die beiden Algorithmen hinsichtlich des Rechenaufwands voneinander unterscheiden.
Keywords
multi-modal navigation • shortest path algorithm • network analysis