# A Method to Optimize Routing Paths for City-Pair Airlines on Three-Layer Air Transport Networks
## 2 Multi-Layer Air Transport Networks  
### Construction of Air Transport Networks  
In this paper, to model the air transportation system more accurately from physical facilities to traffic applications, three-layer networks, including air route networks, city-pair airline networks, and flight operation networks, are built, which are defined as follows. Definition 1: Air Route Network Graph \(G_{ARN}\), which is a undirected graph \(G_{ARN}=(W,R)\), whereeach node \(w_{i}\in W\) represents a waypoint and each edge \(r_{i,j}=(w_{i},w_{j})\in R\) represents the existence of an air route segment between waypoint \(w_{i}\) and \(w_{j}\). An air route network \(G_{ARN}\) plays a fundamental role in the infrastructure of air traffic management systems, where each air route waypoint is a navigation marker whose longitude and latitude coordinates are determined by the ground navoids, which can help the pilots with information about the desired track and the direction that the aircraft is heading. Recently, assisted by GNSS, many waypoints have been set by air traffic managers, without any real ground navoids. In addition, the volume of flights routed on the air route segments will affect the control load of air traffic managers. Thus, it is necessary to optimize the distribution of air traffic flows on the air route segments of the air route network. Definition 2: City-Pair Airline Network Graph \(G_{AN}\), which is a directed graph \(G_{AN}=(A,L)\), where each node \(a_{i}\in A\) represents a city and each directed edge \(l_{i,j}=(a_{i},a_{j})\in L\) represents the existence of a direct airline from city \(a_{i}\) to city \(a_{j}\). In fact, flights are allowed to take off from city \(a_{i}\) to \(a_{j}\) only if there exists a corresponding city-pair airline \((a_{i},a_{j})\) in \(G_{AN}\). Thus, there must be exist one routing path (that is, a sequence of air route segments from city \(a_{i}\) to \(a_{j}\)) at least in air route network \(G_{ARN}\) for each city-pair airline \((a_{i},a_{j})\) in \(G_{AN}\). Figure 1 shows a simple example to illustrate the air route and the city-pair airline from Beijing to Nanjing. In Figure 1, the air route segments are drawn by the solid line and have a sequence of waypoints located along the segment. Furthermore, the city-pair airline between Beijing and Nanjing is shown as the dotted straight line. However, aircraft in reality will not directly fly from one airport to another along the city-pair airline but fly along the air route segments. To take the actual flight operations (flight schedule) into consideration, a flight operation network \(G_{FN}^{t}\) is defined. In this paper, a flight \(f\) is associated with a 4-tuple \((a_{i},a_{j},t_{f}^{dep},t_{f}^{arr})\), where \(a_{i}\) and \(t_{f}^{dep}\) represent the departure airport and departure time, and \(a_{j}\) and \(t_{f}^{arr}\) represent the arrival airport and arrival time. Due to the continuity of flight operation in a day, we discretise the time axis of a day into a set \(\tau=\{1T,2T,\ldots nT\}\) of consecutive time periods, and the size of time interval \(T\) can be set to any value. Therefore, the flight operation network, \(G_{FN}^{t}\), in a time interval \([t,\;\;t+T]\) can be defined as follows. **Definition 3**. : _Flight Operation Network Graph \(G_{FN}^{t}\), which is a directed graph \(G_{FN}^{t}=(A^{t},E^{t})\), where each node \(a_{i}\in A^{t}\) represents an airport and each directed edge \(e_{i,j}^{t}=(a_{i},a_{j})\in E^{t}\) represents the existence of a direct airline from airport \(a_{i}\) to airport \(a_{j}\) during the time interval \([t,\;\;t+T]\)._  
According to the definition of \(G_{FN}^{t}\), the edge \(e_{i,j}^{t}\) in time interval \([t,\;\;t+T]\) exists if and only if there is a flight \(f\) that meets one of the following four situations [2]. 1. \(t<t_{f}^{dep}\) and \(t_{f}^{arr}<t+T\)
2. \(t_{f}^{dep}<t\) and \(t_{f}^{arr}<t+T\)
3. \(t<t_{f}^{dep}\) and \(t+T<t_{f}^{arr}\)
4.