Bidirectional A* Search on Time-Dependent Airway Networks

  • This thesis deals with a new algorithm for finding Shortest Paths on Airway Networks. It is about a Bidirectional A* Search, a Greedy algorithm exploring a network from two sides instead of one. We will use it to solve the so-called 'Horizontal Flight Trajectory Problem', where one searches for an aircraft trajectory between two airports of minimal costs on an Airway Network. The given network will be modeled as a directed graph and in order to reflect reality we concentrate on the dynamic version. Here a timedependent cost function for all arcs is integrated, that shall represent the winds blowing. This way we model the Horizontal Flight Trajectory Problem mathematically as a Time-Dependent Shortest Path Problem. The basic algorithm idea derives from the algorithm presented in 'Bidirectional A* Search on Time-Dependent Road Networks' [1], where a similar setting is elaborated for road networks. The algorithm procedure bears on a modified generalization of Dijkstra's algorithm, made bidirectional and improved in several aspects. As for the backwards search the arrival times are not known in advance, the reversed graph it occurs on has to be weighted by a lower bound. Contrary to the static case the forwards search still has to go on, when they 'meet' in one node. In the static case, the shortest path would have been found at this point. For road networks the TDSPP is well-studied, for airway networks cannot be found as much in literature. In order to test efficiency, we implement Dijkstra's algorithm, unidirectional A* Search and Bidirectional A* Search. We draw up how potential functions for the static case could look like and that with a suitable potential A* Search with works approx. 7 times faster than Dijkstra in the dynamic case. Our computations lead also to the result, that the unidirectional A* Search works even better on the network than our new bidirectional approach does. On average it labels fewer nodes and also yields 1,7 times faster to the solutions. For assessing the efficiency of the different algorithms we compare the running times and to exclude processor characteristics we consider also the set labels relative to the labels on the resulting optimal path. In addition, we present examples of routes visually and explain shortly why there appear local differences regarding performance of A* Search and Bidirectional A* Search.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Celine Nöckel
Document Type:Bachelor's Thesis
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Granting Institution:Technische Universität Berlin
Advisor:Martin Skutella, Ralf Borndörfer
Year of first publication:2018
Pagenumber:51