## 4 Route Planning Algorithm
### Standalone Taxi Route Planning  
This section is concerned with describing how to determine the optimal taxi route for a single aircraft, connecting its apron exit point to its RHP (and _vice versa_), irrespective of the traffic it might encounter on the airport taxiways. Given the previous discussion, route optimality in this task is equivalent to taxi time minimization. The airport taxiway system can be modeled as a weighted and directed graph, in which the travel cost of each edge (the \"cost\" associated with traveling along a certain taxiway) is given by the time necessary for an aircraft to pass through the edge itself. Therefore, the travel cost is always non-negative for each directed edge of the airport taxiway graph. Given the previously defined optimality criterion, the taxi route-planning problem may be recast into what is commonly denoted in the combinatorial optimization framework as the shortest path problem. More precisely, the shortest path problem is concerned with finding a route from vertex A to vertex B having the minimum possible travel cost. The task we are concerned with may be stated as a particular instance of the general shortest path problem, called the single-pair shortest path problem. This classification emphasizes the fact that one has to find the shortest path from a source, vertex A, to a single destination, vertex B, as opposed to, for instance, the single-source shortest path problem, in which one has to find the shortest paths from a source, vertex A, to all other vertices in the graph. Several algorithms exist for solving this single-pair shortest path problem on a weighted and directed graph, with non-negative weights (see [11] and the references therein for an overview). The best known algorithms for finding the single pair shortest path are the ones that solve the broader single-source shortest path problem. Among these, the most popular algorithm is [PERSON]'s algorithm. Indeed, for the problem under analysis, this algorithm may be shown [12] to be:  
* _Complete_, in the sense that it guarantees finding a solution if one exists;
* _Optimal_, in the sense that is capable of identifying the best of several different solutions;
* _Polynomial in time_, in the sense that the running time is proportional to a polynomial function of the number of the graph's vertices, _i.e._, it is computationally efficient. In particular, [PERSON]'s algorithm has an O(\(n^{2}\)) time complexity, where \(n\) is the number of the graph's vertices. For a given source vertex in the graph, the algorithm finds the path with the lowest cost (_i.e._, the shortest path) between that vertex and every other vertex. This algorithm uses a greedy technique often employed in optimization problems. Greedy algorithms make locally optimal choices at each step,assuming that these choices will produce a globally optimal solution. [PERSON]'s algorithm maintains a set of vertices whose minimum costs relative to the origin vertex are already known. Initially, this set contains only the origin vertex. At each step, it adds to the set one remaining vertex whose cost relative to the origin vertex is as small as possible. Because all segments have non-negative costs, the shortest path route from the origin vertex to this remaining vertex passes only through vertices in the set. The algorithm repeats this basic step until the set includes all vertices, so this output array will hold the shortest path and relevant distance from the origin to each vertex in the graph. [PERSON]'s algorithm does actually output a wider solution than what it is strictly needed for solving our task. Nonetheless, it has numerous advantages, such as conceptual simplicity, computational efficiency and a wide availability of tested implementations. Thus, we first solve the standalone taxi route planning task using [PERSON]'s algorithm with the apron exit point (runway exit point for landings) as the source vertex.